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 "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 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 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 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 /* 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 175 static void 176 add_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 191 static void 192 tree_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 215 static tree 216 prepare_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 229 static void 230 tree_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 256 static void 257 tree_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 277 static void 278 tree_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 301 static void 302 tree_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 335 static void 336 tree_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 389 static void 390 tree_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 405 static void 406 tree_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 427 static void 428 tree_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 448 static bool 449 do_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 460 static unsigned int 461 tree_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 493 struct 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 512 struct 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