1 /* The tracer pass for the GNU compiler.
2 Contributed by Jan Hubicka, SuSE Labs.
3 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 /* This pass performs the tail duplication needed for superblock formation.
24 For more information see:
26 Design and Analysis of Profile-Based Optimization in Compaq's
27 Compilation Tools for Alpha; Journal of Instruction-Level
28 Parallelism 3 (2000) 1-25
30 Unlike Compaq's implementation we don't do the loop peeling as most
31 probably a better job can be done by a special pass and we don't
32 need to worry too much about the code size implications as the tail
33 duplicates are crossjumped again if optimizations are not
39 #include "coretypes.h"
43 #include "hard-reg-set.h"
44 #include "basic-block.h"
46 #include "cfglayout.h"
52 #include "tree-pass.h"
54 static int count_insns (basic_block
);
55 static bool ignore_bb_p (basic_block
);
56 static bool better_p (edge
, edge
);
57 static edge
find_best_successor (basic_block
);
58 static edge
find_best_predecessor (basic_block
);
59 static int find_trace (basic_block
, basic_block
*);
60 static void tail_duplicate (void);
61 static void layout_superblocks (void);
63 /* Minimal outgoing edge probability considered for superblock formation. */
64 static int probability_cutoff
;
65 static int branch_ratio_cutoff
;
67 /* Return true if BB has been seen - it is connected to some trace
70 #define seen(bb) (bb->il.rtl->visited || bb->aux)
72 /* Return true if we should ignore the basic block for purposes of tracing. */
74 ignore_bb_p (basic_block bb
)
76 if (bb
->index
< NUM_FIXED_BLOCKS
)
78 if (!maybe_hot_bb_p (bb
))
83 /* Return number of instructions in the block. */
86 count_insns (basic_block bb
)
91 for (insn
= BB_HEAD (bb
);
92 insn
!= NEXT_INSN (BB_END (bb
));
93 insn
= NEXT_INSN (insn
))
94 if (active_insn_p (insn
))
99 /* Return true if E1 is more frequent than E2. */
101 better_p (edge e1
, edge e2
)
103 if (e1
->count
!= e2
->count
)
104 return e1
->count
> e2
->count
;
105 if (e1
->src
->frequency
* e1
->probability
!=
106 e2
->src
->frequency
* e2
->probability
)
107 return (e1
->src
->frequency
* e1
->probability
108 > e2
->src
->frequency
* e2
->probability
);
109 /* This is needed to avoid changes in the decision after
111 if (e1
->src
!= e2
->src
)
112 return e1
->src
->index
> e2
->src
->index
;
113 return e1
->dest
->index
> e2
->dest
->index
;
116 /* Return most frequent successor of basic block BB. */
119 find_best_successor (basic_block bb
)
125 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
126 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
)
144 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
145 if (!best
|| better_p (e
, best
))
147 if (!best
|| ignore_bb_p (best
->src
))
149 if (EDGE_FREQUENCY (best
) * REG_BR_PROB_BASE
150 < bb
->frequency
* branch_ratio_cutoff
)
155 /* Find the trace using bb and record it in the TRACE array.
156 Return number of basic blocks recorded. */
159 find_trace (basic_block bb
, basic_block
*trace
)
165 fprintf (dump_file
, "Trace seed %i [%i]", bb
->index
, bb
->frequency
);
167 while ((e
= find_best_predecessor (bb
)) != NULL
)
169 basic_block bb2
= e
->src
;
170 if (seen (bb2
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
171 || find_best_successor (bb2
) != e
)
174 fprintf (dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
178 fprintf (dump_file
, " forward %i [%i]", bb
->index
, bb
->frequency
);
181 /* Follow the trace in forward direction. */
182 while ((e
= find_best_successor (bb
)) != NULL
)
185 if (seen (bb
) || (e
->flags
& (EDGE_DFS_BACK
| EDGE_COMPLEX
))
186 || find_best_predecessor (bb
) != e
)
189 fprintf (dump_file
, ",%i [%i]", bb
->index
, bb
->frequency
);
193 fprintf (dump_file
, "\n");
197 /* Look for basic blocks in frequency order, construct traces and tail duplicate
201 tail_duplicate (void)
203 fibnode_t
*blocks
= XCNEWVEC (fibnode_t
, last_basic_block
);
204 basic_block
*trace
= XNEWVEC (basic_block
, n_basic_blocks
);
205 int *counts
= XNEWVEC (int, last_basic_block
);
206 int ninsns
= 0, nduplicated
= 0;
207 gcov_type weighted_insns
= 0, traced_insns
= 0;
208 fibheap_t heap
= fibheap_new ();
209 gcov_type cover_insns
;
213 if (profile_info
&& flag_branch_probabilities
)
214 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
216 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
217 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
219 branch_ratio_cutoff
=
220 (REG_BR_PROB_BASE
/ 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO
));
224 int n
= count_insns (bb
);
225 if (!ignore_bb_p (bb
))
226 blocks
[bb
->index
] = fibheap_insert (heap
, -bb
->frequency
,
229 counts
[bb
->index
] = n
;
231 weighted_insns
+= n
* bb
->frequency
;
234 if (profile_info
&& flag_branch_probabilities
)
235 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK
);
237 cover_insns
= PARAM_VALUE (TRACER_DYNAMIC_COVERAGE
);
238 cover_insns
= (weighted_insns
* cover_insns
+ 50) / 100;
239 max_dup_insns
= (ninsns
* PARAM_VALUE (TRACER_MAX_CODE_GROWTH
) + 50) / 100;
241 while (traced_insns
< cover_insns
&& nduplicated
< max_dup_insns
242 && !fibheap_empty (heap
))
244 basic_block bb
= fibheap_extract_min (heap
);
250 blocks
[bb
->index
] = NULL
;
252 if (ignore_bb_p (bb
))
254 gcc_assert (!seen (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 (EDGE_COUNT (bb2
->preds
) > 1
277 && can_duplicate_block_p (bb2
))
280 basic_block old
= bb2
;
282 e
= find_edge (bb
, bb2
);
284 nduplicated
+= counts
[bb2
->index
];
285 bb2
= duplicate_block (bb2
, e
, bb
);
287 /* Reconsider the original copy of block we've duplicated.
288 Removing the most common predecessor may make it to be
291 fibheap_insert (heap
, -old
->frequency
, old
);
294 fprintf (dump_file
, "Duplicated %i as %i [%i]\n",
295 old
->index
, bb2
->index
, bb2
->frequency
);
298 bb2
->il
.rtl
->visited
= 1;
300 /* In case the trace became infrequent, stop duplicating. */
301 if (ignore_bb_p (bb
))
305 fprintf (dump_file
, " covered now %.1f\n\n",
306 traced_insns
* 100.0 / weighted_insns
);
309 fprintf (dump_file
, "Duplicated %i insns (%i%%)\n", nduplicated
,
310 nduplicated
* 100 / ninsns
);
315 fibheap_delete (heap
);
318 /* Connect the superblocks into linear sequence. 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 (void)
326 basic_block end
= single_succ (ENTRY_BLOCK_PTR
);
327 basic_block bb
= end
->next_bb
;
329 while (bb
!= EXIT_BLOCK_PTR
)
336 FOR_EACH_EDGE (e
, ei
, end
->succs
)
337 if (e
->dest
!= EXIT_BLOCK_PTR
338 && e
->dest
!= single_succ (ENTRY_BLOCK_PTR
)
339 && !e
->dest
->il
.rtl
->visited
340 && (!best
|| EDGE_FREQUENCY (e
) > EDGE_FREQUENCY (best
)))
345 end
->aux
= best
->dest
;
346 best
->dest
->il
.rtl
->visited
= 1;
349 for (; bb
!= EXIT_BLOCK_PTR
; bb
= bb
->next_bb
)
351 if (!bb
->il
.rtl
->visited
)
354 bb
->il
.rtl
->visited
= 1;
361 /* Main entry point to this file. */
366 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
368 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
371 mark_dfs_back_edges ();
373 dump_flow_info (dump_file
, dump_flags
);
375 layout_superblocks ();
376 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
379 dump_flow_info (dump_file
, dump_flags
);
381 /* Merge basic blocks in duplicated traces. */
386 gate_handle_tracer (void)
388 return (optimize
> 0 && flag_tracer
);
393 rest_of_handle_tracer (void)
396 dump_flow_info (dump_file
, dump_flags
);
401 struct tree_opt_pass pass_tracer
=
404 gate_handle_tracer
, /* gate */
405 rest_of_handle_tracer
, /* execute */
408 0, /* static_pass_number */
409 TV_TRACER
, /* tv_id */
410 0, /* properties_required */
411 0, /* properties_provided */
412 0, /* properties_destroyed */
413 0, /* todo_flags_start */
414 TODO_dump_func
, /* todo_flags_finish */