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