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-2026 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 79156 : mark_bb_seen (basic_block bb)
72 : {
73 79156 : unsigned int size = SBITMAP_SIZE (bb_seen);
74 :
75 79156 : if ((unsigned int)bb->index >= size)
76 0 : bb_seen = sbitmap_resize (bb_seen, size * 2, 0);
77 :
78 79156 : bitmap_set_bit (bb_seen, bb->index);
79 79156 : }
80 :
81 : static inline bool
82 450045 : bb_seen_p (basic_block bb)
83 : {
84 450045 : 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 272084 : cache_can_duplicate_bb_p (const_basic_block bb, bool val)
92 : {
93 272084 : if (val)
94 272052 : bitmap_set_bit (can_duplicate_bb, bb->index);
95 272084 : }
96 :
97 : /* Return cached value of can_duplicate_bb_p for BB. */
98 : static bool
99 1142199 : cached_can_duplicate_bb_p (const_basic_block bb)
100 : {
101 1142199 : if (can_duplicate_bb)
102 : {
103 1142199 : unsigned int size = SBITMAP_SIZE (can_duplicate_bb);
104 1142199 : if ((unsigned int)bb->index < size)
105 1119985 : 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 0 : 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 1221245 : ignore_bb_p (const_basic_block bb)
117 : {
118 1221245 : if (bb->index < NUM_FIXED_BLOCKS)
119 : return true;
120 1204455 : if (optimize_bb_for_size_p (bb))
121 : return true;
122 :
123 1142199 : return !cached_can_duplicate_bb_p (bb);
124 : }
125 :
126 : /* Return number of instructions in the block. */
127 :
128 : static void
129 272084 : analyze_bb (basic_block bb, int *count)
130 : {
131 272084 : gimple_stmt_iterator gsi;
132 272084 : gimple *stmt;
133 272084 : int n = 0;
134 :
135 1887506 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
136 : {
137 1343338 : stmt = gsi_stmt (gsi);
138 1343338 : n += estimate_num_insns (stmt, &eni_size_weights);
139 : }
140 272084 : *count = n;
141 :
142 272084 : cache_can_duplicate_bb_p (bb, can_duplicate_block_p (const_cast<basic_block>
143 : (bb)));
144 272084 : }
145 :
146 : /* Return true if E1 is more frequent than E2. */
147 : static bool
148 635373 : better_p (const_edge e1, const_edge e2)
149 : {
150 934646 : if ((e1->count () > e2->count ()) || (e1->count () < e2->count ()))
151 613244 : return e1->count () > e2->count ();
152 : /* This is needed to avoid changes in the decision after
153 : CFG is modified. */
154 22129 : if (e1->src != e2->src)
155 7759 : return e1->src->index > e2->src->index;
156 14370 : return e1->dest->index > e2->dest->index;
157 : }
158 :
159 : /* Return most frequent successor of basic block BB. */
160 :
161 : static edge
162 417145 : find_best_successor (basic_block bb)
163 : {
164 417145 : edge e;
165 417145 : edge best = NULL;
166 417145 : edge_iterator ei;
167 :
168 1190320 : FOR_EACH_EDGE (e, ei, bb->succs)
169 : {
170 773258 : if (!e->count ().initialized_p ())
171 : return NULL;
172 773175 : if (!best || better_p (e, best))
173 : best = e;
174 : }
175 417062 : if (!best || ignore_bb_p (best->dest))
176 13346 : return NULL;
177 403716 : if (!best->probability.initialized_p ()
178 403716 : || best->probability.to_reg_br_prob_base () <= probability_cutoff)
179 : return NULL;
180 : return best;
181 : }
182 :
183 : /* Return most frequent predecessor of basic block BB. */
184 :
185 : static edge
186 412803 : find_best_predecessor (basic_block bb)
187 : {
188 412803 : edge e;
189 412803 : edge best = NULL;
190 412803 : edge_iterator ei;
191 :
192 1104622 : FOR_EACH_EDGE (e, ei, bb->preds)
193 : {
194 691907 : if (!e->count ().initialized_p ())
195 : return NULL;
196 691819 : if (!best || better_p (e, best))
197 : best = e;
198 : }
199 412715 : if (!best || ignore_bb_p (best->src))
200 17406 : return NULL;
201 395309 : if (bb->count.initialized_p ()
202 1185775 : && (best->count ().to_frequency (cfun) * REG_BR_PROB_BASE
203 395309 : < bb->count.to_frequency (cfun) * branch_ratio_cutoff))
204 152 : return NULL;
205 : return best;
206 : }
207 :
208 : /* Find the trace using bb and record it in the TRACE array.
209 : Return number of basic blocks recorded. */
210 :
211 : static int
212 39931 : find_trace (basic_block bb, basic_block *trace)
213 : {
214 39931 : int i = 0;
215 39931 : edge e;
216 :
217 39931 : if (dump_file)
218 17 : fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->count.to_frequency (cfun));
219 :
220 108473 : while ((e = find_best_predecessor (bb)) != NULL)
221 : {
222 91701 : basic_block bb2 = e->src;
223 181976 : if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
224 170041 : || find_best_successor (bb2) != e)
225 : break;
226 68542 : if (dump_file)
227 13 : fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
228 : bb = bb2;
229 : }
230 39931 : if (dump_file)
231 17 : fprintf (dump_file, " forward %i [%i]", bb->index, bb->count.to_frequency (cfun));
232 39931 : trace[i++] = bb;
233 :
234 : /* Follow the trace in forward direction. */
235 338805 : while ((e = find_best_successor (bb)) != NULL)
236 : {
237 318413 : bb = e->dest;
238 636738 : if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
239 622743 : || find_best_predecessor (bb) != e)
240 : break;
241 298874 : if (dump_file)
242 25 : fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
243 298874 : trace[i++] = bb;
244 : }
245 39931 : if (dump_file)
246 17 : fprintf (dump_file, "\n");
247 39931 : return i;
248 : }
249 :
250 : /* Duplicate block BB2, placing it after BB in the CFG. Return the
251 : newly created block. */
252 : basic_block
253 14712 : transform_duplicate (basic_block bb, basic_block bb2)
254 : {
255 14712 : edge e;
256 14712 : basic_block copy;
257 :
258 14712 : e = find_edge (bb, bb2);
259 :
260 14712 : copy = duplicate_block (bb2, e, bb);
261 14712 : flush_pending_stmts (e);
262 :
263 14712 : add_phi_args_after_copy (©, 1, NULL);
264 :
265 14712 : return (copy);
266 : }
267 :
268 : /* Look for basic blocks in frequency order, construct traces and tail duplicate
269 : if profitable. */
270 :
271 : static bool
272 11705 : tail_duplicate (void)
273 : {
274 11705 : auto_vec<fibonacci_node<long, basic_block_def>*> blocks;
275 11705 : blocks.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
276 :
277 11705 : basic_block *trace = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
278 11705 : int *counts = XNEWVEC (int, last_basic_block_for_fn (cfun));
279 11705 : int ninsns = 0, nduplicated = 0;
280 11705 : gcov_type weighted_insns = 0, traced_insns = 0;
281 11705 : fibonacci_heap<long, basic_block_def> heap (LONG_MIN);
282 11705 : gcov_type cover_insns;
283 11705 : int max_dup_insns;
284 11705 : basic_block bb;
285 11705 : bool changed = false;
286 :
287 : /* Create an oversized sbitmap to reduce the chance that we need to
288 : resize it. */
289 11705 : bb_seen = sbitmap_alloc (last_basic_block_for_fn (cfun) * 2);
290 11705 : bitmap_clear (bb_seen);
291 11705 : can_duplicate_bb = sbitmap_alloc (last_basic_block_for_fn (cfun));
292 11705 : bitmap_clear (can_duplicate_bb);
293 11705 : initialize_original_copy_tables ();
294 :
295 11705 : if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
296 196 : probability_cutoff = param_tracer_min_branch_probability_feedback;
297 : else
298 11509 : probability_cutoff = param_tracer_min_branch_probability;
299 11705 : probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
300 :
301 11705 : branch_ratio_cutoff =
302 11705 : (REG_BR_PROB_BASE / 100 * param_tracer_min_branch_ratio);
303 :
304 283789 : FOR_EACH_BB_FN (bb, cfun)
305 : {
306 272084 : int n;
307 272084 : analyze_bb (bb, &n);
308 272084 : if (!ignore_bb_p (bb))
309 216520 : blocks[bb->index] = heap.insert (-bb->count.to_frequency (cfun), bb);
310 :
311 272084 : counts [bb->index] = n;
312 272084 : ninsns += n;
313 272084 : weighted_insns += n * bb->count.to_frequency (cfun);
314 : }
315 :
316 11705 : if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
317 196 : cover_insns = param_tracer_dynamic_coverage_feedback;
318 : else
319 11509 : cover_insns = param_tracer_dynamic_coverage;
320 11705 : cover_insns = (weighted_insns * cover_insns + 50) / 100;
321 11705 : max_dup_insns = (ninsns * param_tracer_max_code_growth + 50) / 100;
322 :
323 11705 : while (traced_insns < cover_insns && nduplicated < max_dup_insns
324 52091 : && !heap.empty ())
325 : {
326 40386 : basic_block bb = heap.extract_min ();
327 40386 : int n, pos;
328 :
329 40386 : if (!bb)
330 : break;
331 :
332 40386 : blocks[bb->index] = NULL;
333 :
334 40386 : if (ignore_bb_p (bb))
335 455 : continue;
336 39931 : gcc_assert (!bb_seen_p (bb));
337 :
338 39931 : n = find_trace (bb, trace);
339 :
340 39931 : bb = trace[0];
341 39931 : traced_insns += bb->count.to_frequency (cfun) * counts [bb->index];
342 39931 : if (blocks[bb->index])
343 : {
344 11037 : heap.delete_node (blocks[bb->index]);
345 11037 : blocks[bb->index] = NULL;
346 : }
347 :
348 104375 : for (pos = 1; pos < n; pos++)
349 : {
350 79156 : basic_block bb2 = trace[pos];
351 :
352 79156 : if (blocks[bb2->index])
353 : {
354 70696 : heap.delete_node (blocks[bb2->index]);
355 70696 : blocks[bb2->index] = NULL;
356 : }
357 79156 : traced_insns += bb2->count.to_frequency (cfun) * counts [bb2->index];
358 79156 : if (EDGE_COUNT (bb2->preds) > 1
359 16027 : && can_duplicate_block_p (bb2)
360 : /* We have the tendency to duplicate the loop header
361 : of all do { } while loops. Do not do that - it is
362 : not profitable and it might create a loop with multiple
363 : entries or at least rotate the loop. */
364 95183 : && bb2->loop_father->header != bb2)
365 : {
366 14712 : nduplicated += counts [bb2->index];
367 14712 : basic_block copy = transform_duplicate (bb, bb2);
368 :
369 : /* Reconsider the original copy of block we've duplicated.
370 : Removing the most common predecessor may make it to be
371 : head. */
372 14712 : blocks[bb2->index] = heap.insert (-bb2->count.to_frequency (cfun), bb2);
373 :
374 14712 : if (dump_file)
375 7 : fprintf (dump_file, "Duplicated %i as %i [%i]\n",
376 : bb2->index, copy->index, copy->count.to_frequency (cfun));
377 :
378 : bb2 = copy;
379 : changed = true;
380 : }
381 79156 : mark_bb_seen (bb2);
382 79156 : bb = bb2;
383 : /* In case the trace became infrequent, stop duplicating. */
384 79156 : if (ignore_bb_p (bb))
385 : break;
386 : }
387 39931 : if (dump_file)
388 17 : fprintf (dump_file, " covered now %.1f\n\n",
389 17 : traced_insns * 100.0 / weighted_insns);
390 : }
391 11705 : if (dump_file)
392 10 : fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
393 10 : nduplicated * 100 / ninsns);
394 :
395 11705 : free_original_copy_tables ();
396 11705 : sbitmap_free (bb_seen);
397 11705 : sbitmap_free (can_duplicate_bb);
398 11705 : can_duplicate_bb = NULL;
399 11705 : free (trace);
400 11705 : free (counts);
401 :
402 23410 : return changed;
403 11705 : }
404 :
405 : namespace {
406 :
407 : const pass_data pass_data_tracer =
408 : {
409 : GIMPLE_PASS, /* type */
410 : "tracer", /* name */
411 : OPTGROUP_NONE, /* optinfo_flags */
412 : TV_TRACER, /* tv_id */
413 : 0, /* properties_required */
414 : 0, /* properties_provided */
415 : 0, /* properties_destroyed */
416 : 0, /* todo_flags_start */
417 : TODO_update_ssa, /* todo_flags_finish */
418 : };
419 :
420 : class pass_tracer : public gimple_opt_pass
421 : {
422 : public:
423 293828 : pass_tracer (gcc::context *ctxt)
424 587656 : : gimple_opt_pass (pass_data_tracer, ctxt)
425 : {}
426 :
427 : /* opt_pass methods: */
428 1048886 : bool gate (function *) final override
429 : {
430 1048886 : return (optimize > 0 && flag_tracer && flag_reorder_blocks);
431 : }
432 :
433 : unsigned int execute (function *) final override;
434 :
435 : }; // class pass_tracer
436 :
437 : unsigned int
438 20702 : pass_tracer::execute (function *fun)
439 : {
440 20702 : bool changed;
441 :
442 20702 : if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
443 : return 0;
444 :
445 11705 : mark_dfs_back_edges ();
446 11705 : if (dump_file)
447 10 : brief_dump_cfg (dump_file, dump_flags);
448 :
449 : /* Trace formation is done on the fly inside tail_duplicate */
450 11705 : changed = tail_duplicate ();
451 11705 : if (changed)
452 : {
453 5341 : free_dominance_info (CDI_DOMINATORS);
454 : /* If we changed the CFG schedule loops for fixup by cleanup_cfg. */
455 5341 : loops_state_set (LOOPS_NEED_FIXUP);
456 : }
457 :
458 11705 : if (dump_file)
459 10 : brief_dump_cfg (dump_file, dump_flags);
460 :
461 11705 : return changed ? TODO_cleanup_cfg : 0;
462 : }
463 : } // anon namespace
464 :
465 : gimple_opt_pass *
466 293828 : make_pass_tracer (gcc::context *ctxt)
467 : {
468 293828 : return new pass_tracer (ctxt);
469 : }
|
