Line data Source code
1 : /* SSA Jump Threading
2 : Copyright (C) 2005-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "predict.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "fold-const.h"
28 : #include "cfgloop.h"
29 : #include "gimple-iterator.h"
30 : #include "tree-cfg.h"
31 : #include "tree-ssa-threadupdate.h"
32 : #include "tree-ssa-loop.h"
33 : #include "cfganal.h"
34 : #include "tree-pass.h"
35 : #include "gimple-ssa.h"
36 : #include "tree-phinodes.h"
37 : #include "tree-inline.h"
38 : #include "tree-vectorizer.h"
39 : #include "value-range.h"
40 : #include "gimple-range.h"
41 : #include "tree-ssa-threadedge.h"
42 : #include "gimple-range-path.h"
43 : #include "ssa.h"
44 : #include "tree-cfgcleanup.h"
45 : #include "tree-pretty-print.h"
46 : #include "cfghooks.h"
47 : #include "dbgcnt.h"
48 :
49 : // Path registry for the backwards threader. After all paths have been
50 : // registered with register_path(), thread_through_all_blocks() is called
51 : // to modify the CFG.
52 :
53 25867904 : class back_threader_registry : public back_jt_path_registry
54 : {
55 : public:
56 : bool register_path (const vec<basic_block> &, edge taken);
57 : };
58 :
59 : // Class to abstract the profitability code for the backwards threader.
60 :
61 : class back_threader_profitability
62 : {
63 : public:
64 : back_threader_profitability (bool speed_p, gimple *stmt);
65 : bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
66 : bool profitable_path_p (const vec<basic_block> &,
67 : edge taken, bool *irreducible_loop);
68 : private:
69 : const bool m_speed_p;
70 : int m_exit_jump_benefit;
71 : bool m_threaded_multiway_branch;
72 : // The following are computed by possibly_profitable_path_p
73 : bool m_threaded_through_latch;
74 : bool m_multiway_branch_in_path;
75 : bool m_contains_hot_bb;
76 : int m_n_insns;
77 : };
78 :
79 22048900 : back_threader_profitability::back_threader_profitability (bool speed_p,
80 : gimple *last)
81 22048900 : : m_speed_p (speed_p)
82 : {
83 22048900 : m_threaded_multiway_branch = (gimple_code (last) == GIMPLE_SWITCH
84 22048900 : || gimple_code (last) == GIMPLE_GOTO);
85 : // The forward threader has estimate_threading_killed_stmts, in
86 : // particular it estimates further DCE from eliminating the exit
87 : // control stmt.
88 22048900 : m_exit_jump_benefit = estimate_num_insns (last, &eni_size_weights);
89 22048900 : }
90 :
91 : // Back threader flags.
92 : #define BT_NONE 0
93 : // Generate fast code at the expense of code size.
94 : #define BT_SPEED 1
95 : // Resolve unknown SSAs on entry to a threading path. If set, use the
96 : // ranger. If not, assume all ranges on entry to a path are VARYING.
97 : #define BT_RESOLVE 2
98 :
99 : class back_threader
100 : {
101 : public:
102 : back_threader (function *fun, unsigned flags, bool first);
103 : ~back_threader ();
104 : unsigned thread_blocks ();
105 : private:
106 : void maybe_thread_block (basic_block bb);
107 : bool debug_counter ();
108 : edge maybe_register_path (back_threader_profitability &);
109 : void maybe_register_path_dump (edge taken_edge);
110 : void find_paths_to_names (basic_block bb, bitmap imports, unsigned,
111 : back_threader_profitability &);
112 : edge find_taken_edge (const vec<basic_block> &path);
113 : edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
114 : edge find_taken_edge_switch (const vec<basic_block> &path, gswitch *);
115 : edge find_taken_edge_goto (const vec<basic_block> &path, ggoto *);
116 : virtual void debug ();
117 : virtual void dump (FILE *out);
118 :
119 : back_threader_registry m_registry;
120 :
121 : // Current path being analyzed.
122 : auto_vec<basic_block> m_path;
123 : // Hash to mark visited BBs while analyzing a path.
124 : hash_set<basic_block> m_visited_bbs;
125 : // The set of SSA names, any of which could potentially change the
126 : // value of the final conditional in a path.
127 : auto_bitmap m_imports;
128 : // The last statement in the path.
129 : gimple *m_last_stmt;
130 : // Marker to differentiate unreachable edges.
131 : static const edge UNREACHABLE_EDGE;
132 : // Set to TRUE if unknown SSA names along a path should be resolved
133 : // with the ranger. Otherwise, unknown SSA names are assumed to be
134 : // VARYING. Setting to true is more precise but slower.
135 : function *m_fun;
136 : // Ranger for the path solver.
137 : gimple_ranger *m_ranger;
138 : unsigned m_flags;
139 : // Set to TRUE for the first of each thread[12] pass or the first of
140 : // each threadfull[12] pass. This is used to differentiate between
141 : // the different threading passes so we can set up debug counters.
142 : bool m_first;
143 : };
144 :
145 : // Used to differentiate unreachable edges, so we may stop the search
146 : // in a the given direction.
147 : const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
148 :
149 6466976 : back_threader::back_threader (function *fun, unsigned flags, bool first)
150 6466976 : : m_first (first)
151 : {
152 6466976 : if (flags & BT_SPEED)
153 3925556 : loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
154 : else
155 2541420 : loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
156 :
157 6466976 : m_fun = fun;
158 6466976 : m_flags = flags;
159 6466976 : m_last_stmt = NULL;
160 :
161 : // The path solver needs EDGE_DFS_BACK in resolving mode.
162 6466976 : if (flags & BT_RESOLVE)
163 1962782 : mark_dfs_back_edges ();
164 :
165 6466976 : m_ranger = new gimple_ranger;
166 6466976 : }
167 :
168 6466976 : back_threader::~back_threader ()
169 : {
170 6466976 : delete m_ranger;
171 6466976 : loop_optimizer_finalize ();
172 6466976 : }
173 :
174 : // A wrapper for the various debug counters for the threading passes.
175 : // Returns TRUE if it's OK to register the current threading
176 : // candidate.
177 :
178 : bool
179 2545979 : back_threader::debug_counter ()
180 : {
181 : // The ethread pass is mostly harmless ;-).
182 2545979 : if ((m_flags & BT_SPEED) == 0)
183 : return true;
184 :
185 1734965 : if (m_flags & BT_RESOLVE)
186 : {
187 1197229 : if (m_first && !dbg_cnt (back_threadfull1))
188 : return false;
189 :
190 1197229 : if (!m_first && !dbg_cnt (back_threadfull2))
191 : return false;
192 : }
193 : else
194 : {
195 537736 : if (m_first && !dbg_cnt (back_thread1))
196 : return false;
197 :
198 537736 : if (!m_first && !dbg_cnt (back_thread2))
199 : return false;
200 : }
201 : return true;
202 : }
203 :
204 : static void
205 561 : dump_path (FILE *dump_file, const vec<basic_block> &path)
206 : {
207 3013 : for (unsigned i = path.length (); i > 0; --i)
208 : {
209 1891 : basic_block bb = path[i - 1];
210 1891 : fprintf (dump_file, "%d", bb->index);
211 1891 : if (i > 1)
212 1330 : fprintf (dump_file, "->");
213 : }
214 561 : }
215 :
216 : // Dump details of an attempt to register a path.
217 :
218 : void
219 561 : back_threader::maybe_register_path_dump (edge taken)
220 : {
221 561 : if (m_path.is_empty ())
222 : return;
223 :
224 561 : fprintf (dump_file, "path: ");
225 561 : dump_path (dump_file, m_path);
226 561 : fprintf (dump_file, "->");
227 :
228 561 : if (taken == UNREACHABLE_EDGE)
229 11 : fprintf (dump_file, "xx REJECTED (unreachable)\n");
230 550 : else if (taken)
231 101 : fprintf (dump_file, "%d SUCCESS\n", taken->dest->index);
232 : else
233 449 : fprintf (dump_file, "xx REJECTED\n");
234 : }
235 :
236 : // If an outgoing edge can be determined out of the current path,
237 : // register it for jump threading and return the taken edge.
238 : //
239 : // Return NULL if it is unprofitable to thread this path, or the
240 : // outgoing edge is unknown. Return UNREACHABLE_EDGE if the path is
241 : // unreachable.
242 :
243 : edge
244 28840181 : back_threader::maybe_register_path (back_threader_profitability &profit)
245 : {
246 28840181 : edge taken_edge = find_taken_edge (m_path);
247 :
248 28840181 : if (taken_edge && taken_edge != UNREACHABLE_EDGE)
249 : {
250 2969814 : bool irreducible = false;
251 2969814 : if (profit.profitable_path_p (m_path, taken_edge, &irreducible)
252 2545979 : && debug_counter ()
253 5515793 : && m_registry.register_path (m_path, taken_edge))
254 : {
255 1479310 : if (irreducible)
256 33612 : vect_free_loop_info_assumptions (m_path[0]->loop_father);
257 : }
258 : else
259 : taken_edge = NULL;
260 : }
261 :
262 28840181 : if (dump_file && (dump_flags & TDF_DETAILS))
263 561 : maybe_register_path_dump (taken_edge);
264 :
265 28840181 : return taken_edge;
266 : }
267 :
268 : // Return the known taken edge out of a path. If the path can be
269 : // determined to be unreachable, return UNREACHABLE_EDGE. If no
270 : // outgoing edge can be calculated, return NULL.
271 :
272 : edge
273 28840181 : back_threader::find_taken_edge (const vec<basic_block> &path)
274 : {
275 28840181 : gcc_checking_assert (path.length () > 1);
276 28840181 : switch (gimple_code (m_last_stmt))
277 : {
278 28746708 : case GIMPLE_COND:
279 28746708 : return find_taken_edge_cond (path, as_a<gcond *> (m_last_stmt));
280 :
281 92267 : case GIMPLE_SWITCH:
282 92267 : return find_taken_edge_switch (path, as_a<gswitch *> (m_last_stmt));
283 :
284 1206 : case GIMPLE_GOTO:
285 1206 : return find_taken_edge_goto (path, as_a<ggoto *> (m_last_stmt));
286 :
287 : default:
288 : return NULL;
289 : }
290 : }
291 :
292 : // Same as find_taken_edge, but for paths ending in a computed goto.
293 :
294 : edge
295 1206 : back_threader::find_taken_edge_goto (const vec<basic_block> &path,
296 : ggoto *stmt)
297 : {
298 1206 : tree dest = gimple_goto_dest (stmt);
299 :
300 1206 : if (TREE_CODE (dest) == SSA_NAME)
301 : {
302 1206 : prange r;
303 1206 : path_range_query solver (*m_ranger, path, m_imports,
304 1206 : m_flags & BT_RESOLVE);
305 1206 : if (!solver.range_of_expr (r, dest, stmt))
306 : return NULL;
307 :
308 1206 : if (r.undefined_p ())
309 : return UNREACHABLE_EDGE;
310 :
311 1174 : dest = r.pt_invariant ();
312 184 : if (!dest)
313 : return NULL;
314 1206 : }
315 :
316 : // For a destination that did not resolve to a label,
317 : // ::find_taken_edge at most returns the block's single successor,
318 : // the only place it could go.
319 184 : return ::find_taken_edge (gimple_bb (stmt), dest);
320 : }
321 :
322 : // Same as find_taken_edge, but for paths ending in a switch.
323 :
324 : edge
325 92267 : back_threader::find_taken_edge_switch (const vec<basic_block> &path,
326 : gswitch *sw)
327 : {
328 92267 : tree name = gimple_switch_index (sw);
329 92267 : int_range_max r;
330 :
331 92267 : path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE);
332 92267 : solver.range_of_expr (r, name, sw);
333 :
334 92267 : if (r.undefined_p ())
335 : return UNREACHABLE_EDGE;
336 :
337 91828 : if (r.varying_p ())
338 : return NULL;
339 :
340 61481 : tree label = find_case_label_range (sw, &r);
341 61481 : if (!label)
342 : return NULL;
343 :
344 6715 : return find_edge (gimple_bb (sw), label_to_block (cfun, CASE_LABEL (label)));
345 92267 : }
346 :
347 : // Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
348 :
349 : edge
350 28746708 : back_threader::find_taken_edge_cond (const vec<basic_block> &path,
351 : gcond *cond)
352 : {
353 28746708 : int_range_max r;
354 :
355 28746708 : path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE);
356 28746708 : solver.range_of_stmt (r, cond);
357 :
358 28746708 : if (solver.unreachable_path_p ())
359 : return UNREACHABLE_EDGE;
360 :
361 28631810 : int_range<2> true_range = range_true ();
362 28631810 : int_range<2> false_range = range_false ();
363 :
364 28631810 : if (r == true_range || r == false_range)
365 : {
366 2962917 : edge e_true, e_false;
367 2962917 : basic_block bb = gimple_bb (cond);
368 2962917 : extract_true_false_edges_from_block (bb, &e_true, &e_false);
369 2962917 : return r == true_range ? e_true : e_false;
370 : }
371 : return NULL;
372 28746708 : }
373 :
374 : // Find jump threading paths to any of the SSA names in the
375 : // INTERESTING bitmap, and register any such paths.
376 : //
377 : // BB is the current path being processed.
378 : //
379 : // OVERALL_PATHS is the search space up to this block
380 :
381 : void
382 64527629 : back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
383 : unsigned overall_paths,
384 : back_threader_profitability &profit)
385 : {
386 64527629 : if (m_visited_bbs.add (bb))
387 1563641 : return;
388 :
389 62963988 : m_path.safe_push (bb);
390 :
391 : // Try to resolve the path without looking back. Avoid resolving paths
392 : // we know are large but are not (yet) recognized as Finite State Machine.
393 : // ??? Ideally we'd explore the cheapest path to the loop backedge here,
394 : // avoiding the exponential greedy search and only start that from there.
395 : // Precomputing a path-size-to-immediate-dominator-of-successor for each
396 : // edge might help here. Alternatively copying divergent control flow
397 : // on the way to the backedge could be worthwhile.
398 62963988 : bool large_non_fsm;
399 62963988 : edge e;
400 62963988 : if (m_path.length () > 1
401 62963988 : && (!profit.possibly_profitable_path_p (m_path, &large_non_fsm)
402 28897721 : || (!large_non_fsm
403 28840181 : && maybe_register_path (profit))))
404 : ;
405 :
406 : // The backwards thread copier cannot copy blocks that do not belong
407 : // to the same loop, so when the new source of the path entry no
408 : // longer belongs to it we don't need to search further.
409 49351942 : else if (m_path[0]->loop_father != bb->loop_father
410 54855238 : && (!(e = loop_exits_from_bb_p (m_path[0]->loop_father,
411 5503296 : m_path[0]))
412 3836425 : || e->dest->loop_father != bb->loop_father))
413 : ;
414 :
415 : // Continue looking for ways to extend the path but limit the
416 : // search space along a branch
417 46949918 : else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds))
418 46949918 : <= (unsigned)param_max_jump_thread_paths)
419 : {
420 : // For further greedy searching we want to remove interesting
421 : // names defined in BB but add ones on the PHI edges for the
422 : // respective edges and adding imports from those stmts.
423 : // We do this by starting with all names
424 : // not defined in BB as interesting, collecting a list of
425 : // interesting PHIs in BB on the fly. Then we iterate over
426 : // predecessor edges, adding interesting PHI edge defs to
427 : // the set of interesting names to consider when processing it.
428 46826254 : auto_bitmap new_interesting;
429 46826254 : auto_vec<int, 16> new_imports;
430 46826254 : auto_vec<gphi *, 4> interesting_phis;
431 46826254 : bitmap_iterator bi;
432 46826254 : unsigned i;
433 46826254 : auto_vec<tree, 16> worklist;
434 104990925 : EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
435 : {
436 58164671 : tree name = ssa_name (i);
437 58164671 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
438 : /* Imports remain interesting. */
439 58164671 : if (gimple_bb (def_stmt) != bb)
440 : {
441 28922400 : bitmap_set_bit (new_interesting, i);
442 28922400 : continue;
443 : }
444 29242271 : worklist.quick_push (name);
445 135598018 : while (!worklist.is_empty ())
446 : {
447 47871205 : tree name = worklist.pop ();
448 47871205 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
449 : /* Newly discovered imports are interesting. */
450 47871205 : if (gimple_bb (def_stmt) != bb)
451 : {
452 5993981 : bitmap_set_bit (new_interesting, SSA_NAME_VERSION (name));
453 5993981 : continue;
454 : }
455 : /* Local PHIs participate in renaming below. */
456 78148052 : if (gphi *phi = dyn_cast<gphi *> (def_stmt))
457 5606396 : interesting_phis.safe_push (phi);
458 : /* For other local defs process their uses, amending
459 : imports on the way. */
460 : else
461 : {
462 36270828 : tree ssa[3];
463 36270828 : unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt);
464 93815069 : for (unsigned j = 0; j < lim; ++j)
465 : {
466 21273413 : tree rhs = ssa[j];
467 21273413 : if (rhs
468 42546826 : && bitmap_set_bit (m_imports,
469 21273413 : SSA_NAME_VERSION (rhs)))
470 : {
471 18628934 : new_imports.safe_push (SSA_NAME_VERSION (rhs));
472 18628934 : worklist.safe_push (rhs);
473 : }
474 : }
475 : }
476 : }
477 : }
478 46826254 : if (!bitmap_empty_p (new_interesting)
479 46826254 : || !interesting_phis.is_empty ())
480 : {
481 61162072 : auto_vec<int, 4> unwind (interesting_phis.length ());
482 61162072 : auto_vec<int, 4> imports_unwind (interesting_phis.length ());
483 30581036 : edge_iterator iter;
484 30581036 : edge e;
485 74300929 : FOR_EACH_EDGE (e, iter, bb->preds)
486 : {
487 43719893 : if (e->flags & EDGE_ABNORMAL
488 43717446 : || e->src->index == ENTRY_BLOCK)
489 1241164 : continue;
490 139878932 : for (gphi *phi : interesting_phis)
491 : {
492 12442745 : tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
493 12442745 : if (TREE_CODE (def) == SSA_NAME)
494 : {
495 8782313 : int ver = SSA_NAME_VERSION (def);
496 8782313 : if (bitmap_set_bit (new_interesting, ver))
497 : {
498 8747854 : if (bitmap_set_bit (m_imports, ver))
499 7191233 : imports_unwind.quick_push (ver);
500 8747854 : unwind.quick_push (ver);
501 : }
502 : }
503 : }
504 42478729 : find_paths_to_names (e->src, new_interesting, overall_paths,
505 : profit);
506 : // Restore new_interesting.
507 136184041 : for (int def : unwind)
508 8747854 : bitmap_clear_bit (new_interesting, def);
509 42478729 : unwind.truncate (0);
510 : // Restore and m_imports.
511 134627420 : for (int def : imports_unwind)
512 7191233 : bitmap_clear_bit (m_imports, def);
513 42478729 : imports_unwind.truncate (0);
514 : }
515 30581036 : }
516 : /* m_imports tracks all interesting names on the path, so when
517 : backtracking we have to restore it. */
518 159107696 : for (int j : new_imports)
519 18628934 : bitmap_clear_bit (m_imports, j);
520 46826254 : }
521 123664 : else if (dump_file && (dump_flags & TDF_DETAILS))
522 9 : fprintf (dump_file, " FAIL: Search space limit %d reached.\n",
523 : param_max_jump_thread_paths);
524 :
525 : // Reset things to their original state.
526 62963988 : m_path.pop ();
527 62963988 : m_visited_bbs.remove (bb);
528 : }
529 :
530 : // Search backwards from BB looking for paths where the final
531 : // conditional maybe threaded to a successor block. Record such paths
532 : // for jump threading.
533 :
534 : void
535 26295820 : back_threader::maybe_thread_block (basic_block bb)
536 : {
537 26295820 : if (EDGE_COUNT (bb->succs) <= 1)
538 4246920 : return;
539 :
540 26295820 : gimple *stmt = *gsi_last_bb (bb);
541 26295820 : if (!stmt)
542 : return;
543 :
544 26295820 : enum gimple_code code = gimple_code (stmt);
545 26295820 : if (code != GIMPLE_SWITCH
546 26295820 : && code != GIMPLE_COND
547 4199728 : && code != GIMPLE_GOTO)
548 : return;
549 :
550 22097049 : m_last_stmt = stmt;
551 22097049 : m_visited_bbs.empty ();
552 22097049 : m_path.truncate (0);
553 :
554 : // We compute imports of the path during discovery starting
555 : // just with names used in the conditional.
556 22097049 : bitmap_clear (m_imports);
557 22097049 : ssa_op_iter iter;
558 22097049 : tree name;
559 49007578 : FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
560 : {
561 26958678 : if (!gimple_range_ssa_p (name))
562 : return;
563 26910529 : bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
564 : }
565 :
566 : // Interesting is the set of imports we still not have see
567 : // the definition of. So while imports only grow, the
568 : // set of interesting defs dwindles and once empty we can
569 : // stop searching.
570 22048900 : auto_bitmap interesting;
571 22048900 : bitmap_copy (interesting, m_imports);
572 22048900 : back_threader_profitability profit (m_flags & BT_SPEED, stmt);
573 22048900 : find_paths_to_names (bb, interesting, 1, profit);
574 22048900 : }
575 :
576 : DEBUG_FUNCTION void
577 0 : debug (const vec <basic_block> &path)
578 : {
579 0 : dump_path (stderr, path);
580 0 : fputc ('\n', stderr);
581 0 : }
582 :
583 : void
584 0 : back_threader::dump (FILE *out)
585 : {
586 0 : fprintf (out, "\nCandidates for pre-computation:\n");
587 0 : fprintf (out, "===================================\n");
588 :
589 0 : bitmap_iterator bi;
590 0 : unsigned i;
591 :
592 0 : EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
593 : {
594 0 : tree name = ssa_name (i);
595 0 : print_generic_expr (out, name, TDF_NONE);
596 0 : fprintf (out, "\n");
597 : }
598 0 : }
599 :
600 : void
601 0 : back_threader::debug ()
602 : {
603 0 : dump (stderr);
604 0 : }
605 :
606 : /* Examine jump threading path PATH and return TRUE if it is possibly
607 : profitable to thread it, otherwise return FALSE. If this function
608 : returns TRUE profitable_path_p might not be satisfied but when
609 : the path is extended it might be. In particular indicate in
610 : *LARGE_NON_FSM whether the thread is too large for a non-FSM thread
611 : but would be OK if we extend the path to cover the loop backedge.
612 :
613 : ?? It seems we should be able to loosen some of the restrictions in
614 : this function after loop optimizations have run. */
615 :
616 : bool
617 40915088 : back_threader_profitability::possibly_profitable_path_p
618 : (const vec<basic_block> &m_path,
619 : bool *large_non_fsm)
620 : {
621 40915088 : gcc_checking_assert (!m_path.is_empty ());
622 :
623 : /* We can an empty path here (excluding the DEF block) when the
624 : statement that makes a conditional generate a compile-time
625 : constant result is in the same block as the conditional.
626 :
627 : That's not really a jump threading opportunity, but instead is
628 : simple cprop & simplification. We could handle it here if we
629 : wanted by wiring up all the incoming edges. If we run this
630 : early in IPA, that might be worth doing. For now we just
631 : reject that case. */
632 40915088 : if (m_path.length () <= 1)
633 : return false;
634 :
635 40915088 : gimple_stmt_iterator gsi;
636 40915088 : loop_p loop = m_path[0]->loop_father;
637 :
638 : // We recompute the following, when we rewrite possibly_profitable_path_p
639 : // to work incrementally on added BBs we have to unwind them on backtracking
640 40915088 : m_n_insns = 0;
641 40915088 : m_threaded_through_latch = false;
642 40915088 : m_multiway_branch_in_path = false;
643 40915088 : m_contains_hot_bb = false;
644 :
645 40915088 : if (dump_file && (dump_flags & TDF_DETAILS))
646 651 : fprintf (dump_file, "Checking profitability of path (backwards): ");
647 :
648 : /* Count the number of instructions on the path: as these instructions
649 : will have to be duplicated, we will not record the path if there
650 : are too many instructions on the path. Also check that all the
651 : blocks in the path belong to a single loop. */
652 172335108 : for (unsigned j = 0; j < m_path.length (); j++)
653 : {
654 131459831 : basic_block bb = m_path[j];
655 :
656 131459831 : if (dump_file && (dump_flags & TDF_DETAILS))
657 2315 : fprintf (dump_file, " bb:%i", bb->index);
658 : /* Remember, blocks in the path are stored in opposite order in
659 : the PATH array. The last entry in the array represents the
660 : block with an outgoing edge that we will redirect to the jump
661 : threading path. Thus we don't care how many statements are
662 : in that block because it will not be copied or whether or not
663 : it ends in a multiway branch. */
664 262919662 : if (j < m_path.length () - 1)
665 : {
666 90584554 : int orig_n_insns = m_n_insns;
667 90584554 : if (!m_contains_hot_bb && m_speed_p)
668 39469857 : m_contains_hot_bb |= optimize_bb_for_speed_p (bb);
669 90584554 : for (gsi = gsi_after_labels (bb);
670 361537712 : !gsi_end_p (gsi);
671 270953158 : gsi_next_nondebug (&gsi))
672 : {
673 : /* Do not allow OpenACC loop markers and __builtin_constant_p on
674 : threading paths. The latter is disallowed, because an
675 : expression might be constant on two threading paths, and
676 : become non-constant (i.e.: phi) when they merge. */
677 270992969 : gimple *stmt = gsi_stmt (gsi);
678 270992969 : if (gimple_call_internal_p (stmt, IFN_UNIQUE)
679 270992969 : || gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
680 : {
681 39811 : if (dump_file && (dump_flags & TDF_DETAILS))
682 0 : fputc ('\n', dump_file);
683 : return false;
684 : }
685 : /* Do not count empty statements and labels. */
686 270953158 : if (gimple_code (stmt) != GIMPLE_NOP
687 270953158 : && !is_gimple_debug (stmt))
688 225043958 : m_n_insns += estimate_num_insns (stmt, &eni_size_weights);
689 : }
690 90544743 : if (dump_file && (dump_flags & TDF_DETAILS))
691 1664 : fprintf (dump_file, " (%i insns)", m_n_insns-orig_n_insns);
692 :
693 : /* We do not look at the block with the threaded branch
694 : in this loop. So if any block with a last statement that
695 : is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
696 : multiway branch on our path.
697 :
698 : The block in PATH[0] is special, it's the block were we're
699 : going to be able to eliminate its branch. */
700 90544743 : if (j > 0)
701 : {
702 49643070 : gimple *last = *gsi_last_bb (bb);
703 49643070 : if (last
704 49643070 : && (gimple_code (last) == GIMPLE_SWITCH
705 46258480 : || gimple_code (last) == GIMPLE_GOTO))
706 296710 : m_multiway_branch_in_path = true;
707 : }
708 : }
709 :
710 : /* Note if we thread through the latch, we will want to include
711 : the last entry in the array when determining if we thread
712 : through the loop latch. */
713 131420020 : if (loop->latch == bb)
714 : {
715 6149788 : m_threaded_through_latch = true;
716 6149788 : if (dump_file && (dump_flags & TDF_DETAILS))
717 104 : fprintf (dump_file, " (latch)");
718 : }
719 : }
720 :
721 : /* We are going to remove the control statement at the end of the
722 : last block in the threading path. So don't count it against our
723 : statement count. */
724 40875277 : m_n_insns -= m_exit_jump_benefit;
725 :
726 40875277 : if (dump_file && (dump_flags & TDF_DETAILS))
727 651 : fprintf (dump_file, "\n Control statement insns: %i\n"
728 : " Overall: %i insns\n",
729 : m_exit_jump_benefit, m_n_insns);
730 :
731 : /* Threading is profitable if the path duplicated is hot but also
732 : in a case we separate cold path from hot path and permit optimization
733 : of the hot path later. Be on the aggressive side here. In some testcases,
734 : as in PR 78407 this leads to noticeable improvements. */
735 40875277 : if (m_speed_p)
736 : {
737 36721424 : if (m_n_insns >= param_max_fsm_thread_path_insns)
738 : {
739 7992 : if (dump_file && (dump_flags & TDF_DETAILS))
740 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
741 : "the number of instructions on the path "
742 : "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
743 : return false;
744 : }
745 73426864 : edge entry = find_edge (m_path[m_path.length () - 1],
746 36713432 : m_path[m_path.length () - 2]);
747 36713432 : if (probably_never_executed_edge_p (cfun, entry))
748 : {
749 143021 : if (dump_file && (dump_flags & TDF_DETAILS))
750 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
751 : "path entry is probably never executed.\n");
752 : return false;
753 : }
754 : }
755 4153853 : else if (m_n_insns > 1)
756 : {
757 1412906 : if (dump_file && (dump_flags & TDF_DETAILS))
758 11 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
759 : "duplication of %i insns is needed and optimizing for size.\n",
760 : m_n_insns);
761 : return false;
762 : }
763 :
764 : /* The generic copier used by the backthreader does not re-use an
765 : existing threading path to reduce code duplication. So for that
766 : case, drastically reduce the number of statements we are allowed
767 : to copy. We don't know yet whether we will thread through the latch
768 : so we have to be permissive and continue threading, but indicate
769 : to the caller the thread, if final, wouldn't be profitable. */
770 39311358 : if ((!m_threaded_multiway_branch
771 164367 : || !loop->latch
772 163494 : || loop->latch->index == EXIT_BLOCK)
773 39209103 : && (m_n_insns * param_fsm_scale_path_stmts
774 39209103 : >= param_max_jump_thread_duplication_stmts))
775 : {
776 10413637 : if (dump_file && (dump_flags & TDF_DETAILS))
777 68 : fprintf (dump_file,
778 : " FAIL: Did not thread around loop and would copy too "
779 : "many statements.\n");
780 : return false;
781 : }
782 4449621 : *large_non_fsm = (!(m_threaded_through_latch && m_threaded_multiway_branch)
783 28897721 : && (m_n_insns * param_fsm_scale_path_stmts
784 28875237 : >= param_max_jump_thread_duplication_stmts));
785 :
786 28897721 : if (dump_file && (dump_flags & TDF_DETAILS))
787 572 : fputc ('\n', dump_file);
788 : return true;
789 : }
790 :
791 : /* Examine jump threading path PATH and return TRUE if it is profitable to
792 : thread it, otherwise return FALSE.
793 :
794 : The taken edge out of the path is TAKEN_EDGE.
795 :
796 : CREATES_IRREDUCIBLE_LOOP is set to TRUE if threading this path
797 : would create an irreducible loop.
798 :
799 : ?? It seems we should be able to loosen some of the restrictions in
800 : this function after loop optimizations have run. */
801 :
802 : bool
803 2969814 : back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
804 : edge taken_edge,
805 : bool *creates_irreducible_loop)
806 : {
807 : // We can assume that possibly_profitable_path_p holds here
808 :
809 2969814 : loop_p loop = m_path[0]->loop_father;
810 :
811 2969814 : if (dump_file && (dump_flags & TDF_DETAILS))
812 141 : fprintf (dump_file, "Checking profitability of path (backwards): ");
813 :
814 : /* If this path threaded through the loop latch back into the
815 : same loop and the destination does not dominate the loop
816 : latch, then this thread would create an irreducible loop. */
817 2969814 : *creates_irreducible_loop = false;
818 2969814 : if (m_threaded_through_latch
819 124854 : && loop == taken_edge->dest->loop_father
820 3084362 : && (determine_bb_domination_status (loop, taken_edge->dest)
821 : == DOMST_NONDOMINATING))
822 80266 : *creates_irreducible_loop = true;
823 :
824 : /* Threading is profitable if the path duplicated is hot but also
825 : in a case we separate cold path from hot path and permit optimization
826 : of the hot path later. Be on the aggressive side here. In some testcases,
827 : as in PR 78407 this leads to noticeable improvements. */
828 2969814 : if (m_speed_p
829 2969814 : && (optimize_edge_for_speed_p (taken_edge) || m_contains_hot_bb))
830 : {
831 1801893 : if (probably_never_executed_edge_p (cfun, taken_edge))
832 : {
833 27341 : if (dump_file && (dump_flags & TDF_DETAILS))
834 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
835 : "path leads to probably never executed edge.\n");
836 : return false;
837 : }
838 : }
839 1167921 : else if (m_n_insns > 1)
840 : {
841 208781 : if (dump_file && (dump_flags & TDF_DETAILS))
842 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
843 : "duplication of %i insns is needed and optimizing for size.\n",
844 : m_n_insns);
845 : return false;
846 : }
847 :
848 : /* We avoid creating irreducible inner loops unless we thread through
849 : a multiway branch, in which case we have deemed it worth losing
850 : other loop optimizations later.
851 :
852 : We also consider it worth creating an irreducible inner loop after
853 : loop optimizations if the number of copied statement is low. */
854 2733692 : if (!m_threaded_multiway_branch
855 2727129 : && *creates_irreducible_loop
856 74414 : && (!(cfun->curr_properties & PROP_loop_opts_done)
857 36189 : || (m_n_insns * param_fsm_scale_path_stmts
858 36189 : >= param_max_jump_thread_duplication_stmts)))
859 : {
860 38225 : if (dump_file && (dump_flags & TDF_DETAILS))
861 1 : fprintf (dump_file,
862 : " FAIL: Would create irreducible loop early without "
863 : "threading multiway branch.\n");
864 : /* We compute creates_irreducible_loop only late. */
865 : return false;
866 : }
867 :
868 : /* The generic copier used by the backthreader does not re-use an
869 : existing threading path to reduce code duplication. So for that
870 : case, drastically reduce the number of statements we are allowed
871 : to copy. */
872 2695467 : if (!(m_threaded_through_latch && m_threaded_multiway_branch)
873 2692971 : && (m_n_insns * param_fsm_scale_path_stmts
874 2692971 : >= param_max_jump_thread_duplication_stmts))
875 : {
876 0 : if (dump_file && (dump_flags & TDF_DETAILS))
877 0 : fprintf (dump_file,
878 : " FAIL: Did not thread around loop and would copy too "
879 : "many statements.\n");
880 : return false;
881 : }
882 :
883 : /* When there is a multi-way branch on the path, then threading can
884 : explode the CFG due to duplicating the edges for that multi-way
885 : branch. So like above, only allow a multi-way branch on the path
886 : if we actually thread a multi-way branch. */
887 2695467 : if (!m_threaded_multiway_branch && m_multiway_branch_in_path)
888 : {
889 157 : if (dump_file && (dump_flags & TDF_DETAILS))
890 6 : fprintf (dump_file,
891 : " FAIL: Thread through multiway branch without threading "
892 : "a multiway branch.\n");
893 : return false;
894 : }
895 :
896 : /* Threading through an empty latch would cause code to be added to
897 : the latch. This could alter the loop form sufficiently to cause
898 : loop optimizations to fail. Disable these threads until after
899 : loop optimizations have run. */
900 2613062 : if ((m_threaded_through_latch || taken_edge->dest == loop->latch)
901 690171 : && !(cfun->curr_properties & PROP_loop_opts_done)
902 3208363 : && empty_block_p (loop->latch))
903 : {
904 149331 : if (dump_file && (dump_flags & TDF_DETAILS))
905 15 : fprintf (dump_file,
906 : " FAIL: Thread through latch before loop opts would create "
907 : "non-empty latch\n");
908 : return false;
909 : }
910 2545979 : if (dump_file && (dump_flags & TDF_DETAILS))
911 119 : fputc ('\n', dump_file);
912 : return true;
913 : }
914 :
915 :
916 : /* The current path PATH is a vector of blocks forming a jump threading
917 : path in reverse order. TAKEN_EDGE is the edge taken from path[0].
918 :
919 : Convert the current path into the form used by register_jump_thread and
920 : register it.
921 :
922 : Return TRUE if successful or FALSE otherwise. */
923 :
924 : bool
925 2545979 : back_threader_registry::register_path (const vec<basic_block> &m_path,
926 : edge taken_edge)
927 : {
928 2545979 : vec<jump_thread_edge *> *jump_thread_path = allocate_thread_path ();
929 :
930 : // The generic copier ignores the edge type. We can build the
931 : // thread edges with any type.
932 8675510 : for (unsigned int j = 0; j + 1 < m_path.length (); j++)
933 : {
934 3583552 : basic_block bb1 = m_path[m_path.length () - j - 1];
935 3583552 : basic_block bb2 = m_path[m_path.length () - j - 2];
936 :
937 3583552 : edge e = find_edge (bb1, bb2);
938 3583552 : gcc_assert (e);
939 3583552 : push_edge (jump_thread_path, e, EDGE_COPY_SRC_BLOCK);
940 : }
941 :
942 2545979 : push_edge (jump_thread_path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
943 2545979 : return register_jump_thread (jump_thread_path);
944 : }
945 :
946 : // Thread all suitable paths in the current function.
947 : //
948 : // Return TODO_flags.
949 :
950 : unsigned int
951 6466976 : back_threader::thread_blocks ()
952 : {
953 6466976 : basic_block bb;
954 62319255 : FOR_EACH_BB_FN (bb, m_fun)
955 82148099 : if (EDGE_COUNT (bb->succs) > 1)
956 26295820 : maybe_thread_block (bb);
957 :
958 6466976 : bool changed = m_registry.thread_through_all_blocks (true);
959 :
960 6466976 : if (m_flags & BT_SPEED)
961 3925556 : return changed ? TODO_cleanup_cfg : 0;
962 :
963 : return false;
964 : }
965 :
966 : namespace {
967 :
968 : const pass_data pass_data_early_thread_jumps =
969 : {
970 : GIMPLE_PASS,
971 : "ethread",
972 : OPTGROUP_NONE,
973 : TV_TREE_SSA_THREAD_JUMPS,
974 : ( PROP_cfg | PROP_ssa ),
975 : 0,
976 : 0,
977 : 0,
978 : ( TODO_cleanup_cfg | TODO_update_ssa ),
979 : };
980 :
981 : const pass_data pass_data_thread_jumps =
982 : {
983 : GIMPLE_PASS,
984 : "thread",
985 : OPTGROUP_NONE,
986 : TV_TREE_SSA_THREAD_JUMPS,
987 : ( PROP_cfg | PROP_ssa ),
988 : 0,
989 : 0,
990 : 0,
991 : TODO_update_ssa,
992 : };
993 :
994 : const pass_data pass_data_thread_jumps_full =
995 : {
996 : GIMPLE_PASS,
997 : "threadfull",
998 : OPTGROUP_NONE,
999 : TV_TREE_SSA_THREAD_JUMPS,
1000 : ( PROP_cfg | PROP_ssa ),
1001 : 0,
1002 : 0,
1003 : 0,
1004 : TODO_update_ssa,
1005 : };
1006 :
1007 : // Early jump threading pass optimizing for size.
1008 : class pass_early_thread_jumps : public gimple_opt_pass
1009 : {
1010 : public:
1011 294196 : pass_early_thread_jumps (gcc::context *ctxt)
1012 588392 : : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
1013 : {}
1014 :
1015 0 : opt_pass * clone () override
1016 : {
1017 0 : return new pass_early_thread_jumps (m_ctxt);
1018 : }
1019 294196 : void set_pass_param (unsigned int, bool param) override
1020 : {
1021 294196 : m_first = param;
1022 294196 : }
1023 2541743 : bool gate (function *) override
1024 : {
1025 2541743 : return flag_thread_jumps;
1026 : }
1027 2541420 : unsigned int execute (function *fun) override
1028 : {
1029 2541420 : back_threader threader (fun, BT_NONE, m_first);
1030 2541420 : return threader.thread_blocks ();
1031 2541420 : }
1032 : private:
1033 : bool m_first;
1034 : };
1035 :
1036 : // Jump threading pass without resolving of unknown SSAs.
1037 : class pass_thread_jumps : public gimple_opt_pass
1038 : {
1039 : public:
1040 588392 : pass_thread_jumps (gcc::context *ctxt)
1041 1176784 : : gimple_opt_pass (pass_data_thread_jumps, ctxt)
1042 : {}
1043 294196 : opt_pass * clone (void) override
1044 : {
1045 294196 : return new pass_thread_jumps (m_ctxt);
1046 : }
1047 588392 : void set_pass_param (unsigned int, bool param) override
1048 : {
1049 588392 : m_first = param;
1050 588392 : }
1051 2120778 : bool gate (function *) override
1052 : {
1053 2120778 : return flag_thread_jumps && flag_expensive_optimizations;
1054 : }
1055 1962774 : unsigned int execute (function *fun) override
1056 : {
1057 1962774 : back_threader threader (fun, BT_SPEED, m_first);
1058 1962774 : return threader.thread_blocks ();
1059 1962774 : }
1060 : private:
1061 : bool m_first;
1062 : };
1063 :
1064 : // Jump threading pass that fully resolves unknown SSAs.
1065 : class pass_thread_jumps_full : public gimple_opt_pass
1066 : {
1067 : public:
1068 588392 : pass_thread_jumps_full (gcc::context *ctxt)
1069 1176784 : : gimple_opt_pass (pass_data_thread_jumps_full, ctxt)
1070 : {}
1071 294196 : opt_pass * clone (void) override
1072 : {
1073 294196 : return new pass_thread_jumps_full (m_ctxt);
1074 : }
1075 588392 : void set_pass_param (unsigned int, bool param) override
1076 : {
1077 588392 : m_first = param;
1078 588392 : }
1079 2120778 : bool gate (function *) override
1080 : {
1081 2120778 : return flag_thread_jumps && flag_expensive_optimizations;
1082 : }
1083 1962782 : unsigned int execute (function *fun) override
1084 : {
1085 1962782 : back_threader threader (fun, BT_SPEED | BT_RESOLVE, m_first);
1086 1962782 : return threader.thread_blocks ();
1087 1962782 : }
1088 : private:
1089 : bool m_first;
1090 : };
1091 :
1092 : } // namespace {
1093 :
1094 : gimple_opt_pass *
1095 294196 : make_pass_thread_jumps (gcc::context *ctxt)
1096 : {
1097 294196 : return new pass_thread_jumps (ctxt);
1098 : }
1099 :
1100 : gimple_opt_pass *
1101 294196 : make_pass_thread_jumps_full (gcc::context *ctxt)
1102 : {
1103 294196 : return new pass_thread_jumps_full (ctxt);
1104 : }
1105 :
1106 : gimple_opt_pass *
1107 294196 : make_pass_early_thread_jumps (gcc::context *ctxt)
1108 : {
1109 294196 : return new pass_early_thread_jumps (ctxt);
1110 : }
|
