2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Code instrumentation and execution count profiling.
23 * @author Adam M. Szalkowski, Steven Schaefer
24 * @date 06.04.2006, 11.11.2010
45 #include "irprofile.h"
47 /* Instrument blocks walker. */
48 typedef struct block_id_walker_data_t {
49 unsigned int id; /**< current block id number */
50 ir_node *symconst; /**< the SymConst representing the counter array */
51 } block_id_walker_data_t;
53 /* Associate counters with blocks. */
54 typedef struct block_assoc_t {
55 unsigned int i; /**< current block id number */
56 unsigned int *counters; /**< block execution counts */
59 typedef struct intialize_execfreq_env_t {
61 ir_exec_freq *execfreqs;
63 } initialize_execfreq_env_t;
65 /* minimal execution frequency (an execfreq of 0 confuses algos) */
66 #define MIN_EXECFREQ 0.00001
68 /* keep the execcounts here because they are only read once per compiler run */
69 static set *profile = NULL;
71 /* Hook for vcg output. */
74 /* The debug module handle. */
75 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
77 /* Since the backend creates a new firm graph we cannot associate counts with
78 * blocks directly. Instead we associate them with the block ids, which are
81 typedef struct execcount_t {
82 unsigned long block; /**< block id */
83 unsigned int count; /**< execution count */
87 * Compare two execcount_t entries.
89 static int cmp_execcount(const void *a, const void *b, size_t size)
91 const execcount_t *ea = (const execcount_t*)a;
92 const execcount_t *eb = (const execcount_t*)b;
94 return ea->block != eb->block;
98 * Block walker, count number of blocks.
100 static void block_counter(ir_node *bb, void *data)
102 unsigned *count = (unsigned*) data;
108 * Returns the number of blocks the given graph.
110 static unsigned int get_irg_n_blocks(ir_graph *irg)
112 unsigned int count = 0;
113 irg_block_walk_graph(irg, block_counter, NULL, &count);
118 * Returns the number of basic blocks in the current ir program.
120 static unsigned int get_irp_n_blocks(void)
122 int i, n = get_irp_n_irgs();
123 unsigned int count = 0;
125 for (i = 0; i < n; i++) {
126 ir_graph *irg = get_irp_irg(i);
127 count += get_irg_n_blocks(irg);
134 static void dump_profile_node_info(void *ctx, FILE *f, const ir_node *irn)
138 unsigned int execcount = ir_profile_get_block_execcount(irn);
139 fprintf(f, "profiled execution count: %u\n", execcount);
144 * Add the given method entity as a constructor.
146 static void add_constructor(ir_entity *method)
148 ir_type *method_type = get_entity_type(method);
149 ir_type *ptr_type = new_type_pointer(method_type);
151 ir_type *constructors = get_segment_type(IR_SEGMENT_CONSTRUCTORS);
152 ident *ide = id_unique("constructor_ptr.%u");
153 ir_entity *ptr = new_entity(constructors, ide, ptr_type);
154 ir_graph *irg = get_const_code_irg();
155 ir_node *val = new_rd_SymConst_addr_ent(NULL, irg, mode_P_code, method);
157 set_entity_ld_ident(ptr, new_id_from_chars("", 0));
158 set_entity_compiler_generated(ptr, 1);
159 set_entity_linkage(ptr, IR_LINKAGE_CONSTANT | IR_LINKAGE_HIDDEN_USER);
160 set_entity_visibility(ptr, ir_visibility_private);
161 set_atomic_ent_value(ptr, val);
165 * Returns an entity representing the __init_firmprof function from libfirmprof
166 * This is the equivalent of:
167 * extern void __init_firmprof(char *filename, uint *counters, uint size)
169 static ir_entity *get_init_firmprof_ref(void)
171 ident *init_name = new_id_from_str("__init_firmprof");
172 ir_type *init_type = new_type_method(3, 0);
173 ir_type *uint = new_type_primitive(mode_Iu);
174 ir_type *uintptr = new_type_pointer(uint);
175 ir_type *string = new_type_pointer(new_type_primitive(mode_Bs));
178 set_method_param_type(init_type, 0, string);
179 set_method_param_type(init_type, 1, uintptr);
180 set_method_param_type(init_type, 2, uint);
182 result = new_entity(get_glob_type(), init_name, init_type);
183 set_entity_visibility(result, ir_visibility_external);
189 * Generates a new irg which calls the initializer
192 * static void __firmprof_initializer(void) __attribute__ ((constructor))
194 * __init_firmprof(ent_filename, bblock_counts, n_blocks);
197 static ir_graph *gen_initializer_irg(ir_entity *ent_filename,
198 ir_entity *bblock_counts, int n_blocks)
202 ir_node *bb, *ret, *call, *symconst;
203 ir_type *empty_frame_type;
206 ir_entity *init_ent = get_init_firmprof_ref();
208 ident *name = new_id_from_str("__firmprof_initializer");
209 ir_entity *ent = new_entity(get_glob_type(), name, new_type_method(0, 0));
210 set_entity_visibility(ent, ir_visibility_local);
211 set_entity_ld_ident(ent, name);
213 /* create the new ir_graph */
214 irg = new_ir_graph(ent, 0);
215 set_current_ir_graph(irg);
216 empty_frame_type = get_irg_frame_type(irg);
217 set_type_size_bytes(empty_frame_type, 0);
218 set_type_state(empty_frame_type, layout_fixed);
220 bb = get_r_cur_block(irg);
222 sym.entity_p = init_ent;
223 symconst = new_r_SymConst(irg, mode_P_data, sym, symconst_addr_ent);
225 sym.entity_p = ent_filename;
226 ins[0] = new_r_SymConst(irg, mode_P_data, sym, symconst_addr_ent);
227 sym.entity_p = bblock_counts;
228 ins[1] = new_r_SymConst(irg, mode_P_data, sym, symconst_addr_ent);
229 ins[2] = new_r_Const_long(irg, mode_Iu, n_blocks);
231 call = new_r_Call(bb, get_irg_initial_mem(irg), symconst, 3, ins,
232 get_entity_type(init_ent));
233 ret = new_r_Return(bb, new_r_Proj(call, mode_M, pn_Call_M), 0, NULL);
236 add_immBlock_pred(get_irg_end_block(irg), ret);
237 mature_immBlock(get_irg_end_block(irg));
239 irg_finalize_cons(irg);
241 /* add a pointer to the new function in the constructor section */
242 add_constructor(ent);
248 * Instrument a block with code needed for profiling.
249 * This just inserts the instruction nodes, it doesn't connect the memory
250 * nodes in a meaningful way.
252 static void instrument_block(ir_node *bb, ir_node *address, unsigned int id)
254 ir_graph *irg = get_irn_irg(bb);
255 ir_node *load, *store, *offset, *add, *projm, *proji, *unknown, *cnst;
257 /* We can't instrument the end block */
258 if (bb == get_irg_end_block(irg))
261 unknown = new_r_Unknown(irg, mode_M);
262 cnst = new_r_Const_long(irg, mode_Iu, get_mode_size_bytes(mode_Iu) * id);
263 offset = new_r_Add(bb, address, cnst, get_modeP_data());
264 load = new_r_Load(bb, unknown, offset, mode_Iu, cons_none);
265 projm = new_r_Proj(load, mode_M, pn_Load_M);
266 proji = new_r_Proj(load, mode_Iu, pn_Load_res);
267 cnst = new_r_Const(irg, get_mode_one(mode_Iu));
268 add = new_r_Add(bb, proji, cnst, mode_Iu);
269 store = new_r_Store(bb, projm, offset, add, cons_none);
270 projm = new_r_Proj(store, mode_M, pn_Store_M);
272 set_irn_link(bb, projm);
273 set_irn_link(projm, load);
277 * SSA Construction for instrumentation code memory.
279 * This introduces a new memory node and connects it to the instrumentation
280 * codes, inserting phiM nodes as necessary. Note that afterwards, the new
281 * memory is not connected to any return nodes and thus still dead.
283 static void fix_ssa(ir_node *bb, void *data)
285 ir_graph *irg = get_irn_irg(bb);
286 ir_node *mem, *proj, *load;
287 int n, arity = get_Block_n_cfgpreds(bb);
291 /* end blocks are not instrumented, skip! */
292 if (bb == get_irg_end_block(irg))
295 if (bb == get_irg_start_block(irg)) {
296 mem = get_irg_initial_mem(irg);
297 } else if (arity == 1) {
298 ir_node *pred = get_Block_cfgpred_block(bb, 0);
300 mem = (ir_node*) get_irn_link(pred);
302 mem = new_r_NoMem(irg);
304 ir_node **ins = ALLOCAN(ir_node*, arity);
305 for (n = arity - 1; n >= 0; --n) {
306 ir_node *pred = get_Block_cfgpred_block(bb, n);
308 ins[n] = (ir_node*) get_irn_link(pred);
310 ins[n] = new_r_NoMem(irg);
312 mem = new_r_Phi(bb, arity, ins, mode_M);
315 /* The block link fields point to the projm from the instrumentation code,
316 * the projm in turn links to the initial load which lacks a memory
317 * argument at this point. */
318 proj = (ir_node*) get_irn_link(bb);
319 load = (ir_node*) get_irn_link(proj);
320 set_Load_mem(load, mem);
324 * Instrument a single block.
326 static void block_instrument_walker(ir_node *bb, void *data)
328 block_id_walker_data_t *wd = (block_id_walker_data_t*)data;
329 instrument_block(bb, wd->symconst, wd->id);
334 * Synchronize the original memory input of node with the additional operand
335 * from the profiling code.
337 static ir_node *sync_mem(ir_node *bb, ir_node *mem)
340 ins[0] = (ir_node*) get_irn_link(bb);
342 return new_r_Sync(bb, 2, ins);
346 * Instrument a single ir_graph, counters should point to the bblock
349 static void instrument_irg(ir_graph *irg, ir_entity *counters,
350 block_id_walker_data_t *wd)
352 ir_node *end = get_irg_end(irg);
353 ir_node *endbb = get_irg_end_block(irg);
356 /* generate a symbolic constant pointing to the count array */
358 sym.entity_p = counters;
359 wd->symconst = new_r_SymConst(irg, mode_P_data, sym, symconst_addr_ent);
361 /* instrument each block in the current irg */
362 irg_block_walk_graph(irg, block_instrument_walker, NULL, wd);
363 irg_block_walk_graph(irg, fix_ssa, NULL, NULL);
365 /* connect the new memory nodes to the return nodes */
366 for (i = get_Block_n_cfgpreds(endbb) - 1; i >= 0; --i) {
367 ir_node *node = skip_Proj(get_Block_cfgpred(endbb, i));
368 ir_node *bb = get_Block_cfgpred_block(endbb, i);
371 switch (get_irn_opcode(node)) {
373 mem = get_Return_mem(node);
374 set_Return_mem(node, sync_mem(bb, mem));
377 mem = get_Raise_mem(node);
378 set_Raise_mem(node, sync_mem(bb, mem));
383 /* A fragile's op exception. There should be another path to End,
386 assert(is_fragile_op(node) && \
387 "unexpected End control flow predecessor");
391 /* as well as calls with attribute noreturn */
392 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
393 ir_node *node = get_End_keepalive(end, i);
395 ir_node *bb = get_nodes_block(node);
396 ir_node *mem = get_Call_mem(node);
397 set_Call_mem(node, sync_mem(bb, mem));
403 * Creates a new entity representing the equivalent of
404 * static unsigned int name[size]
406 static ir_entity *new_array_entity(ident *name, int size)
409 ir_type *uint_type, *array_type;
411 uint_type = new_type_primitive(mode_Iu);
412 set_type_alignment_bytes(uint_type, get_type_size_bytes(uint_type));
414 array_type = new_type_array(1, uint_type);
415 set_array_bounds_int(array_type, 0, 0, size);
416 set_type_size_bytes(array_type, size * get_mode_size_bytes(mode_Iu));
417 set_type_alignment_bytes(array_type, get_mode_size_bytes(mode_Iu));
418 set_type_state(array_type, layout_fixed);
420 result = new_entity(get_glob_type(), name, array_type);
421 set_entity_visibility(result, ir_visibility_local);
422 set_entity_compiler_generated(result, 1);
428 * Creates a new entity representing the equivalent of
429 * static const char name[strlen(string)+1] = string
431 static ir_entity *new_static_string_entity(ident *name, const char *string)
435 ir_type *char_type = new_type_primitive(mode_Bs);
436 ir_type *string_type = new_type_array(1, char_type);
438 ir_initializer_t *contents;
440 size_t i, length = strlen(string)+1;
442 /* Create the type for a fixed-length string */
443 set_array_bounds_int(string_type, 0, 0, length);
444 set_type_size_bytes(string_type, length);
445 set_type_alignment_bytes(string_type, 1);
446 set_type_state(string_type, layout_fixed);
448 result = new_entity(get_glob_type(), name, string_type);
449 set_entity_visibility(result, ir_visibility_local);
450 set_entity_linkage(result, IR_LINKAGE_CONSTANT);
451 set_entity_compiler_generated(result, 1);
453 /* There seems to be no simpler way to do this. Or at least, cparser
454 * does exactly the same thing... */
455 contents = create_initializer_compound(length);
456 for (i = 0; i < length; i++) {
457 ir_tarval *c = new_tarval_from_long(string[i], mode_Bs);
458 ir_initializer_t *init = create_initializer_tarval(c);
459 set_initializer_compound_value(contents, i, init);
461 set_entity_initializer(result, contents);
467 * Instrument all ir_graphs in the current ir_program. Currently this only
468 * works for graphs in the backend. Additionally, the resulting program
469 * has to be linked with libfirmprof.
471 * @param filename the name of the profile file (usually module_name.prof)
472 * @returns the module initializer, may be NULL
474 ir_graph *ir_profile_instrument(const char *filename)
477 ident *counter_id, *filename_id;
478 ir_entity *bblock_counts, *ent_filename;
479 block_id_walker_data_t wd;
480 FIRM_DBG_REGISTER(dbg, "firm.ir.profile");
482 /* Don't do anything for modules without code. Else the linker will
484 if (get_irp_n_irgs() == 0)
487 /* count the number of block first */
488 n_blocks = get_irp_n_blocks();
490 /* create all the necessary types and entities. Note that the
491 * types must have a fixed layout, because we are already running in the
493 counter_id = new_id_from_str("__FIRMPROF__BLOCK_COUNTS");
494 bblock_counts = new_array_entity(counter_id, n_blocks);
496 filename_id = new_id_from_str("__FIRMPROF__FILE_NAME");
497 ent_filename = new_static_string_entity(filename_id, filename);
499 /* initialize block id array and instrument blocks */
501 for (n = get_irp_n_irgs() - 1; n >= 0; --n) {
502 ir_graph *irg = get_irp_irg(n);
503 instrument_irg(irg, bblock_counts, &wd);
506 return gen_initializer_irg(ent_filename, bblock_counts, n_blocks);
509 static unsigned int *
510 parse_profile(const char *filename, unsigned int num_blocks)
512 unsigned int *result = NULL;
517 FILE *f = fopen(filename, "rb");
519 DBG((dbg, LEVEL_2, "Failed to open profile file (%s)\n", filename));
524 ret = fread(buf, 8, 1, f);
525 if (ret == 0 || strncmp(buf, "firmprof", 8) != 0) {
526 DBG((dbg, LEVEL_2, "Broken fileheader in profile\n"));
530 result = XMALLOCN(unsigned int, num_blocks);
532 /* The profiling output format is defined to be a sequence of integer
533 * values stored little endian format. */
534 for (i = 0; i < num_blocks; ++i) {
537 if ((ret = fread(bytes, 4, 1, f)) < 1)
540 result[i] = (bytes[0] << 0) | (bytes[1] << 8)
541 | (bytes[2] << 16) | (bytes[3] << 24);
545 DBG((dbg, LEVEL_4, "Failed to read counters... (size: %u)\n",
546 sizeof(unsigned int) * num_blocks));
557 * Reads the corresponding profile info file if it exists.
560 static void block_associate_walker(ir_node *bb, void *env)
562 block_assoc_t *b = (block_assoc_t*) env;
565 query.block = get_irn_node_nr(bb);
566 query.count = b->counters[(b->i)++];
567 DBG((dbg, LEVEL_4, "execcount(%+F, %u): %u\n", bb, query.block,
569 set_insert(profile, &query, sizeof(query), query.block);
572 static void irp_associate_blocks(block_assoc_t *env)
575 for (n = get_irp_n_irgs() - 1; n >= 0; --n) {
576 ir_graph *irg = get_irp_irg(n);
577 irg_block_walk_graph(irg, block_associate_walker, NULL, env);
581 bool ir_profile_read(const char *filename)
584 FIRM_DBG_REGISTER(dbg, "firm.ir.profile");
587 env.counters = parse_profile(filename, get_irp_n_blocks());
593 profile = new_set(cmp_execcount, 16);
595 irp_associate_blocks(&env);
598 /* register the vcg hook */
599 hook = dump_add_node_info_callback(dump_profile_node_info, NULL);
604 * Frees the profile info
606 void ir_profile_free(void)
614 dump_remove_node_info_callback(hook);
620 * Tells whether profile module has acquired data
622 bool ir_profile_has_data(void)
624 return profile != NULL;
628 * Get block execution count as determined by profiling
630 unsigned int ir_profile_get_block_execcount(const ir_node *block)
632 execcount_t *ec, query;
634 if (!ir_profile_has_data())
637 query.block = get_irn_node_nr(block);
638 ec = (execcount_t*)set_find(profile, &query, sizeof(query), query.block);
644 "Warning: Profile contains no data for %+F\n", block));
649 static void initialize_execfreq(ir_node *block, void *data)
651 initialize_execfreq_env_t *env = (initialize_execfreq_env_t*)data;
654 if (block == get_irg_start_block(env->irg)
655 || block == get_irg_end_block(env->irg)) {
658 freq = ir_profile_get_block_execcount(block);
659 freq *= env->freq_factor;
660 if (freq < MIN_EXECFREQ)
664 set_execfreq(env->execfreqs, block, freq);
667 ir_exec_freq *ir_create_execfreqs_from_profile(ir_graph *irg)
669 ir_node *start_block;
670 initialize_execfreq_env_t env;
674 env.execfreqs = create_execfreq(irg);
676 /* Find the first block containing instructions */
677 start_block = get_irg_start_block(irg);
678 count = ir_profile_get_block_execcount(start_block);
680 /* the function was never executed, so fallback to estimated freqs */
681 free_execfreq(env.execfreqs);
682 return compute_execfreq(irg, 10);
685 env.freq_factor = 1.0 / count;
686 irg_block_walk_graph(irg, initialize_execfreq, NULL, &env);
688 return env.execfreqs;