OSDN Git Service

4c8d06374d9f34215079f4016fa4df8e4c79c879
[pf3gnuchains/gcc-fork.git] / gcc / tracer.c
1 /* The tracer pass for the GNU compiler.
2    Contributed by Jan Hubicka, SuSE Labs.
3    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5    This file is part of GCC.
6
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)
10    any later version.
11
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.
16
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, 51 Franklin Street, Fifth Floor, Boston, MA
20    02110-1301, USA.  */
21
22 /* This pass performs the tail duplication needed for superblock formation.
23    For more information see:
24
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
28
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
33    performed.  */
34
35
36 #include "config.h"
37 #include "system.h"
38 #include "coretypes.h"
39 #include "tm.h"
40 #include "tree.h"
41 #include "rtl.h"
42 #include "hard-reg-set.h"
43 #include "basic-block.h"
44 #include "output.h"
45 #include "cfglayout.h"
46 #include "fibheap.h"
47 #include "flags.h"
48 #include "timevar.h"
49 #include "params.h"
50 #include "coverage.h"
51 #include "tree-pass.h"
52
53 static int count_insns (basic_block);
54 static bool ignore_bb_p (basic_block);
55 static bool better_p (edge, edge);
56 static edge find_best_successor (basic_block);
57 static edge find_best_predecessor (basic_block);
58 static int find_trace (basic_block, basic_block *);
59 static void tail_duplicate (void);
60 static void layout_superblocks (void);
61
62 /* Minimal outgoing edge probability considered for superblock formation.  */
63 static int probability_cutoff;
64 static int branch_ratio_cutoff;
65
66 /* Return true if BB has been seen - it is connected to some trace
67    already.  */
68
69 #define seen(bb) (bb->il.rtl->visited || bb->aux)
70
71 /* Return true if we should ignore the basic block for purposes of tracing.  */
72 static bool
73 ignore_bb_p (basic_block bb)
74 {
75   if (bb->index < NUM_FIXED_BLOCKS)
76     return true;
77   if (!maybe_hot_bb_p (bb))
78     return true;
79   return false;
80 }
81
82 /* Return number of instructions in the block.  */
83
84 static int
85 count_insns (basic_block bb)
86 {
87   rtx insn;
88   int n = 0;
89
90   for (insn = BB_HEAD (bb);
91        insn != NEXT_INSN (BB_END (bb));
92        insn = NEXT_INSN (insn))
93     if (active_insn_p (insn))
94       n++;
95   return n;
96 }
97
98 /* Return true if E1 is more frequent than E2.  */
99 static bool
100 better_p (edge e1, edge e2)
101 {
102   if (e1->count != e2->count)
103     return e1->count > e2->count;
104   if (e1->src->frequency * e1->probability !=
105       e2->src->frequency * e2->probability)
106     return (e1->src->frequency * e1->probability
107             > e2->src->frequency * e2->probability);
108   /* This is needed to avoid changes in the decision after
109      CFG is modified.  */
110   if (e1->src != e2->src)
111     return e1->src->index > e2->src->index;
112   return e1->dest->index > e2->dest->index;
113 }
114
115 /* Return most frequent successor of basic block BB.  */
116
117 static edge
118 find_best_successor (basic_block bb)
119 {
120   edge e;
121   edge best = NULL;
122   edge_iterator ei;
123
124   FOR_EACH_EDGE (e, ei, bb->succs)
125     if (!best || better_p (e, best))
126       best = e;
127   if (!best || ignore_bb_p (best->dest))
128     return NULL;
129   if (best->probability <= probability_cutoff)
130     return NULL;
131   return best;
132 }
133
134 /* Return most frequent predecessor of basic block BB.  */
135
136 static edge
137 find_best_predecessor (basic_block bb)
138 {
139   edge e;
140   edge best = NULL;
141   edge_iterator ei;
142
143   FOR_EACH_EDGE (e, ei, bb->preds)
144     if (!best || better_p (e, best))
145       best = e;
146   if (!best || ignore_bb_p (best->src))
147     return NULL;
148   if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
149       < bb->frequency * branch_ratio_cutoff)
150     return NULL;
151   return best;
152 }
153
154 /* Find the trace using bb and record it in the TRACE array.
155    Return number of basic blocks recorded.  */
156
157 static int
158 find_trace (basic_block bb, basic_block *trace)
159 {
160   int i = 0;
161   edge e;
162
163   if (dump_file)
164     fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
165
166   while ((e = find_best_predecessor (bb)) != NULL)
167     {
168       basic_block bb2 = e->src;
169       if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
170           || find_best_successor (bb2) != e)
171         break;
172       if (dump_file)
173         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
174       bb = bb2;
175     }
176   if (dump_file)
177     fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
178   trace[i++] = bb;
179
180   /* Follow the trace in forward direction.  */
181   while ((e = find_best_successor (bb)) != NULL)
182     {
183       bb = e->dest;
184       if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
185           || find_best_predecessor (bb) != e)
186         break;
187       if (dump_file)
188         fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
189       trace[i++] = bb;
190     }
191   if (dump_file)
192     fprintf (dump_file, "\n");
193   return i;
194 }
195
196 /* Look for basic blocks in frequency order, construct traces and tail duplicate
197    if profitable.  */
198
199 static void
200 tail_duplicate (void)
201 {
202   fibnode_t *blocks = XCNEWVEC (fibnode_t, last_basic_block);
203   basic_block *trace = XNEWVEC (basic_block, n_basic_blocks);
204   int *counts = XNEWVEC (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;
209   int max_dup_insns;
210   basic_block bb;
211
212   if (profile_info && flag_branch_probabilities)
213     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
214   else
215     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
216   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
217
218   branch_ratio_cutoff =
219     (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
220
221   FOR_EACH_BB (bb)
222     {
223       int n = count_insns (bb);
224       if (!ignore_bb_p (bb))
225         blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
226                                             bb);
227
228       counts [bb->index] = n;
229       ninsns += n;
230       weighted_insns += n * bb->frequency;
231     }
232
233   if (profile_info && flag_branch_probabilities)
234     cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
235   else
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;
239
240   while (traced_insns < cover_insns && nduplicated < max_dup_insns
241          && !fibheap_empty (heap))
242     {
243       basic_block bb = fibheap_extract_min (heap);
244       int n, pos;
245
246       if (!bb)
247         break;
248
249       blocks[bb->index] = NULL;
250
251       if (ignore_bb_p (bb))
252         continue;
253       gcc_assert (!seen (bb));
254
255       n = find_trace (bb, trace);
256
257       bb = trace[0];
258       traced_insns += bb->frequency * counts [bb->index];
259       if (blocks[bb->index])
260         {
261           fibheap_delete_node (heap, blocks[bb->index]);
262           blocks[bb->index] = NULL;
263         }
264
265       for (pos = 1; pos < n; pos++)
266         {
267           basic_block bb2 = trace[pos];
268
269           if (blocks[bb2->index])
270             {
271               fibheap_delete_node (heap, blocks[bb2->index]);
272               blocks[bb2->index] = NULL;
273             }
274           traced_insns += bb2->frequency * counts [bb2->index];
275           if (EDGE_COUNT (bb2->preds) > 1
276               && can_duplicate_block_p (bb2))
277             {
278               edge e;
279               basic_block old = bb2;
280
281               e = find_edge (bb, bb2);
282
283               nduplicated += counts [bb2->index];
284               bb2 = duplicate_block (bb2, e, bb);
285
286               /* Reconsider the original copy of block we've duplicated.
287                  Removing the most common predecessor may make it to be
288                  head.  */
289               blocks[old->index] =
290                 fibheap_insert (heap, -old->frequency, old);
291
292               if (dump_file)
293                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
294                          old->index, bb2->index, bb2->frequency);
295             }
296           bb->aux = bb2;
297           bb2->il.rtl->visited = 1;
298           bb = bb2;
299           /* In case the trace became infrequent, stop duplicating.  */
300           if (ignore_bb_p (bb))
301             break;
302         }
303       if (dump_file)
304         fprintf (dump_file, " covered now %.1f\n\n",
305                  traced_insns * 100.0 / weighted_insns);
306     }
307   if (dump_file)
308     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
309              nduplicated * 100 / ninsns);
310
311   free (blocks);
312   free (trace);
313   free (counts);
314   fibheap_delete (heap);
315 }
316
317 /* Connect the superblocks into linear sequence.  At the moment we attempt to keep
318    the original order as much as possible, but the algorithm may be made smarter
319    later if needed.  BB reordering pass should void most of the benefits of such
320    change though.  */
321
322 static void
323 layout_superblocks (void)
324 {
325   basic_block end = single_succ (ENTRY_BLOCK_PTR);
326   basic_block bb = end->next_bb;
327
328   while (bb != EXIT_BLOCK_PTR)
329     {
330       edge_iterator ei;
331       edge e, best = NULL;
332       while (end->aux)
333         end = end->aux;
334
335       FOR_EACH_EDGE (e, ei, end->succs)
336         if (e->dest != EXIT_BLOCK_PTR
337             && e->dest != single_succ (ENTRY_BLOCK_PTR)
338             && !e->dest->il.rtl->visited
339             && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
340           best = e;
341
342       if (best)
343         {
344           end->aux = best->dest;
345           best->dest->il.rtl->visited = 1;
346         }
347       else
348         for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
349           {
350             if (!bb->il.rtl->visited)
351               {
352                 end->aux = bb;
353                 bb->il.rtl->visited = 1;
354                 break;
355               }
356           }
357     }
358 }
359
360 /* Main entry point to this file.  FLAGS is the set of flags to pass
361    to cfg_layout_initialize().  */
362
363 void
364 tracer (unsigned int flags)
365 {
366   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
367     return;
368
369   cfg_layout_initialize (flags);
370   mark_dfs_back_edges ();
371   if (dump_file)
372     dump_flow_info (dump_file, dump_flags);
373   tail_duplicate ();
374   layout_superblocks ();
375   if (dump_file)
376     dump_flow_info (dump_file, dump_flags);
377   cfg_layout_finalize ();
378
379   /* Merge basic blocks in duplicated traces.  */
380   cleanup_cfg (CLEANUP_EXPENSIVE);
381 }
382 \f
383 static bool
384 gate_handle_tracer (void)
385 {
386   return (optimize > 0 && flag_tracer);
387 }
388
389 /* Run tracer.  */
390 static unsigned int
391 rest_of_handle_tracer (void)
392 {
393   if (dump_file)
394     dump_flow_info (dump_file, dump_flags);
395   tracer (0);
396   reg_scan (get_insns (), max_reg_num ());
397   return 0;
398 }
399
400 struct tree_opt_pass pass_tracer =
401 {
402   "tracer",                             /* name */
403   gate_handle_tracer,                   /* gate */
404   rest_of_handle_tracer,                /* execute */
405   NULL,                                 /* sub */
406   NULL,                                 /* next */
407   0,                                    /* static_pass_number */
408   TV_TRACER,                            /* tv_id */
409   0,                                    /* properties_required */
410   0,                                    /* properties_provided */
411   0,                                    /* properties_destroyed */
412   0,                                    /* todo_flags_start */
413   TODO_dump_func,                       /* todo_flags_finish */
414   'T'                                   /* letter */
415 };
416