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