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