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
10This file is part of GCC.
11
12GCC is free software; you can redistribute it and/or modify it under
13the terms of the GNU General Public License as published by the Free
14Software Foundation; either version 3, or (at your option) any later
15version.
16
17GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18WARRANTY; without even the implied warranty of MERCHANTABILITY or
19FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
20for more details.
21
22You should have received a copy of the GNU General Public License
23along 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
50static GTY(()) tree gcov_type_node;
51static GTY(()) tree gcov_type_tmp_var;
52static GTY(()) tree tree_interval_profiler_fn;
53static GTY(()) tree tree_pow2_profiler_fn;
54static GTY(()) tree tree_one_value_profiler_fn;
55static GTY(()) tree tree_indirect_call_profiler_fn;
56static GTY(()) tree tree_average_profiler_fn;
57static GTY(()) tree tree_ior_profiler_fn;
58
59
60static GTY(()) tree ic_void_ptr_var;
61static GTY(()) tree ic_gcov_type_ptr_var;
62static 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*/
70static void
71tree_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
99static void
100tree_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
175static void
176add_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
191static void
192tree_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
215static tree
216prepare_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
229static void
230tree_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
256static void
257tree_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
277static void
278tree_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
301static void
302tree_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
335static void
336tree_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
389static void
390tree_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
405static void
406tree_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
427static void
428tree_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
448static bool
449do_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
460static unsigned int
461tree_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
493struct 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
512struct 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"
526