1 /* The tracer pass for the GNU compiler.
2 Contributed by Jan Hubicka, SuSE Labs.
3 Copyright (C) 2001, 2002, 2003, 2004 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"
52 static int count_insns (basic_block
);
53 static bool ignore_bb_p (basic_block
);
54 static bool better_p (edge
, edge
);
55 static edge
find_best_successor (basic_block
);
56 static edge
find_best_predecessor (basic_block
);
57 static int find_trace (basic_block
, basic_block
*);
58 static void tail_duplicate (void);
59 static void layout_superblocks (void);
61 /* Minimal outgoing edge probability considered for superblock formation. */
62 static int probability_cutoff
;
63 static int branch_ratio_cutoff
;
65 /* Return true if BB has been seen - it is connected to some trace
68 #define seen(bb) (bb->rbi->visited || bb->rbi->next)
70 /* Return true if we should ignore the basic block for purposes of tracing. */
72 ignore_bb_p (basic_block bb
)
76 if (!maybe_hot_bb_p (bb
))
81 /* Return number of instructions in the block. */
84 count_insns (basic_block bb
)
89 for (insn
= BB_HEAD (bb
);
90 insn
!= NEXT_INSN (BB_END (bb
));
91 insn
= NEXT_INSN (insn
))
92 if (active_insn_p (insn
))
97 /* Return true if E1 is more frequent than E2. */
99 better_p (edge e1
, edge e2
)
101 if (e1
->count
!= e2
->count
)
102 return e1
->count
> e2
->count
;
103 if (e1
->src
->frequency
* e1
->probability
!=
104 e2
->src
->frequency
* e2
->probability
)
105 return (e1
->src
->frequency
* e1
->probability
106 > e2
->src
->frequency
* e2
->probability
);
107 /* This is needed to avoid changes in the decision after
109 if (e1
->src
!= e2
->src
)
110 return e1
->src
->index
> e2
->src
->index
;
111 return e1
->dest
->index
> e2
->dest
->index
;
114 /* Return most frequent successor of basic block BB. */
117 find_best_successor (basic_block bb
)
122 FOR_EACH_EDGE (e
, bb
->succs
)
124 if (!best
|| better_p (e
, best
))
128 if (!best
|| ignore_bb_p (best
->dest
))
130 if (best
->probability
<= probability_cutoff
)
135 /* Return most frequent predecessor of basic block BB. */
138 find_best_predecessor (basic_block bb
)
143 FOR_EACH_EDGE (e
, bb
->preds
)
145 if (!best
|| better_p (e
, best
))
149 if (!best
|| ignore_bb_p (best
->src
))
151 if (EDGE_FREQUENCY (best
) * REG_BR_PROB_BASE
152 < bb
->frequency
* branch_ratio_cutoff
)
157 /* Find the trace using bb and record it in the TRACE array.
158 Return number of basic blocks recorded. */
161 find_trace (basic_block bb
, basic_block
*trace
)
167 fprintf (dump_file
, "Trace seed %i [%i]", bb
->index
, bb
->frequency
);
169 while ((e
= find_best_predecessor (bb
)) != NULL
)
171 basic_block bb2
= e
->src
;
172 if (seen (bb2
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
173 || find_best_successor (bb2
) != e
)
176 fprintf (dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
180 fprintf (dump_file
, " forward %i [%i]", bb
->index
, bb
->frequency
);
183 /* Follow the trace in forward direction. */
184 while ((e
= find_best_successor (bb
)) != NULL
)
187 if (seen (bb
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
188 || find_best_predecessor (bb
) != e
)
191 fprintf (dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
195 fprintf (dump_file
, "\n");
199 /* Look for basic blocks in frequency order, construct traces and tail duplicate
203 tail_duplicate (void)
205 fibnode_t
*blocks
= xcalloc (last_basic_block
, sizeof (fibnode_t
));
206 basic_block
*trace
= xmalloc (sizeof (basic_block
) * n_basic_blocks
);
207 int *counts
= xmalloc (sizeof (int) * last_basic_block
);
208 int ninsns
= 0, nduplicated
= 0;
209 gcov_type weighted_insns
= 0, traced_insns
= 0;
210 fibheap_t heap
= fibheap_new ();
211 gcov_type cover_insns
;
215 if (profile_info
&& flag_branch_probabilities
)
216 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
218 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
219 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
221 branch_ratio_cutoff
=
222 (REG_BR_PROB_BASE
/ 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO
));
226 int n
= count_insns (bb
);
227 if (!ignore_bb_p (bb
))
228 blocks
[bb
->index
] = fibheap_insert (heap
, -bb
->frequency
,
231 counts
[bb
->index
] = n
;
233 weighted_insns
+= n
* bb
->frequency
;
236 if (profile_info
&& flag_branch_probabilities
)
237 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK
);
239 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE
);
240 cover_insns
= (weighted_insns
* cover_insns
+ 50) / 100;
241 max_dup_insns
= (ninsns
* PARAM_VALUE (TRACER_MAX_CODE_GROWTH
) + 50) / 100;
243 while (traced_insns
< cover_insns
&& nduplicated
< max_dup_insns
244 && !fibheap_empty (heap
))
246 basic_block bb
= fibheap_extract_min (heap
);
252 blocks
[bb
->index
] = NULL
;
254 if (ignore_bb_p (bb
))
259 n
= find_trace (bb
, trace
);
262 traced_insns
+= bb
->frequency
* counts
[bb
->index
];
263 if (blocks
[bb
->index
])
265 fibheap_delete_node (heap
, blocks
[bb
->index
]);
266 blocks
[bb
->index
] = NULL
;
269 for (pos
= 1; pos
< n
; pos
++)
271 basic_block bb2
= trace
[pos
];
273 if (blocks
[bb2
->index
])
275 fibheap_delete_node (heap
, blocks
[bb2
->index
]);
276 blocks
[bb2
->index
] = NULL
;
278 traced_insns
+= bb2
->frequency
* counts
[bb2
->index
];
279 if (EDGE_COUNT (bb2
->preds
) > 1
280 && can_duplicate_block_p (bb2
))
283 basic_block old
= bb2
;
285 FOR_EACH_EDGE (e
, bb2
->preds
)
292 nduplicated
+= counts
[bb2
->index
];
293 bb2
= duplicate_block (bb2
, e
);
295 /* Reconsider the original copy of block we've duplicated.
296 Removing the most common predecessor may make it to be
299 fibheap_insert (heap
, -old
->frequency
, old
);
302 fprintf (dump_file
, "Duplicated %i as %i [%i]\n",
303 old
->index
, bb2
->index
, bb2
->frequency
);
306 bb2
->rbi
->visited
= 1;
308 /* In case the trace became infrequent, stop duplicating. */
309 if (ignore_bb_p (bb
))
313 fprintf (dump_file
, " covered now %.1f\n\n",
314 traced_insns
* 100.0 / weighted_insns
);
317 fprintf (dump_file
, "Duplicated %i insns (%i%%)\n", nduplicated
,
318 nduplicated
* 100 / ninsns
);
323 fibheap_delete (heap
);
326 /* Connect the superblocks into linear sequence. At the moment we attempt to keep
327 the original order as much as possible, but the algorithm may be made smarter
328 later if needed. BB reordering pass should void most of the benefits of such
332 layout_superblocks (void)
334 basic_block end
= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
;
335 basic_block bb
= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
->next_bb
;
337 while (bb
!= EXIT_BLOCK_PTR
)
340 while (end
->rbi
->next
)
341 end
= end
->rbi
->next
;
343 FOR_EACH_EDGE (e
, end
->succs
)
345 if (e
->dest
!= EXIT_BLOCK_PTR
346 && e
->dest
!= EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->dest
347 && !e
->dest
->rbi
->visited
348 && (!best
|| EDGE_FREQUENCY (e
) > EDGE_FREQUENCY (best
)))
355 end
->rbi
->next
= best
->dest
;
356 best
->dest
->rbi
->visited
= 1;
359 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
361 if (!bb
->rbi
->visited
)
364 bb
->rbi
->visited
= 1;
371 /* Main entry point to this file. FLAGS is the set of flags to pass
372 to cfg_layout_initialize(). */
375 tracer (unsigned int flags
)
377 if (n_basic_blocks
<= 1)
380 timevar_push (TV_TRACER
);
382 cfg_layout_initialize (flags
);
383 mark_dfs_back_edges ();
385 dump_flow_info (dump_file
);
387 layout_superblocks ();
389 dump_flow_info (dump_file
);
390 cfg_layout_finalize ();
392 /* Merge basic blocks in duplicated traces. */
393 cleanup_cfg (CLEANUP_EXPENSIVE
);
395 timevar_pop (TV_TRACER
);