]>
Commit | Line | Data |
---|---|---|
447f6a7f | 1 | /* Calculate branch probabilities, and basic block execution counts. |
d353bf18 | 2 | Copyright (C) 1990-2015 Free Software Foundation, Inc. |
10f2b886 | 3 | Contributed by James E. Wilson, UC Berkeley/Cygnus Support; |
4 | based on some ideas from Dain Samples of UC Berkeley. | |
5 | Further mangling by Bob Manson, Cygnus Support. | |
6 | ||
f12b58b3 | 7 | This file is part of GCC. |
10f2b886 | 8 | |
f12b58b3 | 9 | GCC is free software; you can redistribute it and/or modify it under |
10 | the terms of the GNU General Public License as published by the Free | |
8c4c00c1 | 11 | Software Foundation; either version 3, or (at your option) any later |
f12b58b3 | 12 | version. |
10f2b886 | 13 | |
f12b58b3 | 14 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
15 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
16 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
17 | for more details. | |
10f2b886 | 18 | |
19 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 20 | along with GCC; see the file COPYING3. If not see |
21 | <http://www.gnu.org/licenses/>. */ | |
10f2b886 | 22 | |
958c14b1 | 23 | /* Generate basic block profile instrumentation and auxiliary files. |
24 | Profile generation is optimized, so that not all arcs in the basic | |
25 | block graph need instrumenting. First, the BB graph is closed with | |
26 | one entry (function start), and one exit (function exit). Any | |
27 | ABNORMAL_EDGE cannot be instrumented (because there is no control | |
28 | path to place the code). We close the graph by inserting fake | |
29 | EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal | |
30 | edges that do not go to the exit_block. We ignore such abnormal | |
31 | edges. Naturally these fake edges are never directly traversed, | |
32 | and so *cannot* be directly instrumented. Some other graph | |
33 | massaging is done. To optimize the instrumentation we generate the | |
34 | BB minimal span tree, only edges that are not on the span tree | |
35 | (plus the entry point) need instrumenting. From that information | |
36 | all other edge counts can be deduced. By construction all fake | |
37 | edges must be on the spanning tree. We also attempt to place | |
38 | EDGE_CRITICAL edges on the spanning tree. | |
39 | ||
4ee9c684 | 40 | The auxiliary files generated are <dumpbase>.gcno (at compile time) |
41 | and <dumpbase>.gcda (at run time). The format is | |
805e22b2 | 42 | described in full in gcov-io.h. */ |
958c14b1 | 43 | |
10f2b886 | 44 | /* ??? Register allocation should use basic block execution counts to |
45 | give preference to the most commonly executed blocks. */ | |
46 | ||
10f2b886 | 47 | /* ??? Should calculate branch probabilities before instrumenting code, since |
48 | then we can use arc counts to help decide which arcs to instrument. */ | |
49 | ||
10f2b886 | 50 | #include "config.h" |
405711de | 51 | #include "system.h" |
805e22b2 | 52 | #include "coretypes.h" |
53 | #include "tm.h" | |
10f2b886 | 54 | #include "rtl.h" |
55 | #include "flags.h" | |
0dbd1c74 | 56 | #include "regs.h" |
b20a8bb4 | 57 | #include "symtab.h" |
a3020f2f | 58 | #include "hard-reg-set.h" |
0a893c29 | 59 | #include "function.h" |
d53441c8 | 60 | #include "alias.h" |
d53441c8 | 61 | #include "tree.h" |
62 | #include "insn-config.h" | |
63 | #include "expmed.h" | |
64 | #include "dojump.h" | |
65 | #include "explow.h" | |
66 | #include "calls.h" | |
67 | #include "emit-rtl.h" | |
68 | #include "varasm.h" | |
69 | #include "stmt.h" | |
70 | #include "expr.h" | |
94ea8568 | 71 | #include "predict.h" |
72 | #include "dominance.h" | |
73 | #include "cfg.h" | |
74 | #include "cfganal.h" | |
a79e7523 | 75 | #include "basic-block.h" |
0b205f4c | 76 | #include "diagnostic-core.h" |
44359ced | 77 | #include "coverage.h" |
0a9d9b9c | 78 | #include "value-prof.h" |
b20a8bb4 | 79 | #include "fold-const.h" |
bc61cadb | 80 | #include "tree-ssa-alias.h" |
81 | #include "internal-fn.h" | |
82 | #include "gimple-expr.h" | |
073c1fd5 | 83 | #include "gimple.h" |
dcf1a1ec | 84 | #include "gimple-iterator.h" |
073c1fd5 | 85 | #include "tree-cfg.h" |
77fce4cd | 86 | #include "cfgloop.h" |
b9ed1410 | 87 | #include "dumpfile.h" |
1140c305 | 88 | #include "plugin-api.h" |
89 | #include "ipa-ref.h" | |
38fe12e3 | 90 | #include "cgraph.h" |
4ee9c684 | 91 | |
e0dc6f2b | 92 | #include "profile.h" |
93 | ||
1ada9901 | 94 | struct bb_profile_info { |
958c14b1 | 95 | unsigned int count_valid : 1; |
96 | ||
7299020b | 97 | /* Number of successor and predecessor edges. */ |
958c14b1 | 98 | gcov_type succ_count; |
99 | gcov_type pred_count; | |
100 | }; | |
86d4af74 | 101 | |
1ada9901 | 102 | #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux) |
86d4af74 | 103 | |
75a70cf9 | 104 | |
6473f3f4 | 105 | /* Counter summary from the last set of coverage counts read. */ |
ab6a34f2 | 106 | |
107 | const struct gcov_ctr_summary *profile_info; | |
108 | ||
2c2093b3 | 109 | /* Counter working set information computed from the current counter |
110 | summary. Not initialized unless profile_info summary is non-NULL. */ | |
111 | static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS]; | |
112 | ||
10f2b886 | 113 | /* Collect statistics on the performance of this pass for the entire source |
114 | file. */ | |
115 | ||
116 | static int total_num_blocks; | |
86d4af74 | 117 | static int total_num_edges; |
84870dc8 | 118 | static int total_num_edges_ignored; |
86d4af74 | 119 | static int total_num_edges_instrumented; |
10f2b886 | 120 | static int total_num_blocks_created; |
121 | static int total_num_passes; | |
122 | static int total_num_times_called; | |
123 | static int total_hist_br_prob[20]; | |
10f2b886 | 124 | static int total_num_branches; |
125 | ||
94bed7c3 | 126 | /* Helper function to update gcov_working_sets. */ |
127 | ||
128 | void add_working_set (gcov_working_set_t *set) { | |
129 | int i = 0; | |
130 | for (; i < NUM_GCOV_WORKING_SETS; i++) | |
131 | gcov_working_sets[i] = set[i]; | |
132 | } | |
133 | ||
10f2b886 | 134 | /* Forward declarations. */ |
3ad4992f | 135 | static void find_spanning_tree (struct edge_list *); |
10f2b886 | 136 | |
86d4af74 | 137 | /* Add edge instrumentation code to the entire insn chain. |
10f2b886 | 138 | |
139 | F is the first insn of the chain. | |
86d4af74 | 140 | NUM_BLOCKS is the number of basic blocks found in F. */ |
10f2b886 | 141 | |
015af757 | 142 | static unsigned |
3ad4992f | 143 | instrument_edges (struct edge_list *el) |
10f2b886 | 144 | { |
015af757 | 145 | unsigned num_instr_edges = 0; |
86d4af74 | 146 | int num_edges = NUM_EDGES (el); |
4c26117a | 147 | basic_block bb; |
3ad4992f | 148 | |
34154e27 | 149 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
86d4af74 | 150 | { |
015af757 | 151 | edge e; |
cd665a06 | 152 | edge_iterator ei; |
015af757 | 153 | |
cd665a06 | 154 | FOR_EACH_EDGE (e, ei, bb->succs) |
10f2b886 | 155 | { |
1ada9901 | 156 | struct edge_profile_info *inf = EDGE_INFO (e); |
3ad4992f | 157 | |
86d4af74 | 158 | if (!inf->ignore && !inf->on_tree) |
10f2b886 | 159 | { |
876760f6 | 160 | gcc_assert (!(e->flags & EDGE_ABNORMAL)); |
450d042a | 161 | if (dump_file) |
162 | fprintf (dump_file, "Edge %d to %d instrumented%s\n", | |
b3d6de89 | 163 | e->src->index, e->dest->index, |
e76f35e8 | 164 | EDGE_CRITICAL_P (e) ? " (and split)" : ""); |
fc49fbc1 | 165 | gimple_gen_edge_profiler (num_instr_edges++, e); |
10f2b886 | 166 | } |
167 | } | |
10f2b886 | 168 | } |
86d4af74 | 169 | |
86d4af74 | 170 | total_num_blocks_created += num_edges; |
450d042a | 171 | if (dump_file) |
172 | fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); | |
015af757 | 173 | return num_instr_edges; |
10f2b886 | 174 | } |
0a9d9b9c | 175 | |
8a5df2ce | 176 | /* Add code to measure histograms for values in list VALUES. */ |
0a9d9b9c | 177 | static void |
8a5df2ce | 178 | instrument_values (histogram_values values) |
0a9d9b9c | 179 | { |
3e7f455b | 180 | unsigned i; |
3ad4992f | 181 | |
0a9d9b9c | 182 | /* Emit code to generate the histograms before the insns. */ |
183 | ||
f1f41a6c | 184 | for (i = 0; i < values.length (); i++) |
0a9d9b9c | 185 | { |
f1f41a6c | 186 | histogram_value hist = values[i]; |
3e7f455b | 187 | unsigned t = COUNTER_FOR_HIST_TYPE (hist->type); |
0a9d9b9c | 188 | |
8a5df2ce | 189 | if (!coverage_counter_alloc (t, hist->n_counters)) |
0a9d9b9c | 190 | continue; |
191 | ||
8a5df2ce | 192 | switch (hist->type) |
0a9d9b9c | 193 | { |
194 | case HIST_TYPE_INTERVAL: | |
fc49fbc1 | 195 | gimple_gen_interval_profiler (hist, t, 0); |
0a9d9b9c | 196 | break; |
197 | ||
198 | case HIST_TYPE_POW2: | |
fc49fbc1 | 199 | gimple_gen_pow2_profiler (hist, t, 0); |
0a9d9b9c | 200 | break; |
201 | ||
202 | case HIST_TYPE_SINGLE_VALUE: | |
fc49fbc1 | 203 | gimple_gen_one_value_profiler (hist, t, 0); |
0a9d9b9c | 204 | break; |
205 | ||
206 | case HIST_TYPE_CONST_DELTA: | |
fc49fbc1 | 207 | gimple_gen_const_delta_profiler (hist, t, 0); |
0a9d9b9c | 208 | break; |
209 | ||
167b550b | 210 | case HIST_TYPE_INDIR_CALL: |
b74245ec | 211 | case HIST_TYPE_INDIR_CALL_TOPN: |
fc49fbc1 | 212 | gimple_gen_ic_profiler (hist, t, 0); |
167b550b | 213 | break; |
214 | ||
162719b3 | 215 | case HIST_TYPE_AVERAGE: |
fc49fbc1 | 216 | gimple_gen_average_profiler (hist, t, 0); |
162719b3 | 217 | break; |
218 | ||
219 | case HIST_TYPE_IOR: | |
fc49fbc1 | 220 | gimple_gen_ior_profiler (hist, t, 0); |
162719b3 | 221 | break; |
222 | ||
38fe12e3 | 223 | case HIST_TYPE_TIME_PROFILE: |
224 | { | |
34154e27 | 225 | basic_block bb = |
226 | split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))); | |
38fe12e3 | 227 | gimple_stmt_iterator gsi = gsi_start_bb (bb); |
228 | ||
229 | gimple_gen_time_profiler (t, 0, gsi); | |
230 | break; | |
231 | } | |
232 | ||
0a9d9b9c | 233 | default: |
876760f6 | 234 | gcc_unreachable (); |
0a9d9b9c | 235 | } |
0a9d9b9c | 236 | } |
237 | } | |
805e22b2 | 238 | \f |
c3b641a2 | 239 | |
8515a84d | 240 | /* Fill the working set information into the profile_info structure. */ |
2c2093b3 | 241 | |
e3ba12e8 | 242 | void |
8515a84d | 243 | get_working_sets (void) |
2c2093b3 | 244 | { |
8515a84d | 245 | unsigned ws_ix, pctinc, pct; |
2c2093b3 | 246 | gcov_working_set_t *ws_info; |
247 | ||
248 | if (!profile_info) | |
249 | return; | |
250 | ||
8515a84d | 251 | compute_working_sets (profile_info, gcov_working_sets); |
2c2093b3 | 252 | |
253 | if (dump_file) | |
254 | { | |
255 | fprintf (dump_file, "Counter working sets:\n"); | |
256 | /* Multiply the percentage by 100 to avoid float. */ | |
257 | pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS; | |
258 | for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS; | |
259 | ws_ix++, pct += pctinc) | |
260 | { | |
261 | if (ws_ix == NUM_GCOV_WORKING_SETS - 1) | |
262 | pct = 9990; | |
263 | ws_info = &gcov_working_sets[ws_ix]; | |
264 | /* Print out the percentage using int arithmatic to avoid float. */ | |
265 | fprintf (dump_file, "\t\t%u.%02u%%: num counts=%u, min counter=" | |
f03df321 | 266 | "%" PRId64 "\n", |
2c2093b3 | 267 | pct / 100, pct - (pct / 100 * 100), |
268 | ws_info->num_counters, | |
3a4303e7 | 269 | (int64_t)ws_info->min_counter); |
2c2093b3 | 270 | } |
271 | } | |
272 | } | |
273 | ||
274 | /* Given a the desired percentage of the full profile (sum_all from the | |
275 | summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns | |
276 | the corresponding working set information. If an exact match for | |
277 | the percentage isn't found, the closest value is used. */ | |
278 | ||
279 | gcov_working_set_t * | |
280 | find_working_set (unsigned pct_times_10) | |
281 | { | |
282 | unsigned i; | |
283 | if (!profile_info) | |
284 | return NULL; | |
285 | gcc_assert (pct_times_10 <= 1000); | |
286 | if (pct_times_10 >= 999) | |
287 | return &gcov_working_sets[NUM_GCOV_WORKING_SETS - 1]; | |
288 | i = pct_times_10 * NUM_GCOV_WORKING_SETS / 1000; | |
289 | if (!i) | |
290 | return &gcov_working_sets[0]; | |
291 | return &gcov_working_sets[i - 1]; | |
292 | } | |
293 | ||
06306fd3 | 294 | /* Computes hybrid profile for all matching entries in da_file. |
295 | ||
296 | CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
90c2be44 | 297 | |
298 | static gcov_type * | |
06306fd3 | 299 | get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum) |
90c2be44 | 300 | { |
805e22b2 | 301 | unsigned num_edges = 0; |
4c26117a | 302 | basic_block bb; |
44359ced | 303 | gcov_type *counts; |
3ad4992f | 304 | |
90c2be44 | 305 | /* Count the edges to be (possibly) instrumented. */ |
34154e27 | 306 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
90c2be44 | 307 | { |
90c2be44 | 308 | edge e; |
cd665a06 | 309 | edge_iterator ei; |
310 | ||
311 | FOR_EACH_EDGE (e, ei, bb->succs) | |
90c2be44 | 312 | if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) |
4c26117a | 313 | num_edges++; |
90c2be44 | 314 | } |
315 | ||
06306fd3 | 316 | counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, cfg_checksum, |
317 | lineno_checksum, &profile_info); | |
44359ced | 318 | if (!counts) |
319 | return NULL; | |
805e22b2 | 320 | |
9af5ce0c | 321 | get_working_sets (); |
2c2093b3 | 322 | |
450d042a | 323 | if (dump_file && profile_info) |
9af5ce0c | 324 | fprintf (dump_file, "Merged %u profiles with maximal count %u.\n", |
325 | profile_info->runs, (unsigned) profile_info->sum_max); | |
90c2be44 | 326 | |
44359ced | 327 | return counts; |
90c2be44 | 328 | } |
90c2be44 | 329 | |
e0dc6f2b | 330 | |
331 | static bool | |
f1f41a6c | 332 | is_edge_inconsistent (vec<edge, va_gc> *edges) |
e0dc6f2b | 333 | { |
334 | edge e; | |
335 | edge_iterator ei; | |
336 | FOR_EACH_EDGE (e, ei, edges) | |
337 | { | |
338 | if (!EDGE_INFO (e)->ignore) | |
339 | { | |
84043c1e | 340 | if (e->count < 0 |
82012ffe | 341 | && (!(e->flags & EDGE_FAKE) |
84043c1e | 342 | || !block_ends_with_call_p (e->src))) |
343 | { | |
344 | if (dump_file) | |
345 | { | |
346 | fprintf (dump_file, | |
f03df321 | 347 | "Edge %i->%i is inconsistent, count%" PRId64, |
84043c1e | 348 | e->src->index, e->dest->index, e->count); |
5147ec07 | 349 | dump_bb (dump_file, e->src, 0, TDF_DETAILS); |
350 | dump_bb (dump_file, e->dest, 0, TDF_DETAILS); | |
84043c1e | 351 | } |
352 | return true; | |
353 | } | |
e0dc6f2b | 354 | } |
355 | } | |
356 | return false; | |
357 | } | |
b9cf3f63 | 358 | |
359 | static void | |
e0dc6f2b | 360 | correct_negative_edge_counts (void) |
b9cf3f63 | 361 | { |
4c26117a | 362 | basic_block bb; |
e0dc6f2b | 363 | edge e; |
364 | edge_iterator ei; | |
b9cf3f63 | 365 | |
34154e27 | 366 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
f01f2080 | 367 | { |
e0dc6f2b | 368 | FOR_EACH_EDGE (e, ei, bb->succs) |
369 | { | |
370 | if (e->count < 0) | |
371 | e->count = 0; | |
372 | } | |
373 | } | |
374 | } | |
f01f2080 | 375 | |
e0dc6f2b | 376 | /* Check consistency. |
377 | Return true if inconsistency is found. */ | |
378 | static bool | |
379 | is_inconsistent (void) | |
380 | { | |
381 | basic_block bb; | |
84043c1e | 382 | bool inconsistent = false; |
fc00614f | 383 | FOR_EACH_BB_FN (bb, cfun) |
e0dc6f2b | 384 | { |
84043c1e | 385 | inconsistent |= is_edge_inconsistent (bb->preds); |
386 | if (!dump_file && inconsistent) | |
387 | return true; | |
388 | inconsistent |= is_edge_inconsistent (bb->succs); | |
389 | if (!dump_file && inconsistent) | |
390 | return true; | |
391 | if (bb->count < 0) | |
392 | { | |
393 | if (dump_file) | |
394 | { | |
395 | fprintf (dump_file, "BB %i count is negative " | |
f03df321 | 396 | "%" PRId64, |
84043c1e | 397 | bb->index, |
398 | bb->count); | |
5147ec07 | 399 | dump_bb (dump_file, bb, 0, TDF_DETAILS); |
84043c1e | 400 | } |
401 | inconsistent = true; | |
402 | } | |
403 | if (bb->count != sum_edge_counts (bb->preds)) | |
404 | { | |
405 | if (dump_file) | |
406 | { | |
4034c43c | 407 | fprintf (dump_file, "BB %i count does not match sum of incoming edges " |
f03df321 | 408 | "%" PRId64" should be %" PRId64, |
84043c1e | 409 | bb->index, |
410 | bb->count, | |
411 | sum_edge_counts (bb->preds)); | |
5147ec07 | 412 | dump_bb (dump_file, bb, 0, TDF_DETAILS); |
84043c1e | 413 | } |
414 | inconsistent = true; | |
415 | } | |
416 | if (bb->count != sum_edge_counts (bb->succs) && | |
34154e27 | 417 | ! (find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)) != NULL |
418 | && block_ends_with_call_p (bb))) | |
84043c1e | 419 | { |
420 | if (dump_file) | |
421 | { | |
422 | fprintf (dump_file, "BB %i count does not match sum of outgoing edges " | |
f03df321 | 423 | "%" PRId64" should be %" PRId64, |
84043c1e | 424 | bb->index, |
425 | bb->count, | |
426 | sum_edge_counts (bb->succs)); | |
5147ec07 | 427 | dump_bb (dump_file, bb, 0, TDF_DETAILS); |
84043c1e | 428 | } |
429 | inconsistent = true; | |
430 | } | |
431 | if (!dump_file && inconsistent) | |
432 | return true; | |
f01f2080 | 433 | } |
434 | ||
84043c1e | 435 | return inconsistent; |
e0dc6f2b | 436 | } |
86d4af74 | 437 | |
e0dc6f2b | 438 | /* Set each basic block count to the sum of its outgoing edge counts */ |
439 | static void | |
440 | set_bb_counts (void) | |
441 | { | |
442 | basic_block bb; | |
34154e27 | 443 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
86d4af74 | 444 | { |
e0dc6f2b | 445 | bb->count = sum_edge_counts (bb->succs); |
446 | gcc_assert (bb->count >= 0); | |
86d4af74 | 447 | } |
e0dc6f2b | 448 | } |
86d4af74 | 449 | |
e0dc6f2b | 450 | /* Reads profile data and returns total number of edge counts read */ |
451 | static int | |
452 | read_profile_edge_counts (gcov_type *exec_counts) | |
453 | { | |
454 | basic_block bb; | |
455 | int num_edges = 0; | |
456 | int exec_counts_pos = 0; | |
86d4af74 | 457 | /* For each edge not on the spanning tree, set its execution count from |
b9cf3f63 | 458 | the .da file. */ |
b9cf3f63 | 459 | /* The first count in the .da file is the number of times that the function |
460 | was entered. This is the exec_count for block zero. */ | |
461 | ||
34154e27 | 462 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
86d4af74 | 463 | { |
86d4af74 | 464 | edge e; |
cd665a06 | 465 | edge_iterator ei; |
466 | ||
467 | FOR_EACH_EDGE (e, ei, bb->succs) | |
86d4af74 | 468 | if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) |
469 | { | |
470 | num_edges++; | |
90c2be44 | 471 | if (exec_counts) |
86d4af74 | 472 | { |
90c2be44 | 473 | e->count = exec_counts[exec_counts_pos++]; |
f01f2080 | 474 | if (e->count > profile_info->sum_max) |
475 | { | |
566d3fc7 | 476 | if (flag_profile_correction) |
477 | { | |
478 | static bool informed = 0; | |
202c2bd9 | 479 | if (dump_enabled_p () && !informed) |
480 | dump_printf_loc (MSG_NOTE, input_location, | |
78bb46f5 | 481 | "corrupted profile info: edge count" |
482 | " exceeds maximal count\n"); | |
566d3fc7 | 483 | informed = 1; |
484 | } | |
485 | else | |
486 | error ("corrupted profile info: edge from %i to %i exceeds maximal count", | |
487 | bb->index, e->dest->index); | |
f01f2080 | 488 | } |
86d4af74 | 489 | } |
490 | else | |
491 | e->count = 0; | |
90c2be44 | 492 | |
86d4af74 | 493 | EDGE_INFO (e)->count_valid = 1; |
494 | BB_INFO (bb)->succ_count--; | |
495 | BB_INFO (e->dest)->pred_count--; | |
450d042a | 496 | if (dump_file) |
63f23608 | 497 | { |
450d042a | 498 | fprintf (dump_file, "\nRead edge from %i to %i, count:", |
b3d6de89 | 499 | bb->index, e->dest->index); |
f03df321 | 500 | fprintf (dump_file, "%" PRId64, |
3a4303e7 | 501 | (int64_t) e->count); |
63f23608 | 502 | } |
86d4af74 | 503 | } |
504 | } | |
b9cf3f63 | 505 | |
e0dc6f2b | 506 | return num_edges; |
507 | } | |
508 | ||
36df8979 | 509 | #define OVERLAP_BASE 10000 |
510 | ||
511 | /* Compare the static estimated profile to the actual profile, and | |
512 | return the "degree of overlap" measure between them. | |
513 | ||
514 | Degree of overlap is a number between 0 and OVERLAP_BASE. It is | |
515 | the sum of each basic block's minimum relative weights between | |
516 | two profiles. And overlap of OVERLAP_BASE means two profiles are | |
517 | identical. */ | |
518 | ||
519 | static int | |
520 | compute_frequency_overlap (void) | |
521 | { | |
522 | gcov_type count_total = 0, freq_total = 0; | |
523 | int overlap = 0; | |
524 | basic_block bb; | |
525 | ||
34154e27 | 526 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
36df8979 | 527 | { |
528 | count_total += bb->count; | |
529 | freq_total += bb->frequency; | |
530 | } | |
531 | ||
532 | if (count_total == 0 || freq_total == 0) | |
533 | return 0; | |
534 | ||
34154e27 | 535 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
36df8979 | 536 | overlap += MIN (bb->count * OVERLAP_BASE / count_total, |
537 | bb->frequency * OVERLAP_BASE / freq_total); | |
538 | ||
539 | return overlap; | |
540 | } | |
541 | ||
e0dc6f2b | 542 | /* Compute the branch probabilities for the various branches. |
06306fd3 | 543 | Annotate them accordingly. |
544 | ||
545 | CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
e0dc6f2b | 546 | |
547 | static void | |
06306fd3 | 548 | compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum) |
e0dc6f2b | 549 | { |
550 | basic_block bb; | |
551 | int i; | |
552 | int num_edges = 0; | |
553 | int changes; | |
554 | int passes; | |
555 | int hist_br_prob[20]; | |
e0dc6f2b | 556 | int num_branches; |
06306fd3 | 557 | gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum); |
e0dc6f2b | 558 | int inconsistent = 0; |
559 | ||
560 | /* Very simple sanity checks so we catch bugs in our profiling code. */ | |
d72cadac | 561 | if (!profile_info) |
562 | return; | |
e0dc6f2b | 563 | |
d72cadac | 564 | if (profile_info->sum_all < profile_info->sum_max) |
565 | { | |
566 | error ("corrupted profile info: sum_all is smaller than sum_max"); | |
567 | exec_counts = NULL; | |
e0dc6f2b | 568 | } |
569 | ||
570 | /* Attach extra info block to each bb. */ | |
1ada9901 | 571 | alloc_aux_for_blocks (sizeof (struct bb_profile_info)); |
34154e27 | 572 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
e0dc6f2b | 573 | { |
574 | edge e; | |
575 | edge_iterator ei; | |
576 | ||
577 | FOR_EACH_EDGE (e, ei, bb->succs) | |
578 | if (!EDGE_INFO (e)->ignore) | |
579 | BB_INFO (bb)->succ_count++; | |
580 | FOR_EACH_EDGE (e, ei, bb->preds) | |
581 | if (!EDGE_INFO (e)->ignore) | |
582 | BB_INFO (bb)->pred_count++; | |
583 | } | |
584 | ||
585 | /* Avoid predicting entry on exit nodes. */ | |
34154e27 | 586 | BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2; |
587 | BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2; | |
e0dc6f2b | 588 | |
589 | num_edges = read_profile_edge_counts (exec_counts); | |
590 | ||
450d042a | 591 | if (dump_file) |
592 | fprintf (dump_file, "\n%d edge counts read\n", num_edges); | |
b9cf3f63 | 593 | |
594 | /* For every block in the file, | |
86d4af74 | 595 | - if every exit/entrance edge has a known count, then set the block count |
596 | - if the block count is known, and every exit/entrance edge but one has | |
597 | a known execution count, then set the count of the remaining edge | |
b9cf3f63 | 598 | |
86d4af74 | 599 | As edge counts are set, decrement the succ/pred count, but don't delete |
600 | the edge, that way we can easily tell when all edges are known, or only | |
601 | one edge is unknown. */ | |
b9cf3f63 | 602 | |
603 | /* The order that the basic blocks are iterated through is important. | |
604 | Since the code that finds spanning trees starts with block 0, low numbered | |
86d4af74 | 605 | edges are put on the spanning tree in preference to high numbered edges. |
606 | Hence, most instrumented edges are at the end. Graph solving works much | |
b9cf3f63 | 607 | faster if we propagate numbers from the end to the start. |
86d4af74 | 608 | |
b9cf3f63 | 609 | This takes an average of slightly more than 3 passes. */ |
610 | ||
611 | changes = 1; | |
612 | passes = 0; | |
613 | while (changes) | |
614 | { | |
615 | passes++; | |
616 | changes = 0; | |
34154e27 | 617 | FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb) |
b9cf3f63 | 618 | { |
1ada9901 | 619 | struct bb_profile_info *bi = BB_INFO (bb); |
86d4af74 | 620 | if (! bi->count_valid) |
b9cf3f63 | 621 | { |
86d4af74 | 622 | if (bi->succ_count == 0) |
b9cf3f63 | 623 | { |
86d4af74 | 624 | edge e; |
cd665a06 | 625 | edge_iterator ei; |
63f23608 | 626 | gcov_type total = 0; |
86d4af74 | 627 | |
cd665a06 | 628 | FOR_EACH_EDGE (e, ei, bb->succs) |
86d4af74 | 629 | total += e->count; |
630 | bb->count = total; | |
631 | bi->count_valid = 1; | |
b9cf3f63 | 632 | changes = 1; |
633 | } | |
86d4af74 | 634 | else if (bi->pred_count == 0) |
b9cf3f63 | 635 | { |
86d4af74 | 636 | edge e; |
cd665a06 | 637 | edge_iterator ei; |
63f23608 | 638 | gcov_type total = 0; |
86d4af74 | 639 | |
cd665a06 | 640 | FOR_EACH_EDGE (e, ei, bb->preds) |
86d4af74 | 641 | total += e->count; |
642 | bb->count = total; | |
643 | bi->count_valid = 1; | |
b9cf3f63 | 644 | changes = 1; |
645 | } | |
646 | } | |
86d4af74 | 647 | if (bi->count_valid) |
b9cf3f63 | 648 | { |
86d4af74 | 649 | if (bi->succ_count == 1) |
b9cf3f63 | 650 | { |
86d4af74 | 651 | edge e; |
cd665a06 | 652 | edge_iterator ei; |
63f23608 | 653 | gcov_type total = 0; |
86d4af74 | 654 | |
b9cf3f63 | 655 | /* One of the counts will be invalid, but it is zero, |
656 | so adding it in also doesn't hurt. */ | |
cd665a06 | 657 | FOR_EACH_EDGE (e, ei, bb->succs) |
86d4af74 | 658 | total += e->count; |
659 | ||
f0b5f617 | 660 | /* Search for the invalid edge, and set its count. */ |
cd665a06 | 661 | FOR_EACH_EDGE (e, ei, bb->succs) |
86d4af74 | 662 | if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) |
b9cf3f63 | 663 | break; |
86d4af74 | 664 | |
665 | /* Calculate count for remaining edge by conservation. */ | |
666 | total = bb->count - total; | |
667 | ||
876760f6 | 668 | gcc_assert (e); |
86d4af74 | 669 | EDGE_INFO (e)->count_valid = 1; |
670 | e->count = total; | |
671 | bi->succ_count--; | |
447f6a7f | 672 | |
86d4af74 | 673 | BB_INFO (e->dest)->pred_count--; |
b9cf3f63 | 674 | changes = 1; |
675 | } | |
86d4af74 | 676 | if (bi->pred_count == 1) |
b9cf3f63 | 677 | { |
86d4af74 | 678 | edge e; |
cd665a06 | 679 | edge_iterator ei; |
63f23608 | 680 | gcov_type total = 0; |
86d4af74 | 681 | |
b9cf3f63 | 682 | /* One of the counts will be invalid, but it is zero, |
683 | so adding it in also doesn't hurt. */ | |
cd665a06 | 684 | FOR_EACH_EDGE (e, ei, bb->preds) |
86d4af74 | 685 | total += e->count; |
686 | ||
015af757 | 687 | /* Search for the invalid edge, and set its count. */ |
cd665a06 | 688 | FOR_EACH_EDGE (e, ei, bb->preds) |
015af757 | 689 | if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) |
b9cf3f63 | 690 | break; |
86d4af74 | 691 | |
692 | /* Calculate count for remaining edge by conservation. */ | |
693 | total = bb->count - total + e->count; | |
694 | ||
876760f6 | 695 | gcc_assert (e); |
86d4af74 | 696 | EDGE_INFO (e)->count_valid = 1; |
697 | e->count = total; | |
698 | bi->pred_count--; | |
447f6a7f | 699 | |
86d4af74 | 700 | BB_INFO (e->src)->succ_count--; |
b9cf3f63 | 701 | changes = 1; |
702 | } | |
703 | } | |
704 | } | |
705 | } | |
450d042a | 706 | if (dump_file) |
36df8979 | 707 | { |
708 | int overlap = compute_frequency_overlap (); | |
4a020a8c | 709 | gimple_dump_cfg (dump_file, dump_flags); |
36df8979 | 710 | fprintf (dump_file, "Static profile overlap: %d.%d%%\n", |
711 | overlap / (OVERLAP_BASE / 100), | |
712 | overlap % (OVERLAP_BASE / 100)); | |
713 | } | |
b9cf3f63 | 714 | |
715 | total_num_passes += passes; | |
450d042a | 716 | if (dump_file) |
717 | fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); | |
b9cf3f63 | 718 | |
719 | /* If the graph has been correctly solved, every block will have a | |
720 | succ and pred count of zero. */ | |
fc00614f | 721 | FOR_EACH_BB_FN (bb, cfun) |
b9cf3f63 | 722 | { |
876760f6 | 723 | gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); |
b9cf3f63 | 724 | } |
2045cdd4 | 725 | |
e0dc6f2b | 726 | /* Check for inconsistent basic block counts */ |
727 | inconsistent = is_inconsistent (); | |
728 | ||
729 | if (inconsistent) | |
730 | { | |
731 | if (flag_profile_correction) | |
732 | { | |
733 | /* Inconsistency detected. Make it flow-consistent. */ | |
734 | static int informed = 0; | |
202c2bd9 | 735 | if (dump_enabled_p () && informed == 0) |
e0dc6f2b | 736 | { |
737 | informed = 1; | |
202c2bd9 | 738 | dump_printf_loc (MSG_NOTE, input_location, |
78bb46f5 | 739 | "correcting inconsistent profile data\n"); |
e0dc6f2b | 740 | } |
741 | correct_negative_edge_counts (); | |
742 | /* Set bb counts to the sum of the outgoing edge counts */ | |
743 | set_bb_counts (); | |
744 | if (dump_file) | |
745 | fprintf (dump_file, "\nCalling mcf_smooth_cfg\n"); | |
746 | mcf_smooth_cfg (); | |
747 | } | |
748 | else | |
749 | error ("corrupted profile info: profile data is not flow-consistent"); | |
750 | } | |
751 | ||
86d4af74 | 752 | /* For every edge, calculate its branch probability and add a reg_note |
b9cf3f63 | 753 | to the branch insn to indicate this. */ |
2045cdd4 | 754 | |
b9cf3f63 | 755 | for (i = 0; i < 20; i++) |
756 | hist_br_prob[i] = 0; | |
b9cf3f63 | 757 | num_branches = 0; |
758 | ||
34154e27 | 759 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
b9cf3f63 | 760 | { |
86d4af74 | 761 | edge e; |
cd665a06 | 762 | edge_iterator ei; |
86d4af74 | 763 | |
d9b3752c | 764 | if (bb->count < 0) |
eb429644 | 765 | { |
d9b3752c | 766 | error ("corrupted profile info: number of iterations for basic block %d thought to be %i", |
767 | bb->index, (int)bb->count); | |
768 | bb->count = 0; | |
769 | } | |
cd665a06 | 770 | FOR_EACH_EDGE (e, ei, bb->succs) |
d9b3752c | 771 | { |
c7bf1374 | 772 | /* Function may return twice in the cased the called function is |
d9b3752c | 773 | setjmp or calls fork, but we can't represent this by extra |
774 | edge from the entry, since extra edge from the exit is | |
775 | already present. We get negative frequency from the entry | |
776 | point. */ | |
777 | if ((e->count < 0 | |
34154e27 | 778 | && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
d9b3752c | 779 | || (e->count > bb->count |
34154e27 | 780 | && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))) |
d9b3752c | 781 | { |
4ee9c684 | 782 | if (block_ends_with_call_p (bb)) |
d9b3752c | 783 | e->count = e->count < 0 ? 0 : bb->count; |
784 | } | |
785 | if (e->count < 0 || e->count > bb->count) | |
eb429644 | 786 | { |
d9b3752c | 787 | error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", |
788 | e->src->index, e->dest->index, | |
789 | (int)e->count); | |
790 | e->count = bb->count / 2; | |
ad73c2a0 | 791 | } |
d9b3752c | 792 | } |
793 | if (bb->count) | |
794 | { | |
cd665a06 | 795 | FOR_EACH_EDGE (e, ei, bb->succs) |
f9d4b7f4 | 796 | e->probability = GCOV_COMPUTE_SCALE (e->count, bb->count); |
4d2e5d52 | 797 | if (bb->index >= NUM_FIXED_BLOCKS |
4ee9c684 | 798 | && block_ends_with_condjump_p (bb) |
cd665a06 | 799 | && EDGE_COUNT (bb->succs) >= 2) |
ad73c2a0 | 800 | { |
801 | int prob; | |
802 | edge e; | |
eb429644 | 803 | int index; |
804 | ||
805 | /* Find the branch edge. It is possible that we do have fake | |
806 | edges here. */ | |
cd665a06 | 807 | FOR_EACH_EDGE (e, ei, bb->succs) |
808 | if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) | |
809 | break; | |
eb429644 | 810 | |
811 | prob = e->probability; | |
812 | index = prob * 20 / REG_BR_PROB_BASE; | |
447f6a7f | 813 | |
eb429644 | 814 | if (index == 20) |
815 | index = 19; | |
816 | hist_br_prob[index]++; | |
817 | ||
ad73c2a0 | 818 | num_branches++; |
b9cf3f63 | 819 | } |
ad73c2a0 | 820 | } |
223fd470 | 821 | /* As a last resort, distribute the probabilities evenly. |
060813d5 | 822 | Use simple heuristics that if there are normal edges, |
805e22b2 | 823 | give all abnormals frequency of 0, otherwise distribute the |
824 | frequency over abnormals (this is the case of noreturn | |
825 | calls). */ | |
f26d8580 | 826 | else if (profile_status_for_fn (cfun) == PROFILE_ABSENT) |
ad73c2a0 | 827 | { |
d9b3752c | 828 | int total = 0; |
829 | ||
cd665a06 | 830 | FOR_EACH_EDGE (e, ei, bb->succs) |
ad73c2a0 | 831 | if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) |
832 | total ++; | |
833 | if (total) | |
834 | { | |
cd665a06 | 835 | FOR_EACH_EDGE (e, ei, bb->succs) |
ad73c2a0 | 836 | if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) |
837 | e->probability = REG_BR_PROB_BASE / total; | |
838 | else | |
839 | e->probability = 0; | |
840 | } | |
841 | else | |
842 | { | |
cd665a06 | 843 | total += EDGE_COUNT (bb->succs); |
844 | FOR_EACH_EDGE (e, ei, bb->succs) | |
ad73c2a0 | 845 | e->probability = REG_BR_PROB_BASE / total; |
846 | } | |
4d2e5d52 | 847 | if (bb->index >= NUM_FIXED_BLOCKS |
4ee9c684 | 848 | && block_ends_with_condjump_p (bb) |
cd665a06 | 849 | && EDGE_COUNT (bb->succs) >= 2) |
c5bafa96 | 850 | num_branches++; |
b9cf3f63 | 851 | } |
b9cf3f63 | 852 | } |
ffedd254 | 853 | counts_to_freqs (); |
f26d8580 | 854 | profile_status_for_fn (cfun) = PROFILE_READ; |
a648ea35 | 855 | compute_function_frequency (); |
b9cf3f63 | 856 | |
450d042a | 857 | if (dump_file) |
b9cf3f63 | 858 | { |
450d042a | 859 | fprintf (dump_file, "%d branches\n", num_branches); |
b9cf3f63 | 860 | if (num_branches) |
861 | for (i = 0; i < 10; i++) | |
450d042a | 862 | fprintf (dump_file, "%d%% branches in range %d-%d%%\n", |
86d4af74 | 863 | (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, |
864 | 5 * i, 5 * i + 5); | |
b9cf3f63 | 865 | |
866 | total_num_branches += num_branches; | |
b9cf3f63 | 867 | for (i = 0; i < 20; i++) |
868 | total_hist_br_prob[i] += hist_br_prob[i]; | |
86d4af74 | 869 | |
450d042a | 870 | fputc ('\n', dump_file); |
871 | fputc ('\n', dump_file); | |
b9cf3f63 | 872 | } |
86d4af74 | 873 | |
b36d64df | 874 | free_aux_for_blocks (); |
90c2be44 | 875 | } |
876 | ||
8a5df2ce | 877 | /* Load value histograms values whose description is stored in VALUES array |
06306fd3 | 878 | from .gcda file. |
879 | ||
880 | CFG_CHECKSUM is the precomputed checksum for the CFG. */ | |
8a5df2ce | 881 | |
cf40db41 | 882 | static void |
06306fd3 | 883 | compute_value_histograms (histogram_values values, unsigned cfg_checksum, |
884 | unsigned lineno_checksum) | |
cf40db41 | 885 | { |
886 | unsigned i, j, t, any; | |
887 | unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; | |
888 | gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; | |
889 | gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; | |
890 | gcov_type *aact_count; | |
38fe12e3 | 891 | struct cgraph_node *node; |
48e1416a | 892 | |
cf40db41 | 893 | for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) |
894 | n_histogram_counters[t] = 0; | |
895 | ||
f1f41a6c | 896 | for (i = 0; i < values.length (); i++) |
8a5df2ce | 897 | { |
f1f41a6c | 898 | histogram_value hist = values[i]; |
8a5df2ce | 899 | n_histogram_counters[(int) hist->type] += hist->n_counters; |
900 | } | |
cf40db41 | 901 | |
902 | any = 0; | |
903 | for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
904 | { | |
72bb94b7 | 905 | if (!n_histogram_counters[t]) |
906 | { | |
907 | histogram_counts[t] = NULL; | |
908 | continue; | |
909 | } | |
910 | ||
cf40db41 | 911 | histogram_counts[t] = |
912 | get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), | |
06306fd3 | 913 | n_histogram_counters[t], cfg_checksum, |
914 | lineno_checksum, NULL); | |
cf40db41 | 915 | if (histogram_counts[t]) |
916 | any = 1; | |
917 | act_count[t] = histogram_counts[t]; | |
918 | } | |
919 | if (!any) | |
920 | return; | |
921 | ||
f1f41a6c | 922 | for (i = 0; i < values.length (); i++) |
cf40db41 | 923 | { |
f1f41a6c | 924 | histogram_value hist = values[i]; |
75a70cf9 | 925 | gimple stmt = hist->hvalue.stmt; |
8a5df2ce | 926 | |
8a5df2ce | 927 | t = (int) hist->type; |
cf40db41 | 928 | |
d2971487 | 929 | aact_count = act_count[t]; |
38fe12e3 | 930 | |
2084f25d | 931 | if (act_count[t]) |
932 | act_count[t] += hist->n_counters; | |
d2971487 | 933 | |
4992f399 | 934 | gimple_add_histogram_value (cfun, stmt, hist); |
4c36ffe6 | 935 | hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); |
ed4294da | 936 | for (j = 0; j < hist->n_counters; j++) |
d4974b91 | 937 | if (aact_count) |
38fe12e3 | 938 | hist->hvalue.counters[j] = aact_count[j]; |
939 | else | |
940 | hist->hvalue.counters[j] = 0; | |
941 | ||
942 | /* Time profiler counter is not related to any statement, | |
943 | so that we have to read the counter and set the value to | |
944 | the corresponding call graph node. */ | |
945 | if (hist->type == HIST_TYPE_TIME_PROFILE) | |
946 | { | |
415d1b9a | 947 | node = cgraph_node::get (hist->fun->decl); |
948 | node->tp_first_run = hist->hvalue.counters[0]; | |
38fe12e3 | 949 | |
950 | if (dump_file) | |
951 | fprintf (dump_file, "Read tp_first_run: %d\n", node->tp_first_run); | |
952 | } | |
cf40db41 | 953 | } |
954 | ||
955 | for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) | |
dd045aee | 956 | free (histogram_counts[t]); |
cf40db41 | 957 | } |
958 | ||
839b6556 | 959 | /* When passed NULL as file_name, initialize. |
9ee236f3 | 960 | When passed something else, output the necessary commands to change |
839b6556 | 961 | line to LINE and offset to FILE_NAME. */ |
962 | static void | |
963 | output_location (char const *file_name, int line, | |
964 | gcov_position_t *offset, basic_block bb) | |
965 | { | |
966 | static char const *prev_file_name; | |
967 | static int prev_line; | |
968 | bool name_differs, line_differs; | |
969 | ||
970 | if (!file_name) | |
971 | { | |
972 | prev_file_name = NULL; | |
973 | prev_line = -1; | |
974 | return; | |
975 | } | |
976 | ||
82715bcd | 977 | name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name); |
839b6556 | 978 | line_differs = prev_line != line; |
979 | ||
980 | if (name_differs || line_differs) | |
981 | { | |
982 | if (!*offset) | |
983 | { | |
984 | *offset = gcov_write_tag (GCOV_TAG_LINES); | |
3e7f455b | 985 | gcov_write_unsigned (bb->index); |
839b6556 | 986 | name_differs = line_differs=true; |
987 | } | |
988 | ||
989 | /* If this is a new source file, then output the | |
990 | file's name to the .bb file. */ | |
991 | if (name_differs) | |
992 | { | |
993 | prev_file_name = file_name; | |
994 | gcov_write_unsigned (0); | |
995 | gcov_write_string (prev_file_name); | |
996 | } | |
997 | if (line_differs) | |
998 | { | |
999 | gcov_write_unsigned (line); | |
1000 | prev_line = line; | |
1001 | } | |
1002 | } | |
1003 | } | |
1004 | ||
3e7f455b | 1005 | /* Instrument and/or analyze program behavior based on program the CFG. |
1006 | ||
1007 | This function creates a representation of the control flow graph (of | |
1008 | the function being compiled) that is suitable for the instrumentation | |
1009 | of edges and/or converting measured edge counts to counts on the | |
1010 | complete CFG. | |
10f2b886 | 1011 | |
86d4af74 | 1012 | When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in |
10f2b886 | 1013 | the flow graph that are needed to reconstruct the dynamic behavior of the |
3e7f455b | 1014 | flow graph. This data is written to the gcno file for gcov. |
10f2b886 | 1015 | |
ad87de1e | 1016 | When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary |
3e7f455b | 1017 | information from the gcda file containing edge count information from |
1018 | previous executions of the function being compiled. In this case, the | |
1019 | control flow graph is annotated with actual execution counts by | |
1020 | compute_branch_probabilities(). | |
10f2b886 | 1021 | |
1022 | Main entry point of this file. */ | |
1023 | ||
1024 | void | |
3ad4992f | 1025 | branch_prob (void) |
10f2b886 | 1026 | { |
4c26117a | 1027 | basic_block bb; |
77a89ce1 | 1028 | unsigned i; |
1029 | unsigned num_edges, ignored_edges; | |
015af757 | 1030 | unsigned num_instrumented; |
86d4af74 | 1031 | struct edge_list *el; |
9af5ce0c | 1032 | histogram_values values = histogram_values (); |
06306fd3 | 1033 | unsigned cfg_checksum, lineno_checksum; |
195731ad | 1034 | |
10f2b886 | 1035 | total_num_times_called++; |
1036 | ||
2f0bfe72 | 1037 | flow_call_edges_add (NULL); |
ba126de4 | 1038 | add_noreturn_fake_exit_edges (); |
2f0bfe72 | 1039 | |
86d4af74 | 1040 | /* We can't handle cyclic regions constructed using abnormal edges. |
1041 | To avoid these we replace every source of abnormal edge by a fake | |
1042 | edge from entry node and every destination by fake edge to exit. | |
1043 | This keeps graph acyclic and our calculation exact for all normal | |
1044 | edges except for exit and entrance ones. | |
447f6a7f | 1045 | |
86d4af74 | 1046 | We also add fake exit edges for each call and asm statement in the |
1047 | basic, since it may not return. */ | |
10f2b886 | 1048 | |
fc00614f | 1049 | FOR_EACH_BB_FN (bb, cfun) |
86d4af74 | 1050 | { |
86d4af74 | 1051 | int need_exit_edge = 0, need_entry_edge = 0; |
1052 | int have_exit_edge = 0, have_entry_edge = 0; | |
86d4af74 | 1053 | edge e; |
cd665a06 | 1054 | edge_iterator ei; |
10f2b886 | 1055 | |
d9b3752c | 1056 | /* Functions returning multiple times are not handled by extra edges. |
1057 | Instead we simply allow negative counts on edges from exit to the | |
1058 | block past call and corresponding probabilities. We can't go | |
1059 | with the extra edges because that would result in flowgraph that | |
1060 | needs to have fake edges outside the spanning tree. */ | |
9239aee6 | 1061 | |
cd665a06 | 1062 | FOR_EACH_EDGE (e, ei, bb->succs) |
86d4af74 | 1063 | { |
75a70cf9 | 1064 | gimple_stmt_iterator gsi; |
1065 | gimple last = NULL; | |
868a69da | 1066 | |
1067 | /* It may happen that there are compiler generated statements | |
1068 | without a locus at all. Go through the basic block from the | |
1069 | last to the first statement looking for a locus. */ | |
b716dab0 | 1070 | for (gsi = gsi_last_nondebug_bb (bb); |
1071 | !gsi_end_p (gsi); | |
1072 | gsi_prev_nondebug (&gsi)) | |
868a69da | 1073 | { |
75a70cf9 | 1074 | last = gsi_stmt (gsi); |
b716dab0 | 1075 | if (gimple_has_location (last)) |
868a69da | 1076 | break; |
1077 | } | |
1078 | ||
b5f162df | 1079 | /* Edge with goto locus might get wrong coverage info unless |
48e1416a | 1080 | it is the only edge out of BB. |
1081 | Don't do that when the locuses match, so | |
b5f162df | 1082 | if (blah) goto something; |
1083 | is not computed twice. */ | |
75a70cf9 | 1084 | if (last |
1085 | && gimple_has_location (last) | |
8e7408e3 | 1086 | && LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION |
868a69da | 1087 | && !single_succ_p (bb) |
b5f162df | 1088 | && (LOCATION_FILE (e->goto_locus) |
75a70cf9 | 1089 | != LOCATION_FILE (gimple_location (last)) |
b5f162df | 1090 | || (LOCATION_LINE (e->goto_locus) |
9c388755 | 1091 | != LOCATION_LINE (gimple_location (last))))) |
b5f162df | 1092 | { |
f4e36c33 | 1093 | basic_block new_bb = split_edge (e); |
9c388755 | 1094 | edge ne = single_succ_edge (new_bb); |
1095 | ne->goto_locus = e->goto_locus; | |
b5f162df | 1096 | } |
86d4af74 | 1097 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) |
34154e27 | 1098 | && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) |
86d4af74 | 1099 | need_exit_edge = 1; |
34154e27 | 1100 | if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
86d4af74 | 1101 | have_exit_edge = 1; |
1102 | } | |
cd665a06 | 1103 | FOR_EACH_EDGE (e, ei, bb->preds) |
86d4af74 | 1104 | { |
1105 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
34154e27 | 1106 | && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
86d4af74 | 1107 | need_entry_edge = 1; |
34154e27 | 1108 | if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
86d4af74 | 1109 | have_entry_edge = 1; |
1110 | } | |
10f2b886 | 1111 | |
86d4af74 | 1112 | if (need_exit_edge && !have_exit_edge) |
1113 | { | |
450d042a | 1114 | if (dump_file) |
1115 | fprintf (dump_file, "Adding fake exit edge to bb %i\n", | |
b3d6de89 | 1116 | bb->index); |
34154e27 | 1117 | make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); |
86d4af74 | 1118 | } |
1119 | if (need_entry_edge && !have_entry_edge) | |
1120 | { | |
450d042a | 1121 | if (dump_file) |
1122 | fprintf (dump_file, "Adding fake entry edge to bb %i\n", | |
b3d6de89 | 1123 | bb->index); |
34154e27 | 1124 | make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE); |
180c5ea0 | 1125 | /* Avoid bbs that have both fake entry edge and also some |
1126 | exit edge. One of those edges wouldn't be added to the | |
1127 | spanning tree, but we can't instrument any of them. */ | |
1128 | if (have_exit_edge || need_exit_edge) | |
1129 | { | |
1130 | gimple_stmt_iterator gsi; | |
1131 | gimple first; | |
180c5ea0 | 1132 | |
b2c0e0b7 | 1133 | gsi = gsi_start_nondebug_after_labels_bb (bb); |
180c5ea0 | 1134 | gcc_checking_assert (!gsi_end_p (gsi)); |
1135 | first = gsi_stmt (gsi); | |
180c5ea0 | 1136 | /* Don't split the bbs containing __builtin_setjmp_receiver |
b2c0e0b7 | 1137 | or ABNORMAL_DISPATCHER calls. These are very |
180c5ea0 | 1138 | special and don't expect anything to be inserted before |
1139 | them. */ | |
bb268663 | 1140 | if (is_gimple_call (first) |
b8e66853 | 1141 | && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER) |
b2c0e0b7 | 1142 | || (gimple_call_flags (first) & ECF_RETURNS_TWICE) |
1143 | || (gimple_call_internal_p (first) | |
1144 | && (gimple_call_internal_fn (first) | |
1145 | == IFN_ABNORMAL_DISPATCHER)))) | |
bb268663 | 1146 | continue; |
1147 | ||
1148 | if (dump_file) | |
1149 | fprintf (dump_file, "Splitting bb %i after labels\n", | |
1150 | bb->index); | |
1151 | split_block_after_labels (bb); | |
180c5ea0 | 1152 | } |
86d4af74 | 1153 | } |
1154 | } | |
10f2b886 | 1155 | |
86d4af74 | 1156 | el = create_edge_list (); |
1157 | num_edges = NUM_EDGES (el); | |
1ada9901 | 1158 | alloc_aux_for_edges (sizeof (struct edge_profile_info)); |
10f2b886 | 1159 | |
3c0a32c9 | 1160 | /* The basic blocks are expected to be numbered sequentially. */ |
1161 | compact_blocks (); | |
1162 | ||
84870dc8 | 1163 | ignored_edges = 0; |
86d4af74 | 1164 | for (i = 0 ; i < num_edges ; i++) |
1165 | { | |
1166 | edge e = INDEX_EDGE (el, i); | |
1167 | e->count = 0; | |
86d4af74 | 1168 | |
1169 | /* Mark edges we've replaced by fake edges above as ignored. */ | |
1170 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
34154e27 | 1171 | && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
1172 | && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
195731ad | 1173 | { |
84870dc8 | 1174 | EDGE_INFO (e)->ignore = 1; |
1175 | ignored_edges++; | |
195731ad | 1176 | } |
86d4af74 | 1177 | } |
10f2b886 | 1178 | |
86d4af74 | 1179 | /* Create spanning tree from basic block graph, mark each edge that is |
1180 | on the spanning tree. We insert as many abnormal and critical edges | |
dd5b4b36 | 1181 | as possible to minimize number of edge splits necessary. */ |
10f2b886 | 1182 | |
86d4af74 | 1183 | find_spanning_tree (el); |
3ad4992f | 1184 | |
84870dc8 | 1185 | /* Fake edges that are not on the tree will not be instrumented, so |
aa40f561 | 1186 | mark them ignored. */ |
015af757 | 1187 | for (num_instrumented = i = 0; i < num_edges; i++) |
84870dc8 | 1188 | { |
1189 | edge e = INDEX_EDGE (el, i); | |
1ada9901 | 1190 | struct edge_profile_info *inf = EDGE_INFO (e); |
015af757 | 1191 | |
1192 | if (inf->ignore || inf->on_tree) | |
1193 | /*NOP*/; | |
1194 | else if (e->flags & EDGE_FAKE) | |
195731ad | 1195 | { |
1196 | inf->ignore = 1; | |
1197 | ignored_edges++; | |
1198 | } | |
015af757 | 1199 | else |
1200 | num_instrumented++; | |
84870dc8 | 1201 | } |
1202 | ||
a28770e1 | 1203 | total_num_blocks += n_basic_blocks_for_fn (cfun); |
450d042a | 1204 | if (dump_file) |
a28770e1 | 1205 | fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun)); |
84870dc8 | 1206 | |
1207 | total_num_edges += num_edges; | |
450d042a | 1208 | if (dump_file) |
1209 | fprintf (dump_file, "%d edges\n", num_edges); | |
84870dc8 | 1210 | |
1211 | total_num_edges_ignored += ignored_edges; | |
450d042a | 1212 | if (dump_file) |
1213 | fprintf (dump_file, "%d ignored edges\n", ignored_edges); | |
84870dc8 | 1214 | |
2ba3016c | 1215 | total_num_edges_instrumented += num_instrumented; |
1216 | if (dump_file) | |
1217 | fprintf (dump_file, "%d instrumentation edges\n", num_instrumented); | |
06306fd3 | 1218 | |
1219 | /* Compute two different checksums. Note that we want to compute | |
1220 | the checksum in only once place, since it depends on the shape | |
1221 | of the control flow which can change during | |
1222 | various transformations. */ | |
a06672d4 | 1223 | cfg_checksum = coverage_compute_cfg_checksum (cfun); |
06306fd3 | 1224 | lineno_checksum = coverage_compute_lineno_checksum (); |
1225 | ||
834f169c | 1226 | /* Write the data from which gcov can reconstruct the basic block |
3e7f455b | 1227 | graph and function line numbers (the gcno file). */ |
6c56d3c9 | 1228 | if (coverage_begin_function (lineno_checksum, cfg_checksum)) |
10f2b886 | 1229 | { |
834f169c | 1230 | gcov_position_t offset; |
3ad4992f | 1231 | |
6c56d3c9 | 1232 | /* Basic block flags */ |
f187042d | 1233 | offset = gcov_write_tag (GCOV_TAG_BLOCKS); |
a28770e1 | 1234 | for (i = 0; i != (unsigned) (n_basic_blocks_for_fn (cfun)); i++) |
f187042d | 1235 | gcov_write_unsigned (0); |
1236 | gcov_write_length (offset); | |
3ad4992f | 1237 | |
6c56d3c9 | 1238 | /* Arcs */ |
34154e27 | 1239 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
1240 | EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
b9cf3f63 | 1241 | { |
86d4af74 | 1242 | edge e; |
cd665a06 | 1243 | edge_iterator ei; |
86d4af74 | 1244 | |
f187042d | 1245 | offset = gcov_write_tag (GCOV_TAG_ARCS); |
3e7f455b | 1246 | gcov_write_unsigned (bb->index); |
3ad4992f | 1247 | |
cd665a06 | 1248 | FOR_EACH_EDGE (e, ei, bb->succs) |
b9cf3f63 | 1249 | { |
1ada9901 | 1250 | struct edge_profile_info *i = EDGE_INFO (e); |
86d4af74 | 1251 | if (!i->ignore) |
1252 | { | |
805e22b2 | 1253 | unsigned flag_bits = 0; |
3ad4992f | 1254 | |
86d4af74 | 1255 | if (i->on_tree) |
805e22b2 | 1256 | flag_bits |= GCOV_ARC_ON_TREE; |
84870dc8 | 1257 | if (e->flags & EDGE_FAKE) |
805e22b2 | 1258 | flag_bits |= GCOV_ARC_FAKE; |
86d4af74 | 1259 | if (e->flags & EDGE_FALLTHRU) |
805e22b2 | 1260 | flag_bits |= GCOV_ARC_FALLTHROUGH; |
839b6556 | 1261 | /* On trees we don't have fallthru flags, but we can |
1262 | recompute them from CFG shape. */ | |
34806856 | 1263 | if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) |
839b6556 | 1264 | && e->src->next_bb == e->dest) |
1265 | flag_bits |= GCOV_ARC_FALLTHROUGH; | |
86d4af74 | 1266 | |
3e7f455b | 1267 | gcov_write_unsigned (e->dest->index); |
f187042d | 1268 | gcov_write_unsigned (flag_bits); |
86d4af74 | 1269 | } |
10f2b886 | 1270 | } |
77a89ce1 | 1271 | |
f187042d | 1272 | gcov_write_length (offset); |
10f2b886 | 1273 | } |
3ad4992f | 1274 | |
6c56d3c9 | 1275 | /* Line numbers. */ |
839b6556 | 1276 | /* Initialize the output. */ |
1277 | output_location (NULL, 0, NULL, NULL); | |
3ad4992f | 1278 | |
fc00614f | 1279 | FOR_EACH_BB_FN (bb, cfun) |
44359ced | 1280 | { |
75a70cf9 | 1281 | gimple_stmt_iterator gsi; |
b39a37c3 | 1282 | gcov_position_t offset = 0; |
839b6556 | 1283 | |
34154e27 | 1284 | if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) |
34806856 | 1285 | { |
48e1416a | 1286 | expanded_location curr_location = |
34806856 | 1287 | expand_location (DECL_SOURCE_LOCATION (current_function_decl)); |
1288 | output_location (curr_location.file, curr_location.line, | |
1289 | &offset, bb); | |
44359ced | 1290 | } |
3ad4992f | 1291 | |
75a70cf9 | 1292 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
44359ced | 1293 | { |
75a70cf9 | 1294 | gimple stmt = gsi_stmt (gsi); |
1295 | if (gimple_has_location (stmt)) | |
1296 | output_location (gimple_filename (stmt), gimple_lineno (stmt), | |
ad4583d9 | 1297 | &offset, bb); |
34806856 | 1298 | } |
839b6556 | 1299 | |
b39a37c3 | 1300 | /* Notice GOTO expressions eliminated while constructing the CFG. */ |
75a70cf9 | 1301 | if (single_succ_p (bb) |
8e7408e3 | 1302 | && LOCATION_LOCUS (single_succ_edge (bb)->goto_locus) |
1303 | != UNKNOWN_LOCATION) | |
34806856 | 1304 | { |
b39a37c3 | 1305 | expanded_location curr_location |
1306 | = expand_location (single_succ_edge (bb)->goto_locus); | |
1307 | output_location (curr_location.file, curr_location.line, | |
1308 | &offset, bb); | |
34806856 | 1309 | } |
839b6556 | 1310 | |
34806856 | 1311 | if (offset) |
1312 | { | |
1313 | /* A file of NULL indicates the end of run. */ | |
1314 | gcov_write_unsigned (0); | |
1315 | gcov_write_string (NULL); | |
1316 | gcov_write_length (offset); | |
44359ced | 1317 | } |
34806856 | 1318 | } |
10f2b886 | 1319 | } |
4ee9c684 | 1320 | |
0a9d9b9c | 1321 | if (flag_profile_values) |
fc49fbc1 | 1322 | gimple_find_values_to_profile (&values); |
0a9d9b9c | 1323 | |
86d4af74 | 1324 | if (flag_branch_probabilities) |
cf40db41 | 1325 | { |
06306fd3 | 1326 | compute_branch_probabilities (cfg_checksum, lineno_checksum); |
cf40db41 | 1327 | if (flag_profile_values) |
06306fd3 | 1328 | compute_value_histograms (values, cfg_checksum, lineno_checksum); |
cf40db41 | 1329 | } |
86d4af74 | 1330 | |
41d24834 | 1331 | remove_fake_edges (); |
1332 | ||
4ee9c684 | 1333 | /* For each edge not on the spanning tree, add counting code. */ |
015af757 | 1334 | if (profile_arc_flag |
1335 | && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented)) | |
b9cf3f63 | 1336 | { |
4b0a9554 | 1337 | unsigned n_instrumented; |
1338 | ||
fc49fbc1 | 1339 | gimple_init_edge_profiler (); |
4b0a9554 | 1340 | |
1341 | n_instrumented = instrument_edges (el); | |
015af757 | 1342 | |
876760f6 | 1343 | gcc_assert (n_instrumented == num_instrumented); |
77a89ce1 | 1344 | |
0a9d9b9c | 1345 | if (flag_profile_values) |
8a5df2ce | 1346 | instrument_values (values); |
0a9d9b9c | 1347 | |
77a89ce1 | 1348 | /* Commit changes done by instrumentation. */ |
75a70cf9 | 1349 | gsi_commit_edge_inserts (); |
10f2b886 | 1350 | } |
1351 | ||
77a89ce1 | 1352 | free_aux_for_edges (); |
4ee9c684 | 1353 | |
f1f41a6c | 1354 | values.release (); |
86d4af74 | 1355 | free_edge_list (el); |
06306fd3 | 1356 | coverage_end_function (lineno_checksum, cfg_checksum); |
10f2b886 | 1357 | } |
1358 | \f | |
86d4af74 | 1359 | /* Union find algorithm implementation for the basic blocks using |
aa40f561 | 1360 | aux fields. */ |
10f2b886 | 1361 | |
86d4af74 | 1362 | static basic_block |
3ad4992f | 1363 | find_group (basic_block bb) |
10f2b886 | 1364 | { |
86d4af74 | 1365 | basic_block group = bb, bb1; |
10f2b886 | 1366 | |
86d4af74 | 1367 | while ((basic_block) group->aux != group) |
1368 | group = (basic_block) group->aux; | |
10f2b886 | 1369 | |
86d4af74 | 1370 | /* Compress path. */ |
1371 | while ((basic_block) bb->aux != group) | |
10f2b886 | 1372 | { |
86d4af74 | 1373 | bb1 = (basic_block) bb->aux; |
1374 | bb->aux = (void *) group; | |
1375 | bb = bb1; | |
10f2b886 | 1376 | } |
86d4af74 | 1377 | return group; |
1378 | } | |
10f2b886 | 1379 | |
86d4af74 | 1380 | static void |
3ad4992f | 1381 | union_groups (basic_block bb1, basic_block bb2) |
86d4af74 | 1382 | { |
1383 | basic_block bb1g = find_group (bb1); | |
1384 | basic_block bb2g = find_group (bb2); | |
10f2b886 | 1385 | |
86d4af74 | 1386 | /* ??? I don't have a place for the rank field. OK. Lets go w/o it, |
1387 | this code is unlikely going to be performance problem anyway. */ | |
876760f6 | 1388 | gcc_assert (bb1g != bb2g); |
10f2b886 | 1389 | |
86d4af74 | 1390 | bb1g->aux = bb2g; |
10f2b886 | 1391 | } |
86d4af74 | 1392 | \f |
1393 | /* This function searches all of the edges in the program flow graph, and puts | |
1394 | as many bad edges as possible onto the spanning tree. Bad edges include | |
1395 | abnormals edges, which can't be instrumented at the moment. Since it is | |
edc2a478 | 1396 | possible for fake edges to form a cycle, we will have to develop some |
86d4af74 | 1397 | better way in the future. Also put critical edges to the tree, since they |
1398 | are more expensive to instrument. */ | |
10f2b886 | 1399 | |
1400 | static void | |
3ad4992f | 1401 | find_spanning_tree (struct edge_list *el) |
10f2b886 | 1402 | { |
86d4af74 | 1403 | int i; |
1404 | int num_edges = NUM_EDGES (el); | |
4c26117a | 1405 | basic_block bb; |
10f2b886 | 1406 | |
86d4af74 | 1407 | /* We use aux field for standard union-find algorithm. */ |
34154e27 | 1408 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb) |
4c26117a | 1409 | bb->aux = bb; |
10f2b886 | 1410 | |
86d4af74 | 1411 | /* Add fake edge exit to entry we can't instrument. */ |
34154e27 | 1412 | union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
86d4af74 | 1413 | |
edc2a478 | 1414 | /* First add all abnormal edges to the tree unless they form a cycle. Also |
efee62d1 | 1415 | add all edges to the exit block to avoid inserting profiling code behind |
90c2be44 | 1416 | setting return value from function. */ |
86d4af74 | 1417 | for (i = 0; i < num_edges; i++) |
1418 | { | |
1419 | edge e = INDEX_EDGE (el, i); | |
90c2be44 | 1420 | if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) |
34154e27 | 1421 | || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
86d4af74 | 1422 | && !EDGE_INFO (e)->ignore |
1423 | && (find_group (e->src) != find_group (e->dest))) | |
1424 | { | |
450d042a | 1425 | if (dump_file) |
1426 | fprintf (dump_file, "Abnormal edge %d to %d put to tree\n", | |
195731ad | 1427 | e->src->index, e->dest->index); |
86d4af74 | 1428 | EDGE_INFO (e)->on_tree = 1; |
1429 | union_groups (e->src, e->dest); | |
1430 | } | |
1431 | } | |
1432 | ||
edc2a478 | 1433 | /* Now insert all critical edges to the tree unless they form a cycle. */ |
86d4af74 | 1434 | for (i = 0; i < num_edges; i++) |
1435 | { | |
1436 | edge e = INDEX_EDGE (el, i); | |
015af757 | 1437 | if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore |
1438 | && find_group (e->src) != find_group (e->dest)) | |
86d4af74 | 1439 | { |
450d042a | 1440 | if (dump_file) |
1441 | fprintf (dump_file, "Critical edge %d to %d put to tree\n", | |
195731ad | 1442 | e->src->index, e->dest->index); |
86d4af74 | 1443 | EDGE_INFO (e)->on_tree = 1; |
1444 | union_groups (e->src, e->dest); | |
1445 | } | |
1446 | } | |
1447 | ||
1448 | /* And now the rest. */ | |
1449 | for (i = 0; i < num_edges; i++) | |
1450 | { | |
1451 | edge e = INDEX_EDGE (el, i); | |
015af757 | 1452 | if (!EDGE_INFO (e)->ignore |
1453 | && find_group (e->src) != find_group (e->dest)) | |
86d4af74 | 1454 | { |
450d042a | 1455 | if (dump_file) |
1456 | fprintf (dump_file, "Normal edge %d to %d put to tree\n", | |
195731ad | 1457 | e->src->index, e->dest->index); |
86d4af74 | 1458 | EDGE_INFO (e)->on_tree = 1; |
1459 | union_groups (e->src, e->dest); | |
1460 | } | |
1461 | } | |
b36d64df | 1462 | |
3e7f455b | 1463 | clear_aux_for_blocks (); |
10f2b886 | 1464 | } |
1465 | \f | |
1466 | /* Perform file-level initialization for branch-prob processing. */ | |
1467 | ||
1468 | void | |
3ad4992f | 1469 | init_branch_prob (void) |
10f2b886 | 1470 | { |
10f2b886 | 1471 | int i; |
1472 | ||
10f2b886 | 1473 | total_num_blocks = 0; |
86d4af74 | 1474 | total_num_edges = 0; |
84870dc8 | 1475 | total_num_edges_ignored = 0; |
86d4af74 | 1476 | total_num_edges_instrumented = 0; |
10f2b886 | 1477 | total_num_blocks_created = 0; |
1478 | total_num_passes = 0; | |
1479 | total_num_times_called = 0; | |
1480 | total_num_branches = 0; | |
10f2b886 | 1481 | for (i = 0; i < 20; i++) |
1482 | total_hist_br_prob[i] = 0; | |
1483 | } | |
1484 | ||
1485 | /* Performs file-level cleanup after branch-prob processing | |
1486 | is completed. */ | |
1487 | ||
1488 | void | |
3ad4992f | 1489 | end_branch_prob (void) |
10f2b886 | 1490 | { |
450d042a | 1491 | if (dump_file) |
10f2b886 | 1492 | { |
450d042a | 1493 | fprintf (dump_file, "\n"); |
1494 | fprintf (dump_file, "Total number of blocks: %d\n", | |
86d4af74 | 1495 | total_num_blocks); |
450d042a | 1496 | fprintf (dump_file, "Total number of edges: %d\n", total_num_edges); |
1497 | fprintf (dump_file, "Total number of ignored edges: %d\n", | |
84870dc8 | 1498 | total_num_edges_ignored); |
450d042a | 1499 | fprintf (dump_file, "Total number of instrumented edges: %d\n", |
86d4af74 | 1500 | total_num_edges_instrumented); |
450d042a | 1501 | fprintf (dump_file, "Total number of blocks created: %d\n", |
10f2b886 | 1502 | total_num_blocks_created); |
450d042a | 1503 | fprintf (dump_file, "Total number of graph solution passes: %d\n", |
10f2b886 | 1504 | total_num_passes); |
1505 | if (total_num_times_called != 0) | |
450d042a | 1506 | fprintf (dump_file, "Average number of graph solution passes: %d\n", |
10f2b886 | 1507 | (total_num_passes + (total_num_times_called >> 1)) |
1508 | / total_num_times_called); | |
450d042a | 1509 | fprintf (dump_file, "Total number of branches: %d\n", |
86d4af74 | 1510 | total_num_branches); |
10f2b886 | 1511 | if (total_num_branches) |
1512 | { | |
1513 | int i; | |
1514 | ||
1515 | for (i = 0; i < 10; i++) | |
450d042a | 1516 | fprintf (dump_file, "%d%% branches in range %d-%d%%\n", |
10f2b886 | 1517 | (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 |
1518 | / total_num_branches, 5*i, 5*i+5); | |
1519 | } | |
1520 | } | |
1521 | } |