1 /* The tracer pass for the GNU compiler.
2 Contributed by Jan Hubicka, SuSE Labs.
3 Copyright (C) 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This pass performs the tail duplication needed for superblock formation.
23 For more information see:
25 Design and Analysis of Profile-Based Optimization in Compaq's
26 Compilation Tools for Alpha; Journal of Instruction-Level
27 Parallelism 3 (2000) 1-25
29 Unlike Compaq's implementation we don't do the loop peeling as most
30 probably a better job can be done by a special pass and we don't
31 need to worry too much about the code size implications as the tail
32 duplicates are crossjumped again if optimizations are not
40 #include "hard-reg-set.h"
41 #include "basic-block.h"
43 #include "cfglayout.h"
49 static int count_insns PARAMS ((basic_block));
50 static bool ignore_bb_p PARAMS ((basic_block));
51 static bool better_p PARAMS ((edge, edge));
52 static edge find_best_successor PARAMS ((basic_block));
53 static edge find_best_predecessor PARAMS ((basic_block));
54 static int find_trace PARAMS ((basic_block, basic_block *));
55 static void tail_duplicate PARAMS ((void));
56 static void layout_superblocks PARAMS ((void));
57 static bool ignore_bb_p PARAMS ((basic_block));
59 /* Minimal outgoing edge probability considered for superblock formation. */
60 static int probability_cutoff;
61 static int branch_ratio_cutoff;
63 /* Return true if BB has been seen - it is connected to some trace
66 #define seen(bb) (RBI (bb)->visited || RBI (bb)->next)
68 /* Return true if we should ignore the basic block for purposes of tracing. */
75 if (!maybe_hot_bb_p (bb))
80 /* Return number of instructions in the block. */
89 for (insn = bb->head; insn != NEXT_INSN (bb->end); insn = NEXT_INSN (insn))
90 if (active_insn_p (insn))
95 /* Return true if E1 is more frequent than E2. */
100 if (e1->count != e2->count)
101 return e1->count > e2->count;
102 if (e1->src->frequency * e1->probability !=
103 e2->src->frequency * e2->probability)
104 return (e1->src->frequency * e1->probability
105 > e2->src->frequency * e2->probability);
106 /* This is needed to avoid changes in the decision after
108 if (e1->src != e2->src)
109 return e1->src->index > e2->src->index;
110 return e1->dest->index > e2->dest->index;
113 /* Return most frequent successor of basic block BB. */
116 find_best_successor (bb)
122 for (e = bb->succ; e; e = e->succ_next)
123 if (!best || better_p (e, best))
125 if (!best || ignore_bb_p (best->dest))
127 if (best->probability <= probability_cutoff)
132 /* Return most frequent predecessor of basic block BB. */
135 find_best_predecessor (bb)
141 for (e = bb->pred; e; e = e->pred_next)
142 if (!best || better_p (e, best))
144 if (!best || ignore_bb_p (best->src))
146 if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
147 < bb->frequency * branch_ratio_cutoff)
152 /* Find the trace using bb and record it in the TRACE array.
153 Return number of basic blocks recorded. */
156 find_trace (bb, trace)
164 fprintf (rtl_dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
166 while ((e = find_best_predecessor (bb)) != NULL)
168 basic_block bb2 = e->src;
169 if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
170 || find_best_successor (bb2) != e)
173 fprintf (rtl_dump_file, ",%i [%i]", bb->index, bb->frequency);
177 fprintf (rtl_dump_file, " forward %i [%i]", bb->index, bb->frequency);
180 /* Follow the trace in forward direction. */
181 while ((e = find_best_successor (bb)) != NULL)
184 if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
185 || find_best_predecessor (bb) != e)
188 fprintf (rtl_dump_file, ",%i [%i]", bb->index, bb->frequency);
192 fprintf (rtl_dump_file, "\n");
196 /* Look for basic blocks in frequency order, construct traces and tail duplicate
202 fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
203 basic_block *trace = xmalloc (sizeof (basic_block) * n_basic_blocks);
204 int *counts = xmalloc (sizeof (int) * last_basic_block);
205 int ninsns = 0, nduplicated = 0;
206 gcov_type weighted_insns = 0, traced_insns = 0;
207 fibheap_t heap = fibheap_new ();
208 gcov_type cover_insns;
212 if (profile_info.count_profiles_merged && flag_branch_probabilities)
213 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
215 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
216 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
218 branch_ratio_cutoff =
219 (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
223 int n = count_insns (bb);
224 if (!ignore_bb_p (bb))
225 blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
228 counts [bb->index] = n;
230 weighted_insns += n * bb->frequency;
233 if (profile_info.count_profiles_merged && flag_branch_probabilities)
234 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
236 cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
237 cover_insns = (weighted_insns * cover_insns + 50) / 100;
238 max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
240 while (traced_insns < cover_insns && nduplicated < max_dup_insns
241 && !fibheap_empty (heap))
243 basic_block bb = fibheap_extract_min (heap);
249 blocks[bb->index] = NULL;
251 if (ignore_bb_p (bb))
256 n = find_trace (bb, trace);
259 traced_insns += bb->frequency * counts [bb->index];
260 if (blocks[bb->index])
262 fibheap_delete_node (heap, blocks[bb->index]);
263 blocks[bb->index] = NULL;
266 for (pos = 1; pos < n; pos++)
268 basic_block bb2 = trace[pos];
270 if (blocks[bb2->index])
272 fibheap_delete_node (heap, blocks[bb2->index]);
273 blocks[bb2->index] = NULL;
275 traced_insns += bb2->frequency * counts [bb2->index];
276 if (bb2->pred && bb2->pred->pred_next
277 && cfg_layout_can_duplicate_bb_p (bb2))
280 basic_block old = bb2;
284 nduplicated += counts [bb2->index];
285 bb2 = cfg_layout_duplicate_bb (bb2, e);
287 /* Reconsider the original copy of block we've duplicated.
288 Removing the most common predecesor may make it to be
291 fibheap_insert (heap, -old->frequency, old);
294 fprintf (rtl_dump_file, "Duplicated %i as %i [%i]\n",
295 old->index, bb2->index, bb2->frequency);
297 RBI (bb)->next = bb2;
298 RBI (bb2)->visited = 1;
300 /* In case the trace became infrequent, stop duplicating. */
301 if (ignore_bb_p (bb))
305 fprintf (rtl_dump_file, " covered now %.1f\n\n",
306 traced_insns * 100.0 / weighted_insns);
309 fprintf (rtl_dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
310 nduplicated * 100 / ninsns);
315 fibheap_delete (heap);
318 /* Connect the superblocks into linear seuqence. At the moment we attempt to keep
319 the original order as much as possible, but the algorithm may be made smarter
320 later if needed. BB reordering pass should void most of the benefits of such
324 layout_superblocks ()
326 basic_block end = ENTRY_BLOCK_PTR->succ->dest;
327 basic_block bb = ENTRY_BLOCK_PTR->succ->dest->next_bb;
329 while (bb != EXIT_BLOCK_PTR)
332 while (RBI (end)->next)
333 end = RBI (end)->next;
335 for (e = end->succ; e; e = e->succ_next)
336 if (e->dest != EXIT_BLOCK_PTR
337 && e->dest != ENTRY_BLOCK_PTR->succ->dest
338 && !RBI (e->dest)->visited
339 && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
344 RBI (end)->next = best->dest;
345 RBI (best->dest)->visited = 1;
348 for (; bb != EXIT_BLOCK_PTR; bb=bb->next_bb)
350 if (!RBI (bb)->visited)
352 RBI (end)->next = bb;
353 RBI (bb)->visited = 1;
360 /* Main entry point to this file. */
365 if (n_basic_blocks <= 1)
367 cfg_layout_initialize ();
368 mark_dfs_back_edges ();
370 dump_flow_info (rtl_dump_file);
372 layout_superblocks ();
374 dump_flow_info (rtl_dump_file);
375 cfg_layout_finalize ();
376 /* Merge basic blocks in duplicated traces. */
377 cleanup_cfg (CLEANUP_EXPENSIVE);