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, 2008
   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 gcov_type_tmp_var;
  52 static GTY(()) tree tree_interval_profiler_fn;
  53 static GTY(()) tree tree_pow2_profiler_fn;
  54 static GTY(()) tree tree_one_value_profiler_fn;
  55 static GTY(()) tree tree_indirect_call_profiler_fn;
  56 static GTY(()) tree tree_average_profiler_fn;
  57 static GTY(()) tree tree_ior_profiler_fn;
  58 \f
  59
  60 static GTY(()) tree ic_void_ptr_var;
  61 static GTY(()) tree ic_gcov_type_ptr_var;
  62 static GTY(()) tree ptr_void;
  63
  64 /* Do initialization work for the edge profiler.  */
  65
  66 /* Add code:
  67    static gcov* __gcov_indirect_call_counters; // pointer to actual counter
  68    static void* __gcov_indirect_call_callee; // actual callee address
  69 */
  70 static void
  71 tree_init_ic_make_global_vars (void)
  72 {
  73   tree  gcov_type_ptr;
  74
  75   ptr_void = build_pointer_type (void_type_node);
  76
  77   ic_void_ptr_var
  78     = build_decl (UNKNOWN_LOCATION, VAR_DECL,
  79                   get_identifier ("__gcov_indirect_call_callee"),
  80                   ptr_void);
  81   TREE_STATIC (ic_void_ptr_var) = 1;
  82   TREE_PUBLIC (ic_void_ptr_var) = 0;
  83   DECL_ARTIFICIAL (ic_void_ptr_var) = 1;
  84   DECL_INITIAL (ic_void_ptr_var) = NULL;
  85   varpool_finalize_decl (ic_void_ptr_var);
  86
  87   gcov_type_ptr = build_pointer_type (get_gcov_type ());
  88   ic_gcov_type_ptr_var
  89     = build_decl (UNKNOWN_LOCATION, VAR_DECL,
  90                   get_identifier ("__gcov_indirect_call_counters"),
  91                   gcov_type_ptr);
  92   TREE_STATIC (ic_gcov_type_ptr_var) = 1;
  93   TREE_PUBLIC (ic_gcov_type_ptr_var) = 0;
  94   DECL_ARTIFICIAL (ic_gcov_type_ptr_var) = 1;
  95   DECL_INITIAL (ic_gcov_type_ptr_var) = NULL;
  96   varpool_finalize_decl (ic_gcov_type_ptr_var);
  97 }
  98
  99 static void
 100 tree_init_edge_profiler (void)
 101 {
 102   tree interval_profiler_fn_type;
 103   tree pow2_profiler_fn_type;
 104   tree one_value_profiler_fn_type;
 105   tree gcov_type_ptr;
 106   tree ic_profiler_fn_type;
 107   tree average_profiler_fn_type;
 108
 109   if (!gcov_type_node)
 110     {
 111       gcov_type_node = get_gcov_type ();
 112       gcov_type_ptr = build_pointer_type (gcov_type_node);
 113
 114       /* void (*) (gcov_type *, gcov_type, int, unsigned)  */
 115       interval_profiler_fn_type
 116               = build_function_type_list (void_type_node,
 117                                           gcov_type_ptr, gcov_type_node,
 118                                           integer_type_node,
 119                                           unsigned_type_node, NULL_TREE);
 120       tree_interval_profiler_fn
 121               = build_fn_decl ("__gcov_interval_profiler",
 122                                      interval_profiler_fn_type);
 123
 124       /* void (*) (gcov_type *, gcov_type)  */
 125       pow2_profiler_fn_type
 126               = build_function_type_list (void_type_node,
 127                                           gcov_type_ptr, gcov_type_node,
 128                                           NULL_TREE);
 129       tree_pow2_profiler_fn = build_fn_decl ("__gcov_pow2_profiler",
 130                                                    pow2_profiler_fn_type);
 131
 132       /* void (*) (gcov_type *, gcov_type)  */
 133       one_value_profiler_fn_type
 134               = build_function_type_list (void_type_node,
 135                                           gcov_type_ptr, gcov_type_node,
 136                                           NULL_TREE);
 137       tree_one_value_profiler_fn
 138               = build_fn_decl ("__gcov_one_value_profiler",
 139                                      one_value_profiler_fn_type);
 140
 141       tree_init_ic_make_global_vars ();
 142
 143       /* void (*) (gcov_type *, gcov_type, void *, void *)  */
 144       ic_profiler_fn_type
 145                = build_function_type_list (void_type_node,
 146                                           gcov_type_ptr, gcov_type_node,
 147                                           ptr_void,
 148                                           ptr_void, NULL_TREE);
 149       tree_indirect_call_profiler_fn
 150               = build_fn_decl ("__gcov_indirect_call_profiler",
 151                                      ic_profiler_fn_type);
 152       /* void (*) (gcov_type *, gcov_type)  */
 153       average_profiler_fn_type
 154               = build_function_type_list (void_type_node,
 155                                           gcov_type_ptr, gcov_type_node, NULL_TREE);
 156       tree_average_profiler_fn
 157               = build_fn_decl ("__gcov_average_profiler",
 158                                      average_profiler_fn_type);
 159       tree_ior_profiler_fn
 160               = build_fn_decl ("__gcov_ior_profiler",
 161                                      average_profiler_fn_type);
 162       /* LTO streamer needs assembler names.  Because we create these decls
 163          late, we need to initialize them by hand.  */
 164       DECL_ASSEMBLER_NAME (tree_interval_profiler_fn);
 165       DECL_ASSEMBLER_NAME (tree_pow2_profiler_fn);
 166       DECL_ASSEMBLER_NAME (tree_one_value_profiler_fn);
 167       DECL_ASSEMBLER_NAME (tree_indirect_call_profiler_fn);
 168       DECL_ASSEMBLER_NAME (tree_average_profiler_fn);
 169       DECL_ASSEMBLER_NAME (tree_ior_profiler_fn);
 170     }
 171 }
 172
 173 /* New call was added, make goto call edges if neccesary.  */
 174
 175 static void
 176 add_abnormal_goto_call_edges (gimple_stmt_iterator gsi)
 177 {
 178   gimple stmt = gsi_stmt (gsi);
 179
 180   if (!stmt_can_make_abnormal_goto (stmt))
 181     return;
 182   if (!gsi_end_p (gsi))
 183     split_block (gimple_bb (stmt), stmt);
 184   make_abnormal_goto_edges (gimple_bb (stmt), true);
 185 }
 186
 187 /* Output instructions as GIMPLE trees to increment the edge
 188    execution count, and insert them on E.  We rely on
 189    gsi_insert_on_edge to preserve the order.  */
 190
 191 static void
 192 tree_gen_edge_profiler (int edgeno, edge e)
 193 {
 194   tree ref, one;
 195   gimple stmt1, stmt2, stmt3;
 196
 197   /* We share one temporary variable declaration per function.  This
 198      gets re-set in tree_profiling.  */
 199   if (gcov_type_tmp_var == NULL_TREE)
 200     gcov_type_tmp_var = create_tmp_var (gcov_type_node, "PROF_edge_counter");
 201   ref = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
 202   one = build_int_cst (gcov_type_node, 1);
 203   stmt1 = gimple_build_assign (gcov_type_tmp_var, ref);
 204   stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, gcov_type_tmp_var,
 205                                         gcov_type_tmp_var, one);
 206   stmt3 = gimple_build_assign (unshare_expr (ref), gcov_type_tmp_var);
 207   gsi_insert_on_edge (e, stmt1);
 208   gsi_insert_on_edge (e, stmt2);
 209   gsi_insert_on_edge (e, stmt3);
 210 }
 211
 212 /* Emits code to get VALUE to instrument at GSI, and returns the
 213    variable containing the value.  */
 214
 215 static tree
 216 prepare_instrumented_value (gimple_stmt_iterator *gsi, histogram_value value)
 217 {
 218   tree val = value->hvalue.value;
 219   if (POINTER_TYPE_P (TREE_TYPE (val)))
 220     val = fold_convert (sizetype, val);
 221   return force_gimple_operand_gsi (gsi, fold_convert (gcov_type_node, val),
 222                                    true, NULL_TREE, true, GSI_SAME_STMT);
 223 }
 224
 225 /* Output instructions as GIMPLE trees to increment the interval histogram
 226    counter.  VALUE is the expression whose value is profiled.  TAG is the
 227    tag of the section for counters, BASE is offset of the counter position.  */
 228
 229 static void
 230 tree_gen_interval_profiler (histogram_value value, unsigned tag, unsigned base)
 231 {
 232   gimple stmt = value->hvalue.stmt;
 233   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 234   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 235   gimple call;
 236   tree val;
 237   tree start = build_int_cst_type (integer_type_node,
 238                                    value->hdata.intvl.int_start);
 239   tree steps = build_int_cst_type (unsigned_type_node,
 240                                    value->hdata.intvl.steps);
 241
 242   ref_ptr = force_gimple_operand_gsi (&gsi,
 243                                       build_addr (ref, current_function_decl),
 244                                       true, NULL_TREE, true, GSI_SAME_STMT);
 245   val = prepare_instrumented_value (&gsi, value);
 246   call = gimple_build_call (tree_interval_profiler_fn, 4,
 247                             ref_ptr, val, start, steps);
 248   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 249   add_abnormal_goto_call_edges (gsi);
 250 }
 251
 252 /* Output instructions as GIMPLE trees to increment the power of two histogram
 253    counter.  VALUE is the expression whose value is profiled.  TAG is the tag
 254    of the section for counters, BASE is offset of the counter position.  */
 255
 256 static void
 257 tree_gen_pow2_profiler (histogram_value value, unsigned tag, unsigned base)
 258 {
 259   gimple stmt = value->hvalue.stmt;
 260   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 261   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 262   gimple call;
 263   tree val;
 264
 265   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 266                                       true, NULL_TREE, true, GSI_SAME_STMT);
 267   val = prepare_instrumented_value (&gsi, value);
 268   call = gimple_build_call (tree_pow2_profiler_fn, 2, ref_ptr, val);
 269   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 270   add_abnormal_goto_call_edges (gsi);
 271 }
 272
 273 /* Output instructions as GIMPLE trees for code to find the most common value.
 274    VALUE is the expression whose value is profiled.  TAG is the tag of the
 275    section for counters, BASE is offset of the counter position.  */
 276
 277 static void
 278 tree_gen_one_value_profiler (histogram_value value, unsigned tag, unsigned base)
 279 {
 280   gimple stmt = value->hvalue.stmt;
 281   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 282   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 283   gimple call;
 284   tree val;
 285
 286   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 287                                       true, NULL_TREE, true, GSI_SAME_STMT);
 288   val = prepare_instrumented_value (&gsi, value);
 289   call = gimple_build_call (tree_one_value_profiler_fn, 2, ref_ptr, val);
 290   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 291   add_abnormal_goto_call_edges (gsi);
 292 }
 293
 294
 295 /* Output instructions as GIMPLE trees for code to find the most
 296    common called function in indirect call.
 297    VALUE is the call expression whose indirect callee is profiled.
 298    TAG is the tag of the section for counters, BASE is offset of the
 299    counter position.  */
 300
 301 static void
 302 tree_gen_ic_profiler (histogram_value value, unsigned tag, unsigned base)
 303 {
 304   tree tmp1;
 305   gimple stmt1, stmt2, stmt3;
 306   gimple stmt = value->hvalue.stmt;
 307   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 308   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 309
 310   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 311                                       true, NULL_TREE, true, GSI_SAME_STMT);
 312
 313   /* Insert code:
 314
 315     __gcov_indirect_call_counters = get_relevant_counter_ptr ();
 316     __gcov_indirect_call_callee = (void *) indirect call argument;
 317    */
 318
 319   tmp1 = create_tmp_var (ptr_void, "PROF");
 320   stmt1 = gimple_build_assign (ic_gcov_type_ptr_var, ref_ptr);
 321   stmt2 = gimple_build_assign (tmp1, unshare_expr (value->hvalue.value));
 322   stmt3 = gimple_build_assign (ic_void_ptr_var, tmp1);
 323
 324   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 325   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 326   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
 327 }
 328
 329
 330 /* Output instructions as GIMPLE trees for code to find the most
 331    common called function in indirect call. Insert instructions at the
 332    beginning of every possible called function.
 333   */
 334
 335 static void
 336 tree_gen_ic_func_profiler (void)
 337 {
 338   struct cgraph_node * c_node = cgraph_node (current_function_decl);
 339   gimple_stmt_iterator gsi;
 340   edge e;
 341   basic_block bb;
 342   edge_iterator ei;
 343   gimple stmt1, stmt2;
 344   tree tree_uid, cur_func;
 345
 346   if (!c_node->needed)
 347     return;
 348
 349   tree_init_edge_profiler ();
 350
 351   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 352     {
 353       tree void0;
 354
 355       bb = split_edge (e);
 356       gsi = gsi_start_bb (bb);
 357
 358       cur_func = force_gimple_operand_gsi (&gsi,
 359                                            build_addr (current_function_decl,
 360                                                        current_function_decl),
 361                                            true, NULL_TREE,
 362                                            true, GSI_SAME_STMT);
 363       tree_uid = build_int_cst (gcov_type_node, c_node->pid);
 364       stmt1 = gimple_build_call (tree_indirect_call_profiler_fn, 4,
 365                                  ic_gcov_type_ptr_var,
 366                                  tree_uid,
 367                                  cur_func,
 368                                  ic_void_ptr_var);
 369       gsi_insert_after (&gsi, stmt1, GSI_NEW_STMT);
 370       gcc_assert (EDGE_COUNT (bb->succs) == 1);
 371       bb = split_edge (EDGE_I (bb->succs, 0));
 372       add_abnormal_goto_call_edges (gsi);
 373
 374       gsi = gsi_start_bb (bb);
 375       /* Set __gcov_indirect_call_callee to 0,
 376          so that calls from other modules won't get misattributed
 377          to the last caller of the current callee. */
 378       void0 = build_int_cst (build_pointer_type (void_type_node), 0);
 379       stmt2 = gimple_build_assign (ic_void_ptr_var, void0);
 380       gsi_insert_after (&gsi, stmt2, GSI_NEW_STMT);
 381     }
 382 }
 383
 384 /* Output instructions as GIMPLE trees for code to find the most common value
 385    of a difference between two evaluations of an expression.
 386    VALUE is the expression whose value is profiled.  TAG is the tag of the
 387    section for counters, BASE is offset of the counter position.  */
 388
 389 static void
 390 tree_gen_const_delta_profiler (histogram_value value ATTRIBUTE_UNUSED,
 391                                unsigned tag ATTRIBUTE_UNUSED,
 392                                unsigned base ATTRIBUTE_UNUSED)
 393 {
 394   /* FIXME implement this.  */
 395 #ifdef ENABLE_CHECKING
 396   internal_error ("unimplemented functionality");
 397 #endif
 398   gcc_unreachable ();
 399 }
 400
 401 /* Output instructions as GIMPLE trees to increment the average histogram
 402    counter.  VALUE is the expression whose value is profiled.  TAG is the
 403    tag of the section for counters, BASE is offset of the counter position.  */
 404
 405 static void
 406 tree_gen_average_profiler (histogram_value value, unsigned tag, unsigned base)
 407 {
 408   gimple stmt = value->hvalue.stmt;
 409   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 410   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 411   gimple call;
 412   tree val;
 413
 414   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 415                                       true, NULL_TREE,
 416                                       true, GSI_SAME_STMT);
 417   val = prepare_instrumented_value (&gsi, value);
 418   call = gimple_build_call (tree_average_profiler_fn, 2, ref_ptr, val);
 419   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 420   add_abnormal_goto_call_edges (gsi);
 421 }
 422
 423 /* Output instructions as GIMPLE trees to increment the ior histogram
 424    counter.  VALUE is the expression whose value is profiled.  TAG is the
 425    tag of the section for counters, BASE is offset of the counter position.  */
 426
 427 static void
 428 tree_gen_ior_profiler (histogram_value value, unsigned tag, unsigned base)
 429 {
 430   gimple stmt = value->hvalue.stmt;
 431   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 432   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 433   gimple call;
 434   tree val;
 435
 436   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 437                                       true, NULL_TREE, true, GSI_SAME_STMT);
 438   val = prepare_instrumented_value (&gsi, value);
 439   call = gimple_build_call (tree_ior_profiler_fn, 2, ref_ptr, val);
 440   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 441   add_abnormal_goto_call_edges (gsi);
 442 }
 443
 444 /* Return 1 if tree-based profiling is in effect, else 0.
 445    If it is, set up hooks for tree-based profiling.
 446    Gate for pass_tree_profile.  */
 447
 448 static bool
 449 do_tree_profiling (void)
 450 {
 451   if (profile_arc_flag || flag_test_coverage || flag_branch_probabilities)
 452     {
 453       tree_register_profile_hooks ();
 454       gimple_register_value_prof_hooks ();
 455       return true;
 456     }
 457   return false;
 458 }
 459
 460 static unsigned int
 461 tree_profiling (void)
 462 {
 463   /* Don't profile functions produced at destruction time, particularly
 464      the gcov datastructure initializer.  Don't profile if it has been
 465      already instrumented either (when OpenMP expansion creates
 466      child function from already instrumented body).  */
 467   if (cgraph_state == CGRAPH_STATE_FINISHED
 468       || cfun->after_tree_profile)
 469     return 0;
 470
 471   /* Re-set global shared temporary variable for edge-counters.  */
 472   gcov_type_tmp_var = NULL_TREE;
 473
 474   branch_prob ();
 475
 476   if (! flag_branch_probabilities
 477       && flag_profile_values)
 478     tree_gen_ic_func_profiler ();
 479
 480   if (flag_branch_probabilities
 481       && flag_profile_values
 482       && flag_value_profile_transformations)
 483     value_profile_transformations ();
 484   /* The above could hose dominator info.  Currently there is
 485      none coming in, this is a safety valve.  It should be
 486      easy to adjust it, if and when there is some.  */
 487   free_dominance_info (CDI_DOMINATORS);
 488   free_dominance_info (CDI_POST_DOMINATORS);
 489   cfun->after_tree_profile = 1;
 490   return 0;
 491 }
 492
 493 struct gimple_opt_pass pass_tree_profile =
 494 {
 495  {
 496   GIMPLE_PASS,
 497   "tree_profile",                       /* name */
 498   do_tree_profiling,                    /* gate */
 499   tree_profiling,                       /* execute */
 500   NULL,                                 /* sub */
 501   NULL,                                 /* next */
 502   0,                                    /* static_pass_number */
 503   TV_BRANCH_PROB,                       /* tv_id */
 504   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 505   0,                                    /* properties_provided */
 506   0,                                    /* properties_destroyed */
 507   0,                                    /* todo_flags_start */
 508   TODO_verify_stmts | TODO_dump_func    /* todo_flags_finish */
 509  }
 510 };
 511
 512 struct profile_hooks tree_profile_hooks =
 513 {
 514   tree_init_edge_profiler,       /* init_edge_profiler */
 515   tree_gen_edge_profiler,        /* gen_edge_profiler */
 516   tree_gen_interval_profiler,    /* gen_interval_profiler */
 517   tree_gen_pow2_profiler,        /* gen_pow2_profiler */
 518   tree_gen_one_value_profiler,   /* gen_one_value_profiler */
 519   tree_gen_const_delta_profiler, /* gen_const_delta_profiler */
 520   tree_gen_ic_profiler,          /* gen_ic_profiler */
 521   tree_gen_average_profiler,     /* gen_average_profiler */
 522   tree_gen_ior_profiler          /* gen_ior_profiler */
 523 };
 524
 525 #include "gt-tree-profile.h"