]>
Commit | Line | Data |
---|---|---|
447f6a7f | 1 | /* Calculate branch probabilities, and basic block execution counts. |
ad565c04 | 2 | Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, |
3 | 2000, 2001 Free Software Foundation, Inc. | |
10f2b886 | 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 | ||
f12b58b3 | 8 | This file is part of GCC. |
10f2b886 | 9 | |
f12b58b3 | 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. | |
10f2b886 | 14 | |
f12b58b3 | 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. | |
10f2b886 | 19 | |
20 | You should have received a copy of the GNU General Public License | |
f12b58b3 | 21 | along with GCC; see the file COPYING. If not, write to the Free |
22 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
23 | 02111-1307, USA. */ | |
10f2b886 | 24 | |
10f2b886 | 25 | /* ??? Register allocation should use basic block execution counts to |
26 | give preference to the most commonly executed blocks. */ | |
27 | ||
28 | /* ??? The .da files are not safe. Changing the program after creating .da | |
29 | files or using different options when compiling with -fbranch-probabilities | |
30 | can result the arc data not matching the program. Maybe add instrumented | |
31 | arc count to .bbg file? Maybe check whether PFG matches the .bbg file? */ | |
32 | ||
33 | /* ??? Should calculate branch probabilities before instrumenting code, since | |
34 | then we can use arc counts to help decide which arcs to instrument. */ | |
35 | ||
10f2b886 | 36 | #include "config.h" |
405711de | 37 | #include "system.h" |
10f2b886 | 38 | #include "rtl.h" |
0a893c29 | 39 | #include "tree.h" |
10f2b886 | 40 | #include "flags.h" |
10f2b886 | 41 | #include "insn-config.h" |
42 | #include "output.h" | |
0dbd1c74 | 43 | #include "regs.h" |
86d4af74 | 44 | #include "expr.h" |
0a893c29 | 45 | #include "function.h" |
12874aaf | 46 | #include "toplev.h" |
521dd524 | 47 | #include "ggc.h" |
d6cb6164 | 48 | #include "hard-reg-set.h" |
86d4af74 | 49 | #include "basic-block.h" |
63f23608 | 50 | #include "gcov-io.h" |
01d15dc5 | 51 | #include "target.h" |
90c2be44 | 52 | #include "profile.h" |
53 | #include "libfuncs.h" | |
20325f61 | 54 | #include "langhooks.h" |
10f2b886 | 55 | |
86d4af74 | 56 | /* Additional information about the edges we need. */ |
57 | struct edge_info | |
58 | { | |
59 | unsigned int count_valid : 1; | |
60 | unsigned int on_tree : 1; | |
61 | unsigned int ignore : 1; | |
62 | }; | |
10f2b886 | 63 | struct bb_info |
86d4af74 | 64 | { |
65 | unsigned int count_valid : 1; | |
63f23608 | 66 | gcov_type succ_count; |
67 | gcov_type pred_count; | |
86d4af74 | 68 | }; |
69 | ||
70 | #define EDGE_INFO(e) ((struct edge_info *) (e)->aux) | |
71 | #define BB_INFO(b) ((struct bb_info *) (b)->aux) | |
72 | ||
73 | /* Keep all basic block indexes nonnegative in the gcov output. Index 0 | |
1e625a2e | 74 | is used for entry block, last block exit block. */ |
86d4af74 | 75 | #define GCOV_INDEX_TO_BB(i) ((i) == 0 ? ENTRY_BLOCK_PTR \ |
f20183e6 | 76 | : (((i) == last_basic_block + 1) \ |
86d4af74 | 77 | ? EXIT_BLOCK_PTR : BASIC_BLOCK ((i)-1))) |
447f6a7f | 78 | #define BB_TO_GCOV_INDEX(bb) ((bb) == ENTRY_BLOCK_PTR ? 0 \ |
79 | : ((bb) == EXIT_BLOCK_PTR \ | |
f20183e6 | 80 | ? last_basic_block + 1 : (bb)->index + 1)) |
10f2b886 | 81 | |
f21e1254 | 82 | /* Instantiate the profile info structure. */ |
83 | ||
84 | struct profile_info profile_info; | |
85 | ||
10f2b886 | 86 | /* Name and file pointer of the output file for the basic block graph. */ |
87 | ||
10f2b886 | 88 | static FILE *bbg_file; |
89 | ||
90 | /* Name and file pointer of the input file for the arc count data. */ | |
91 | ||
10f2b886 | 92 | static FILE *da_file; |
93 | ||
aa40f561 | 94 | /* Pointer of the output file for the basic block/line number map. */ |
10f2b886 | 95 | static FILE *bb_file; |
96 | ||
aa40f561 | 97 | /* Last source file name written to bb_file. */ |
10f2b886 | 98 | |
99 | static char *last_bb_file_name; | |
100 | ||
10f2b886 | 101 | /* Collect statistics on the performance of this pass for the entire source |
102 | file. */ | |
103 | ||
104 | static int total_num_blocks; | |
86d4af74 | 105 | static int total_num_edges; |
84870dc8 | 106 | static int total_num_edges_ignored; |
86d4af74 | 107 | static int total_num_edges_instrumented; |
10f2b886 | 108 | static int total_num_blocks_created; |
109 | static int total_num_passes; | |
110 | static int total_num_times_called; | |
111 | static int total_hist_br_prob[20]; | |
112 | static int total_num_never_executed; | |
113 | static int total_num_branches; | |
114 | ||
115 | /* Forward declarations. */ | |
86d4af74 | 116 | static void find_spanning_tree PARAMS ((struct edge_list *)); |
117 | static void init_edge_profiler PARAMS ((void)); | |
118 | static rtx gen_edge_profiler PARAMS ((int)); | |
119 | static void instrument_edges PARAMS ((struct edge_list *)); | |
c70f7111 | 120 | static void output_gcov_string PARAMS ((const char *, long)); |
86d4af74 | 121 | static void compute_branch_probabilities PARAMS ((void)); |
90c2be44 | 122 | static gcov_type * get_exec_counts PARAMS ((void)); |
123 | static long compute_checksum PARAMS ((void)); | |
86d4af74 | 124 | static basic_block find_group PARAMS ((basic_block)); |
125 | static void union_groups PARAMS ((basic_block, basic_block)); | |
10f2b886 | 126 | |
10f2b886 | 127 | /* If non-zero, we need to output a constructor to set up the |
aa40f561 | 128 | per-object-file data. */ |
10f2b886 | 129 | static int need_func_profiler = 0; |
10f2b886 | 130 | \f |
86d4af74 | 131 | /* Add edge instrumentation code to the entire insn chain. |
10f2b886 | 132 | |
133 | F is the first insn of the chain. | |
86d4af74 | 134 | NUM_BLOCKS is the number of basic blocks found in F. */ |
10f2b886 | 135 | |
136 | static void | |
86d4af74 | 137 | instrument_edges (el) |
138 | struct edge_list *el; | |
10f2b886 | 139 | { |
86d4af74 | 140 | int num_instr_edges = 0; |
141 | int num_edges = NUM_EDGES (el); | |
4c26117a | 142 | basic_block bb; |
86d4af74 | 143 | remove_fake_edges (); |
144 | ||
4c26117a | 145 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
86d4af74 | 146 | { |
86d4af74 | 147 | edge e = bb->succ; |
148 | while (e) | |
10f2b886 | 149 | { |
86d4af74 | 150 | struct edge_info *inf = EDGE_INFO (e); |
151 | if (!inf->ignore && !inf->on_tree) | |
10f2b886 | 152 | { |
86d4af74 | 153 | if (e->flags & EDGE_ABNORMAL) |
10f2b886 | 154 | abort (); |
86d4af74 | 155 | if (rtl_dump_file) |
156 | fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n", | |
b3d6de89 | 157 | e->src->index, e->dest->index, |
e76f35e8 | 158 | EDGE_CRITICAL_P (e) ? " (and split)" : ""); |
86d4af74 | 159 | need_func_profiler = 1; |
160 | insert_insn_on_edge ( | |
161 | gen_edge_profiler (total_num_edges_instrumented | |
162 | + num_instr_edges++), e); | |
10f2b886 | 163 | } |
86d4af74 | 164 | e = e->succ_next; |
10f2b886 | 165 | } |
10f2b886 | 166 | } |
86d4af74 | 167 | |
90c2be44 | 168 | profile_info.count_edges_instrumented_now = num_instr_edges; |
86d4af74 | 169 | total_num_edges_instrumented += num_instr_edges; |
90c2be44 | 170 | profile_info.count_instrumented_edges = total_num_edges_instrumented; |
86d4af74 | 171 | |
172 | total_num_blocks_created += num_edges; | |
173 | if (rtl_dump_file) | |
174 | fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges); | |
175 | ||
fb20d6fa | 176 | commit_edge_insertions_watch_calls (); |
10f2b886 | 177 | } |
178 | ||
179 | /* Output STRING to bb_file, surrounded by DELIMITER. */ | |
180 | ||
181 | static void | |
182 | output_gcov_string (string, delimiter) | |
5b379086 | 183 | const char *string; |
10f2b886 | 184 | long delimiter; |
185 | { | |
186 | long temp; | |
447f6a7f | 187 | |
10f2b886 | 188 | /* Write a delimiter to indicate that a file name follows. */ |
189 | __write_long (delimiter, bb_file, 4); | |
190 | ||
191 | /* Write the string. */ | |
192 | temp = strlen (string) + 1; | |
193 | fwrite (string, temp, 1, bb_file); | |
194 | ||
195 | /* Append a few zeros, to align the output to a 4 byte boundary. */ | |
196 | temp = temp & 0x3; | |
197 | if (temp) | |
198 | { | |
199 | char c[4]; | |
200 | ||
201 | c[0] = c[1] = c[2] = c[3] = 0; | |
202 | fwrite (c, sizeof (char), 4 - temp, bb_file); | |
203 | } | |
204 | ||
86d4af74 | 205 | /* Store another delimiter in the .bb file, just to make it easy to find |
206 | the end of the file name. */ | |
10f2b886 | 207 | __write_long (delimiter, bb_file, 4); |
208 | } | |
209 | \f | |
c3b641a2 | 210 | |
195731ad | 211 | /* Computes hybrid profile for all matching entries in da_file. |
90c2be44 | 212 | Sets max_counter_in_program as a side effect. */ |
213 | ||
214 | static gcov_type * | |
215 | get_exec_counts () | |
216 | { | |
217 | int num_edges = 0; | |
4c26117a | 218 | basic_block bb; |
219 | int okay = 1, i; | |
90c2be44 | 220 | int mismatch = 0; |
221 | gcov_type *profile; | |
222 | char *function_name_buffer; | |
223 | int function_name_buffer_len; | |
224 | gcov_type max_counter_in_run; | |
225 | ||
226 | profile_info.max_counter_in_program = 0; | |
227 | profile_info.count_profiles_merged = 0; | |
228 | ||
229 | /* No .da file, no execution counts. */ | |
230 | if (!da_file) | |
231 | return 0; | |
232 | ||
233 | /* Count the edges to be (possibly) instrumented. */ | |
234 | ||
4c26117a | 235 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
90c2be44 | 236 | { |
90c2be44 | 237 | edge e; |
238 | for (e = bb->succ; e; e = e->succ_next) | |
239 | if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
4c26117a | 240 | num_edges++; |
90c2be44 | 241 | } |
242 | ||
195731ad | 243 | /* now read and combine all matching profiles. */ |
90c2be44 | 244 | |
245 | profile = xmalloc (sizeof (gcov_type) * num_edges); | |
246 | rewind (da_file); | |
247 | function_name_buffer_len = strlen (current_function_name) + 1; | |
248 | function_name_buffer = xmalloc (function_name_buffer_len + 1); | |
249 | ||
b3d6de89 | 250 | for (i = 0; i < num_edges; i++) |
251 | profile[i] = 0; | |
90c2be44 | 252 | |
253 | while (1) | |
254 | { | |
255 | long magic, extra_bytes; | |
256 | long func_count; | |
257 | int i; | |
258 | ||
259 | if (__read_long (&magic, da_file, 4) != 0) | |
260 | break; | |
261 | ||
262 | if (magic != -123) | |
263 | { | |
264 | okay = 0; | |
265 | break; | |
266 | } | |
267 | ||
268 | if (__read_long (&func_count, da_file, 4) != 0) | |
269 | { | |
270 | okay = 0; | |
271 | break; | |
272 | } | |
273 | ||
274 | if (__read_long (&extra_bytes, da_file, 4) != 0) | |
275 | { | |
276 | okay = 0; | |
277 | break; | |
278 | } | |
279 | ||
280 | fseek (da_file, 4 + 8, SEEK_CUR); | |
281 | ||
282 | /* read the maximal counter. */ | |
283 | __read_gcov_type (&max_counter_in_run, da_file, 8); | |
284 | ||
285 | /* skip the rest of "statistics" emited by __bb_exit_func. */ | |
286 | fseek (da_file, extra_bytes - (4 + 8 + 8), SEEK_CUR); | |
287 | ||
288 | for (i = 0; i < func_count; i++) | |
289 | { | |
290 | long arc_count; | |
291 | long chksum; | |
292 | int j; | |
293 | ||
294 | if (__read_gcov_string | |
295 | (function_name_buffer, function_name_buffer_len, da_file, | |
296 | -1) != 0) | |
297 | { | |
298 | okay = 0; | |
299 | break; | |
300 | } | |
301 | ||
302 | if (__read_long (&chksum, da_file, 4) != 0) | |
303 | { | |
304 | okay = 0; | |
305 | break; | |
306 | } | |
307 | ||
308 | if (__read_long (&arc_count, da_file, 4) != 0) | |
309 | { | |
310 | okay = 0; | |
311 | break; | |
312 | } | |
313 | ||
314 | if (strcmp (function_name_buffer, current_function_name) != 0) | |
315 | { | |
316 | /* skip */ | |
317 | if (fseek (da_file, arc_count * 8, SEEK_CUR) < 0) | |
318 | { | |
319 | okay = 0; | |
320 | break; | |
321 | } | |
322 | } | |
323 | else if (arc_count != num_edges | |
324 | || chksum != profile_info.current_function_cfg_checksum) | |
325 | okay = 0, mismatch = 1; | |
326 | else | |
327 | { | |
328 | gcov_type tmp; | |
329 | ||
330 | profile_info.max_counter_in_program += max_counter_in_run; | |
331 | profile_info.count_profiles_merged++; | |
332 | ||
333 | for (j = 0; j < arc_count; j++) | |
334 | if (__read_gcov_type (&tmp, da_file, 8) != 0) | |
335 | { | |
336 | okay = 0; | |
337 | break; | |
338 | } | |
339 | else | |
340 | { | |
341 | profile[j] += tmp; | |
342 | } | |
343 | } | |
344 | } | |
345 | ||
346 | if (!okay) | |
347 | break; | |
348 | ||
349 | } | |
350 | ||
351 | free (function_name_buffer); | |
352 | ||
353 | if (!okay) | |
354 | { | |
355 | if (mismatch) | |
356 | error | |
357 | ("Profile does not match flowgraph of function %s (out of date?)", | |
358 | current_function_name); | |
359 | else | |
360 | error (".da file corrupted"); | |
361 | free (profile); | |
362 | return 0; | |
363 | } | |
4c45e018 | 364 | if (rtl_dump_file) |
365 | { | |
366 | fprintf(rtl_dump_file, "Merged %i profiles with maximal count %i.\n", | |
367 | profile_info.count_profiles_merged, | |
368 | (int)profile_info.max_counter_in_program); | |
369 | } | |
90c2be44 | 370 | |
371 | return profile; | |
372 | } | |
373 | \f | |
374 | ||
b9cf3f63 | 375 | /* Compute the branch probabilities for the various branches. |
376 | Annotate them accordingly. */ | |
377 | ||
378 | static void | |
86d4af74 | 379 | compute_branch_probabilities () |
b9cf3f63 | 380 | { |
4c26117a | 381 | basic_block bb; |
b3d6de89 | 382 | int i; |
383 | int num_edges = 0; | |
b9cf3f63 | 384 | int changes; |
385 | int passes; | |
b9cf3f63 | 386 | int hist_br_prob[20]; |
86d4af74 | 387 | int num_never_executed; |
388 | int num_branches; | |
90c2be44 | 389 | gcov_type *exec_counts = get_exec_counts (); |
390 | int exec_counts_pos = 0; | |
b9cf3f63 | 391 | |
86d4af74 | 392 | /* Attach extra info block to each bb. */ |
393 | ||
b36d64df | 394 | alloc_aux_for_blocks (sizeof (struct bb_info)); |
4c26117a | 395 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
86d4af74 | 396 | { |
86d4af74 | 397 | edge e; |
398 | ||
86d4af74 | 399 | for (e = bb->succ; e; e = e->succ_next) |
400 | if (!EDGE_INFO (e)->ignore) | |
401 | BB_INFO (bb)->succ_count++; | |
402 | for (e = bb->pred; e; e = e->pred_next) | |
403 | if (!EDGE_INFO (e)->ignore) | |
404 | BB_INFO (bb)->pred_count++; | |
405 | } | |
406 | ||
407 | /* Avoid predicting entry on exit nodes. */ | |
408 | BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; | |
409 | BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; | |
410 | ||
411 | /* For each edge not on the spanning tree, set its execution count from | |
b9cf3f63 | 412 | the .da file. */ |
413 | ||
414 | /* The first count in the .da file is the number of times that the function | |
415 | was entered. This is the exec_count for block zero. */ | |
416 | ||
4c26117a | 417 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
86d4af74 | 418 | { |
86d4af74 | 419 | edge e; |
420 | for (e = bb->succ; e; e = e->succ_next) | |
421 | if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) | |
422 | { | |
423 | num_edges++; | |
90c2be44 | 424 | if (exec_counts) |
86d4af74 | 425 | { |
90c2be44 | 426 | e->count = exec_counts[exec_counts_pos++]; |
86d4af74 | 427 | } |
428 | else | |
429 | e->count = 0; | |
90c2be44 | 430 | |
86d4af74 | 431 | EDGE_INFO (e)->count_valid = 1; |
432 | BB_INFO (bb)->succ_count--; | |
433 | BB_INFO (e->dest)->pred_count--; | |
63f23608 | 434 | if (rtl_dump_file) |
435 | { | |
436 | fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:", | |
b3d6de89 | 437 | bb->index, e->dest->index); |
63f23608 | 438 | fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, |
439 | (HOST_WIDEST_INT) e->count); | |
440 | } | |
86d4af74 | 441 | } |
442 | } | |
b9cf3f63 | 443 | |
86d4af74 | 444 | if (rtl_dump_file) |
63f23608 | 445 | fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges); |
b9cf3f63 | 446 | |
447 | /* For every block in the file, | |
86d4af74 | 448 | - if every exit/entrance edge has a known count, then set the block count |
449 | - if the block count is known, and every exit/entrance edge but one has | |
450 | a known execution count, then set the count of the remaining edge | |
b9cf3f63 | 451 | |
86d4af74 | 452 | As edge counts are set, decrement the succ/pred count, but don't delete |
453 | the edge, that way we can easily tell when all edges are known, or only | |
454 | one edge is unknown. */ | |
b9cf3f63 | 455 | |
456 | /* The order that the basic blocks are iterated through is important. | |
457 | Since the code that finds spanning trees starts with block 0, low numbered | |
86d4af74 | 458 | edges are put on the spanning tree in preference to high numbered edges. |
459 | Hence, most instrumented edges are at the end. Graph solving works much | |
b9cf3f63 | 460 | faster if we propagate numbers from the end to the start. |
86d4af74 | 461 | |
b9cf3f63 | 462 | This takes an average of slightly more than 3 passes. */ |
463 | ||
464 | changes = 1; | |
465 | passes = 0; | |
466 | while (changes) | |
467 | { | |
468 | passes++; | |
469 | changes = 0; | |
4c26117a | 470 | FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) |
b9cf3f63 | 471 | { |
86d4af74 | 472 | struct bb_info *bi = BB_INFO (bb); |
473 | if (! bi->count_valid) | |
b9cf3f63 | 474 | { |
86d4af74 | 475 | if (bi->succ_count == 0) |
b9cf3f63 | 476 | { |
86d4af74 | 477 | edge e; |
63f23608 | 478 | gcov_type total = 0; |
86d4af74 | 479 | |
480 | for (e = bb->succ; e; e = e->succ_next) | |
481 | total += e->count; | |
482 | bb->count = total; | |
483 | bi->count_valid = 1; | |
b9cf3f63 | 484 | changes = 1; |
485 | } | |
86d4af74 | 486 | else if (bi->pred_count == 0) |
b9cf3f63 | 487 | { |
86d4af74 | 488 | edge e; |
63f23608 | 489 | gcov_type total = 0; |
86d4af74 | 490 | |
491 | for (e = bb->pred; e; e = e->pred_next) | |
492 | total += e->count; | |
493 | bb->count = total; | |
494 | bi->count_valid = 1; | |
b9cf3f63 | 495 | changes = 1; |
496 | } | |
497 | } | |
86d4af74 | 498 | if (bi->count_valid) |
b9cf3f63 | 499 | { |
86d4af74 | 500 | if (bi->succ_count == 1) |
b9cf3f63 | 501 | { |
86d4af74 | 502 | edge e; |
63f23608 | 503 | gcov_type total = 0; |
86d4af74 | 504 | |
b9cf3f63 | 505 | /* One of the counts will be invalid, but it is zero, |
506 | so adding it in also doesn't hurt. */ | |
86d4af74 | 507 | for (e = bb->succ; e; e = e->succ_next) |
508 | total += e->count; | |
509 | ||
510 | /* Seedgeh for the invalid edge, and set its count. */ | |
511 | for (e = bb->succ; e; e = e->succ_next) | |
512 | if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) | |
b9cf3f63 | 513 | break; |
86d4af74 | 514 | |
515 | /* Calculate count for remaining edge by conservation. */ | |
516 | total = bb->count - total; | |
517 | ||
518 | if (! e) | |
b9cf3f63 | 519 | abort (); |
86d4af74 | 520 | EDGE_INFO (e)->count_valid = 1; |
521 | e->count = total; | |
522 | bi->succ_count--; | |
447f6a7f | 523 | |
86d4af74 | 524 | BB_INFO (e->dest)->pred_count--; |
b9cf3f63 | 525 | changes = 1; |
526 | } | |
86d4af74 | 527 | if (bi->pred_count == 1) |
b9cf3f63 | 528 | { |
86d4af74 | 529 | edge e; |
63f23608 | 530 | gcov_type total = 0; |
86d4af74 | 531 | |
b9cf3f63 | 532 | /* One of the counts will be invalid, but it is zero, |
533 | so adding it in also doesn't hurt. */ | |
86d4af74 | 534 | for (e = bb->pred; e; e = e->pred_next) |
535 | total += e->count; | |
536 | ||
537 | /* Seedgeh for the invalid edge, and set its count. */ | |
538 | for (e = bb->pred; e; e = e->pred_next) | |
539 | if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) | |
b9cf3f63 | 540 | break; |
86d4af74 | 541 | |
542 | /* Calculate count for remaining edge by conservation. */ | |
543 | total = bb->count - total + e->count; | |
544 | ||
545 | if (! e) | |
b9cf3f63 | 546 | abort (); |
86d4af74 | 547 | EDGE_INFO (e)->count_valid = 1; |
548 | e->count = total; | |
549 | bi->pred_count--; | |
447f6a7f | 550 | |
86d4af74 | 551 | BB_INFO (e->src)->succ_count--; |
b9cf3f63 | 552 | changes = 1; |
553 | } | |
554 | } | |
555 | } | |
556 | } | |
86d4af74 | 557 | if (rtl_dump_file) |
558 | dump_flow_info (rtl_dump_file); | |
b9cf3f63 | 559 | |
560 | total_num_passes += passes; | |
86d4af74 | 561 | if (rtl_dump_file) |
562 | fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes); | |
b9cf3f63 | 563 | |
564 | /* If the graph has been correctly solved, every block will have a | |
565 | succ and pred count of zero. */ | |
4c26117a | 566 | FOR_EACH_BB (bb) |
b9cf3f63 | 567 | { |
86d4af74 | 568 | if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count) |
b9cf3f63 | 569 | abort (); |
570 | } | |
571 | ||
86d4af74 | 572 | /* For every edge, calculate its branch probability and add a reg_note |
b9cf3f63 | 573 | to the branch insn to indicate this. */ |
574 | ||
575 | for (i = 0; i < 20; i++) | |
576 | hist_br_prob[i] = 0; | |
577 | num_never_executed = 0; | |
578 | num_branches = 0; | |
579 | ||
4c26117a | 580 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
b9cf3f63 | 581 | { |
86d4af74 | 582 | edge e; |
63f23608 | 583 | gcov_type total; |
86d4af74 | 584 | rtx note; |
585 | ||
586 | total = bb->count; | |
eb429644 | 587 | if (total) |
eb429644 | 588 | { |
ad73c2a0 | 589 | for (e = bb->succ; e; e = e->succ_next) |
eb429644 | 590 | { |
ad73c2a0 | 591 | e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total; |
592 | if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) | |
593 | { | |
cb8bacb6 | 594 | error ("corrupted profile info: prob for %d-%d thought to be %d", |
b3d6de89 | 595 | e->src->index, e->dest->index, e->probability); |
ad73c2a0 | 596 | e->probability = REG_BR_PROB_BASE / 2; |
597 | } | |
598 | } | |
b3d6de89 | 599 | if (bb->index >= 0 |
ad73c2a0 | 600 | && any_condjump_p (bb->end) |
601 | && bb->succ->succ_next) | |
602 | { | |
603 | int prob; | |
604 | edge e; | |
eb429644 | 605 | int index; |
606 | ||
607 | /* Find the branch edge. It is possible that we do have fake | |
608 | edges here. */ | |
609 | for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU); | |
610 | e = e->succ_next) | |
611 | continue; /* Loop body has been intentionally left blank. */ | |
612 | ||
613 | prob = e->probability; | |
614 | index = prob * 20 / REG_BR_PROB_BASE; | |
447f6a7f | 615 | |
eb429644 | 616 | if (index == 20) |
617 | index = 19; | |
618 | hist_br_prob[index]++; | |
619 | ||
620 | note = find_reg_note (bb->end, REG_BR_PROB, 0); | |
86d4af74 | 621 | /* There may be already note put by some other pass, such |
eb429644 | 622 | as builtin_expect expander. */ |
86d4af74 | 623 | if (note) |
624 | XEXP (note, 0) = GEN_INT (prob); | |
625 | else | |
eb429644 | 626 | REG_NOTES (bb->end) |
86d4af74 | 627 | = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), |
eb429644 | 628 | REG_NOTES (bb->end)); |
ad73c2a0 | 629 | num_branches++; |
b9cf3f63 | 630 | } |
ad73c2a0 | 631 | } |
632 | /* Otherwise distribute the probabilities evenly so we get sane sum. | |
633 | Use simple heuristics that if there are normal edges, give all abnormals | |
634 | frequency of 0, otherwise distribute the frequency over abnormals | |
635 | (this is the case of noreturn calls). */ | |
636 | else | |
637 | { | |
638 | for (e = bb->succ; e; e = e->succ_next) | |
639 | if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
640 | total ++; | |
641 | if (total) | |
642 | { | |
643 | for (e = bb->succ; e; e = e->succ_next) | |
644 | if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) | |
645 | e->probability = REG_BR_PROB_BASE / total; | |
646 | else | |
647 | e->probability = 0; | |
648 | } | |
649 | else | |
650 | { | |
651 | for (e = bb->succ; e; e = e->succ_next) | |
652 | total ++; | |
653 | for (e = bb->succ; e; e = e->succ_next) | |
654 | e->probability = REG_BR_PROB_BASE / total; | |
655 | } | |
b3d6de89 | 656 | if (bb->index >= 0 |
ad73c2a0 | 657 | && any_condjump_p (bb->end) |
658 | && bb->succ->succ_next) | |
659 | num_branches++, num_never_executed; | |
b9cf3f63 | 660 | } |
b9cf3f63 | 661 | } |
b9cf3f63 | 662 | |
86d4af74 | 663 | if (rtl_dump_file) |
b9cf3f63 | 664 | { |
86d4af74 | 665 | fprintf (rtl_dump_file, "%d branches\n", num_branches); |
666 | fprintf (rtl_dump_file, "%d branches never executed\n", | |
b9cf3f63 | 667 | num_never_executed); |
668 | if (num_branches) | |
669 | for (i = 0; i < 10; i++) | |
86d4af74 | 670 | fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n", |
671 | (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, | |
672 | 5 * i, 5 * i + 5); | |
b9cf3f63 | 673 | |
674 | total_num_branches += num_branches; | |
675 | total_num_never_executed += num_never_executed; | |
676 | for (i = 0; i < 20; i++) | |
677 | total_hist_br_prob[i] += hist_br_prob[i]; | |
86d4af74 | 678 | |
679 | fputc ('\n', rtl_dump_file); | |
680 | fputc ('\n', rtl_dump_file); | |
b9cf3f63 | 681 | } |
86d4af74 | 682 | |
b36d64df | 683 | free_aux_for_blocks (); |
90c2be44 | 684 | if (exec_counts) |
685 | free (exec_counts); | |
686 | } | |
687 | ||
688 | /* Compute checksum for the current function. */ | |
689 | ||
690 | #define CHSUM_HASH 500000003 | |
691 | #define CHSUM_SHIFT 2 | |
692 | ||
693 | static long | |
694 | compute_checksum () | |
695 | { | |
696 | long chsum = 0; | |
4c26117a | 697 | basic_block bb; |
195731ad | 698 | |
4c26117a | 699 | FOR_EACH_BB (bb) |
90c2be44 | 700 | { |
90c2be44 | 701 | edge e; |
702 | ||
703 | for (e = bb->succ; e; e = e->succ_next) | |
704 | { | |
705 | chsum = ((chsum << CHSUM_SHIFT) + (BB_TO_GCOV_INDEX (e->dest) + 1)) % CHSUM_HASH; | |
706 | } | |
707 | ||
708 | chsum = (chsum << CHSUM_SHIFT) % CHSUM_HASH; | |
709 | } | |
710 | ||
711 | return chsum; | |
b9cf3f63 | 712 | } |
713 | ||
10f2b886 | 714 | /* Instrument and/or analyze program behavior based on program flow graph. |
715 | In either case, this function builds a flow graph for the function being | |
716 | compiled. The flow graph is stored in BB_GRAPH. | |
717 | ||
86d4af74 | 718 | When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in |
10f2b886 | 719 | the flow graph that are needed to reconstruct the dynamic behavior of the |
720 | flow graph. | |
721 | ||
ad87de1e | 722 | When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary |
86d4af74 | 723 | information from a data file containing edge count information from previous |
10f2b886 | 724 | executions of the function being compiled. In this case, the flow graph is |
725 | annotated with actual execution counts, which are later propagated into the | |
726 | rtl for optimization purposes. | |
727 | ||
728 | Main entry point of this file. */ | |
729 | ||
730 | void | |
86d4af74 | 731 | branch_prob () |
10f2b886 | 732 | { |
4c26117a | 733 | basic_block bb; |
86d4af74 | 734 | int i; |
84870dc8 | 735 | int num_edges, ignored_edges; |
86d4af74 | 736 | struct edge_list *el; |
10f2b886 | 737 | |
90c2be44 | 738 | profile_info.current_function_cfg_checksum = compute_checksum (); |
739 | ||
740 | if (rtl_dump_file) | |
195731ad | 741 | fprintf (rtl_dump_file, "CFG checksum is %ld\n", |
90c2be44 | 742 | profile_info.current_function_cfg_checksum); |
195731ad | 743 | |
86d4af74 | 744 | /* Start of a function. */ |
10f2b886 | 745 | if (flag_test_coverage) |
746 | output_gcov_string (current_function_name, (long) -2); | |
747 | ||
10f2b886 | 748 | total_num_times_called++; |
749 | ||
2f0bfe72 | 750 | flow_call_edges_add (NULL); |
ba126de4 | 751 | add_noreturn_fake_exit_edges (); |
2f0bfe72 | 752 | |
86d4af74 | 753 | /* We can't handle cyclic regions constructed using abnormal edges. |
754 | To avoid these we replace every source of abnormal edge by a fake | |
755 | edge from entry node and every destination by fake edge to exit. | |
756 | This keeps graph acyclic and our calculation exact for all normal | |
757 | edges except for exit and entrance ones. | |
447f6a7f | 758 | |
86d4af74 | 759 | We also add fake exit edges for each call and asm statement in the |
760 | basic, since it may not return. */ | |
10f2b886 | 761 | |
4c26117a | 762 | FOR_EACH_BB (bb) |
86d4af74 | 763 | { |
86d4af74 | 764 | int need_exit_edge = 0, need_entry_edge = 0; |
765 | int have_exit_edge = 0, have_entry_edge = 0; | |
9239aee6 | 766 | rtx insn; |
86d4af74 | 767 | edge e; |
10f2b886 | 768 | |
9239aee6 | 769 | /* Add fake edges from entry block to the call insns that may return |
770 | twice. The CFG is not quite correct then, as call insn plays more | |
771 | role of CODE_LABEL, but for our purposes, everything should be OK, | |
772 | as we never insert code to the beggining of basic block. */ | |
773 | for (insn = bb->head; insn != NEXT_INSN (bb->end); | |
774 | insn = NEXT_INSN (insn)) | |
775 | { | |
776 | if (GET_CODE (insn) == CALL_INSN | |
777 | && find_reg_note (insn, REG_SETJMP, NULL)) | |
778 | { | |
779 | if (GET_CODE (bb->head) == CODE_LABEL | |
780 | || insn != NEXT_INSN (bb->head)) | |
781 | { | |
782 | e = split_block (bb, PREV_INSN (insn)); | |
7392df29 | 783 | make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE); |
9239aee6 | 784 | break; |
785 | } | |
786 | else | |
787 | { | |
788 | /* We should not get abort here, as call to setjmp should not | |
789 | be the very first instruction of function. */ | |
4c26117a | 790 | if (bb == ENTRY_BLOCK_PTR) |
9239aee6 | 791 | abort (); |
7392df29 | 792 | make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); |
9239aee6 | 793 | } |
794 | } | |
795 | } | |
796 | ||
86d4af74 | 797 | for (e = bb->succ; e; e = e->succ_next) |
798 | { | |
799 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
800 | && e->dest != EXIT_BLOCK_PTR) | |
801 | need_exit_edge = 1; | |
802 | if (e->dest == EXIT_BLOCK_PTR) | |
803 | have_exit_edge = 1; | |
804 | } | |
805 | for (e = bb->pred; e; e = e->pred_next) | |
806 | { | |
807 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
808 | && e->src != ENTRY_BLOCK_PTR) | |
809 | need_entry_edge = 1; | |
810 | if (e->src == ENTRY_BLOCK_PTR) | |
811 | have_entry_edge = 1; | |
812 | } | |
10f2b886 | 813 | |
86d4af74 | 814 | if (need_exit_edge && !have_exit_edge) |
815 | { | |
816 | if (rtl_dump_file) | |
817 | fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n", | |
b3d6de89 | 818 | bb->index); |
195731ad | 819 | make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); |
86d4af74 | 820 | } |
821 | if (need_entry_edge && !have_entry_edge) | |
822 | { | |
823 | if (rtl_dump_file) | |
824 | fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n", | |
b3d6de89 | 825 | bb->index); |
195731ad | 826 | make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); |
86d4af74 | 827 | } |
828 | } | |
10f2b886 | 829 | |
86d4af74 | 830 | el = create_edge_list (); |
831 | num_edges = NUM_EDGES (el); | |
b36d64df | 832 | alloc_aux_for_edges (sizeof (struct edge_info)); |
10f2b886 | 833 | |
3c0a32c9 | 834 | /* The basic blocks are expected to be numbered sequentially. */ |
835 | compact_blocks (); | |
836 | ||
84870dc8 | 837 | ignored_edges = 0; |
86d4af74 | 838 | for (i = 0 ; i < num_edges ; i++) |
839 | { | |
840 | edge e = INDEX_EDGE (el, i); | |
841 | e->count = 0; | |
86d4af74 | 842 | |
843 | /* Mark edges we've replaced by fake edges above as ignored. */ | |
844 | if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
845 | && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) | |
195731ad | 846 | { |
84870dc8 | 847 | EDGE_INFO (e)->ignore = 1; |
848 | ignored_edges++; | |
195731ad | 849 | } |
86d4af74 | 850 | } |
10f2b886 | 851 | |
86d4af74 | 852 | #ifdef ENABLE_CHECKING |
853 | verify_flow_info (); | |
854 | #endif | |
10f2b886 | 855 | |
86d4af74 | 856 | /* Output line number information about each basic block for |
857 | GCOV utility. */ | |
858 | if (flag_test_coverage) | |
859 | { | |
4c26117a | 860 | FOR_EACH_BB (bb) |
195731ad | 861 | { |
86d4af74 | 862 | rtx insn = bb->head; |
195731ad | 863 | static int ignore_next_note = 0; |
86d4af74 | 864 | |
865 | /* We are looking for line number notes. Search backward before | |
866 | basic block to find correct ones. */ | |
867 | insn = prev_nonnote_insn (insn); | |
868 | if (!insn) | |
869 | insn = get_insns (); | |
870 | else | |
871 | insn = NEXT_INSN (insn); | |
10f2b886 | 872 | |
86d4af74 | 873 | /* Output a zero to the .bb file to indicate that a new |
874 | block list is starting. */ | |
875 | __write_long (0, bb_file, 4); | |
10f2b886 | 876 | |
86d4af74 | 877 | while (insn != bb->end) |
878 | { | |
879 | if (GET_CODE (insn) == NOTE) | |
880 | { | |
881 | /* Must ignore the line number notes that immediately | |
882 | follow the end of an inline function to avoid counting | |
883 | it twice. There is a note before the call, and one | |
884 | after the call. */ | |
885 | if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER) | |
886 | ignore_next_note = 1; | |
887 | else if (NOTE_LINE_NUMBER (insn) > 0) | |
888 | { | |
889 | if (ignore_next_note) | |
890 | ignore_next_note = 0; | |
891 | else | |
892 | { | |
893 | /* If this is a new source file, then output the | |
894 | file's name to the .bb file. */ | |
895 | if (! last_bb_file_name | |
896 | || strcmp (NOTE_SOURCE_FILE (insn), | |
897 | last_bb_file_name)) | |
898 | { | |
899 | if (last_bb_file_name) | |
900 | free (last_bb_file_name); | |
901 | last_bb_file_name | |
902 | = xstrdup (NOTE_SOURCE_FILE (insn)); | |
903 | output_gcov_string (NOTE_SOURCE_FILE (insn), | |
904 | (long)-1); | |
905 | } | |
906 | /* Output the line number to the .bb file. Must be | |
907 | done after the output_bb_profile_data() call, and | |
908 | after the file name is written, to ensure that it | |
909 | is correctly handled by gcov. */ | |
910 | __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4); | |
911 | } | |
912 | } | |
913 | } | |
914 | insn = NEXT_INSN (insn); | |
915 | } | |
195731ad | 916 | } |
86d4af74 | 917 | __write_long (0, bb_file, 4); |
918 | } | |
10f2b886 | 919 | |
86d4af74 | 920 | /* Create spanning tree from basic block graph, mark each edge that is |
921 | on the spanning tree. We insert as many abnormal and critical edges | |
dd5b4b36 | 922 | as possible to minimize number of edge splits necessary. */ |
10f2b886 | 923 | |
86d4af74 | 924 | find_spanning_tree (el); |
b9cf3f63 | 925 | |
84870dc8 | 926 | /* Fake edges that are not on the tree will not be instrumented, so |
aa40f561 | 927 | mark them ignored. */ |
84870dc8 | 928 | for (i = 0; i < num_edges; i++) |
929 | { | |
930 | edge e = INDEX_EDGE (el, i); | |
931 | struct edge_info *inf = EDGE_INFO (e); | |
932 | if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree) | |
195731ad | 933 | { |
934 | inf->ignore = 1; | |
935 | ignored_edges++; | |
936 | } | |
84870dc8 | 937 | } |
938 | ||
b3d6de89 | 939 | total_num_blocks += n_basic_blocks + 2; |
84870dc8 | 940 | if (rtl_dump_file) |
b3d6de89 | 941 | fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks); |
84870dc8 | 942 | |
943 | total_num_edges += num_edges; | |
944 | if (rtl_dump_file) | |
945 | fprintf (rtl_dump_file, "%d edges\n", num_edges); | |
946 | ||
947 | total_num_edges_ignored += ignored_edges; | |
948 | if (rtl_dump_file) | |
949 | fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges); | |
950 | ||
b9cf3f63 | 951 | /* Create a .bbg file from which gcov can reconstruct the basic block |
952 | graph. First output the number of basic blocks, and then for every | |
86d4af74 | 953 | edge output the source and target basic block numbers. |
b9cf3f63 | 954 | NOTE: The format of this file must be compatible with gcov. */ |
955 | ||
956 | if (flag_test_coverage) | |
10f2b886 | 957 | { |
b9cf3f63 | 958 | int flag_bits; |
10f2b886 | 959 | |
90c2be44 | 960 | __write_gcov_string (current_function_name, |
961 | strlen (current_function_name), bbg_file, -1); | |
962 | ||
963 | /* write checksum. */ | |
964 | __write_long (profile_info.current_function_cfg_checksum, bbg_file, 4); | |
195731ad | 965 | |
86d4af74 | 966 | /* The plus 2 stands for entry and exit block. */ |
b3d6de89 | 967 | __write_long (n_basic_blocks + 2, bbg_file, 4); |
84870dc8 | 968 | __write_long (num_edges - ignored_edges + 1, bbg_file, 4); |
10f2b886 | 969 | |
4c26117a | 970 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) |
b9cf3f63 | 971 | { |
86d4af74 | 972 | edge e; |
b9cf3f63 | 973 | long count = 0; |
86d4af74 | 974 | |
975 | for (e = bb->succ; e; e = e->succ_next) | |
976 | if (!EDGE_INFO (e)->ignore) | |
977 | count++; | |
b9cf3f63 | 978 | __write_long (count, bbg_file, 4); |
10f2b886 | 979 | |
86d4af74 | 980 | for (e = bb->succ; e; e = e->succ_next) |
b9cf3f63 | 981 | { |
86d4af74 | 982 | struct edge_info *i = EDGE_INFO (e); |
983 | if (!i->ignore) | |
984 | { | |
985 | flag_bits = 0; | |
986 | if (i->on_tree) | |
987 | flag_bits |= 0x1; | |
84870dc8 | 988 | if (e->flags & EDGE_FAKE) |
86d4af74 | 989 | flag_bits |= 0x2; |
990 | if (e->flags & EDGE_FALLTHRU) | |
991 | flag_bits |= 0x4; | |
992 | ||
993 | __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4); | |
994 | __write_long (flag_bits, bbg_file, 4); | |
995 | } | |
10f2b886 | 996 | } |
997 | } | |
35a3065a | 998 | /* Emit fake loopback edge for EXIT block to maintain compatibility with |
86d4af74 | 999 | old gcov format. */ |
1000 | __write_long (1, bbg_file, 4); | |
1001 | __write_long (0, bbg_file, 4); | |
1002 | __write_long (0x1, bbg_file, 4); | |
10f2b886 | 1003 | |
86d4af74 | 1004 | /* Emit a -1 to separate the list of all edges from the list of |
b9cf3f63 | 1005 | loop back edges that follows. */ |
1006 | __write_long (-1, bbg_file, 4); | |
10f2b886 | 1007 | } |
10f2b886 | 1008 | |
86d4af74 | 1009 | if (flag_branch_probabilities) |
1010 | compute_branch_probabilities (); | |
1011 | ||
1012 | /* For each edge not on the spanning tree, add counting code as rtl. */ | |
10f2b886 | 1013 | |
b9cf3f63 | 1014 | if (profile_arc_flag) |
1015 | { | |
86d4af74 | 1016 | instrument_edges (el); |
b9cf3f63 | 1017 | allocate_reg_info (max_reg_num (), FALSE, FALSE); |
10f2b886 | 1018 | } |
1019 | ||
86d4af74 | 1020 | remove_fake_edges (); |
2f0bfe72 | 1021 | /* Re-merge split basic blocks and the mess introduced by |
1022 | insert_insn_on_edge. */ | |
1023 | cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0); | |
1024 | if (rtl_dump_file) | |
1025 | dump_flow_info (rtl_dump_file); | |
1026 | ||
b36d64df | 1027 | free_aux_for_edges (); |
86d4af74 | 1028 | free_edge_list (el); |
10f2b886 | 1029 | } |
1030 | \f | |
86d4af74 | 1031 | /* Union find algorithm implementation for the basic blocks using |
aa40f561 | 1032 | aux fields. */ |
10f2b886 | 1033 | |
86d4af74 | 1034 | static basic_block |
1035 | find_group (bb) | |
1036 | basic_block bb; | |
10f2b886 | 1037 | { |
86d4af74 | 1038 | basic_block group = bb, bb1; |
10f2b886 | 1039 | |
86d4af74 | 1040 | while ((basic_block) group->aux != group) |
1041 | group = (basic_block) group->aux; | |
10f2b886 | 1042 | |
86d4af74 | 1043 | /* Compress path. */ |
1044 | while ((basic_block) bb->aux != group) | |
10f2b886 | 1045 | { |
86d4af74 | 1046 | bb1 = (basic_block) bb->aux; |
1047 | bb->aux = (void *) group; | |
1048 | bb = bb1; | |
10f2b886 | 1049 | } |
86d4af74 | 1050 | return group; |
1051 | } | |
10f2b886 | 1052 | |
86d4af74 | 1053 | static void |
1054 | union_groups (bb1, bb2) | |
1055 | basic_block bb1, bb2; | |
1056 | { | |
1057 | basic_block bb1g = find_group (bb1); | |
1058 | basic_block bb2g = find_group (bb2); | |
10f2b886 | 1059 | |
86d4af74 | 1060 | /* ??? I don't have a place for the rank field. OK. Lets go w/o it, |
1061 | this code is unlikely going to be performance problem anyway. */ | |
1062 | if (bb1g == bb2g) | |
1063 | abort (); | |
10f2b886 | 1064 | |
86d4af74 | 1065 | bb1g->aux = bb2g; |
10f2b886 | 1066 | } |
86d4af74 | 1067 | \f |
1068 | /* This function searches all of the edges in the program flow graph, and puts | |
1069 | as many bad edges as possible onto the spanning tree. Bad edges include | |
1070 | abnormals edges, which can't be instrumented at the moment. Since it is | |
1071 | possible for fake edges to form an cycle, we will have to develop some | |
1072 | better way in the future. Also put critical edges to the tree, since they | |
1073 | are more expensive to instrument. */ | |
10f2b886 | 1074 | |
1075 | static void | |
86d4af74 | 1076 | find_spanning_tree (el) |
1077 | struct edge_list *el; | |
10f2b886 | 1078 | { |
86d4af74 | 1079 | int i; |
1080 | int num_edges = NUM_EDGES (el); | |
4c26117a | 1081 | basic_block bb; |
10f2b886 | 1082 | |
86d4af74 | 1083 | /* We use aux field for standard union-find algorithm. */ |
4c26117a | 1084 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
1085 | bb->aux = bb; | |
10f2b886 | 1086 | |
86d4af74 | 1087 | /* Add fake edge exit to entry we can't instrument. */ |
1088 | union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR); | |
1089 | ||
90c2be44 | 1090 | /* First add all abnormal edges to the tree unless they form an cycle. Also |
1091 | add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind | |
1092 | setting return value from function. */ | |
86d4af74 | 1093 | for (i = 0; i < num_edges; i++) |
1094 | { | |
1095 | edge e = INDEX_EDGE (el, i); | |
90c2be44 | 1096 | if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) |
195731ad | 1097 | || e->dest == EXIT_BLOCK_PTR |
1098 | ) | |
86d4af74 | 1099 | && !EDGE_INFO (e)->ignore |
1100 | && (find_group (e->src) != find_group (e->dest))) | |
1101 | { | |
90c2be44 | 1102 | if (rtl_dump_file) |
1103 | fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n", | |
195731ad | 1104 | e->src->index, e->dest->index); |
86d4af74 | 1105 | EDGE_INFO (e)->on_tree = 1; |
1106 | union_groups (e->src, e->dest); | |
1107 | } | |
1108 | } | |
1109 | ||
1110 | /* Now insert all critical edges to the tree unless they form an cycle. */ | |
1111 | for (i = 0; i < num_edges; i++) | |
1112 | { | |
1113 | edge e = INDEX_EDGE (el, i); | |
e76f35e8 | 1114 | if ((EDGE_CRITICAL_P (e)) |
86d4af74 | 1115 | && !EDGE_INFO (e)->ignore |
1116 | && (find_group (e->src) != find_group (e->dest))) | |
1117 | { | |
90c2be44 | 1118 | if (rtl_dump_file) |
1119 | fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n", | |
195731ad | 1120 | e->src->index, e->dest->index); |
86d4af74 | 1121 | EDGE_INFO (e)->on_tree = 1; |
1122 | union_groups (e->src, e->dest); | |
1123 | } | |
1124 | } | |
1125 | ||
1126 | /* And now the rest. */ | |
1127 | for (i = 0; i < num_edges; i++) | |
1128 | { | |
1129 | edge e = INDEX_EDGE (el, i); | |
1130 | if (find_group (e->src) != find_group (e->dest) | |
1131 | && !EDGE_INFO (e)->ignore) | |
1132 | { | |
90c2be44 | 1133 | if (rtl_dump_file) |
1134 | fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n", | |
195731ad | 1135 | e->src->index, e->dest->index); |
86d4af74 | 1136 | EDGE_INFO (e)->on_tree = 1; |
1137 | union_groups (e->src, e->dest); | |
1138 | } | |
1139 | } | |
b36d64df | 1140 | |
4c26117a | 1141 | FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) |
1142 | bb->aux = NULL; | |
10f2b886 | 1143 | } |
1144 | \f | |
1145 | /* Perform file-level initialization for branch-prob processing. */ | |
1146 | ||
1147 | void | |
1148 | init_branch_prob (filename) | |
951f0f62 | 1149 | const char *filename; |
10f2b886 | 1150 | { |
1151 | long len; | |
1152 | int i; | |
1153 | ||
1154 | if (flag_test_coverage) | |
1155 | { | |
10f2b886 | 1156 | int len = strlen (filename); |
86d4af74 | 1157 | char *data_file, *bbg_file_name; |
1158 | ||
1159 | /* Open an output file for the basic block/line number map. */ | |
1160 | data_file = (char *) alloca (len + 4); | |
10f2b886 | 1161 | strcpy (data_file, filename); |
1162 | strip_off_ending (data_file, len); | |
1163 | strcat (data_file, ".bb"); | |
155b05dc | 1164 | if ((bb_file = fopen (data_file, "wb")) == 0) |
f060a027 | 1165 | fatal_io_error ("can't open %s", data_file); |
10f2b886 | 1166 | |
1167 | /* Open an output file for the program flow graph. */ | |
10f2b886 | 1168 | bbg_file_name = (char *) alloca (len + 5); |
1169 | strcpy (bbg_file_name, filename); | |
1170 | strip_off_ending (bbg_file_name, len); | |
1171 | strcat (bbg_file_name, ".bbg"); | |
155b05dc | 1172 | if ((bbg_file = fopen (bbg_file_name, "wb")) == 0) |
f060a027 | 1173 | fatal_io_error ("can't open %s", bbg_file_name); |
10f2b886 | 1174 | |
1175 | /* Initialize to zero, to ensure that the first file name will be | |
1176 | written to the .bb file. */ | |
1177 | last_bb_file_name = 0; | |
1178 | } | |
1179 | ||
1180 | if (flag_branch_probabilities) | |
1181 | { | |
86d4af74 | 1182 | char *da_file_name; |
1183 | ||
10f2b886 | 1184 | len = strlen (filename); |
1185 | da_file_name = (char *) alloca (len + 4); | |
1186 | strcpy (da_file_name, filename); | |
1187 | strip_off_ending (da_file_name, len); | |
1188 | strcat (da_file_name, ".da"); | |
155b05dc | 1189 | if ((da_file = fopen (da_file_name, "rb")) == 0) |
ebae5c09 | 1190 | warning ("file %s not found, execution counts assumed to be zero", |
10f2b886 | 1191 | da_file_name); |
10f2b886 | 1192 | } |
1193 | ||
1194 | if (profile_arc_flag) | |
86d4af74 | 1195 | init_edge_profiler (); |
10f2b886 | 1196 | |
1197 | total_num_blocks = 0; | |
86d4af74 | 1198 | total_num_edges = 0; |
84870dc8 | 1199 | total_num_edges_ignored = 0; |
86d4af74 | 1200 | total_num_edges_instrumented = 0; |
10f2b886 | 1201 | total_num_blocks_created = 0; |
1202 | total_num_passes = 0; | |
1203 | total_num_times_called = 0; | |
1204 | total_num_branches = 0; | |
1205 | total_num_never_executed = 0; | |
1206 | for (i = 0; i < 20; i++) | |
1207 | total_hist_br_prob[i] = 0; | |
1208 | } | |
1209 | ||
1210 | /* Performs file-level cleanup after branch-prob processing | |
1211 | is completed. */ | |
1212 | ||
1213 | void | |
86d4af74 | 1214 | end_branch_prob () |
10f2b886 | 1215 | { |
1216 | if (flag_test_coverage) | |
1217 | { | |
1218 | fclose (bb_file); | |
1219 | fclose (bbg_file); | |
1220 | } | |
1221 | ||
90c2be44 | 1222 | if (flag_branch_probabilities && da_file) |
1223 | fclose (da_file); | |
10f2b886 | 1224 | |
86d4af74 | 1225 | if (rtl_dump_file) |
10f2b886 | 1226 | { |
86d4af74 | 1227 | fprintf (rtl_dump_file, "\n"); |
1228 | fprintf (rtl_dump_file, "Total number of blocks: %d\n", | |
1229 | total_num_blocks); | |
1230 | fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges); | |
84870dc8 | 1231 | fprintf (rtl_dump_file, "Total number of ignored edges: %d\n", |
1232 | total_num_edges_ignored); | |
86d4af74 | 1233 | fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n", |
1234 | total_num_edges_instrumented); | |
1235 | fprintf (rtl_dump_file, "Total number of blocks created: %d\n", | |
10f2b886 | 1236 | total_num_blocks_created); |
86d4af74 | 1237 | fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n", |
10f2b886 | 1238 | total_num_passes); |
1239 | if (total_num_times_called != 0) | |
86d4af74 | 1240 | fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n", |
10f2b886 | 1241 | (total_num_passes + (total_num_times_called >> 1)) |
1242 | / total_num_times_called); | |
86d4af74 | 1243 | fprintf (rtl_dump_file, "Total number of branches: %d\n", |
1244 | total_num_branches); | |
1245 | fprintf (rtl_dump_file, "Total number of branches never executed: %d\n", | |
10f2b886 | 1246 | total_num_never_executed); |
1247 | if (total_num_branches) | |
1248 | { | |
1249 | int i; | |
1250 | ||
1251 | for (i = 0; i < 10; i++) | |
86d4af74 | 1252 | fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n", |
10f2b886 | 1253 | (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 |
1254 | / total_num_branches, 5*i, 5*i+5); | |
1255 | } | |
1256 | } | |
1257 | } | |
1258 | \f | |
86d4af74 | 1259 | /* The label used by the edge profiling code. */ |
10f2b886 | 1260 | |
1f3233d1 | 1261 | static GTY(()) rtx profiler_label; |
10f2b886 | 1262 | |
1263 | /* Initialize the profiler_label. */ | |
1264 | ||
1265 | static void | |
86d4af74 | 1266 | init_edge_profiler () |
10f2b886 | 1267 | { |
1268 | /* Generate and save a copy of this so it can be shared. */ | |
44acf429 | 1269 | char buf[20]; |
1270 | ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2); | |
ec6cb94a | 1271 | profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)); |
10f2b886 | 1272 | } |
1273 | ||
86d4af74 | 1274 | /* Output instructions as RTL to increment the edge execution count. */ |
10f2b886 | 1275 | |
86d4af74 | 1276 | static rtx |
1277 | gen_edge_profiler (edgeno) | |
1278 | int edgeno; | |
10f2b886 | 1279 | { |
63f23608 | 1280 | enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0); |
86d4af74 | 1281 | rtx mem_ref, tmp; |
10f2b886 | 1282 | rtx sequence; |
1283 | ||
10f2b886 | 1284 | start_sequence (); |
1285 | ||
86d4af74 | 1286 | tmp = force_reg (Pmode, profiler_label); |
63f23608 | 1287 | tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno); |
86d4af74 | 1288 | mem_ref = validize_mem (gen_rtx_MEM (mode, tmp)); |
10f2b886 | 1289 | |
4c45e018 | 1290 | set_mem_alias_set (mem_ref, new_alias_set ()); |
1291 | ||
ad99e708 | 1292 | tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx, |
1293 | mem_ref, 0, OPTAB_WIDEN); | |
10f2b886 | 1294 | |
86d4af74 | 1295 | if (tmp != mem_ref) |
1296 | emit_move_insn (copy_rtx (mem_ref), tmp); | |
10f2b886 | 1297 | |
1298 | sequence = gen_sequence (); | |
1299 | end_sequence (); | |
86d4af74 | 1300 | return sequence; |
10f2b886 | 1301 | } |
1302 | ||
1303 | /* Output code for a constructor that will invoke __bb_init_func, if | |
aa40f561 | 1304 | this has not already been done. */ |
10f2b886 | 1305 | |
1306 | void | |
1307 | output_func_start_profiler () | |
1308 | { | |
1309 | tree fnname, fndecl; | |
71d9fc9b | 1310 | char *name; |
44acf429 | 1311 | char buf[20]; |
71d9fc9b | 1312 | const char *cfnname; |
10f2b886 | 1313 | rtx table_address; |
63f23608 | 1314 | enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0); |
b1ea9667 | 1315 | int save_flag_inline_functions = flag_inline_functions; |
10f2b886 | 1316 | |
1317 | /* It's either already been output, or we don't need it because we're | |
aa40f561 | 1318 | not doing profile-edges. */ |
10f2b886 | 1319 | if (! need_func_profiler) |
1320 | return; | |
1321 | ||
1322 | need_func_profiler = 0; | |
1323 | ||
1324 | /* Synthesize a constructor function to invoke __bb_init_func with a | |
aa40f561 | 1325 | pointer to this object file's profile block. */ |
10f2b886 | 1326 | |
1327 | /* Try and make a unique name given the "file function name". | |
1328 | ||
aa40f561 | 1329 | And no, I don't like this either. */ |
10f2b886 | 1330 | |
1331 | fnname = get_file_function_name ('I'); | |
1332 | cfnname = IDENTIFIER_POINTER (fnname); | |
284a7b54 | 1333 | name = concat (cfnname, "GCOV", NULL); |
10f2b886 | 1334 | fnname = get_identifier (name); |
1335 | free (name); | |
1336 | ||
1337 | fndecl = build_decl (FUNCTION_DECL, fnname, | |
1338 | build_function_type (void_type_node, NULL_TREE)); | |
43cf8c6a | 1339 | DECL_EXTERNAL (fndecl) = 0; |
86d4af74 | 1340 | |
86d4af74 | 1341 | /* It can be a static function as long as collect2 does not have |
1342 | to scan the object file to find its ctor/dtor routine. */ | |
01d15dc5 | 1343 | TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors; |
1344 | ||
1345 | TREE_USED (fndecl) = 1; | |
86d4af74 | 1346 | |
10f2b886 | 1347 | DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node); |
be2828ce | 1348 | |
20325f61 | 1349 | fndecl = (*lang_hooks.decls.pushdecl) (fndecl); |
be2828ce | 1350 | rest_of_decl_compilation (fndecl, 0, 1, 0); |
1351 | announce_function (fndecl); | |
10f2b886 | 1352 | current_function_decl = fndecl; |
be2828ce | 1353 | DECL_INITIAL (fndecl) = error_mark_node; |
125c7a9d | 1354 | make_decl_rtl (fndecl, NULL); |
10f2b886 | 1355 | init_function_start (fndecl, input_filename, lineno); |
20325f61 | 1356 | (*lang_hooks.decls.pushlevel) (0); |
10f2b886 | 1357 | expand_function_start (fndecl, 0); |
90c2be44 | 1358 | cfun->arc_profile = 0; |
10f2b886 | 1359 | |
aa40f561 | 1360 | /* Actually generate the code to call __bb_init_func. */ |
44acf429 | 1361 | ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0); |
1362 | table_address = force_reg (Pmode, | |
ec6cb94a | 1363 | gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf))); |
0ba5f96c | 1364 | emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL, |
10f2b886 | 1365 | mode, 1, table_address, Pmode); |
1366 | ||
1367 | expand_function_end (input_filename, lineno, 0); | |
20325f61 | 1368 | (*lang_hooks.decls.poplevel) (1, 0, 1); |
b1ea9667 | 1369 | |
1370 | /* Since fndecl isn't in the list of globals, it would never be emitted | |
1371 | when it's considered to be 'safe' for inlining, so turn off | |
1372 | flag_inline_functions. */ | |
1373 | flag_inline_functions = 0; | |
1374 | ||
10f2b886 | 1375 | rest_of_compilation (fndecl); |
b1ea9667 | 1376 | |
1377 | /* Reset flag_inline_functions to its original value. */ | |
1378 | flag_inline_functions = save_flag_inline_functions; | |
1379 | ||
997d68fe | 1380 | if (! quiet_flag) |
1381 | fflush (asm_out_file); | |
10f2b886 | 1382 | current_function_decl = NULL_TREE; |
1383 | ||
01d15dc5 | 1384 | if (targetm.have_ctors_dtors) |
1385 | (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0), | |
1386 | DEFAULT_INIT_PRIORITY); | |
10f2b886 | 1387 | } |
1f3233d1 | 1388 | |
1389 | #include "gt-profile.h" |