1 /* The tracer pass for the GNU compiler.
2 Contributed by Jan Hubicka, SuSE Labs.
3 Copyright (C) 2001, 2002, 2003 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
38 #include "coretypes.h"
42 #include "hard-reg-set.h"
43 #include "basic-block.h"
45 #include "cfglayout.h"
51 static int count_insns (basic_block
);
52 static bool ignore_bb_p (basic_block
);
53 static bool better_p (edge
, edge
);
54 static edge
find_best_successor (basic_block
);
55 static edge
find_best_predecessor (basic_block
);
56 static int find_trace (basic_block
, basic_block
*);
57 static void tail_duplicate (void);
58 static void layout_superblocks (void);
60 /* Minimal outgoing edge probability considered for superblock formation. */
61 static int probability_cutoff
;
62 static int branch_ratio_cutoff
;
64 /* Return true if BB has been seen - it is connected to some trace
67 #define seen(bb) (bb->rbi->visited || bb->rbi->next)
69 /* Return true if we should ignore the basic block for purposes of tracing. */
71 ignore_bb_p (basic_block bb
)
75 if (!maybe_hot_bb_p (bb
))
80 /* Return number of instructions in the block. */
83 count_insns (basic_block bb
)
88 for (insn
= BB_HEAD (bb
);
89 insn
!= NEXT_INSN (BB_END (bb
));
90 insn
= NEXT_INSN (insn
))
91 if (active_insn_p (insn
))
96 /* Return true if E1 is more frequent than E2. */
98 better_p (edge e1
, edge 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 (basic_block bb
)
121 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
122 if (!best
|| better_p (e
, best
))
124 if (!best
|| ignore_bb_p (best
->dest
))
126 if (best
->probability
<= probability_cutoff
)
131 /* Return most frequent predecessor of basic block BB. */
134 find_best_predecessor (basic_block bb
)
139 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
140 if (!best
|| better_p (e
, best
))
142 if (!best
|| ignore_bb_p (best
->src
))
144 if (EDGE_FREQUENCY (best
) * REG_BR_PROB_BASE
145 < bb
->frequency
* branch_ratio_cutoff
)
150 /* Find the trace using bb and record it in the TRACE array.
151 Return number of basic blocks recorded. */
154 find_trace (basic_block bb
, basic_block
*trace
)
160 fprintf (rtl_dump_file
, "Trace seed %i [%i]", bb
->index
, bb
->frequency
);
162 while ((e
= find_best_predecessor (bb
)) != NULL
)
164 basic_block bb2
= e
->src
;
165 if (seen (bb2
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
166 || find_best_successor (bb2
) != e
)
169 fprintf (rtl_dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
173 fprintf (rtl_dump_file
, " forward %i [%i]", bb
->index
, bb
->frequency
);
176 /* Follow the trace in forward direction. */
177 while ((e
= find_best_successor (bb
)) != NULL
)
180 if (seen (bb
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
181 || find_best_predecessor (bb
) != e
)
184 fprintf (rtl_dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
188 fprintf (rtl_dump_file
, "\n");
192 /* Look for basic blocks in frequency order, construct traces and tail duplicate
196 tail_duplicate (void)
198 fibnode_t
*blocks
= xcalloc (last_basic_block
, sizeof (fibnode_t
));
199 basic_block
*trace
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
200 int *counts
= xmalloc (sizeof (int) * last_basic_block
);
201 int ninsns
= 0, nduplicated
= 0;
202 gcov_type weighted_insns
= 0, traced_insns
= 0;
203 fibheap_t heap
= fibheap_new ();
204 gcov_type cover_insns
;
208 if (profile_info
&& flag_branch_probabilities
)
209 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
211 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
212 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
214 branch_ratio_cutoff
=
215 (REG_BR_PROB_BASE
/ 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO
));
219 int n
= count_insns (bb
);
220 if (!ignore_bb_p (bb
))
221 blocks
[bb
->index
] = fibheap_insert (heap
, -bb
->frequency
,
224 counts
[bb
->index
] = n
;
226 weighted_insns
+= n
* bb
->frequency
;
229 if (profile_info
&& flag_branch_probabilities
)
230 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK
);
232 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE
);
233 cover_insns
= (weighted_insns
* cover_insns
+ 50) / 100;
234 max_dup_insns
= (ninsns
* PARAM_VALUE (TRACER_MAX_CODE_GROWTH
) + 50) / 100;
236 while (traced_insns
< cover_insns
&& nduplicated
< max_dup_insns
237 && !fibheap_empty (heap
))
239 basic_block bb
= fibheap_extract_min (heap
);
245 blocks
[bb
->index
] = NULL
;
247 if (ignore_bb_p (bb
))
252 n
= find_trace (bb
, trace
);
255 traced_insns
+= bb
->frequency
* counts
[bb
->index
];
256 if (blocks
[bb
->index
])
258 fibheap_delete_node (heap
, blocks
[bb
->index
]);
259 blocks
[bb
->index
] = NULL
;
262 for (pos
= 1; pos
< n
; pos
++)
264 basic_block bb2
= trace
[pos
];
266 if (blocks
[bb2
->index
])
268 fibheap_delete_node (heap
, blocks
[bb2
->index
]);
269 blocks
[bb2
->index
] = NULL
;
271 traced_insns
+= bb2
->frequency
* counts
[bb2
->index
];
272 if (bb2
->pred
&& bb2
->pred
->pred_next
273 && cfg_layout_can_duplicate_bb_p (bb2
))
276 basic_block old
= bb2
;
280 nduplicated
+= counts
[bb2
->index
];
281 bb2
= cfg_layout_duplicate_bb (bb2
, e
);
283 /* Reconsider the original copy of block we've duplicated.
284 Removing the most common predecessor may make it to be
287 fibheap_insert (heap
, -old
->frequency
, old
);
290 fprintf (rtl_dump_file
, "Duplicated %i as %i [%i]\n",
291 old
->index
, bb2
->index
, bb2
->frequency
);
294 bb2
->rbi
->visited
= 1;
296 /* In case the trace became infrequent, stop duplicating. */
297 if (ignore_bb_p (bb
))
301 fprintf (rtl_dump_file
, " covered now %.1f\n\n",
302 traced_insns
* 100.0 / weighted_insns
);
305 fprintf (rtl_dump_file
, "Duplicated %i insns (%i%%)\n", nduplicated
,
306 nduplicated
* 100 / ninsns
);
311 fibheap_delete (heap
);
314 /* Connect the superblocks into linear sequence. At the moment we attempt to keep
315 the original order as much as possible, but the algorithm may be made smarter
316 later if needed. BB reordering pass should void most of the benefits of such
320 layout_superblocks (void)
322 basic_block end
= ENTRY_BLOCK_PTR
->succ
->dest
;
323 basic_block bb
= ENTRY_BLOCK_PTR
->succ
->dest
->next_bb
;
325 while (bb
!= EXIT_BLOCK_PTR
)
328 while (end
->rbi
->next
)
329 end
= end
->rbi
->next
;
331 for (e
= end
->succ
; e
; e
= e
->succ_next
)
332 if (e
->dest
!= EXIT_BLOCK_PTR
333 && e
->dest
!= ENTRY_BLOCK_PTR
->succ
->dest
334 && !e
->dest
->rbi
->visited
335 && (!best
|| EDGE_FREQUENCY (e
) > EDGE_FREQUENCY (best
)))
340 end
->rbi
->next
= best
->dest
;
341 best
->dest
->rbi
->visited
= 1;
344 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
346 if (!bb
->rbi
->visited
)
349 bb
->rbi
->visited
= 1;
356 /* Main entry point to this file. */
361 if (n_basic_blocks
<= 1)
363 cfg_layout_initialize ();
364 mark_dfs_back_edges ();
366 dump_flow_info (rtl_dump_file
);
368 layout_superblocks ();
370 dump_flow_info (rtl_dump_file
);
371 cfg_layout_finalize ();
372 /* Merge basic blocks in duplicated traces. */
373 cleanup_cfg (CLEANUP_EXPENSIVE
);