Branch data Line data Source code
1 : : /* The tracer pass for the GNU compiler.
2 : : Contributed by Jan Hubicka, SuSE Labs.
3 : : Adapted to work on GIMPLE instead of RTL by Robert Kidd, UIUC.
4 : : Copyright (C) 2001-2024 Free Software Foundation, Inc.
5 : :
6 : : This file is part of GCC.
7 : :
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 3, or (at your option)
11 : : any later version.
12 : :
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.
17 : :
18 : : You should have received a copy of the GNU General Public License
19 : : along with GCC; see the file COPYING3. If not see
20 : : <http://www.gnu.org/licenses/>. */
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 "backend.h"
40 : : #include "rtl.h"
41 : : #include "tree.h"
42 : : #include "gimple.h"
43 : : #include "cfghooks.h"
44 : : #include "tree-pass.h"
45 : : #include "profile.h"
46 : : #include "cfganal.h"
47 : : #include "gimple-iterator.h"
48 : : #include "tree-cfg.h"
49 : : #include "tree-ssa.h"
50 : : #include "tree-inline.h"
51 : : #include "cfgloop.h"
52 : : #include "alloc-pool.h"
53 : : #include "fibonacci_heap.h"
54 : : #include "tracer.h"
55 : :
56 : : static void analyze_bb (basic_block, int *);
57 : : static bool better_p (const_edge, const_edge);
58 : : static edge find_best_successor (basic_block);
59 : : static edge find_best_predecessor (basic_block);
60 : : static int find_trace (basic_block, basic_block *);
61 : :
62 : : /* Minimal outgoing edge probability considered for superblock formation. */
63 : : static int probability_cutoff;
64 : : static int branch_ratio_cutoff;
65 : :
66 : : /* A bit BB->index is set if BB has already been seen, i.e. it is
67 : : connected to some trace already. */
68 : : static sbitmap bb_seen;
69 : :
70 : : static inline void
71 : 67997 : mark_bb_seen (basic_block bb)
72 : : {
73 : 67997 : unsigned int size = SBITMAP_SIZE (bb_seen);
74 : :
75 : 67997 : if ((unsigned int)bb->index >= size)
76 : 0 : bb_seen = sbitmap_resize (bb_seen, size * 2, 0);
77 : :
78 : 67997 : bitmap_set_bit (bb_seen, bb->index);
79 : 67997 : }
80 : :
81 : : static inline bool
82 : 283526 : bb_seen_p (basic_block bb)
83 : : {
84 : 283526 : return bitmap_bit_p (bb_seen, bb->index);
85 : : }
86 : :
87 : : static sbitmap can_duplicate_bb;
88 : :
89 : : /* Cache VAL as value of can_duplicate_bb_p for BB. */
90 : : static inline void
91 : 214877 : cache_can_duplicate_bb_p (const_basic_block bb, bool val)
92 : : {
93 : 214877 : if (val)
94 : 214856 : bitmap_set_bit (can_duplicate_bb, bb->index);
95 : 214877 : }
96 : :
97 : : /* Return cached value of can_duplicate_bb_p for BB. */
98 : : static bool
99 : 812139 : cached_can_duplicate_bb_p (const_basic_block bb)
100 : : {
101 : 812139 : if (can_duplicate_bb)
102 : : {
103 : 764103 : unsigned int size = SBITMAP_SIZE (can_duplicate_bb);
104 : 764103 : if ((unsigned int)bb->index < size)
105 : 748148 : return bitmap_bit_p (can_duplicate_bb, bb->index);
106 : :
107 : : /* Assume added bb's should not be duplicated. */
108 : : return false;
109 : : }
110 : :
111 : 48036 : return can_duplicate_block_p (bb);
112 : : }
113 : :
114 : : /* Return true if we should ignore the basic block for purposes of tracing. */
115 : : bool
116 : 872675 : ignore_bb_p (const_basic_block bb)
117 : : {
118 : 872675 : if (bb->index < NUM_FIXED_BLOCKS)
119 : : return true;
120 : 858274 : if (optimize_bb_for_size_p (bb))
121 : : return true;
122 : :
123 : 812139 : return !cached_can_duplicate_bb_p (bb);
124 : : }
125 : :
126 : : /* Return number of instructions in the block. */
127 : :
128 : : static void
129 : 214877 : analyze_bb (basic_block bb, int *count)
130 : : {
131 : 214877 : gimple_stmt_iterator gsi;
132 : 214877 : gimple *stmt;
133 : 214877 : int n = 0;
134 : :
135 : 1416800 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
136 : : {
137 : 987046 : stmt = gsi_stmt (gsi);
138 : 987046 : n += estimate_num_insns (stmt, &eni_size_weights);
139 : : }
140 : 214877 : *count = n;
141 : :
142 : 214877 : cache_can_duplicate_bb_p (bb, can_duplicate_block_p (CONST_CAST_BB (bb)));
143 : 214877 : }
144 : :
145 : : /* Return true if E1 is more frequent than E2. */
146 : : static bool
147 : 347895 : better_p (const_edge e1, const_edge e2)
148 : : {
149 : 519410 : if ((e1->count () > e2->count ()) || (e1->count () < e2->count ()))
150 : 318847 : return e1->count () > e2->count ();
151 : : /* This is needed to avoid changes in the decision after
152 : : CFG is modified. */
153 : 29048 : if (e1->src != e2->src)
154 : 18650 : return e1->src->index > e2->src->index;
155 : 10398 : return e1->dest->index > e2->dest->index;
156 : : }
157 : :
158 : : /* Return most frequent successor of basic block BB. */
159 : :
160 : : static edge
161 : 256208 : find_best_successor (basic_block bb)
162 : : {
163 : 256208 : edge e;
164 : 256208 : edge best = NULL;
165 : 256208 : edge_iterator ei;
166 : :
167 : 712889 : FOR_EACH_EDGE (e, ei, bb->succs)
168 : : {
169 : 456763 : if (!e->count ().initialized_p ())
170 : : return NULL;
171 : 456681 : if (!best || better_p (e, best))
172 : : best = e;
173 : : }
174 : 256126 : if (!best || ignore_bb_p (best->dest))
175 : 10889 : return NULL;
176 : 245237 : if (!best->probability.initialized_p ()
177 : 245237 : || best->probability.to_reg_br_prob_base () <= probability_cutoff)
178 : : return NULL;
179 : : return best;
180 : : }
181 : :
182 : : /* Return most frequent predecessor of basic block BB. */
183 : :
184 : : static edge
185 : 253631 : find_best_predecessor (basic_block bb)
186 : : {
187 : 253631 : edge e;
188 : 253631 : edge best = NULL;
189 : 253631 : edge_iterator ei;
190 : :
191 : 654357 : FOR_EACH_EDGE (e, ei, bb->preds)
192 : : {
193 : 400813 : if (!e->count ().initialized_p ())
194 : : return NULL;
195 : 400726 : if (!best || better_p (e, best))
196 : : best = e;
197 : : }
198 : 253544 : if (!best || ignore_bb_p (best->src))
199 : 13758 : return NULL;
200 : 239786 : if (bb->count.initialized_p ()
201 : 719149 : && (best->count ().to_frequency (cfun) * REG_BR_PROB_BASE
202 : 239786 : < bb->count.to_frequency (cfun) * branch_ratio_cutoff))
203 : 209 : return NULL;
204 : : return best;
205 : : }
206 : :
207 : : /* Find the trace using bb and record it in the TRACE array.
208 : : Return number of basic blocks recorded. */
209 : :
210 : : static int
211 : 31789 : find_trace (basic_block bb, basic_block *trace)
212 : : {
213 : 31789 : int i = 0;
214 : 31789 : edge e;
215 : :
216 : 31789 : if (dump_file)
217 : 17 : fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->count.to_frequency (cfun));
218 : :
219 : 75398 : while ((e = find_best_predecessor (bb)) != NULL)
220 : : {
221 : 62219 : basic_block bb2 = e->src;
222 : 123259 : if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
223 : 113291 : || find_best_successor (bb2) != e)
224 : : break;
225 : 43609 : if (dump_file)
226 : 15 : fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
227 : : bb = bb2;
228 : : }
229 : 31789 : if (dump_file)
230 : 17 : fprintf (dump_file, " forward %i [%i]", bb->index, bb->count.to_frequency (cfun));
231 : 31789 : trace[i++] = bb;
232 : :
233 : : /* Follow the trace in forward direction. */
234 : 205136 : while ((e = find_best_successor (bb)) != NULL)
235 : : {
236 : 189518 : bb = e->dest;
237 : 378995 : if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
238 : 367751 : || find_best_predecessor (bb) != e)
239 : : break;
240 : 173347 : if (dump_file)
241 : 30 : fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
242 : 173347 : trace[i++] = bb;
243 : : }
244 : 31789 : if (dump_file)
245 : 17 : fprintf (dump_file, "\n");
246 : 31789 : return i;
247 : : }
248 : :
249 : : /* Duplicate block BB2, placing it after BB in the CFG. Return the
250 : : newly created block. */
251 : : basic_block
252 : 12368 : transform_duplicate (basic_block bb, basic_block bb2)
253 : : {
254 : 12368 : edge e;
255 : 12368 : basic_block copy;
256 : :
257 : 12368 : e = find_edge (bb, bb2);
258 : :
259 : 12368 : copy = duplicate_block (bb2, e, bb);
260 : 12368 : flush_pending_stmts (e);
261 : :
262 : 12368 : add_phi_args_after_copy (©, 1, NULL);
263 : :
264 : 12368 : return (copy);
265 : : }
266 : :
267 : : /* Look for basic blocks in frequency order, construct traces and tail duplicate
268 : : if profitable. */
269 : :
270 : : static bool
271 : 10218 : tail_duplicate (void)
272 : : {
273 : 10218 : auto_vec<fibonacci_node<long, basic_block_def>*> blocks;
274 : 10218 : blocks.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
275 : :
276 : 10218 : basic_block *trace = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
277 : 10218 : int *counts = XNEWVEC (int, last_basic_block_for_fn (cfun));
278 : 10218 : int ninsns = 0, nduplicated = 0;
279 : 10218 : gcov_type weighted_insns = 0, traced_insns = 0;
280 : 10218 : fibonacci_heap<long, basic_block_def> heap (LONG_MIN);
281 : 10218 : gcov_type cover_insns;
282 : 10218 : int max_dup_insns;
283 : 10218 : basic_block bb;
284 : 10218 : bool changed = false;
285 : :
286 : : /* Create an oversized sbitmap to reduce the chance that we need to
287 : : resize it. */
288 : 10218 : bb_seen = sbitmap_alloc (last_basic_block_for_fn (cfun) * 2);
289 : 10218 : bitmap_clear (bb_seen);
290 : 10218 : can_duplicate_bb = sbitmap_alloc (last_basic_block_for_fn (cfun));
291 : 10218 : bitmap_clear (can_duplicate_bb);
292 : 10218 : initialize_original_copy_tables ();
293 : :
294 : 10218 : if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
295 : 175 : probability_cutoff = param_tracer_min_branch_probability_feedback;
296 : : else
297 : 10043 : probability_cutoff = param_tracer_min_branch_probability;
298 : 10218 : probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
299 : :
300 : 10218 : branch_ratio_cutoff =
301 : 10218 : (REG_BR_PROB_BASE / 100 * param_tracer_min_branch_ratio);
302 : :
303 : 225095 : FOR_EACH_BB_FN (bb, cfun)
304 : : {
305 : 214877 : int n;
306 : 214877 : analyze_bb (bb, &n);
307 : 214877 : if (!ignore_bb_p (bb))
308 : 173745 : blocks[bb->index] = heap.insert (-bb->count.to_frequency (cfun), bb);
309 : :
310 : 214877 : counts [bb->index] = n;
311 : 214877 : ninsns += n;
312 : 214877 : weighted_insns += n * bb->count.to_frequency (cfun);
313 : : }
314 : :
315 : 10218 : if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
316 : 175 : cover_insns = param_tracer_dynamic_coverage_feedback;
317 : : else
318 : 10043 : cover_insns = param_tracer_dynamic_coverage;
319 : 10218 : cover_insns = (weighted_insns * cover_insns + 50) / 100;
320 : 10218 : max_dup_insns = (ninsns * param_tracer_max_code_growth + 50) / 100;
321 : :
322 : 10218 : while (traced_insns < cover_insns && nduplicated < max_dup_insns
323 : 42378 : && !heap.empty ())
324 : : {
325 : 32160 : basic_block bb = heap.extract_min ();
326 : 32160 : int n, pos;
327 : :
328 : 32160 : if (!bb)
329 : : break;
330 : :
331 : 32160 : blocks[bb->index] = NULL;
332 : :
333 : 32160 : if (ignore_bb_p (bb))
334 : 371 : continue;
335 : 31789 : gcc_assert (!bb_seen_p (bb));
336 : :
337 : 31789 : n = find_trace (bb, trace);
338 : :
339 : 31789 : bb = trace[0];
340 : 31789 : traced_insns += bb->count.to_frequency (cfun) * counts [bb->index];
341 : 31789 : if (blocks[bb->index])
342 : : {
343 : 8099 : heap.delete_node (blocks[bb->index]);
344 : 8099 : blocks[bb->index] = NULL;
345 : : }
346 : :
347 : 89330 : for (pos = 1; pos < n; pos++)
348 : : {
349 : 67997 : basic_block bb2 = trace[pos];
350 : :
351 : 67997 : if (blocks[bb2->index])
352 : : {
353 : 61913 : heap.delete_node (blocks[bb2->index]);
354 : 61913 : blocks[bb2->index] = NULL;
355 : : }
356 : 67997 : traced_insns += bb2->count.to_frequency (cfun) * counts [bb2->index];
357 : 67997 : if (EDGE_COUNT (bb2->preds) > 1
358 : 11694 : && can_duplicate_block_p (bb2)
359 : : /* We have the tendency to duplicate the loop header
360 : : of all do { } while loops. Do not do that - it is
361 : : not profitable and it might create a loop with multiple
362 : : entries or at least rotate the loop. */
363 : 79691 : && bb2->loop_father->header != bb2)
364 : : {
365 : 10456 : nduplicated += counts [bb2->index];
366 : 10456 : basic_block copy = transform_duplicate (bb, bb2);
367 : :
368 : : /* Reconsider the original copy of block we've duplicated.
369 : : Removing the most common predecessor may make it to be
370 : : head. */
371 : 10456 : blocks[bb2->index] = heap.insert (-bb2->count.to_frequency (cfun), bb2);
372 : :
373 : 10456 : if (dump_file)
374 : 7 : fprintf (dump_file, "Duplicated %i as %i [%i]\n",
375 : : bb2->index, copy->index, copy->count.to_frequency (cfun));
376 : :
377 : : bb2 = copy;
378 : : changed = true;
379 : : }
380 : 67997 : mark_bb_seen (bb2);
381 : 67997 : bb = bb2;
382 : : /* In case the trace became infrequent, stop duplicating. */
383 : 67997 : if (ignore_bb_p (bb))
384 : : break;
385 : : }
386 : 31789 : if (dump_file)
387 : 17 : fprintf (dump_file, " covered now %.1f\n\n",
388 : 17 : traced_insns * 100.0 / weighted_insns);
389 : : }
390 : 10218 : if (dump_file)
391 : 10 : fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
392 : 10 : nduplicated * 100 / ninsns);
393 : :
394 : 10218 : free_original_copy_tables ();
395 : 10218 : sbitmap_free (bb_seen);
396 : 10218 : sbitmap_free (can_duplicate_bb);
397 : 10218 : can_duplicate_bb = NULL;
398 : 10218 : free (trace);
399 : 10218 : free (counts);
400 : :
401 : 20436 : return changed;
402 : 10218 : }
403 : :
404 : : namespace {
405 : :
406 : : const pass_data pass_data_tracer =
407 : : {
408 : : GIMPLE_PASS, /* type */
409 : : "tracer", /* name */
410 : : OPTGROUP_NONE, /* optinfo_flags */
411 : : TV_TRACER, /* tv_id */
412 : : 0, /* properties_required */
413 : : 0, /* properties_provided */
414 : : 0, /* properties_destroyed */
415 : : 0, /* todo_flags_start */
416 : : TODO_update_ssa, /* todo_flags_finish */
417 : : };
418 : :
419 : : class pass_tracer : public gimple_opt_pass
420 : : {
421 : : public:
422 : 281914 : pass_tracer (gcc::context *ctxt)
423 : 563828 : : gimple_opt_pass (pass_data_tracer, ctxt)
424 : : {}
425 : :
426 : : /* opt_pass methods: */
427 : 985383 : bool gate (function *) final override
428 : : {
429 : 985383 : return (optimize > 0 && flag_tracer && flag_reorder_blocks);
430 : : }
431 : :
432 : : unsigned int execute (function *) final override;
433 : :
434 : : }; // class pass_tracer
435 : :
436 : : unsigned int
437 : 18297 : pass_tracer::execute (function *fun)
438 : : {
439 : 18297 : bool changed;
440 : :
441 : 18297 : if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
442 : : return 0;
443 : :
444 : 10218 : mark_dfs_back_edges ();
445 : 10218 : if (dump_file)
446 : 10 : brief_dump_cfg (dump_file, dump_flags);
447 : :
448 : : /* Trace formation is done on the fly inside tail_duplicate */
449 : 10218 : changed = tail_duplicate ();
450 : 10218 : if (changed)
451 : : {
452 : 4285 : free_dominance_info (CDI_DOMINATORS);
453 : : /* If we changed the CFG schedule loops for fixup by cleanup_cfg. */
454 : 4285 : loops_state_set (LOOPS_NEED_FIXUP);
455 : : }
456 : :
457 : 10218 : if (dump_file)
458 : 10 : brief_dump_cfg (dump_file, dump_flags);
459 : :
460 : 10218 : return changed ? TODO_cleanup_cfg : 0;
461 : : }
462 : : } // anon namespace
463 : :
464 : : gimple_opt_pass *
465 : 281914 : make_pass_tracer (gcc::context *ctxt)
466 : : {
467 : 281914 : return new pass_tracer (ctxt);
468 : : }
|
