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, counter_ptr, ptr_var;
 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_NEW_STMT);
 362       counter_ptr = force_gimple_operand_gsi (&gsi, ic_gcov_type_ptr_var,
 363                                               true, NULL_TREE, false,
 364                                               GSI_NEW_STMT);
 365       ptr_var = force_gimple_operand_gsi (&gsi, ic_void_ptr_var,
 366                                           true, NULL_TREE, false,
 367                                           GSI_NEW_STMT);
 368       tree_uid = build_int_cst (gcov_type_node, c_node->pid);
 369       stmt1 = gimple_build_call (tree_indirect_call_profiler_fn, 4,
 370                                  counter_ptr, tree_uid, cur_func, ptr_var);
 371       gsi_insert_after (&gsi, stmt1, GSI_NEW_STMT);
 372       gcc_assert (EDGE_COUNT (bb->succs) == 1);
 373       bb = split_edge (EDGE_I (bb->succs, 0));
 374       add_abnormal_goto_call_edges (gsi);
 375
 376       gsi = gsi_start_bb (bb);
 377       /* Set __gcov_indirect_call_callee to 0,
 378          so that calls from other modules won't get misattributed
 379          to the last caller of the current callee. */
 380       void0 = build_int_cst (build_pointer_type (void_type_node), 0);
 381       stmt2 = gimple_build_assign (ic_void_ptr_var, void0);
 382       gsi_insert_after (&gsi, stmt2, GSI_NEW_STMT);
 383     }
 384 }
 385
 386 /* Output instructions as GIMPLE trees for code to find the most common value
 387    of a difference between two evaluations of an expression.
 388    VALUE is the expression whose value is profiled.  TAG is the tag of the
 389    section for counters, BASE is offset of the counter position.  */
 390
 391 static void
 392 tree_gen_const_delta_profiler (histogram_value value ATTRIBUTE_UNUSED,
 393                                unsigned tag ATTRIBUTE_UNUSED,
 394                                unsigned base ATTRIBUTE_UNUSED)
 395 {
 396   /* FIXME implement this.  */
 397 #ifdef ENABLE_CHECKING
 398   internal_error ("unimplemented functionality");
 399 #endif
 400   gcc_unreachable ();
 401 }
 402
 403 /* Output instructions as GIMPLE trees to increment the average histogram
 404    counter.  VALUE is the expression whose value is profiled.  TAG is the
 405    tag of the section for counters, BASE is offset of the counter position.  */
 406
 407 static void
 408 tree_gen_average_profiler (histogram_value value, unsigned tag, unsigned base)
 409 {
 410   gimple stmt = value->hvalue.stmt;
 411   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 412   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 413   gimple call;
 414   tree val;
 415
 416   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 417                                       true, NULL_TREE,
 418                                       true, GSI_SAME_STMT);
 419   val = prepare_instrumented_value (&gsi, value);
 420   call = gimple_build_call (tree_average_profiler_fn, 2, ref_ptr, val);
 421   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 422   add_abnormal_goto_call_edges (gsi);
 423 }
 424
 425 /* Output instructions as GIMPLE trees to increment the ior histogram
 426    counter.  VALUE is the expression whose value is profiled.  TAG is the
 427    tag of the section for counters, BASE is offset of the counter position.  */
 428
 429 static void
 430 tree_gen_ior_profiler (histogram_value value, unsigned tag, unsigned base)
 431 {
 432   gimple stmt = value->hvalue.stmt;
 433   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 434   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 435   gimple call;
 436   tree val;
 437
 438   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 439                                       true, NULL_TREE, true, GSI_SAME_STMT);
 440   val = prepare_instrumented_value (&gsi, value);
 441   call = gimple_build_call (tree_ior_profiler_fn, 2, ref_ptr, val);
 442   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 443   add_abnormal_goto_call_edges (gsi);
 444 }
 445
 446 /* Return 1 if tree-based profiling is in effect, else 0.
 447    If it is, set up hooks for tree-based profiling.
 448    Gate for pass_tree_profile.  */
 449
 450 static bool
 451 do_tree_profiling (void)
 452 {
 453   if (profile_arc_flag || flag_test_coverage || flag_branch_probabilities)
 454     {
 455       tree_register_profile_hooks ();
 456       gimple_register_value_prof_hooks ();
 457       return true;
 458     }
 459   return false;
 460 }
 461
 462 static unsigned int
 463 tree_profiling (void)
 464 {
 465   /* Don't profile functions produced at destruction time, particularly
 466      the gcov datastructure initializer.  Don't profile if it has been
 467      already instrumented either (when OpenMP expansion creates
 468      child function from already instrumented body).  */
 469   if (cgraph_state == CGRAPH_STATE_FINISHED
 470       || cfun->after_tree_profile)
 471     return 0;
 472
 473   /* Don't profile functions produced for builtin stuff.  */
 474   if (DECL_SOURCE_LOCATION (current_function_decl) == BUILTINS_LOCATION)
 475     return 0;
 476
 477   /* Re-set global shared temporary variable for edge-counters.  */
 478   gcov_type_tmp_var = NULL_TREE;
 479
 480   branch_prob ();
 481
 482   if (! flag_branch_probabilities
 483       && flag_profile_values)
 484     tree_gen_ic_func_profiler ();
 485
 486   if (flag_branch_probabilities
 487       && flag_profile_values
 488       && flag_value_profile_transformations)
 489     value_profile_transformations ();
 490   /* The above could hose dominator info.  Currently there is
 491      none coming in, this is a safety valve.  It should be
 492      easy to adjust it, if and when there is some.  */
 493   free_dominance_info (CDI_DOMINATORS);
 494   free_dominance_info (CDI_POST_DOMINATORS);
 495   cfun->after_tree_profile = 1;
 496   return 0;
 497 }
 498
 499 struct gimple_opt_pass pass_tree_profile =
 500 {
 501  {
 502   GIMPLE_PASS,
 503   "tree_profile",                       /* name */
 504   do_tree_profiling,                    /* gate */
 505   tree_profiling,                       /* execute */
 506   NULL,                                 /* sub */
 507   NULL,                                 /* next */
 508   0,                                    /* static_pass_number */
 509   TV_BRANCH_PROB,                       /* tv_id */
 510   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 511   0,                                    /* properties_provided */
 512   0,                                    /* properties_destroyed */
 513   0,                                    /* todo_flags_start */
 514   TODO_verify_stmts | TODO_dump_func    /* todo_flags_finish */
 515  }
 516 };
 517
 518 struct profile_hooks tree_profile_hooks =
 519 {
 520   tree_init_edge_profiler,       /* init_edge_profiler */
 521   tree_gen_edge_profiler,        /* gen_edge_profiler */
 522   tree_gen_interval_profiler,    /* gen_interval_profiler */
 523   tree_gen_pow2_profiler,        /* gen_pow2_profiler */
 524   tree_gen_one_value_profiler,   /* gen_one_value_profiler */
 525   tree_gen_const_delta_profiler, /* gen_const_delta_profiler */
 526   tree_gen_ic_profiler,          /* gen_ic_profiler */
 527   tree_gen_average_profiler,     /* gen_average_profiler */
 528   tree_gen_ior_profiler          /* gen_ior_profiler */
 529 };
 530
 531 #include "gt-tree-profile.h"