gcc/tree-profile.c

   1 /* Calculate branch probabilities, and basic block execution counts.
   2    Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
   3    2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4    Free Software Foundation, Inc.
   5    Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
   6    based on some ideas from Dain Samples of UC Berkeley.
   7    Further mangling by Bob Manson, Cygnus Support.
   8    Converted to use trees by Dale Johannesen, Apple Computer.
   9
  10 This file is part of GCC.
  11
  12 GCC is free software; you can redistribute it and/or modify it under
  13 the terms of the GNU General Public License as published by the Free
  14 Software Foundation; either version 3, or (at your option) any later
  15 version.
  16
  17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20 for more details.
  21
  22 You should have received a copy of the GNU General Public License
  23 along with GCC; see the file COPYING3.  If not see
  24 <http://www.gnu.org/licenses/>.  */
  25
  26 /* Generate basic block profile instrumentation and auxiliary files.
  27    Tree-based version.  See profile.c for overview.  */
  28
  29 #include "config.h"
  30 #include "system.h"
  31 #include "coretypes.h"
  32 #include "tm.h"
  33 #include "rtl.h"
  34 #include "flags.h"
  35 #include "output.h"
  36 #include "regs.h"
  37 #include "expr.h"
  38 #include "function.h"
  39 #include "toplev.h"
  40 #include "coverage.h"
  41 #include "tree.h"
  42 #include "tree-flow.h"
  43 #include "tree-dump.h"
  44 #include "tree-pass.h"
  45 #include "timevar.h"
  46 #include "value-prof.h"
  47 #include "ggc.h"
  48 #include "cgraph.h"
  49
  50 static GTY(()) tree gcov_type_node;
  51 static GTY(()) tree tree_interval_profiler_fn;
  52 static GTY(()) tree tree_pow2_profiler_fn;
  53 static GTY(()) tree tree_one_value_profiler_fn;
  54 static GTY(()) tree tree_indirect_call_profiler_fn;
  55 static GTY(()) tree tree_average_profiler_fn;
  56 static GTY(()) tree tree_ior_profiler_fn;
  57 \f
  58
  59 static GTY(()) tree ic_void_ptr_var;
  60 static GTY(()) tree ic_gcov_type_ptr_var;
  61 static GTY(()) tree ptr_void;
  62
  63 /* Do initialization work for the edge profiler.  */
  64
  65 /* Add code:
  66    static gcov* __gcov_indirect_call_counters; // pointer to actual counter
  67    static void* __gcov_indirect_call_callee; // actual callee addres
  68 */
  69 static void
  70 tree_init_ic_make_global_vars (void)
  71 {
  72   tree  gcov_type_ptr;
  73
  74   ptr_void = build_pointer_type (void_type_node);
  75
  76   ic_void_ptr_var
  77     = build_decl (VAR_DECL,
  78                   get_identifier ("__gcov_indirect_call_callee"),
  79                   ptr_void);
  80   TREE_STATIC (ic_void_ptr_var) = 1;
  81   TREE_PUBLIC (ic_void_ptr_var) = 0;
  82   DECL_ARTIFICIAL (ic_void_ptr_var) = 1;
  83   DECL_INITIAL (ic_void_ptr_var) = NULL;
  84   assemble_variable (ic_void_ptr_var, 0, 0, 0);
  85
  86   gcov_type_ptr = build_pointer_type (get_gcov_type ());
  87   ic_gcov_type_ptr_var
  88     = build_decl (VAR_DECL,
  89                   get_identifier ("__gcov_indirect_call_counters"),
  90                   gcov_type_ptr);
  91   TREE_STATIC (ic_gcov_type_ptr_var) = 1;
  92   TREE_PUBLIC (ic_gcov_type_ptr_var) = 0;
  93   DECL_ARTIFICIAL (ic_gcov_type_ptr_var) = 1;
  94   DECL_INITIAL (ic_gcov_type_ptr_var) = NULL;
  95   assemble_variable (ic_gcov_type_ptr_var, 0, 0, 0);
  96 }
  97
  98 static void
  99 tree_init_edge_profiler (void)
 100 {
 101   tree interval_profiler_fn_type;
 102   tree pow2_profiler_fn_type;
 103   tree one_value_profiler_fn_type;
 104   tree gcov_type_ptr;
 105   tree ic_profiler_fn_type;
 106   tree average_profiler_fn_type;
 107
 108   if (!gcov_type_node)
 109     {
 110       gcov_type_node = get_gcov_type ();
 111       gcov_type_ptr = build_pointer_type (gcov_type_node);
 112
 113       /* void (*) (gcov_type *, gcov_type, int, unsigned)  */
 114       interval_profiler_fn_type
 115               = build_function_type_list (void_type_node,
 116                                           gcov_type_ptr, gcov_type_node,
 117                                           integer_type_node,
 118                                           unsigned_type_node, NULL_TREE);
 119       tree_interval_profiler_fn
 120               = build_fn_decl ("__gcov_interval_profiler",
 121                                      interval_profiler_fn_type);
 122
 123       /* void (*) (gcov_type *, gcov_type)  */
 124       pow2_profiler_fn_type
 125               = build_function_type_list (void_type_node,
 126                                           gcov_type_ptr, gcov_type_node,
 127                                           NULL_TREE);
 128       tree_pow2_profiler_fn = build_fn_decl ("__gcov_pow2_profiler",
 129                                                    pow2_profiler_fn_type);
 130
 131       /* void (*) (gcov_type *, gcov_type)  */
 132       one_value_profiler_fn_type
 133               = build_function_type_list (void_type_node,
 134                                           gcov_type_ptr, gcov_type_node,
 135                                           NULL_TREE);
 136       tree_one_value_profiler_fn
 137               = build_fn_decl ("__gcov_one_value_profiler",
 138                                      one_value_profiler_fn_type);
 139
 140       tree_init_ic_make_global_vars ();
 141
 142       /* void (*) (gcov_type *, gcov_type, void *, void *)  */
 143       ic_profiler_fn_type
 144                = build_function_type_list (void_type_node,
 145                                           gcov_type_ptr, gcov_type_node,
 146                                           ptr_void,
 147                                           ptr_void, NULL_TREE);
 148       tree_indirect_call_profiler_fn
 149               = build_fn_decl ("__gcov_indirect_call_profiler",
 150                                      ic_profiler_fn_type);
 151       /* void (*) (gcov_type *, gcov_type)  */
 152       average_profiler_fn_type
 153               = build_function_type_list (void_type_node,
 154                                           gcov_type_ptr, gcov_type_node, NULL_TREE);
 155       tree_average_profiler_fn
 156               = build_fn_decl ("__gcov_average_profiler",
 157                                      average_profiler_fn_type);
 158       tree_ior_profiler_fn
 159               = build_fn_decl ("__gcov_ior_profiler",
 160                                      average_profiler_fn_type);
 161     }
 162 }
 163
 164 /* Output instructions as GIMPLE trees to increment the edge
 165    execution count, and insert them on E.  We rely on
 166    bsi_insert_on_edge to preserve the order.  */
 167
 168 static void
 169 tree_gen_edge_profiler (int edgeno, edge e)
 170 {
 171   tree tmp1 = create_tmp_var (gcov_type_node, "PROF");
 172   tree tmp2 = create_tmp_var (gcov_type_node, "PROF");
 173   tree ref = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
 174   tree one = build_int_cst (gcov_type_node, 1);
 175   tree stmt1 = build_gimple_modify_stmt (tmp1, ref);
 176   tree stmt2 = build_gimple_modify_stmt (tmp2,
 177                                          build2 (PLUS_EXPR, gcov_type_node,
 178                                                  tmp1, one));
 179   tree stmt3 = build_gimple_modify_stmt (ref, tmp2);
 180   bsi_insert_on_edge (e, stmt1);
 181   bsi_insert_on_edge (e, stmt2);
 182   bsi_insert_on_edge (e, stmt3);
 183 }
 184
 185 /* Emits code to get VALUE to instrument at BSI, and returns the
 186    variable containing the value.  */
 187
 188 static tree
 189 prepare_instrumented_value (block_stmt_iterator *bsi,
 190                             histogram_value value)
 191 {
 192   tree val = value->hvalue.value;
 193   return force_gimple_operand_bsi (bsi, fold_convert (gcov_type_node, val),
 194                                    true, NULL_TREE, true, BSI_SAME_STMT);
 195 }
 196
 197 /* Output instructions as GIMPLE trees to increment the interval histogram
 198    counter.  VALUE is the expression whose value is profiled.  TAG is the
 199    tag of the section for counters, BASE is offset of the counter position.  */
 200
 201 static void
 202 tree_gen_interval_profiler (histogram_value value, unsigned tag, unsigned base)
 203 {
 204   tree stmt = value->hvalue.stmt;
 205   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 206   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 207   tree call, val;
 208   tree start = build_int_cst_type (integer_type_node, value->hdata.intvl.int_start);
 209   tree steps = build_int_cst_type (unsigned_type_node, value->hdata.intvl.steps);
 210
 211   ref_ptr = force_gimple_operand_bsi (&bsi,
 212                                       build_addr (ref, current_function_decl),
 213                                       true, NULL_TREE, true, BSI_SAME_STMT);
 214   val = prepare_instrumented_value (&bsi, value);
 215   call = build_call_expr (tree_interval_profiler_fn, 4,
 216                           ref_ptr, val, start, steps);
 217   bsi_insert_before (&bsi, call, BSI_SAME_STMT);
 218 }
 219
 220 /* Output instructions as GIMPLE trees to increment the power of two histogram
 221    counter.  VALUE is the expression whose value is profiled.  TAG is the tag
 222    of the section for counters, BASE is offset of the counter position.  */
 223
 224 static void
 225 tree_gen_pow2_profiler (histogram_value value, unsigned tag, unsigned base)
 226 {
 227   tree stmt = value->hvalue.stmt;
 228   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 229   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 230   tree call, val;
 231
 232   ref_ptr = force_gimple_operand_bsi (&bsi,
 233                                       build_addr (ref, current_function_decl),
 234                                       true, NULL_TREE, true, BSI_SAME_STMT);
 235   val = prepare_instrumented_value (&bsi, value);
 236   call = build_call_expr (tree_pow2_profiler_fn, 2, ref_ptr, val);
 237   bsi_insert_before (&bsi, call, BSI_SAME_STMT);
 238 }
 239
 240 /* Output instructions as GIMPLE trees for code to find the most common value.
 241    VALUE is the expression whose value is profiled.  TAG is the tag of the
 242    section for counters, BASE is offset of the counter position.  */
 243
 244 static void
 245 tree_gen_one_value_profiler (histogram_value value, unsigned tag, unsigned base)
 246 {
 247   tree stmt = value->hvalue.stmt;
 248   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 249   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 250   tree call, val;
 251
 252   ref_ptr = force_gimple_operand_bsi (&bsi,
 253                                       build_addr (ref, current_function_decl),
 254                                       true, NULL_TREE, true, BSI_SAME_STMT);
 255   val = prepare_instrumented_value (&bsi, value);
 256   call = build_call_expr (tree_one_value_profiler_fn, 2, ref_ptr, val);
 257   bsi_insert_before (&bsi, call, BSI_SAME_STMT);
 258 }
 259
 260
 261 /* Output instructions as GIMPLE trees for code to find the most
 262    common called function in indirect call.
 263    VALUE is the call expression whose indirect callee is profiled.
 264    TAG is the tag of the section for counters, BASE is offset of the
 265    counter position.  */
 266
 267 static void
 268 tree_gen_ic_profiler (histogram_value value, unsigned tag, unsigned base)
 269 {
 270   tree tmp1, stmt1, stmt2, stmt3;
 271   tree stmt = value->hvalue.stmt;
 272   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 273   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 274
 275   ref_ptr = force_gimple_operand_bsi (&bsi,
 276                                       build_addr (ref, current_function_decl),
 277                                       true, NULL_TREE, true, BSI_SAME_STMT);
 278
 279   /* Insert code:
 280
 281     __gcov_indirect_call_counters = get_relevant_counter_ptr ();
 282     __gcov_indirect_call_callee = (void *) indirect call argument;
 283    */
 284
 285   tmp1 = create_tmp_var (ptr_void, "PROF");
 286   stmt1 = build_gimple_modify_stmt (ic_gcov_type_ptr_var, ref_ptr);
 287   stmt2 = build_gimple_modify_stmt (tmp1, unshare_expr (value->hvalue.value));
 288   stmt3 = build_gimple_modify_stmt (ic_void_ptr_var, tmp1);
 289
 290   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 291   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 292   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 293 }
 294
 295
 296 /* Output instructions as GIMPLE trees for code to find the most
 297    common called function in indirect call. Insert instructions at the
 298    beginning of every possible called function.
 299   */
 300
 301 static void
 302 tree_gen_ic_func_profiler (void)
 303 {
 304   struct cgraph_node * c_node = cgraph_node (current_function_decl);
 305   block_stmt_iterator bsi;
 306   edge e;
 307   basic_block bb;
 308   edge_iterator ei;
 309   tree stmt1;
 310   tree tree_uid, cur_func;
 311
 312   if (flag_unit_at_a_time)
 313     {
 314       if (!c_node->needed)
 315         return;
 316     }
 317
 318   tree_init_edge_profiler ();
 319
 320   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 321     {
 322       bb = split_edge (e);
 323       bsi = bsi_start (bb);
 324       cur_func = force_gimple_operand_bsi (&bsi,
 325                                            build_addr (current_function_decl,
 326                                                        current_function_decl),
 327                                            true, NULL_TREE,
 328                                            true, BSI_SAME_STMT);
 329       tree_uid = build_int_cst (gcov_type_node, c_node->pid);
 330       stmt1 = build_call_expr (tree_indirect_call_profiler_fn, 4,
 331                                ic_gcov_type_ptr_var,
 332                                tree_uid,
 333                                cur_func,
 334                                ic_void_ptr_var);
 335       bsi_insert_after (&bsi, stmt1, BSI_NEW_STMT);
 336     }
 337 }
 338
 339 /* Output instructions as GIMPLE trees for code to find the most common value
 340    of a difference between two evaluations of an expression.
 341    VALUE is the expression whose value is profiled.  TAG is the tag of the
 342    section for counters, BASE is offset of the counter position.  */
 343
 344 static void
 345 tree_gen_const_delta_profiler (histogram_value value ATTRIBUTE_UNUSED,
 346                                 unsigned tag ATTRIBUTE_UNUSED,
 347                                 unsigned base ATTRIBUTE_UNUSED)
 348 {
 349   /* FIXME implement this.  */
 350 #ifdef ENABLE_CHECKING
 351   internal_error ("unimplemented functionality");
 352 #endif
 353   gcc_unreachable ();
 354 }
 355
 356 /* Output instructions as GIMPLE trees to increment the average histogram
 357    counter.  VALUE is the expression whose value is profiled.  TAG is the
 358    tag of the section for counters, BASE is offset of the counter position.  */
 359
 360 static void
 361 tree_gen_average_profiler (histogram_value value, unsigned tag, unsigned base)
 362 {
 363   tree stmt = value->hvalue.stmt;
 364   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 365   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 366   tree call, val;
 367
 368   ref_ptr = force_gimple_operand_bsi (&bsi,
 369                                       build_addr (ref, current_function_decl),
 370                                       true, NULL_TREE,
 371                                       true, BSI_SAME_STMT);
 372   val = prepare_instrumented_value (&bsi, value);
 373   call = build_call_expr (tree_average_profiler_fn, 2, ref_ptr, val);
 374   bsi_insert_before (&bsi, call, BSI_SAME_STMT);
 375 }
 376
 377 /* Output instructions as GIMPLE trees to increment the ior histogram
 378    counter.  VALUE is the expression whose value is profiled.  TAG is the
 379    tag of the section for counters, BASE is offset of the counter position.  */
 380
 381 static void
 382 tree_gen_ior_profiler (histogram_value value, unsigned tag, unsigned base)
 383 {
 384   tree stmt = value->hvalue.stmt;
 385   block_stmt_iterator bsi = bsi_for_stmt (stmt);
 386   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 387   tree call, val;
 388
 389   ref_ptr = force_gimple_operand_bsi (&bsi,
 390                                       build_addr (ref, current_function_decl),
 391                                       true, NULL_TREE, true, BSI_SAME_STMT);
 392   val = prepare_instrumented_value (&bsi, value);
 393   call = build_call_expr (tree_ior_profiler_fn, 2, ref_ptr, val);
 394   bsi_insert_before (&bsi, call, BSI_SAME_STMT);
 395 }
 396
 397 /* Return 1 if tree-based profiling is in effect, else 0.
 398    If it is, set up hooks for tree-based profiling.
 399    Gate for pass_tree_profile.  */
 400
 401 static bool
 402 do_tree_profiling (void)
 403 {
 404   if (profile_arc_flag || flag_test_coverage || flag_branch_probabilities)
 405     {
 406       tree_register_profile_hooks ();
 407       tree_register_value_prof_hooks ();
 408       return true;
 409     }
 410   return false;
 411 }
 412
 413 static unsigned int
 414 tree_profiling (void)
 415 {
 416   /* Don't profile functions produced at destruction time, particularly
 417      the gcov datastructure initializer.  */
 418   if (cgraph_state == CGRAPH_STATE_FINISHED)
 419     return 0;
 420   branch_prob ();
 421
 422   if (! flag_branch_probabilities
 423       && flag_profile_values)
 424     tree_gen_ic_func_profiler ();
 425
 426   if (flag_branch_probabilities
 427       && flag_profile_values
 428       && flag_value_profile_transformations)
 429     value_profile_transformations ();
 430   /* The above could hose dominator info.  Currently there is
 431      none coming in, this is a safety valve.  It should be
 432      easy to adjust it, if and when there is some.  */
 433   free_dominance_info (CDI_DOMINATORS);
 434   free_dominance_info (CDI_POST_DOMINATORS);
 435   return 0;
 436 }
 437
 438 struct tree_opt_pass pass_tree_profile =
 439 {
 440   "tree_profile",                       /* name */
 441   do_tree_profiling,                    /* gate */
 442   tree_profiling,                       /* execute */
 443   NULL,                                 /* sub */
 444   NULL,                                 /* next */
 445   0,                                    /* static_pass_number */
 446   TV_BRANCH_PROB,                       /* tv_id */
 447   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 448   PROP_gimple_leh | PROP_cfg,           /* properties_provided */
 449   0,                                    /* properties_destroyed */
 450   0,                                    /* todo_flags_start */
 451   TODO_verify_stmts | TODO_dump_func,   /* todo_flags_finish */
 452   0                                     /* letter */
 453 };
 454
 455 struct profile_hooks tree_profile_hooks =
 456 {
 457   tree_init_edge_profiler,       /* init_edge_profiler */
 458   tree_gen_edge_profiler,        /* gen_edge_profiler */
 459   tree_gen_interval_profiler,    /* gen_interval_profiler */
 460   tree_gen_pow2_profiler,        /* gen_pow2_profiler */
 461   tree_gen_one_value_profiler,   /* gen_one_value_profiler */
 462   tree_gen_const_delta_profiler, /* gen_const_delta_profiler */
 463   tree_gen_ic_profiler,          /* gen_ic_profiler */
 464   tree_gen_average_profiler,     /* gen_average_profiler */
 465   tree_gen_ior_profiler          /* gen_ior_profiler */
 466 };
 467
 468 #include "gt-tree-profile.h"