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