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   DECL_TLS_MODEL (ic_void_ptr_var) = decl_default_tls_model (ic_void_ptr_var);
  86   varpool_finalize_decl (ic_void_ptr_var);
  87
  88   gcov_type_ptr = build_pointer_type (get_gcov_type ());
  89   ic_gcov_type_ptr_var
  90     = build_decl (UNKNOWN_LOCATION, VAR_DECL,
  91                   get_identifier ("__gcov_indirect_call_counters"),
  92                   gcov_type_ptr);
  93   TREE_STATIC (ic_gcov_type_ptr_var) = 1;
  94   TREE_PUBLIC (ic_gcov_type_ptr_var) = 0;
  95   DECL_ARTIFICIAL (ic_gcov_type_ptr_var) = 1;
  96   DECL_INITIAL (ic_gcov_type_ptr_var) = NULL;
  97   DECL_TLS_MODEL (ic_gcov_type_ptr_var) = decl_default_tls_model (ic_gcov_type_ptr_var);
  98   varpool_finalize_decl (ic_gcov_type_ptr_var);
  99 }
 100
 101 static void
 102 tree_init_edge_profiler (void)
 103 {
 104   tree interval_profiler_fn_type;
 105   tree pow2_profiler_fn_type;
 106   tree one_value_profiler_fn_type;
 107   tree gcov_type_ptr;
 108   tree ic_profiler_fn_type;
 109   tree average_profiler_fn_type;
 110
 111   if (!gcov_type_node)
 112     {
 113       gcov_type_node = get_gcov_type ();
 114       gcov_type_ptr = build_pointer_type (gcov_type_node);
 115
 116       /* void (*) (gcov_type *, gcov_type, int, unsigned)  */
 117       interval_profiler_fn_type
 118               = build_function_type_list (void_type_node,
 119                                           gcov_type_ptr, gcov_type_node,
 120                                           integer_type_node,
 121                                           unsigned_type_node, NULL_TREE);
 122       tree_interval_profiler_fn
 123               = build_fn_decl ("__gcov_interval_profiler",
 124                                      interval_profiler_fn_type);
 125
 126       /* void (*) (gcov_type *, gcov_type)  */
 127       pow2_profiler_fn_type
 128               = build_function_type_list (void_type_node,
 129                                           gcov_type_ptr, gcov_type_node,
 130                                           NULL_TREE);
 131       tree_pow2_profiler_fn = build_fn_decl ("__gcov_pow2_profiler",
 132                                                    pow2_profiler_fn_type);
 133
 134       /* void (*) (gcov_type *, gcov_type)  */
 135       one_value_profiler_fn_type
 136               = build_function_type_list (void_type_node,
 137                                           gcov_type_ptr, gcov_type_node,
 138                                           NULL_TREE);
 139       tree_one_value_profiler_fn
 140               = build_fn_decl ("__gcov_one_value_profiler",
 141                                      one_value_profiler_fn_type);
 142
 143       tree_init_ic_make_global_vars ();
 144
 145       /* void (*) (gcov_type *, gcov_type, void *, void *)  */
 146       ic_profiler_fn_type
 147                = build_function_type_list (void_type_node,
 148                                           gcov_type_ptr, gcov_type_node,
 149                                           ptr_void,
 150                                           ptr_void, NULL_TREE);
 151       tree_indirect_call_profiler_fn
 152               = build_fn_decl ("__gcov_indirect_call_profiler",
 153                                      ic_profiler_fn_type);
 154       /* void (*) (gcov_type *, gcov_type)  */
 155       average_profiler_fn_type
 156               = build_function_type_list (void_type_node,
 157                                           gcov_type_ptr, gcov_type_node, NULL_TREE);
 158       tree_average_profiler_fn
 159               = build_fn_decl ("__gcov_average_profiler",
 160                                      average_profiler_fn_type);
 161       tree_ior_profiler_fn
 162               = build_fn_decl ("__gcov_ior_profiler",
 163                                      average_profiler_fn_type);
 164       /* LTO streamer needs assembler names.  Because we create these decls
 165          late, we need to initialize them by hand.  */
 166       DECL_ASSEMBLER_NAME (tree_interval_profiler_fn);
 167       DECL_ASSEMBLER_NAME (tree_pow2_profiler_fn);
 168       DECL_ASSEMBLER_NAME (tree_one_value_profiler_fn);
 169       DECL_ASSEMBLER_NAME (tree_indirect_call_profiler_fn);
 170       DECL_ASSEMBLER_NAME (tree_average_profiler_fn);
 171       DECL_ASSEMBLER_NAME (tree_ior_profiler_fn);
 172     }
 173 }
 174
 175 /* New call was added, make goto call edges if neccesary.  */
 176
 177 static void
 178 add_abnormal_goto_call_edges (gimple_stmt_iterator gsi)
 179 {
 180   gimple stmt = gsi_stmt (gsi);
 181
 182   if (!stmt_can_make_abnormal_goto (stmt))
 183     return;
 184   if (!gsi_end_p (gsi))
 185     split_block (gimple_bb (stmt), stmt);
 186   make_abnormal_goto_edges (gimple_bb (stmt), true);
 187 }
 188
 189 /* Output instructions as GIMPLE trees to increment the edge
 190    execution count, and insert them on E.  We rely on
 191    gsi_insert_on_edge to preserve the order.  */
 192
 193 static void
 194 tree_gen_edge_profiler (int edgeno, edge e)
 195 {
 196   tree ref, one;
 197   gimple stmt1, stmt2, stmt3;
 198
 199   /* We share one temporary variable declaration per function.  This
 200      gets re-set in tree_profiling.  */
 201   if (gcov_type_tmp_var == NULL_TREE)
 202     gcov_type_tmp_var = create_tmp_var (gcov_type_node, "PROF_edge_counter");
 203   ref = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
 204   one = build_int_cst (gcov_type_node, 1);
 205   stmt1 = gimple_build_assign (gcov_type_tmp_var, ref);
 206   stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, gcov_type_tmp_var,
 207                                         gcov_type_tmp_var, one);
 208   stmt3 = gimple_build_assign (unshare_expr (ref), gcov_type_tmp_var);
 209   gsi_insert_on_edge (e, stmt1);
 210   gsi_insert_on_edge (e, stmt2);
 211   gsi_insert_on_edge (e, stmt3);
 212 }
 213
 214 /* Emits code to get VALUE to instrument at GSI, and returns the
 215    variable containing the value.  */
 216
 217 static tree
 218 prepare_instrumented_value (gimple_stmt_iterator *gsi, histogram_value value)
 219 {
 220   tree val = value->hvalue.value;
 221   if (POINTER_TYPE_P (TREE_TYPE (val)))
 222     val = fold_convert (sizetype, val);
 223   return force_gimple_operand_gsi (gsi, fold_convert (gcov_type_node, val),
 224                                    true, NULL_TREE, true, GSI_SAME_STMT);
 225 }
 226
 227 /* Output instructions as GIMPLE trees to increment the interval histogram
 228    counter.  VALUE is the expression whose value is profiled.  TAG is the
 229    tag of the section for counters, BASE is offset of the counter position.  */
 230
 231 static void
 232 tree_gen_interval_profiler (histogram_value value, unsigned tag, unsigned base)
 233 {
 234   gimple stmt = value->hvalue.stmt;
 235   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 236   tree ref = tree_coverage_counter_ref (tag, base), ref_ptr;
 237   gimple call;
 238   tree val;
 239   tree start = build_int_cst_type (integer_type_node,
 240                                    value->hdata.intvl.int_start);
 241   tree steps = build_int_cst_type (unsigned_type_node,
 242                                    value->hdata.intvl.steps);
 243
 244   ref_ptr = force_gimple_operand_gsi (&gsi,
 245                                       build_addr (ref, current_function_decl),
 246                                       true, NULL_TREE, true, GSI_SAME_STMT);
 247   val = prepare_instrumented_value (&gsi, value);
 248   call = gimple_build_call (tree_interval_profiler_fn, 4,
 249                             ref_ptr, val, start, steps);
 250   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 251   add_abnormal_goto_call_edges (gsi);
 252 }
 253
 254 /* Output instructions as GIMPLE trees to increment the power of two histogram
 255    counter.  VALUE is the expression whose value is profiled.  TAG is the tag
 256    of the section for counters, BASE is offset of the counter position.  */
 257
 258 static void
 259 tree_gen_pow2_profiler (histogram_value value, unsigned tag, unsigned base)
 260 {
 261   gimple stmt = value->hvalue.stmt;
 262   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 263   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 264   gimple call;
 265   tree val;
 266
 267   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 268                                       true, NULL_TREE, true, GSI_SAME_STMT);
 269   val = prepare_instrumented_value (&gsi, value);
 270   call = gimple_build_call (tree_pow2_profiler_fn, 2, ref_ptr, val);
 271   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 272   add_abnormal_goto_call_edges (gsi);
 273 }
 274
 275 /* Output instructions as GIMPLE trees for code to find the most common value.
 276    VALUE is the expression whose value is profiled.  TAG is the tag of the
 277    section for counters, BASE is offset of the counter position.  */
 278
 279 static void
 280 tree_gen_one_value_profiler (histogram_value value, unsigned tag, unsigned base)
 281 {
 282   gimple stmt = value->hvalue.stmt;
 283   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 284   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 285   gimple call;
 286   tree val;
 287
 288   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 289                                       true, NULL_TREE, true, GSI_SAME_STMT);
 290   val = prepare_instrumented_value (&gsi, value);
 291   call = gimple_build_call (tree_one_value_profiler_fn, 2, ref_ptr, val);
 292   gsi_insert_before (&gsi, call, GSI_NEW_STMT);
 293   add_abnormal_goto_call_edges (gsi);
 294 }
 295
 296
 297 /* Output instructions as GIMPLE trees for code to find the most
 298    common called function in indirect call.
 299    VALUE is the call expression whose indirect callee is profiled.
 300    TAG is the tag of the section for counters, BASE is offset of the
 301    counter position.  */
 302
 303 static void
 304 tree_gen_ic_profiler (histogram_value value, unsigned tag, unsigned base)
 305 {
 306   tree tmp1;
 307   gimple stmt1, stmt2, stmt3;
 308   gimple stmt = value->hvalue.stmt;
 309   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 310   tree ref_ptr = tree_coverage_counter_addr (tag, base);
 311
 312   ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
 313                                       true, NULL_TREE, true, GSI_SAME_STMT);
 314
 315   /* Insert code:
 316
 317     __gcov_indirect_call_counters = get_relevant_counter_ptr ();
 318     __gcov_indirect_call_callee = (void *) indirect call argument;
 319    */
 320
 321   tmp1 = create_tmp_var (ptr_void, "PROF");
 322   stmt1 = gimple_build_assign (ic_gcov_type_ptr_var, ref_ptr);
 323   stmt2 = gimple_build_assign (tmp1, unshare_expr (value->hvalue.value));
 324   stmt3 = gimple_build_assign (ic_void_ptr_var, tmp1);
 325
 326   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 327   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 328   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
 329 }
 330
 331
 332 /* Output instructions as GIMPLE trees for code to find the most
 333    common called function in indirect call. Insert instructions at the
 334    beginning of every possible called function.
 335   */
 336
 337 static void
 338 tree_gen_ic_func_profiler (void)
 339 {
 340   struct cgraph_node * c_node = cgraph_node (current_function_decl);
 341   gimple_stmt_iterator gsi;
 342   edge e;
 343   basic_block bb;
 344   edge_iterator ei;
 345   gimple stmt1, stmt2;
 346   tree tree_uid, cur_func;
 347
 348   if (!c_node->needed)
 349     return;
 350
 351   tree_init_edge_profiler ();
 352
 353   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 354     {
 355       tree void0;
 356
 357       bb = split_edge (e);
 358       gsi = gsi_start_bb (bb);
 359
 360       cur_func = force_gimple_operand_gsi (&gsi,
 361                                            build_addr (current_function_decl,
 362                                                        current_function_decl),
 363                                            true, NULL_TREE,
 364                                            true, GSI_SAME_STMT);
 365       tree_uid = build_int_cst (gcov_type_node, c_node->pid);
 366       stmt1 = gimple_build_call (tree_indirect_call_profiler_fn, 4,
 367                                  ic_gcov_type_ptr_var,
 368                                  tree_uid,
 369                                  cur_func,
 370                                  ic_void_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   /* Re-set global shared temporary variable for edge-counters.  */
 474   gcov_type_tmp_var = NULL_TREE;
 475
 476   branch_prob ();
 477
 478   if (! flag_branch_probabilities
 479       && flag_profile_values)
 480     tree_gen_ic_func_profiler ();
 481
 482   if (flag_branch_probabilities
 483       && flag_profile_values
 484       && flag_value_profile_transformations)
 485     value_profile_transformations ();
 486   /* The above could hose dominator info.  Currently there is
 487      none coming in, this is a safety valve.  It should be
 488      easy to adjust it, if and when there is some.  */
 489   free_dominance_info (CDI_DOMINATORS);
 490   free_dominance_info (CDI_POST_DOMINATORS);
 491   cfun->after_tree_profile = 1;
 492   return 0;
 493 }
 494
 495 struct gimple_opt_pass pass_tree_profile =
 496 {
 497  {
 498   GIMPLE_PASS,
 499   "tree_profile",                       /* name */
 500   do_tree_profiling,                    /* gate */
 501   tree_profiling,                       /* execute */
 502   NULL,                                 /* sub */
 503   NULL,                                 /* next */
 504   0,                                    /* static_pass_number */
 505   TV_BRANCH_PROB,                       /* tv_id */
 506   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 507   0,                                    /* properties_provided */
 508   0,                                    /* properties_destroyed */
 509   0,                                    /* todo_flags_start */
 510   TODO_verify_stmts | TODO_dump_func    /* todo_flags_finish */
 511  }
 512 };
 513
 514 struct profile_hooks tree_profile_hooks =
 515 {
 516   tree_init_edge_profiler,       /* init_edge_profiler */
 517   tree_gen_edge_profiler,        /* gen_edge_profiler */
 518   tree_gen_interval_profiler,    /* gen_interval_profiler */
 519   tree_gen_pow2_profiler,        /* gen_pow2_profiler */
 520   tree_gen_one_value_profiler,   /* gen_one_value_profiler */
 521   tree_gen_const_delta_profiler, /* gen_const_delta_profiler */
 522   tree_gen_ic_profiler,          /* gen_ic_profiler */
 523   tree_gen_average_profiler,     /* gen_average_profiler */
 524   tree_gen_ior_profiler          /* gen_ior_profiler */
 525 };
 526
 527 #include "gt-tree-profile.h"