Mercurial > hg > CbC > CbC_gcc
annotate gcc/profile.c @ 81:dbfc0d2dde36
minor fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 24 Sep 2011 02:43:04 +0900 |
| parents | f6334be47118 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Calculate branch probabilities, and basic block execution counts. |
| 2 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010 |
| 0 | 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 | |
| 9 This file is part of GCC. | |
| 10 | |
| 11 GCC is free software; you can redistribute it and/or modify it under | |
| 12 the terms of the GNU General Public License as published by the Free | |
| 13 Software Foundation; either version 3, or (at your option) any later | |
| 14 version. | |
| 15 | |
| 16 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
| 17 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 19 for more details. | |
| 20 | |
| 21 You should have received a copy of the GNU General Public License | |
| 22 along with GCC; see the file COPYING3. If not see | |
| 23 <http://www.gnu.org/licenses/>. */ | |
| 24 | |
| 25 /* Generate basic block profile instrumentation and auxiliary files. | |
| 26 Profile generation is optimized, so that not all arcs in the basic | |
| 27 block graph need instrumenting. First, the BB graph is closed with | |
| 28 one entry (function start), and one exit (function exit). Any | |
| 29 ABNORMAL_EDGE cannot be instrumented (because there is no control | |
| 30 path to place the code). We close the graph by inserting fake | |
| 31 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal | |
| 32 edges that do not go to the exit_block. We ignore such abnormal | |
| 33 edges. Naturally these fake edges are never directly traversed, | |
| 34 and so *cannot* be directly instrumented. Some other graph | |
| 35 massaging is done. To optimize the instrumentation we generate the | |
| 36 BB minimal span tree, only edges that are not on the span tree | |
| 37 (plus the entry point) need instrumenting. From that information | |
| 38 all other edge counts can be deduced. By construction all fake | |
| 39 edges must be on the spanning tree. We also attempt to place | |
| 40 EDGE_CRITICAL edges on the spanning tree. | |
| 41 | |
| 42 The auxiliary files generated are <dumpbase>.gcno (at compile time) | |
| 43 and <dumpbase>.gcda (at run time). The format is | |
| 44 described in full in gcov-io.h. */ | |
| 45 | |
| 46 /* ??? Register allocation should use basic block execution counts to | |
| 47 give preference to the most commonly executed blocks. */ | |
| 48 | |
| 49 /* ??? Should calculate branch probabilities before instrumenting code, since | |
| 50 then we can use arc counts to help decide which arcs to instrument. */ | |
| 51 | |
| 52 #include "config.h" | |
| 53 #include "system.h" | |
| 54 #include "coretypes.h" | |
| 55 #include "tm.h" | |
| 56 #include "rtl.h" | |
| 57 #include "flags.h" | |
| 58 #include "output.h" | |
| 59 #include "regs.h" | |
| 60 #include "expr.h" | |
| 61 #include "function.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
62 #include "basic-block.h" |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
63 #include "diagnostic-core.h" |
| 0 | 64 #include "coverage.h" |
| 65 #include "value-prof.h" | |
| 66 #include "tree.h" | |
| 67 #include "cfghooks.h" | |
| 68 #include "tree-flow.h" | |
| 69 #include "timevar.h" | |
| 70 #include "cfgloop.h" | |
| 71 #include "tree-pass.h" | |
| 72 | |
| 73 #include "profile.h" | |
| 74 | |
| 75 struct bb_info { | |
| 76 unsigned int count_valid : 1; | |
| 77 | |
| 78 /* Number of successor and predecessor edges. */ | |
| 79 gcov_type succ_count; | |
| 80 gcov_type pred_count; | |
| 81 }; | |
| 82 | |
| 83 #define BB_INFO(b) ((struct bb_info *) (b)->aux) | |
| 84 | |
| 85 | |
| 86 /* Counter summary from the last set of coverage counts read. */ | |
| 87 | |
| 88 const struct gcov_ctr_summary *profile_info; | |
| 89 | |
| 90 /* Collect statistics on the performance of this pass for the entire source | |
| 91 file. */ | |
| 92 | |
| 93 static int total_num_blocks; | |
| 94 static int total_num_edges; | |
| 95 static int total_num_edges_ignored; | |
| 96 static int total_num_edges_instrumented; | |
| 97 static int total_num_blocks_created; | |
| 98 static int total_num_passes; | |
| 99 static int total_num_times_called; | |
| 100 static int total_hist_br_prob[20]; | |
| 101 static int total_num_branches; | |
| 102 | |
| 103 /* Forward declarations. */ | |
| 104 static void find_spanning_tree (struct edge_list *); | |
| 105 static unsigned instrument_edges (struct edge_list *); | |
| 106 static void instrument_values (histogram_values); | |
| 107 static void compute_branch_probabilities (void); | |
| 108 static void compute_value_histograms (histogram_values); | |
| 109 static gcov_type * get_exec_counts (void); | |
| 110 static basic_block find_group (basic_block); | |
| 111 static void union_groups (basic_block, basic_block); | |
| 112 | |
| 113 /* Add edge instrumentation code to the entire insn chain. | |
| 114 | |
| 115 F is the first insn of the chain. | |
| 116 NUM_BLOCKS is the number of basic blocks found in F. */ | |
| 117 | |
| 118 static unsigned | |
| 119 instrument_edges (struct edge_list *el) | |
| 120 { | |
| 121 unsigned num_instr_edges = 0; | |
| 122 int num_edges = NUM_EDGES (el); | |
| 123 basic_block bb; | |
| 124 | |
| 125 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 126 { | |
| 127 edge e; | |
| 128 edge_iterator ei; | |
| 129 | |
| 130 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 131 { | |
| 132 struct edge_info *inf = EDGE_INFO (e); | |
| 133 | |
| 134 if (!inf->ignore && !inf->on_tree) | |
| 135 { | |
| 136 gcc_assert (!(e->flags & EDGE_ABNORMAL)); | |
| 137 if (dump_file) | |
| 138 fprintf (dump_file, "Edge %d to %d instrumented%s\n", | |
| 139 e->src->index, e->dest->index, | |
| 140 EDGE_CRITICAL_P (e) ? " (and split)" : ""); | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
141 gimple_gen_edge_profiler (num_instr_edges++, e); |
| 0 | 142 } |
| 143 } | |
| 144 } | |
| 145 | |
| 146 total_num_blocks_created += num_edges; | |
| 147 if (dump_file) | |
| 148 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); | |
| 149 return num_instr_edges; | |
| 150 } | |
| 151 | |
| 152 /* Add code to measure histograms for values in list VALUES. */ | |
| 153 static void | |
| 154 instrument_values (histogram_values values) | |
| 155 { | |
| 156 unsigned i, t; | |
| 157 | |
| 158 /* Emit code to generate the histograms before the insns. */ | |
| 159 | |
| 160 for (i = 0; i < VEC_length (histogram_value, values); i++) | |
| 161 { | |
| 162 histogram_value hist = VEC_index (histogram_value, values, i); | |
| 163 switch (hist->type) | |
| 164 { | |
| 165 case HIST_TYPE_INTERVAL: | |
| 166 t = GCOV_COUNTER_V_INTERVAL; | |
| 167 break; | |
| 168 | |
| 169 case HIST_TYPE_POW2: | |
| 170 t = GCOV_COUNTER_V_POW2; | |
| 171 break; | |
| 172 | |
| 173 case HIST_TYPE_SINGLE_VALUE: | |
| 174 t = GCOV_COUNTER_V_SINGLE; | |
| 175 break; | |
| 176 | |
| 177 case HIST_TYPE_CONST_DELTA: | |
| 178 t = GCOV_COUNTER_V_DELTA; | |
| 179 break; | |
| 180 | |
| 181 case HIST_TYPE_INDIR_CALL: | |
| 182 t = GCOV_COUNTER_V_INDIR; | |
| 183 break; | |
| 184 | |
| 185 case HIST_TYPE_AVERAGE: | |
| 186 t = GCOV_COUNTER_AVERAGE; | |
| 187 break; | |
| 188 | |
| 189 case HIST_TYPE_IOR: | |
| 190 t = GCOV_COUNTER_IOR; | |
| 191 break; | |
| 192 | |
| 193 default: | |
| 194 gcc_unreachable (); | |
| 195 } | |
| 196 if (!coverage_counter_alloc (t, hist->n_counters)) | |
| 197 continue; | |
| 198 | |
| 199 switch (hist->type) | |
| 200 { | |
| 201 case HIST_TYPE_INTERVAL: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
202 gimple_gen_interval_profiler (hist, t, 0); |
| 0 | 203 break; |
| 204 | |
| 205 case HIST_TYPE_POW2: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
206 gimple_gen_pow2_profiler (hist, t, 0); |
| 0 | 207 break; |
| 208 | |
| 209 case HIST_TYPE_SINGLE_VALUE: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
210 gimple_gen_one_value_profiler (hist, t, 0); |
| 0 | 211 break; |
| 212 | |
| 213 case HIST_TYPE_CONST_DELTA: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
214 gimple_gen_const_delta_profiler (hist, t, 0); |
| 0 | 215 break; |
| 216 | |
| 217 case HIST_TYPE_INDIR_CALL: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
218 gimple_gen_ic_profiler (hist, t, 0); |
| 0 | 219 break; |
| 220 | |
| 221 case HIST_TYPE_AVERAGE: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
222 gimple_gen_average_profiler (hist, t, 0); |
| 0 | 223 break; |
| 224 | |
| 225 case HIST_TYPE_IOR: | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
226 gimple_gen_ior_profiler (hist, t, 0); |
| 0 | 227 break; |
| 228 | |
| 229 default: | |
| 230 gcc_unreachable (); | |
| 231 } | |
| 232 } | |
| 233 } | |
| 234 | |
| 235 | |
| 236 /* Computes hybrid profile for all matching entries in da_file. */ | |
| 237 | |
| 238 static gcov_type * | |
| 239 get_exec_counts (void) | |
| 240 { | |
| 241 unsigned num_edges = 0; | |
| 242 basic_block bb; | |
| 243 gcov_type *counts; | |
| 244 | |
| 245 /* Count the edges to be (possibly) instrumented. */ | |
| 246 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 247 { | |
| 248 edge e; | |
| 249 edge_iterator ei; | |
| 250 | |
| 251 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 252 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
| 253 num_edges++; | |
| 254 } | |
| 255 | |
| 256 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info); | |
| 257 if (!counts) | |
| 258 return NULL; | |
| 259 | |
| 260 if (dump_file && profile_info) | |
| 261 fprintf(dump_file, "Merged %u profiles with maximal count %u.\n", | |
| 262 profile_info->runs, (unsigned) profile_info->sum_max); | |
| 263 | |
| 264 return counts; | |
| 265 } | |
| 266 | |
| 267 | |
| 268 static bool | |
| 269 is_edge_inconsistent (VEC(edge,gc) *edges) | |
| 270 { | |
| 271 edge e; | |
| 272 edge_iterator ei; | |
| 273 FOR_EACH_EDGE (e, ei, edges) | |
| 274 { | |
| 275 if (!EDGE_INFO (e)->ignore) | |
| 276 { | |
| 277 if (e->count < 0 | |
| 278 && (!(e->flags & EDGE_FAKE) | |
| 279 || !block_ends_with_call_p (e->src))) | |
| 280 { | |
| 281 if (dump_file) | |
| 282 { | |
| 283 fprintf (dump_file, | |
| 284 "Edge %i->%i is inconsistent, count"HOST_WIDEST_INT_PRINT_DEC, | |
| 285 e->src->index, e->dest->index, e->count); | |
| 286 dump_bb (e->src, dump_file, 0); | |
| 287 dump_bb (e->dest, dump_file, 0); | |
| 288 } | |
| 289 return true; | |
| 290 } | |
| 291 } | |
| 292 } | |
| 293 return false; | |
| 294 } | |
| 295 | |
| 296 static void | |
| 297 correct_negative_edge_counts (void) | |
| 298 { | |
| 299 basic_block bb; | |
| 300 edge e; | |
| 301 edge_iterator ei; | |
| 302 | |
| 303 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 304 { | |
| 305 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 306 { | |
| 307 if (e->count < 0) | |
| 308 e->count = 0; | |
| 309 } | |
| 310 } | |
| 311 } | |
| 312 | |
| 313 /* Check consistency. | |
| 314 Return true if inconsistency is found. */ | |
| 315 static bool | |
| 316 is_inconsistent (void) | |
| 317 { | |
| 318 basic_block bb; | |
| 319 bool inconsistent = false; | |
| 320 FOR_EACH_BB (bb) | |
| 321 { | |
| 322 inconsistent |= is_edge_inconsistent (bb->preds); | |
| 323 if (!dump_file && inconsistent) | |
| 324 return true; | |
| 325 inconsistent |= is_edge_inconsistent (bb->succs); | |
| 326 if (!dump_file && inconsistent) | |
| 327 return true; | |
| 328 if (bb->count < 0) | |
| 329 { | |
| 330 if (dump_file) | |
| 331 { | |
| 332 fprintf (dump_file, "BB %i count is negative " | |
| 333 HOST_WIDEST_INT_PRINT_DEC, | |
| 334 bb->index, | |
| 335 bb->count); | |
| 336 dump_bb (bb, dump_file, 0); | |
| 337 } | |
| 338 inconsistent = true; | |
| 339 } | |
| 340 if (bb->count != sum_edge_counts (bb->preds)) | |
| 341 { | |
| 342 if (dump_file) | |
| 343 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
344 fprintf (dump_file, "BB %i count does not match sum of incoming edges " |
| 0 | 345 HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC, |
| 346 bb->index, | |
| 347 bb->count, | |
| 348 sum_edge_counts (bb->preds)); | |
| 349 dump_bb (bb, dump_file, 0); | |
| 350 } | |
| 351 inconsistent = true; | |
| 352 } | |
| 353 if (bb->count != sum_edge_counts (bb->succs) && | |
| 354 ! (find_edge (bb, EXIT_BLOCK_PTR) != NULL && block_ends_with_call_p (bb))) | |
| 355 { | |
| 356 if (dump_file) | |
| 357 { | |
| 358 fprintf (dump_file, "BB %i count does not match sum of outgoing edges " | |
| 359 HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC, | |
| 360 bb->index, | |
| 361 bb->count, | |
| 362 sum_edge_counts (bb->succs)); | |
| 363 dump_bb (bb, dump_file, 0); | |
| 364 } | |
| 365 inconsistent = true; | |
| 366 } | |
| 367 if (!dump_file && inconsistent) | |
| 368 return true; | |
| 369 } | |
| 370 | |
| 371 return inconsistent; | |
| 372 } | |
| 373 | |
| 374 /* Set each basic block count to the sum of its outgoing edge counts */ | |
| 375 static void | |
| 376 set_bb_counts (void) | |
| 377 { | |
| 378 basic_block bb; | |
| 379 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 380 { | |
| 381 bb->count = sum_edge_counts (bb->succs); | |
| 382 gcc_assert (bb->count >= 0); | |
| 383 } | |
| 384 } | |
| 385 | |
| 386 /* Reads profile data and returns total number of edge counts read */ | |
| 387 static int | |
| 388 read_profile_edge_counts (gcov_type *exec_counts) | |
| 389 { | |
| 390 basic_block bb; | |
| 391 int num_edges = 0; | |
| 392 int exec_counts_pos = 0; | |
| 393 /* For each edge not on the spanning tree, set its execution count from | |
| 394 the .da file. */ | |
| 395 /* The first count in the .da file is the number of times that the function | |
| 396 was entered. This is the exec_count for block zero. */ | |
| 397 | |
| 398 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 399 { | |
| 400 edge e; | |
| 401 edge_iterator ei; | |
| 402 | |
| 403 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 404 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
| 405 { | |
| 406 num_edges++; | |
| 407 if (exec_counts) | |
| 408 { | |
| 409 e->count = exec_counts[exec_counts_pos++]; | |
| 410 if (e->count > profile_info->sum_max) | |
| 411 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
412 if (flag_profile_correction) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
413 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
414 static bool informed = 0; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
415 if (!informed) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
416 inform (input_location, |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
417 "corrupted profile info: edge count exceeds maximal count"); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
418 informed = 1; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
419 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
420 else |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
421 error ("corrupted profile info: edge from %i to %i exceeds maximal count", |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
422 bb->index, e->dest->index); |
| 0 | 423 } |
| 424 } | |
| 425 else | |
| 426 e->count = 0; | |
| 427 | |
| 428 EDGE_INFO (e)->count_valid = 1; | |
| 429 BB_INFO (bb)->succ_count--; | |
| 430 BB_INFO (e->dest)->pred_count--; | |
| 431 if (dump_file) | |
| 432 { | |
| 433 fprintf (dump_file, "\nRead edge from %i to %i, count:", | |
| 434 bb->index, e->dest->index); | |
| 435 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, | |
| 436 (HOST_WIDEST_INT) e->count); | |
| 437 } | |
| 438 } | |
| 439 } | |
| 440 | |
| 441 return num_edges; | |
| 442 } | |
| 443 | |
| 444 /* Compute the branch probabilities for the various branches. | |
| 445 Annotate them accordingly. */ | |
| 446 | |
| 447 static void | |
| 448 compute_branch_probabilities (void) | |
| 449 { | |
| 450 basic_block bb; | |
| 451 int i; | |
| 452 int num_edges = 0; | |
| 453 int changes; | |
| 454 int passes; | |
| 455 int hist_br_prob[20]; | |
| 456 int num_branches; | |
| 457 gcov_type *exec_counts = get_exec_counts (); | |
| 458 int inconsistent = 0; | |
| 459 | |
| 460 /* Very simple sanity checks so we catch bugs in our profiling code. */ | |
| 461 if (!profile_info) | |
| 462 return; | |
| 463 if (profile_info->run_max * profile_info->runs < profile_info->sum_max) | |
| 464 { | |
| 465 error ("corrupted profile info: run_max * runs < sum_max"); | |
| 466 exec_counts = NULL; | |
| 467 } | |
| 468 | |
| 469 if (profile_info->sum_all < profile_info->sum_max) | |
| 470 { | |
| 471 error ("corrupted profile info: sum_all is smaller than sum_max"); | |
| 472 exec_counts = NULL; | |
| 473 } | |
| 474 | |
| 475 /* Attach extra info block to each bb. */ | |
| 476 alloc_aux_for_blocks (sizeof (struct bb_info)); | |
| 477 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 478 { | |
| 479 edge e; | |
| 480 edge_iterator ei; | |
| 481 | |
| 482 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 483 if (!EDGE_INFO (e)->ignore) | |
| 484 BB_INFO (bb)->succ_count++; | |
| 485 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 486 if (!EDGE_INFO (e)->ignore) | |
| 487 BB_INFO (bb)->pred_count++; | |
| 488 } | |
| 489 | |
| 490 /* Avoid predicting entry on exit nodes. */ | |
| 491 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; | |
| 492 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; | |
| 493 | |
| 494 num_edges = read_profile_edge_counts (exec_counts); | |
| 495 | |
| 496 if (dump_file) | |
| 497 fprintf (dump_file, "\n%d edge counts read\n", num_edges); | |
| 498 | |
| 499 /* For every block in the file, | |
| 500 - if every exit/entrance edge has a known count, then set the block count | |
| 501 - if the block count is known, and every exit/entrance edge but one has | |
| 502 a known execution count, then set the count of the remaining edge | |
| 503 | |
| 504 As edge counts are set, decrement the succ/pred count, but don't delete | |
| 505 the edge, that way we can easily tell when all edges are known, or only | |
| 506 one edge is unknown. */ | |
| 507 | |
| 508 /* The order that the basic blocks are iterated through is important. | |
| 509 Since the code that finds spanning trees starts with block 0, low numbered | |
| 510 edges are put on the spanning tree in preference to high numbered edges. | |
| 511 Hence, most instrumented edges are at the end. Graph solving works much | |
| 512 faster if we propagate numbers from the end to the start. | |
| 513 | |
| 514 This takes an average of slightly more than 3 passes. */ | |
| 515 | |
| 516 changes = 1; | |
| 517 passes = 0; | |
| 518 while (changes) | |
| 519 { | |
| 520 passes++; | |
| 521 changes = 0; | |
| 522 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) | |
| 523 { | |
| 524 struct bb_info *bi = BB_INFO (bb); | |
| 525 if (! bi->count_valid) | |
| 526 { | |
| 527 if (bi->succ_count == 0) | |
| 528 { | |
| 529 edge e; | |
| 530 edge_iterator ei; | |
| 531 gcov_type total = 0; | |
| 532 | |
| 533 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 534 total += e->count; | |
| 535 bb->count = total; | |
| 536 bi->count_valid = 1; | |
| 537 changes = 1; | |
| 538 } | |
| 539 else if (bi->pred_count == 0) | |
| 540 { | |
| 541 edge e; | |
| 542 edge_iterator ei; | |
| 543 gcov_type total = 0; | |
| 544 | |
| 545 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 546 total += e->count; | |
| 547 bb->count = total; | |
| 548 bi->count_valid = 1; | |
| 549 changes = 1; | |
| 550 } | |
| 551 } | |
| 552 if (bi->count_valid) | |
| 553 { | |
| 554 if (bi->succ_count == 1) | |
| 555 { | |
| 556 edge e; | |
| 557 edge_iterator ei; | |
| 558 gcov_type total = 0; | |
| 559 | |
| 560 /* One of the counts will be invalid, but it is zero, | |
| 561 so adding it in also doesn't hurt. */ | |
| 562 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 563 total += e->count; | |
| 564 | |
| 565 /* Search for the invalid edge, and set its count. */ | |
| 566 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 567 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) | |
| 568 break; | |
| 569 | |
| 570 /* Calculate count for remaining edge by conservation. */ | |
| 571 total = bb->count - total; | |
| 572 | |
| 573 gcc_assert (e); | |
| 574 EDGE_INFO (e)->count_valid = 1; | |
| 575 e->count = total; | |
| 576 bi->succ_count--; | |
| 577 | |
| 578 BB_INFO (e->dest)->pred_count--; | |
| 579 changes = 1; | |
| 580 } | |
| 581 if (bi->pred_count == 1) | |
| 582 { | |
| 583 edge e; | |
| 584 edge_iterator ei; | |
| 585 gcov_type total = 0; | |
| 586 | |
| 587 /* One of the counts will be invalid, but it is zero, | |
| 588 so adding it in also doesn't hurt. */ | |
| 589 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 590 total += e->count; | |
| 591 | |
| 592 /* Search for the invalid edge, and set its count. */ | |
| 593 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 594 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) | |
| 595 break; | |
| 596 | |
| 597 /* Calculate count for remaining edge by conservation. */ | |
| 598 total = bb->count - total + e->count; | |
| 599 | |
| 600 gcc_assert (e); | |
| 601 EDGE_INFO (e)->count_valid = 1; | |
| 602 e->count = total; | |
| 603 bi->pred_count--; | |
| 604 | |
| 605 BB_INFO (e->src)->succ_count--; | |
| 606 changes = 1; | |
| 607 } | |
| 608 } | |
| 609 } | |
| 610 } | |
| 611 if (dump_file) | |
| 612 dump_flow_info (dump_file, dump_flags); | |
| 613 | |
| 614 total_num_passes += passes; | |
| 615 if (dump_file) | |
| 616 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); | |
| 617 | |
| 618 /* If the graph has been correctly solved, every block will have a | |
| 619 succ and pred count of zero. */ | |
| 620 FOR_EACH_BB (bb) | |
| 621 { | |
| 622 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); | |
| 623 } | |
| 624 | |
| 625 /* Check for inconsistent basic block counts */ | |
| 626 inconsistent = is_inconsistent (); | |
| 627 | |
| 628 if (inconsistent) | |
| 629 { | |
| 630 if (flag_profile_correction) | |
| 631 { | |
| 632 /* Inconsistency detected. Make it flow-consistent. */ | |
| 633 static int informed = 0; | |
| 634 if (informed == 0) | |
| 635 { | |
| 636 informed = 1; | |
| 637 inform (input_location, "correcting inconsistent profile data"); | |
| 638 } | |
| 639 correct_negative_edge_counts (); | |
| 640 /* Set bb counts to the sum of the outgoing edge counts */ | |
| 641 set_bb_counts (); | |
| 642 if (dump_file) | |
| 643 fprintf (dump_file, "\nCalling mcf_smooth_cfg\n"); | |
| 644 mcf_smooth_cfg (); | |
| 645 } | |
| 646 else | |
| 647 error ("corrupted profile info: profile data is not flow-consistent"); | |
| 648 } | |
| 649 | |
| 650 /* For every edge, calculate its branch probability and add a reg_note | |
| 651 to the branch insn to indicate this. */ | |
| 652 | |
| 653 for (i = 0; i < 20; i++) | |
| 654 hist_br_prob[i] = 0; | |
| 655 num_branches = 0; | |
| 656 | |
| 657 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 658 { | |
| 659 edge e; | |
| 660 edge_iterator ei; | |
| 661 | |
| 662 if (bb->count < 0) | |
| 663 { | |
| 664 error ("corrupted profile info: number of iterations for basic block %d thought to be %i", | |
| 665 bb->index, (int)bb->count); | |
| 666 bb->count = 0; | |
| 667 } | |
| 668 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 669 { | |
| 670 /* Function may return twice in the cased the called function is | |
| 671 setjmp or calls fork, but we can't represent this by extra | |
| 672 edge from the entry, since extra edge from the exit is | |
| 673 already present. We get negative frequency from the entry | |
| 674 point. */ | |
| 675 if ((e->count < 0 | |
| 676 && e->dest == EXIT_BLOCK_PTR) | |
| 677 || (e->count > bb->count | |
| 678 && e->dest != EXIT_BLOCK_PTR)) | |
| 679 { | |
| 680 if (block_ends_with_call_p (bb)) | |
| 681 e->count = e->count < 0 ? 0 : bb->count; | |
| 682 } | |
| 683 if (e->count < 0 || e->count > bb->count) | |
| 684 { | |
| 685 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", | |
| 686 e->src->index, e->dest->index, | |
| 687 (int)e->count); | |
| 688 e->count = bb->count / 2; | |
| 689 } | |
| 690 } | |
| 691 if (bb->count) | |
| 692 { | |
| 693 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 694 e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count; | |
| 695 if (bb->index >= NUM_FIXED_BLOCKS | |
| 696 && block_ends_with_condjump_p (bb) | |
| 697 && EDGE_COUNT (bb->succs) >= 2) | |
| 698 { | |
| 699 int prob; | |
| 700 edge e; | |
| 701 int index; | |
| 702 | |
| 703 /* Find the branch edge. It is possible that we do have fake | |
| 704 edges here. */ | |
| 705 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 706 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) | |
| 707 break; | |
| 708 | |
| 709 prob = e->probability; | |
| 710 index = prob * 20 / REG_BR_PROB_BASE; | |
| 711 | |
| 712 if (index == 20) | |
| 713 index = 19; | |
| 714 hist_br_prob[index]++; | |
| 715 | |
| 716 num_branches++; | |
| 717 } | |
| 718 } | |
| 719 /* As a last resort, distribute the probabilities evenly. | |
| 720 Use simple heuristics that if there are normal edges, | |
| 721 give all abnormals frequency of 0, otherwise distribute the | |
| 722 frequency over abnormals (this is the case of noreturn | |
| 723 calls). */ | |
| 724 else if (profile_status == PROFILE_ABSENT) | |
| 725 { | |
| 726 int total = 0; | |
| 727 | |
| 728 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 729 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
| 730 total ++; | |
| 731 if (total) | |
| 732 { | |
| 733 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 734 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
| 735 e->probability = REG_BR_PROB_BASE / total; | |
| 736 else | |
| 737 e->probability = 0; | |
| 738 } | |
| 739 else | |
| 740 { | |
| 741 total += EDGE_COUNT (bb->succs); | |
| 742 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 743 e->probability = REG_BR_PROB_BASE / total; | |
| 744 } | |
| 745 if (bb->index >= NUM_FIXED_BLOCKS | |
| 746 && block_ends_with_condjump_p (bb) | |
| 747 && EDGE_COUNT (bb->succs) >= 2) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
748 num_branches++; |
| 0 | 749 } |
| 750 } | |
| 751 counts_to_freqs (); | |
| 752 profile_status = PROFILE_READ; | |
| 753 | |
| 754 if (dump_file) | |
| 755 { | |
| 756 fprintf (dump_file, "%d branches\n", num_branches); | |
| 757 if (num_branches) | |
| 758 for (i = 0; i < 10; i++) | |
| 759 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", | |
| 760 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, | |
| 761 5 * i, 5 * i + 5); | |
| 762 | |
| 763 total_num_branches += num_branches; | |
| 764 for (i = 0; i < 20; i++) | |
| 765 total_hist_br_prob[i] += hist_br_prob[i]; | |
| 766 | |
| 767 fputc ('\n', dump_file); | |
| 768 fputc ('\n', dump_file); | |
| 769 } | |
| 770 | |
| 771 free_aux_for_blocks (); | |
| 772 } | |
| 773 | |
| 774 /* Load value histograms values whose description is stored in VALUES array | |
| 775 from .gcda file. */ | |
| 776 | |
| 777 static void | |
| 778 compute_value_histograms (histogram_values values) | |
| 779 { | |
| 780 unsigned i, j, t, any; | |
| 781 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; | |
| 782 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; | |
| 783 gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; | |
| 784 gcov_type *aact_count; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
785 |
| 0 | 786 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) |
| 787 n_histogram_counters[t] = 0; | |
| 788 | |
| 789 for (i = 0; i < VEC_length (histogram_value, values); i++) | |
| 790 { | |
| 791 histogram_value hist = VEC_index (histogram_value, values, i); | |
| 792 n_histogram_counters[(int) hist->type] += hist->n_counters; | |
| 793 } | |
| 794 | |
| 795 any = 0; | |
| 796 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
| 797 { | |
| 798 if (!n_histogram_counters[t]) | |
| 799 { | |
| 800 histogram_counts[t] = NULL; | |
| 801 continue; | |
| 802 } | |
| 803 | |
| 804 histogram_counts[t] = | |
| 805 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), | |
| 806 n_histogram_counters[t], NULL); | |
| 807 if (histogram_counts[t]) | |
| 808 any = 1; | |
| 809 act_count[t] = histogram_counts[t]; | |
| 810 } | |
| 811 if (!any) | |
| 812 return; | |
| 813 | |
| 814 for (i = 0; i < VEC_length (histogram_value, values); i++) | |
| 815 { | |
| 816 histogram_value hist = VEC_index (histogram_value, values, i); | |
| 817 gimple stmt = hist->hvalue.stmt; | |
| 818 | |
| 819 t = (int) hist->type; | |
| 820 | |
| 821 aact_count = act_count[t]; | |
| 822 act_count[t] += hist->n_counters; | |
| 823 | |
| 824 gimple_add_histogram_value (cfun, stmt, hist); | |
| 825 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); | |
| 826 for (j = 0; j < hist->n_counters; j++) | |
| 827 hist->hvalue.counters[j] = aact_count[j]; | |
| 828 } | |
| 829 | |
| 830 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
| 831 if (histogram_counts[t]) | |
| 832 free (histogram_counts[t]); | |
| 833 } | |
| 834 | |
| 835 /* The entry basic block will be moved around so that it has index=1, | |
| 836 there is nothing at index 0 and the exit is at n_basic_block. */ | |
| 837 #define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1) | |
| 838 /* When passed NULL as file_name, initialize. | |
| 839 When passed something else, output the necessary commands to change | |
| 840 line to LINE and offset to FILE_NAME. */ | |
| 841 static void | |
| 842 output_location (char const *file_name, int line, | |
| 843 gcov_position_t *offset, basic_block bb) | |
| 844 { | |
| 845 static char const *prev_file_name; | |
| 846 static int prev_line; | |
| 847 bool name_differs, line_differs; | |
| 848 | |
| 849 if (!file_name) | |
| 850 { | |
| 851 prev_file_name = NULL; | |
| 852 prev_line = -1; | |
| 853 return; | |
| 854 } | |
| 855 | |
| 856 name_differs = !prev_file_name || strcmp (file_name, prev_file_name); | |
| 857 line_differs = prev_line != line; | |
| 858 | |
| 859 if (name_differs || line_differs) | |
| 860 { | |
| 861 if (!*offset) | |
| 862 { | |
| 863 *offset = gcov_write_tag (GCOV_TAG_LINES); | |
| 864 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); | |
| 865 name_differs = line_differs=true; | |
| 866 } | |
| 867 | |
| 868 /* If this is a new source file, then output the | |
| 869 file's name to the .bb file. */ | |
| 870 if (name_differs) | |
| 871 { | |
| 872 prev_file_name = file_name; | |
| 873 gcov_write_unsigned (0); | |
| 874 gcov_write_string (prev_file_name); | |
| 875 } | |
| 876 if (line_differs) | |
| 877 { | |
| 878 gcov_write_unsigned (line); | |
| 879 prev_line = line; | |
| 880 } | |
| 881 } | |
| 882 } | |
| 883 | |
| 884 /* Instrument and/or analyze program behavior based on program flow graph. | |
| 885 In either case, this function builds a flow graph for the function being | |
| 886 compiled. The flow graph is stored in BB_GRAPH. | |
| 887 | |
| 888 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in | |
| 889 the flow graph that are needed to reconstruct the dynamic behavior of the | |
| 890 flow graph. | |
| 891 | |
| 892 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary | |
| 893 information from a data file containing edge count information from previous | |
| 894 executions of the function being compiled. In this case, the flow graph is | |
| 895 annotated with actual execution counts, which are later propagated into the | |
| 896 rtl for optimization purposes. | |
| 897 | |
| 898 Main entry point of this file. */ | |
| 899 | |
| 900 void | |
| 901 branch_prob (void) | |
| 902 { | |
| 903 basic_block bb; | |
| 904 unsigned i; | |
| 905 unsigned num_edges, ignored_edges; | |
| 906 unsigned num_instrumented; | |
| 907 struct edge_list *el; | |
| 908 histogram_values values = NULL; | |
| 909 | |
| 910 total_num_times_called++; | |
| 911 | |
| 912 flow_call_edges_add (NULL); | |
| 913 add_noreturn_fake_exit_edges (); | |
| 914 | |
| 915 /* We can't handle cyclic regions constructed using abnormal edges. | |
| 916 To avoid these we replace every source of abnormal edge by a fake | |
| 917 edge from entry node and every destination by fake edge to exit. | |
| 918 This keeps graph acyclic and our calculation exact for all normal | |
| 919 edges except for exit and entrance ones. | |
| 920 | |
| 921 We also add fake exit edges for each call and asm statement in the | |
| 922 basic, since it may not return. */ | |
| 923 | |
| 924 FOR_EACH_BB (bb) | |
| 925 { | |
| 926 int need_exit_edge = 0, need_entry_edge = 0; | |
| 927 int have_exit_edge = 0, have_entry_edge = 0; | |
| 928 edge e; | |
| 929 edge_iterator ei; | |
| 930 | |
| 931 /* Functions returning multiple times are not handled by extra edges. | |
| 932 Instead we simply allow negative counts on edges from exit to the | |
| 933 block past call and corresponding probabilities. We can't go | |
| 934 with the extra edges because that would result in flowgraph that | |
| 935 needs to have fake edges outside the spanning tree. */ | |
| 936 | |
| 937 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 938 { | |
| 939 gimple_stmt_iterator gsi; | |
| 940 gimple last = NULL; | |
| 941 | |
| 942 /* It may happen that there are compiler generated statements | |
| 943 without a locus at all. Go through the basic block from the | |
| 944 last to the first statement looking for a locus. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
945 for (gsi = gsi_last_nondebug_bb (bb); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
946 !gsi_end_p (gsi); |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
947 gsi_prev_nondebug (&gsi)) |
| 0 | 948 { |
| 949 last = gsi_stmt (gsi); | |
| 950 if (gimple_has_location (last)) | |
| 951 break; | |
| 952 } | |
| 953 | |
| 954 /* Edge with goto locus might get wrong coverage info unless | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
955 it is the only edge out of BB. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
956 Don't do that when the locuses match, so |
| 0 | 957 if (blah) goto something; |
| 958 is not computed twice. */ | |
| 959 if (last | |
| 960 && gimple_has_location (last) | |
| 961 && e->goto_locus != UNKNOWN_LOCATION | |
| 962 && !single_succ_p (bb) | |
| 963 && (LOCATION_FILE (e->goto_locus) | |
| 964 != LOCATION_FILE (gimple_location (last)) | |
| 965 || (LOCATION_LINE (e->goto_locus) | |
| 966 != LOCATION_LINE (gimple_location (last))))) | |
| 967 { | |
| 968 basic_block new_bb = split_edge (e); | |
| 969 edge ne = single_succ_edge (new_bb); | |
| 970 ne->goto_locus = e->goto_locus; | |
| 971 ne->goto_block = e->goto_block; | |
| 972 } | |
| 973 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
| 974 && e->dest != EXIT_BLOCK_PTR) | |
| 975 need_exit_edge = 1; | |
| 976 if (e->dest == EXIT_BLOCK_PTR) | |
| 977 have_exit_edge = 1; | |
| 978 } | |
| 979 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 980 { | |
| 981 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
| 982 && e->src != ENTRY_BLOCK_PTR) | |
| 983 need_entry_edge = 1; | |
| 984 if (e->src == ENTRY_BLOCK_PTR) | |
| 985 have_entry_edge = 1; | |
| 986 } | |
| 987 | |
| 988 if (need_exit_edge && !have_exit_edge) | |
| 989 { | |
| 990 if (dump_file) | |
| 991 fprintf (dump_file, "Adding fake exit edge to bb %i\n", | |
| 992 bb->index); | |
| 993 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); | |
| 994 } | |
| 995 if (need_entry_edge && !have_entry_edge) | |
| 996 { | |
| 997 if (dump_file) | |
| 998 fprintf (dump_file, "Adding fake entry edge to bb %i\n", | |
| 999 bb->index); | |
| 1000 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); | |
| 1001 } | |
| 1002 } | |
| 1003 | |
| 1004 el = create_edge_list (); | |
| 1005 num_edges = NUM_EDGES (el); | |
| 1006 alloc_aux_for_edges (sizeof (struct edge_info)); | |
| 1007 | |
| 1008 /* The basic blocks are expected to be numbered sequentially. */ | |
| 1009 compact_blocks (); | |
| 1010 | |
| 1011 ignored_edges = 0; | |
| 1012 for (i = 0 ; i < num_edges ; i++) | |
| 1013 { | |
| 1014 edge e = INDEX_EDGE (el, i); | |
| 1015 e->count = 0; | |
| 1016 | |
| 1017 /* Mark edges we've replaced by fake edges above as ignored. */ | |
| 1018 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
| 1019 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) | |
| 1020 { | |
| 1021 EDGE_INFO (e)->ignore = 1; | |
| 1022 ignored_edges++; | |
| 1023 } | |
| 1024 } | |
| 1025 | |
| 1026 /* Create spanning tree from basic block graph, mark each edge that is | |
| 1027 on the spanning tree. We insert as many abnormal and critical edges | |
| 1028 as possible to minimize number of edge splits necessary. */ | |
| 1029 | |
| 1030 find_spanning_tree (el); | |
| 1031 | |
| 1032 /* Fake edges that are not on the tree will not be instrumented, so | |
| 1033 mark them ignored. */ | |
| 1034 for (num_instrumented = i = 0; i < num_edges; i++) | |
| 1035 { | |
| 1036 edge e = INDEX_EDGE (el, i); | |
| 1037 struct edge_info *inf = EDGE_INFO (e); | |
| 1038 | |
| 1039 if (inf->ignore || inf->on_tree) | |
| 1040 /*NOP*/; | |
| 1041 else if (e->flags & EDGE_FAKE) | |
| 1042 { | |
| 1043 inf->ignore = 1; | |
| 1044 ignored_edges++; | |
| 1045 } | |
| 1046 else | |
| 1047 num_instrumented++; | |
| 1048 } | |
| 1049 | |
| 1050 total_num_blocks += n_basic_blocks; | |
| 1051 if (dump_file) | |
| 1052 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks); | |
| 1053 | |
| 1054 total_num_edges += num_edges; | |
| 1055 if (dump_file) | |
| 1056 fprintf (dump_file, "%d edges\n", num_edges); | |
| 1057 | |
| 1058 total_num_edges_ignored += ignored_edges; | |
| 1059 if (dump_file) | |
| 1060 fprintf (dump_file, "%d ignored edges\n", ignored_edges); | |
| 1061 | |
| 1062 /* Write the data from which gcov can reconstruct the basic block | |
| 1063 graph. */ | |
| 1064 | |
| 1065 /* Basic block flags */ | |
| 1066 if (coverage_begin_output ()) | |
| 1067 { | |
| 1068 gcov_position_t offset; | |
| 1069 | |
| 1070 offset = gcov_write_tag (GCOV_TAG_BLOCKS); | |
| 1071 for (i = 0; i != (unsigned) (n_basic_blocks); i++) | |
| 1072 gcov_write_unsigned (0); | |
| 1073 gcov_write_length (offset); | |
| 1074 } | |
| 1075 | |
| 1076 /* Keep all basic block indexes nonnegative in the gcov output. | |
| 1077 Index 0 is used for entry block, last index is for exit block. | |
| 1078 */ | |
| 1079 ENTRY_BLOCK_PTR->index = 1; | |
| 1080 EXIT_BLOCK_PTR->index = last_basic_block; | |
| 1081 | |
| 1082 /* Arcs */ | |
| 1083 if (coverage_begin_output ()) | |
| 1084 { | |
| 1085 gcov_position_t offset; | |
| 1086 | |
| 1087 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) | |
| 1088 { | |
| 1089 edge e; | |
| 1090 edge_iterator ei; | |
| 1091 | |
| 1092 offset = gcov_write_tag (GCOV_TAG_ARCS); | |
| 1093 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); | |
| 1094 | |
| 1095 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1096 { | |
| 1097 struct edge_info *i = EDGE_INFO (e); | |
| 1098 if (!i->ignore) | |
| 1099 { | |
| 1100 unsigned flag_bits = 0; | |
| 1101 | |
| 1102 if (i->on_tree) | |
| 1103 flag_bits |= GCOV_ARC_ON_TREE; | |
| 1104 if (e->flags & EDGE_FAKE) | |
| 1105 flag_bits |= GCOV_ARC_FAKE; | |
| 1106 if (e->flags & EDGE_FALLTHRU) | |
| 1107 flag_bits |= GCOV_ARC_FALLTHROUGH; | |
| 1108 /* On trees we don't have fallthru flags, but we can | |
| 1109 recompute them from CFG shape. */ | |
| 1110 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) | |
| 1111 && e->src->next_bb == e->dest) | |
| 1112 flag_bits |= GCOV_ARC_FALLTHROUGH; | |
| 1113 | |
| 1114 gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest)); | |
| 1115 gcov_write_unsigned (flag_bits); | |
| 1116 } | |
| 1117 } | |
| 1118 | |
| 1119 gcov_write_length (offset); | |
| 1120 } | |
| 1121 } | |
| 1122 | |
| 1123 /* Line numbers. */ | |
| 1124 if (coverage_begin_output ()) | |
| 1125 { | |
| 1126 gcov_position_t offset; | |
| 1127 | |
| 1128 /* Initialize the output. */ | |
| 1129 output_location (NULL, 0, NULL, NULL); | |
| 1130 | |
| 1131 FOR_EACH_BB (bb) | |
| 1132 { | |
| 1133 gimple_stmt_iterator gsi; | |
| 1134 | |
| 1135 offset = 0; | |
| 1136 | |
| 1137 if (bb == ENTRY_BLOCK_PTR->next_bb) | |
| 1138 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1139 expanded_location curr_location = |
| 0 | 1140 expand_location (DECL_SOURCE_LOCATION (current_function_decl)); |
| 1141 output_location (curr_location.file, curr_location.line, | |
| 1142 &offset, bb); | |
| 1143 } | |
| 1144 | |
| 1145 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 1146 { | |
| 1147 gimple stmt = gsi_stmt (gsi); | |
| 1148 if (gimple_has_location (stmt)) | |
| 1149 output_location (gimple_filename (stmt), gimple_lineno (stmt), | |
| 1150 &offset, bb); | |
| 1151 } | |
| 1152 | |
| 1153 /* Notice GOTO expressions we eliminated while constructing the | |
| 1154 CFG. */ | |
| 1155 if (single_succ_p (bb) | |
| 1156 && single_succ_edge (bb)->goto_locus != UNKNOWN_LOCATION) | |
| 1157 { | |
| 1158 location_t curr_location = single_succ_edge (bb)->goto_locus; | |
| 1159 /* ??? The FILE/LINE API is inconsistent for these cases. */ | |
| 1160 output_location (LOCATION_FILE (curr_location), | |
| 1161 LOCATION_LINE (curr_location), &offset, bb); | |
| 1162 } | |
| 1163 | |
| 1164 if (offset) | |
| 1165 { | |
| 1166 /* A file of NULL indicates the end of run. */ | |
| 1167 gcov_write_unsigned (0); | |
| 1168 gcov_write_string (NULL); | |
| 1169 gcov_write_length (offset); | |
| 1170 } | |
| 1171 } | |
| 1172 } | |
| 1173 | |
| 1174 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK; | |
| 1175 EXIT_BLOCK_PTR->index = EXIT_BLOCK; | |
| 1176 #undef BB_TO_GCOV_INDEX | |
| 1177 | |
| 1178 if (flag_profile_values) | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1179 gimple_find_values_to_profile (&values); |
| 0 | 1180 |
| 1181 if (flag_branch_probabilities) | |
| 1182 { | |
| 1183 compute_branch_probabilities (); | |
| 1184 if (flag_profile_values) | |
| 1185 compute_value_histograms (values); | |
| 1186 } | |
| 1187 | |
| 1188 remove_fake_edges (); | |
| 1189 | |
| 1190 /* For each edge not on the spanning tree, add counting code. */ | |
| 1191 if (profile_arc_flag | |
| 1192 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented)) | |
| 1193 { | |
| 1194 unsigned n_instrumented; | |
| 1195 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1196 gimple_init_edge_profiler (); |
| 0 | 1197 |
| 1198 n_instrumented = instrument_edges (el); | |
| 1199 | |
| 1200 gcc_assert (n_instrumented == num_instrumented); | |
| 1201 | |
| 1202 if (flag_profile_values) | |
| 1203 instrument_values (values); | |
| 1204 | |
| 1205 /* Commit changes done by instrumentation. */ | |
| 1206 gsi_commit_edge_inserts (); | |
| 1207 } | |
| 1208 | |
| 1209 free_aux_for_edges (); | |
| 1210 | |
| 1211 VEC_free (histogram_value, heap, values); | |
| 1212 free_edge_list (el); | |
| 1213 coverage_end_function (); | |
| 1214 } | |
| 1215 | |
| 1216 /* Union find algorithm implementation for the basic blocks using | |
| 1217 aux fields. */ | |
| 1218 | |
| 1219 static basic_block | |
| 1220 find_group (basic_block bb) | |
| 1221 { | |
| 1222 basic_block group = bb, bb1; | |
| 1223 | |
| 1224 while ((basic_block) group->aux != group) | |
| 1225 group = (basic_block) group->aux; | |
| 1226 | |
| 1227 /* Compress path. */ | |
| 1228 while ((basic_block) bb->aux != group) | |
| 1229 { | |
| 1230 bb1 = (basic_block) bb->aux; | |
| 1231 bb->aux = (void *) group; | |
| 1232 bb = bb1; | |
| 1233 } | |
| 1234 return group; | |
| 1235 } | |
| 1236 | |
| 1237 static void | |
| 1238 union_groups (basic_block bb1, basic_block bb2) | |
| 1239 { | |
| 1240 basic_block bb1g = find_group (bb1); | |
| 1241 basic_block bb2g = find_group (bb2); | |
| 1242 | |
| 1243 /* ??? I don't have a place for the rank field. OK. Lets go w/o it, | |
| 1244 this code is unlikely going to be performance problem anyway. */ | |
| 1245 gcc_assert (bb1g != bb2g); | |
| 1246 | |
| 1247 bb1g->aux = bb2g; | |
| 1248 } | |
| 1249 | |
| 1250 /* This function searches all of the edges in the program flow graph, and puts | |
| 1251 as many bad edges as possible onto the spanning tree. Bad edges include | |
| 1252 abnormals edges, which can't be instrumented at the moment. Since it is | |
| 1253 possible for fake edges to form a cycle, we will have to develop some | |
| 1254 better way in the future. Also put critical edges to the tree, since they | |
| 1255 are more expensive to instrument. */ | |
| 1256 | |
| 1257 static void | |
| 1258 find_spanning_tree (struct edge_list *el) | |
| 1259 { | |
| 1260 int i; | |
| 1261 int num_edges = NUM_EDGES (el); | |
| 1262 basic_block bb; | |
| 1263 | |
| 1264 /* We use aux field for standard union-find algorithm. */ | |
| 1265 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 1266 bb->aux = bb; | |
| 1267 | |
| 1268 /* Add fake edge exit to entry we can't instrument. */ | |
| 1269 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR); | |
| 1270 | |
| 1271 /* First add all abnormal edges to the tree unless they form a cycle. Also | |
| 1272 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind | |
| 1273 setting return value from function. */ | |
| 1274 for (i = 0; i < num_edges; i++) | |
| 1275 { | |
| 1276 edge e = INDEX_EDGE (el, i); | |
| 1277 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) | |
| 1278 || e->dest == EXIT_BLOCK_PTR) | |
| 1279 && !EDGE_INFO (e)->ignore | |
| 1280 && (find_group (e->src) != find_group (e->dest))) | |
| 1281 { | |
| 1282 if (dump_file) | |
| 1283 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n", | |
| 1284 e->src->index, e->dest->index); | |
| 1285 EDGE_INFO (e)->on_tree = 1; | |
| 1286 union_groups (e->src, e->dest); | |
| 1287 } | |
| 1288 } | |
| 1289 | |
| 1290 /* Now insert all critical edges to the tree unless they form a cycle. */ | |
| 1291 for (i = 0; i < num_edges; i++) | |
| 1292 { | |
| 1293 edge e = INDEX_EDGE (el, i); | |
| 1294 if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore | |
| 1295 && find_group (e->src) != find_group (e->dest)) | |
| 1296 { | |
| 1297 if (dump_file) | |
| 1298 fprintf (dump_file, "Critical edge %d to %d put to tree\n", | |
| 1299 e->src->index, e->dest->index); | |
| 1300 EDGE_INFO (e)->on_tree = 1; | |
| 1301 union_groups (e->src, e->dest); | |
| 1302 } | |
| 1303 } | |
| 1304 | |
| 1305 /* And now the rest. */ | |
| 1306 for (i = 0; i < num_edges; i++) | |
| 1307 { | |
| 1308 edge e = INDEX_EDGE (el, i); | |
| 1309 if (!EDGE_INFO (e)->ignore | |
| 1310 && find_group (e->src) != find_group (e->dest)) | |
| 1311 { | |
| 1312 if (dump_file) | |
| 1313 fprintf (dump_file, "Normal edge %d to %d put to tree\n", | |
| 1314 e->src->index, e->dest->index); | |
| 1315 EDGE_INFO (e)->on_tree = 1; | |
| 1316 union_groups (e->src, e->dest); | |
| 1317 } | |
| 1318 } | |
| 1319 | |
| 1320 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) | |
| 1321 bb->aux = NULL; | |
| 1322 } | |
| 1323 | |
| 1324 /* Perform file-level initialization for branch-prob processing. */ | |
| 1325 | |
| 1326 void | |
| 1327 init_branch_prob (void) | |
| 1328 { | |
| 1329 int i; | |
| 1330 | |
| 1331 total_num_blocks = 0; | |
| 1332 total_num_edges = 0; | |
| 1333 total_num_edges_ignored = 0; | |
| 1334 total_num_edges_instrumented = 0; | |
| 1335 total_num_blocks_created = 0; | |
| 1336 total_num_passes = 0; | |
| 1337 total_num_times_called = 0; | |
| 1338 total_num_branches = 0; | |
| 1339 for (i = 0; i < 20; i++) | |
| 1340 total_hist_br_prob[i] = 0; | |
| 1341 } | |
| 1342 | |
| 1343 /* Performs file-level cleanup after branch-prob processing | |
| 1344 is completed. */ | |
| 1345 | |
| 1346 void | |
| 1347 end_branch_prob (void) | |
| 1348 { | |
| 1349 if (dump_file) | |
| 1350 { | |
| 1351 fprintf (dump_file, "\n"); | |
| 1352 fprintf (dump_file, "Total number of blocks: %d\n", | |
| 1353 total_num_blocks); | |
| 1354 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges); | |
| 1355 fprintf (dump_file, "Total number of ignored edges: %d\n", | |
| 1356 total_num_edges_ignored); | |
| 1357 fprintf (dump_file, "Total number of instrumented edges: %d\n", | |
| 1358 total_num_edges_instrumented); | |
| 1359 fprintf (dump_file, "Total number of blocks created: %d\n", | |
| 1360 total_num_blocks_created); | |
| 1361 fprintf (dump_file, "Total number of graph solution passes: %d\n", | |
| 1362 total_num_passes); | |
| 1363 if (total_num_times_called != 0) | |
| 1364 fprintf (dump_file, "Average number of graph solution passes: %d\n", | |
| 1365 (total_num_passes + (total_num_times_called >> 1)) | |
| 1366 / total_num_times_called); | |
| 1367 fprintf (dump_file, "Total number of branches: %d\n", | |
| 1368 total_num_branches); | |
| 1369 if (total_num_branches) | |
| 1370 { | |
| 1371 int i; | |
| 1372 | |
| 1373 for (i = 0; i < 10; i++) | |
| 1374 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", | |
| 1375 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 | |
| 1376 / total_num_branches, 5*i, 5*i+5); | |
| 1377 } | |
| 1378 } | |
| 1379 } | |
| 1380 |