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 "tree-ssa-threadbackward.h"
44 : #include "ssa.h"
45 : #include "tree-cfgcleanup.h"
46 : #include "tree-pretty-print.h"
47 : #include "cfghooks.h"
48 : #include "dbgcnt.h"
49 :
50 : // Class to abstract the profitability code for the backwards threader.
51 :
52 44484810 : class back_threader_profitability
53 : {
54 : public:
55 : back_threader_profitability (bool speed_p, gimple *stmt);
56 : void push_bb (const vec<basic_block> &);
57 : void pop_bb ();
58 : bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
59 : bool profitable_path_p (const vec<basic_block> &,
60 : edge taken, bool *irreducible_loop);
61 : private:
62 : int account_bb (basic_block, bool);
63 : // Number of insns on the path, less the branch we get to remove.
64 112955380 : int net_insns () const { return m_stats.n_insns - m_exit_jump_benefit; }
65 : const bool m_speed_p;
66 : int m_exit_jump_benefit;
67 : bool m_threaded_multiway_branch;
68 : // The loop the path starts in, i.e. m_path[0]->loop_father.
69 : class loop *m_loop;
70 : // The following are accumulated by push_bb as the path grows and
71 : // restored by pop_bb as it shrinks.
72 : struct path_stats
73 : {
74 : int n_insns;
75 : bool threaded_through_latch;
76 : bool multiway_branch_in_path;
77 : bool contains_hot_bb;
78 : bool unprofitable_bb;
79 : };
80 : path_stats m_stats;
81 : // One entry per push. These are the stats as they stood before that push,
82 : // and the insns of the block. Basically the entry pushed for m_path[i]
83 : // accounts m_path[i - 1].
84 : struct unwind_state
85 : {
86 : path_stats stats;
87 : int bb_insns;
88 : };
89 : auto_vec<unwind_state, 20> m_unwind;
90 : };
91 :
92 22242405 : back_threader_profitability::back_threader_profitability (bool speed_p,
93 : gimple *last)
94 22242405 : : m_speed_p (speed_p)
95 : {
96 22242405 : m_threaded_multiway_branch = (gimple_code (last) == GIMPLE_SWITCH
97 22242405 : || gimple_code (last) == GIMPLE_GOTO);
98 : // The forward threader has estimate_threading_killed_stmts, in
99 : // particular it estimates further DCE from eliminating the exit
100 : // control stmt.
101 22242405 : m_exit_jump_benefit = estimate_num_insns (last, &eni_size_weights);
102 22242405 : m_loop = NULL;
103 22242405 : m_stats = path_stats ();
104 22242405 : }
105 :
106 : /* Account for BB in the cumulative stats for the path being threaded.
107 : CHECK_MULTIWAY is true for all blocks except the block whose branch
108 : we are going to eliminate. Return the number of insns in BB, which
109 : PUSH_BB records so the dump can print a per-block count. */
110 :
111 : int
112 40956595 : back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
113 : {
114 40956595 : int n_insns = 0;
115 :
116 40956595 : if (!m_stats.contains_hot_bb && m_speed_p)
117 13989935 : m_stats.contains_hot_bb |= optimize_bb_for_speed_p (bb);
118 :
119 40956595 : for (gimple_stmt_iterator gsi = gsi_after_labels (bb);
120 187635532 : !gsi_end_p (gsi);
121 146678937 : gsi_next_nondebug (&gsi))
122 : {
123 : /* Do not allow OpenACC loop markers and __builtin_constant_p on
124 : threading paths. The latter is disallowed, because an
125 : expression might be constant on two threading paths, and
126 : become non-constant (i.e.: phi) when they merge. */
127 146717733 : gimple *stmt = gsi_stmt (gsi);
128 146717733 : if (gimple_call_internal_p (stmt, IFN_UNIQUE)
129 146717733 : || gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
130 : {
131 38796 : m_stats.unprofitable_bb = true;
132 38796 : return n_insns;
133 : }
134 : /* Do not count empty statements and labels. */
135 146678937 : if (gimple_code (stmt) != GIMPLE_NOP
136 146678937 : && !is_gimple_debug (stmt))
137 126661420 : n_insns += estimate_num_insns (stmt, &eni_size_weights);
138 : }
139 :
140 : /* We do not look at the block with the threaded branch in this loop.
141 : So if any block with a last statement that is a GIMPLE_SWITCH or
142 : GIMPLE_GOTO is seen, then we have a multiway branch on our path. */
143 40917799 : if (check_multiway)
144 : {
145 25258817 : gimple *last = *gsi_last_bb (bb);
146 25258817 : if (last
147 25258817 : && (gimple_code (last) == GIMPLE_SWITCH
148 23763909 : || gimple_code (last) == GIMPLE_GOTO))
149 285319 : m_stats.multiway_branch_in_path = true;
150 : }
151 :
152 : return n_insns;
153 : }
154 :
155 : /* Update the stats after a block has been appended to PATH. */
156 :
157 : void
158 63199000 : back_threader_profitability::push_bb (const vec<basic_block> &path)
159 : {
160 63199000 : unwind_state state = { m_stats, /*bb_insns=*/0 };
161 :
162 63199000 : unsigned n = path.length ();
163 63199000 : if (n == 1)
164 22242405 : m_loop = path[0]->loop_father;
165 : else
166 : {
167 : /* Appending a block makes the previous entry block part of the copied
168 : path, so that's where to account for now. */
169 40956595 : unsigned copied = n - 2;
170 40956595 : bool check_multiway = copied > 0;
171 40956595 : state.bb_insns = account_bb (path[copied], check_multiway);
172 40956595 : m_stats.n_insns += state.bb_insns;
173 : }
174 63199000 : m_unwind.safe_push (state);
175 :
176 : /* Note if we thread through the latch, we will want to include the
177 : last entry in the array when determining if we thread through the
178 : loop latch. */
179 63199000 : if (m_loop->latch == path[n - 1])
180 3400399 : m_stats.threaded_through_latch = true;
181 63199000 : }
182 :
183 : void
184 63199000 : back_threader_profitability::pop_bb ()
185 : {
186 63199000 : m_stats = m_unwind.pop ().stats;
187 63199000 : }
188 :
189 : // Used to differentiate unreachable edges, so we may stop the search
190 : // in a the given direction.
191 : const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
192 :
193 6523291 : back_threader::back_threader (function *fun, unsigned flags, bool first)
194 6523291 : : m_visited_flag (fun), m_first (first)
195 : {
196 6523291 : if (flags & BT_SPEED)
197 3954356 : loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
198 : else
199 2568935 : loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
200 :
201 6523291 : m_fun = fun;
202 6523291 : m_flags = flags;
203 6523291 : m_last_stmt = NULL;
204 :
205 : // The path solver needs EDGE_DFS_BACK in resolving mode.
206 6523291 : if (flags & BT_RESOLVE)
207 1977181 : mark_dfs_back_edges ();
208 :
209 6523291 : m_ranger = new gimple_ranger;
210 6523291 : m_solver = NULL;
211 6523291 : }
212 :
213 6523291 : back_threader::~back_threader ()
214 : {
215 6523291 : delete m_ranger;
216 6523291 : loop_optimizer_finalize ();
217 6523291 : }
218 :
219 : // A wrapper for the various debug counters for the threading passes.
220 : // Returns TRUE if it's OK to register the current threading
221 : // candidate.
222 :
223 : bool
224 2546120 : back_threader::debug_counter ()
225 : {
226 : // The ethread pass is mostly harmless ;-).
227 2546120 : if ((m_flags & BT_SPEED) == 0)
228 : return true;
229 :
230 1727115 : if (m_flags & BT_RESOLVE)
231 : {
232 1185677 : if (m_first && !dbg_cnt (back_threadfull1))
233 : return false;
234 :
235 1185677 : if (!m_first && !dbg_cnt (back_threadfull2))
236 : return false;
237 : }
238 : else
239 : {
240 541438 : if (m_first && !dbg_cnt (back_thread1))
241 : return false;
242 :
243 541438 : if (!m_first && !dbg_cnt (back_thread2))
244 : return false;
245 : }
246 : return true;
247 : }
248 :
249 : static void
250 590 : dump_path (FILE *dump_file, const vec<basic_block> &path)
251 : {
252 3143 : for (unsigned i = path.length (); i > 0; --i)
253 : {
254 1963 : basic_block bb = path[i - 1];
255 1963 : fprintf (dump_file, "%d", bb->index);
256 1963 : if (i > 1)
257 1373 : fprintf (dump_file, "->");
258 : }
259 590 : }
260 :
261 : // Dump details of an attempt to register a path.
262 :
263 : void
264 590 : back_threader::maybe_register_path_dump (edge taken)
265 : {
266 590 : if (m_path.is_empty ())
267 : return;
268 :
269 590 : fprintf (dump_file, "path: ");
270 590 : dump_path (dump_file, m_path);
271 590 : fprintf (dump_file, "->");
272 :
273 590 : if (taken == UNREACHABLE_EDGE)
274 11 : fprintf (dump_file, "xx REJECTED (unreachable)\n");
275 579 : else if (taken)
276 113 : fprintf (dump_file, "%d SUCCESS\n", taken->dest->index);
277 : else
278 466 : fprintf (dump_file, "xx REJECTED\n");
279 : }
280 :
281 : // If an outgoing edge can be determined out of the current path,
282 : // register it for jump threading and return the taken edge.
283 : //
284 : // Return NULL if it is unprofitable to thread this path, or the
285 : // outgoing edge is unknown. Return UNREACHABLE_EDGE if the path is
286 : // unreachable.
287 :
288 : edge
289 28857336 : back_threader::maybe_register_path (back_threader_profitability &profit)
290 : {
291 28857336 : edge taken_edge = find_taken_edge (m_path);
292 :
293 28857336 : if (taken_edge && taken_edge != UNREACHABLE_EDGE)
294 : {
295 2977367 : bool irreducible = false;
296 2977367 : if (profit.profitable_path_p (m_path, taken_edge, &irreducible)
297 2546120 : && debug_counter ()
298 5523487 : && m_registry.register_path (m_path, taken_edge))
299 : {
300 1467059 : if (irreducible)
301 34863 : vect_free_loop_info_assumptions (m_path[0]->loop_father);
302 : }
303 : else
304 : taken_edge = NULL;
305 : }
306 :
307 28857336 : if (dump_file && (dump_flags & TDF_DETAILS))
308 590 : maybe_register_path_dump (taken_edge);
309 :
310 28857336 : return taken_edge;
311 : }
312 :
313 : // Return the known taken edge out of a path. If the path can be
314 : // determined to be unreachable, return UNREACHABLE_EDGE. If no
315 : // outgoing edge can be calculated, return NULL.
316 :
317 : edge
318 28857336 : back_threader::find_taken_edge (const vec<basic_block> &path)
319 : {
320 28857336 : gcc_checking_assert (path.length () > 1);
321 28857336 : switch (gimple_code (m_last_stmt))
322 : {
323 28761705 : case GIMPLE_COND:
324 28761705 : return find_taken_edge_cond (path, as_a<gcond *> (m_last_stmt));
325 :
326 94182 : case GIMPLE_SWITCH:
327 94182 : return find_taken_edge_switch (path, as_a<gswitch *> (m_last_stmt));
328 :
329 1449 : case GIMPLE_GOTO:
330 1449 : return find_taken_edge_goto (path, as_a<ggoto *> (m_last_stmt));
331 :
332 : default:
333 : return NULL;
334 : }
335 : }
336 :
337 : // Same as find_taken_edge, but for paths ending in a computed goto.
338 :
339 : edge
340 1449 : back_threader::find_taken_edge_goto (const vec<basic_block> &path,
341 : ggoto *stmt)
342 : {
343 1449 : tree dest = gimple_goto_dest (stmt);
344 :
345 1449 : if (TREE_CODE (dest) == SSA_NAME)
346 : {
347 1449 : prange r;
348 1449 : m_solver->reset_path (path, m_imports);
349 1449 : if (!m_solver->range_of_expr (r, dest, stmt))
350 : return NULL;
351 :
352 1449 : if (r.undefined_p ())
353 : return UNREACHABLE_EDGE;
354 :
355 1417 : dest = r.pt_invariant ();
356 186 : if (!dest)
357 : return NULL;
358 1449 : }
359 :
360 : // For a destination that did not resolve to a label,
361 : // ::find_taken_edge at most returns the block's single successor,
362 : // the only place it could go.
363 186 : return ::find_taken_edge (gimple_bb (stmt), dest);
364 : }
365 :
366 : // Same as find_taken_edge, but for paths ending in a switch.
367 :
368 : edge
369 94182 : back_threader::find_taken_edge_switch (const vec<basic_block> &path,
370 : gswitch *sw)
371 : {
372 94182 : tree name = gimple_switch_index (sw);
373 94182 : int_range_max r;
374 :
375 94182 : m_solver->reset_path (path, m_imports);
376 94182 : m_solver->range_of_expr (r, name, sw);
377 :
378 94182 : if (r.undefined_p ())
379 : return UNREACHABLE_EDGE;
380 :
381 93726 : if (r.varying_p ())
382 : return NULL;
383 :
384 63399 : tree label = find_case_label_range (sw, &r);
385 63399 : if (!label)
386 : return NULL;
387 :
388 6930 : return find_edge (gimple_bb (sw), label_to_block (cfun, CASE_LABEL (label)));
389 94182 : }
390 :
391 : // Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
392 :
393 : edge
394 28761705 : back_threader::find_taken_edge_cond (const vec<basic_block> &path,
395 : gcond *cond)
396 : {
397 28761705 : int_range_max r;
398 :
399 28761705 : m_solver->reset_path (path, m_imports);
400 28761705 : m_solver->range_of_stmt (r, cond);
401 :
402 28761705 : if (m_solver->unreachable_path_p ())
403 : return UNREACHABLE_EDGE;
404 :
405 28641688 : int_range<2> true_range = range_true ();
406 28641688 : int_range<2> false_range = range_false ();
407 :
408 28641688 : if (r == true_range || r == false_range)
409 : {
410 2970253 : edge e_true, e_false;
411 2970253 : basic_block bb = gimple_bb (cond);
412 2970253 : extract_true_false_edges_from_block (bb, &e_true, &e_false);
413 2970253 : return r == true_range ? e_true : e_false;
414 : }
415 : return NULL;
416 28761705 : }
417 :
418 : // Find jump threading paths to any of the SSA names in the
419 : // INTERESTING bitmap, and register any such paths.
420 : //
421 : // BB is the current path being processed.
422 : //
423 : // OVERALL_PATHS is the search space up to this block
424 :
425 : void
426 64779631 : back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
427 : unsigned overall_paths,
428 : back_threader_profitability &profit)
429 : {
430 64779631 : if (bb->flags & m_visited_flag)
431 1580631 : return;
432 :
433 63199000 : bb->flags |= m_visited_flag;
434 :
435 63199000 : m_path.safe_push (bb);
436 63199000 : profit.push_bb (m_path);
437 :
438 : // Try to resolve the path without looking back. Avoid resolving paths
439 : // we know are large but are not (yet) recognized as Finite State Machine.
440 : // ??? Ideally we'd explore the cheapest path to the loop backedge here,
441 : // avoiding the exponential greedy search and only start that from there.
442 : // Precomputing a path-size-to-immediate-dominator-of-successor for each
443 : // edge might help here. Alternatively copying divergent control flow
444 : // on the way to the backedge could be worthwhile.
445 63199000 : bool large_non_fsm;
446 63199000 : edge e;
447 63199000 : if (m_path.length () > 1
448 63199000 : && (!profit.possibly_profitable_path_p (m_path, &large_non_fsm)
449 28912962 : || (!large_non_fsm
450 28857336 : && maybe_register_path (profit))))
451 : ;
452 :
453 : // The backwards thread copier cannot copy blocks that do not belong
454 : // to the same loop, so when the new source of the path entry no
455 : // longer belongs to it we don't need to search further.
456 49567803 : else if (m_path[0]->loop_father != bb->loop_father
457 55144596 : && (!(e = loop_exits_from_bb_p (m_path[0]->loop_father,
458 5576793 : m_path[0]))
459 3891874 : || e->dest->loop_father != bb->loop_father))
460 : ;
461 :
462 : // Continue looking for ways to extend the path but limit the
463 : // search space along a branch
464 47129549 : else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds))
465 47129549 : <= (unsigned)param_max_jump_thread_paths)
466 : {
467 : // For further greedy searching we want to remove interesting
468 : // names defined in BB but add ones on the PHI edges for the
469 : // respective edges and adding imports from those stmts.
470 : // We do this by starting with all names
471 : // not defined in BB as interesting, collecting a list of
472 : // interesting PHIs in BB on the fly. Then we iterate over
473 : // predecessor edges, adding interesting PHI edge defs to
474 : // the set of interesting names to consider when processing it.
475 47006084 : auto_bitmap new_interesting;
476 47006084 : auto_vec<int, 16> new_imports;
477 47006084 : auto_vec<gphi *, 4> interesting_phis;
478 47006084 : bitmap_iterator bi;
479 47006084 : unsigned i;
480 47006084 : auto_vec<tree, 16> worklist;
481 : // Add NAME to the list of imports.
482 67785170 : auto add_import = [&] (tree name)
483 : {
484 20779086 : if (bitmap_set_bit (m_imports, SSA_NAME_VERSION (name)))
485 : {
486 18235224 : new_imports.safe_push (SSA_NAME_VERSION (name));
487 18235224 : worklist.safe_push (name);
488 : }
489 67785170 : };
490 105318101 : EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
491 : {
492 58312017 : tree name = ssa_name (i);
493 58312017 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
494 : /* Imports remain interesting. */
495 58312017 : if (gimple_bb (def_stmt) != bb)
496 : {
497 29038440 : bitmap_set_bit (new_interesting, i);
498 29038440 : continue;
499 : }
500 29273577 : worklist.quick_push (name);
501 135329532 : while (!worklist.is_empty ())
502 : {
503 47508801 : tree name = worklist.pop ();
504 47508801 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
505 : /* Newly discovered imports are interesting. */
506 47508801 : if (gimple_bb (def_stmt) != bb)
507 : {
508 5827561 : bitmap_set_bit (new_interesting, SSA_NAME_VERSION (name));
509 5827561 : continue;
510 : }
511 : /* Local PHIs participate in renaming below. */
512 77771900 : if (gphi *phi = dyn_cast<gphi *> (def_stmt))
513 5590580 : interesting_phis.safe_push (phi);
514 : /* For other local defs process their uses, amending
515 : imports on the way. */
516 : else
517 : {
518 36090660 : tree ssa[3];
519 36090660 : unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt);
520 92960406 : for (unsigned j = 0; j < lim; ++j)
521 20779086 : if (ssa[j])
522 20779086 : add_import (ssa[j]);
523 : }
524 : }
525 : }
526 47006084 : if (!bitmap_empty_p (new_interesting)
527 47006084 : || !interesting_phis.is_empty ())
528 : {
529 61207434 : auto_vec<int, 4> unwind (interesting_phis.length ());
530 61207434 : auto_vec<int, 4> imports_unwind (interesting_phis.length ());
531 30603717 : edge_iterator iter;
532 30603717 : edge e;
533 74393457 : FOR_EACH_EDGE (e, iter, bb->preds)
534 : {
535 43789740 : if (e->flags & EDGE_ABNORMAL
536 43787288 : || e->src->index == ENTRY_BLOCK)
537 1252514 : continue;
538 140034943 : for (gphi *phi : interesting_phis)
539 : {
540 12423265 : tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
541 12423265 : if (TREE_CODE (def) == SSA_NAME)
542 : {
543 8758241 : int ver = SSA_NAME_VERSION (def);
544 8758241 : if (bitmap_set_bit (new_interesting, ver))
545 : {
546 8723108 : if (bitmap_set_bit (m_imports, ver))
547 7167001 : imports_unwind.quick_push (ver);
548 8723108 : unwind.quick_push (ver);
549 : }
550 : }
551 : }
552 42537226 : find_paths_to_names (e->src, new_interesting, overall_paths,
553 : profit);
554 : // Restore new_interesting.
555 136334786 : for (int def : unwind)
556 8723108 : bitmap_clear_bit (new_interesting, def);
557 42537226 : unwind.truncate (0);
558 : // Restore and m_imports.
559 134778679 : for (int def : imports_unwind)
560 7167001 : bitmap_clear_bit (m_imports, def);
561 42537226 : imports_unwind.truncate (0);
562 : }
563 30603717 : }
564 : /* m_imports tracks all interesting names on the path, so when
565 : backtracking we have to restore it. */
566 159253476 : for (int j : new_imports)
567 18235224 : bitmap_clear_bit (m_imports, j);
568 47006084 : }
569 123465 : else if (dump_file && (dump_flags & TDF_DETAILS))
570 9 : fprintf (dump_file, " FAIL: Search space limit %d reached.\n",
571 : param_max_jump_thread_paths);
572 :
573 : // Reset things to their original state.
574 63199000 : profit.pop_bb ();
575 63199000 : m_path.pop ();
576 63199000 : bb->flags &= ~m_visited_flag;
577 : }
578 :
579 : // Search backwards from BB looking for paths where the final
580 : // conditional maybe threaded to a successor block. Record such paths
581 : // for jump threading.
582 :
583 : void
584 26670035 : back_threader::maybe_thread_block (basic_block bb)
585 : {
586 26670035 : if (EDGE_COUNT (bb->succs) <= 1)
587 4427630 : return;
588 :
589 26670035 : gimple *stmt = *gsi_last_bb (bb);
590 26670035 : if (!stmt)
591 : return;
592 :
593 26670035 : enum gimple_code code = gimple_code (stmt);
594 26670035 : if (code != GIMPLE_SWITCH
595 26670035 : && code != GIMPLE_COND
596 4380451 : && code != GIMPLE_GOTO)
597 : return;
598 :
599 22290558 : m_last_stmt = stmt;
600 22290558 : m_path.truncate (0);
601 :
602 : // We compute imports of the path during discovery starting
603 : // just with names used in the conditional.
604 22290558 : bitmap_clear (m_imports);
605 22290558 : ssa_op_iter iter;
606 22290558 : tree name;
607 49453186 : FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
608 : {
609 27210781 : if (!gimple_range_ssa_p (name))
610 : return;
611 27162628 : bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
612 : }
613 :
614 : // Interesting is the set of imports we still not have see
615 : // the definition of. So while imports only grow, the
616 : // set of interesting defs dwindles and once empty we can
617 : // stop searching.
618 22242405 : auto_bitmap interesting;
619 22242405 : bitmap_copy (interesting, m_imports);
620 22242405 : back_threader_profitability profit (m_flags & BT_SPEED, stmt);
621 22242405 : find_paths_to_names (bb, interesting, 1, profit);
622 22242405 : }
623 :
624 : DEBUG_FUNCTION void
625 0 : debug (const vec <basic_block> &path)
626 : {
627 0 : dump_path (stderr, path);
628 0 : fputc ('\n', stderr);
629 0 : }
630 :
631 : void
632 0 : back_threader::dump (FILE *out)
633 : {
634 0 : fprintf (out, "\nCandidates for pre-computation:\n");
635 0 : fprintf (out, "===================================\n");
636 :
637 0 : bitmap_iterator bi;
638 0 : unsigned i;
639 :
640 0 : EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
641 : {
642 0 : tree name = ssa_name (i);
643 0 : print_generic_expr (out, name, TDF_NONE);
644 0 : fprintf (out, "\n");
645 : }
646 0 : }
647 :
648 : void
649 0 : back_threader::debug ()
650 : {
651 0 : dump (stderr);
652 0 : }
653 :
654 : /* Examine jump threading path PATH and return TRUE if it is possibly
655 : profitable to thread it, otherwise return FALSE. If this function
656 : returns TRUE profitable_path_p might not be satisfied but when
657 : the path is extended it might be. In particular indicate in
658 : *LARGE_NON_FSM whether the thread is too large for a non-FSM thread
659 : but would be OK if we extend the path to cover the loop backedge.
660 :
661 : ?? It seems we should be able to loosen some of the restrictions in
662 : this function after loop optimizations have run. */
663 :
664 : bool
665 40956595 : back_threader_profitability::possibly_profitable_path_p
666 : (const vec<basic_block> &m_path,
667 : bool *large_non_fsm)
668 : {
669 40956595 : gcc_checking_assert (!m_path.is_empty ());
670 :
671 : /* We can an empty path here (excluding the DEF block) when the
672 : statement that makes a conditional generate a compile-time
673 : constant result is in the same block as the conditional.
674 :
675 : That's not really a jump threading opportunity, but instead is
676 : simple cprop & simplification. We could handle it here if we
677 : wanted by wiring up all the incoming edges. If we run this
678 : early in IPA, that might be worth doing. For now we just
679 : reject that case. */
680 40956595 : if (m_path.length () <= 1)
681 : return false;
682 :
683 40956595 : loop_p loop = m_loop;
684 :
685 40956595 : if (m_stats.unprofitable_bb)
686 : return false;
687 :
688 40917799 : if (dump_file && (dump_flags & TDF_DETAILS))
689 : {
690 681 : fprintf (dump_file, "Checking profitability of path (backwards): ");
691 3751 : for (unsigned j = 0; j < m_path.length (); j++)
692 : {
693 2389 : fprintf (dump_file, " bb:%i", m_path[j]->index);
694 : /* The last block on the path is not copied, so it has no
695 : count of its own. */
696 2389 : if (j + 1 < m_path.length ())
697 1708 : fprintf (dump_file, " (%i insns)", m_unwind[j + 1].bb_insns);
698 2389 : if (loop->latch == m_path[j])
699 104 : fprintf (dump_file, " (latch)");
700 : }
701 681 : fprintf (dump_file, "\n Control statement insns: %i\n"
702 : " Overall: %i insns\n",
703 : m_exit_jump_benefit, net_insns ());
704 : }
705 :
706 : /* Threading is profitable if the path duplicated is hot but also
707 : in a case we separate cold path from hot path and permit optimization
708 : of the hot path later. Be on the aggressive side here. In some testcases,
709 : as in PR 78407 this leads to noticeable improvements. */
710 40917799 : if (m_speed_p)
711 : {
712 36726715 : if (net_insns () >= param_max_fsm_thread_path_insns)
713 : {
714 7533 : if (dump_file && (dump_flags & TDF_DETAILS))
715 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
716 : "the number of instructions on the path "
717 : "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
718 : return false;
719 : }
720 73438364 : edge entry = find_edge (m_path[m_path.length () - 1],
721 36719182 : m_path[m_path.length () - 2]);
722 36719182 : if (probably_never_executed_edge_p (cfun, entry))
723 : {
724 144932 : if (dump_file && (dump_flags & TDF_DETAILS))
725 1 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
726 : "path entry is probably never executed.\n");
727 : return false;
728 : }
729 : }
730 4191084 : else if (net_insns () > 1)
731 : {
732 1424163 : if (dump_file && (dump_flags & TDF_DETAILS))
733 11 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
734 : "duplication of %i insns is needed and optimizing for size.\n",
735 : net_insns ());
736 : return false;
737 : }
738 :
739 : /* The generic copier used by the backthreader does not re-use an
740 : existing threading path to reduce code duplication. So for that
741 : case, drastically reduce the number of statements we are allowed
742 : to copy. We don't know yet whether we will thread through the latch
743 : so we have to be permissive and continue threading, but indicate
744 : to the caller the thread, if final, wouldn't be profitable. */
745 39341171 : if ((!m_threaded_multiway_branch
746 164602 : || !loop->latch
747 163660 : || loop->latch->index == EXIT_BLOCK)
748 39341171 : && (net_insns () * param_fsm_scale_path_stmts
749 39239026 : >= param_max_jump_thread_duplication_stmts))
750 : {
751 10428209 : if (dump_file && (dump_flags & TDF_DETAILS))
752 68 : fprintf (dump_file,
753 : " FAIL: Did not thread around loop and would copy too "
754 : "many statements.\n");
755 : return false;
756 : }
757 4490611 : *large_non_fsm = (!(m_stats.threaded_through_latch
758 : && m_threaded_multiway_branch)
759 28912962 : && (net_insns () * param_fsm_scale_path_stmts
760 28889182 : >= param_max_jump_thread_duplication_stmts));
761 :
762 28912962 : if (dump_file && (dump_flags & TDF_DETAILS))
763 601 : fputc ('\n', dump_file);
764 : return true;
765 : }
766 :
767 : /* Examine jump threading path PATH and return TRUE if it is profitable to
768 : thread it, otherwise return FALSE.
769 :
770 : The taken edge out of the path is TAKEN_EDGE.
771 :
772 : CREATES_IRREDUCIBLE_LOOP is set to TRUE if threading this path
773 : would create an irreducible loop.
774 :
775 : ?? It seems we should be able to loosen some of the restrictions in
776 : this function after loop optimizations have run. */
777 :
778 : bool
779 2977367 : back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
780 : edge taken_edge,
781 : bool *creates_irreducible_loop)
782 : {
783 : // We can assume that possibly_profitable_path_p holds here
784 :
785 2977367 : loop_p loop = m_path[0]->loop_father;
786 :
787 2977367 : if (dump_file && (dump_flags & TDF_DETAILS))
788 156 : fprintf (dump_file, "Checking profitability of path (backwards): ");
789 :
790 : /* If this path threaded through the loop latch back into the
791 : same loop and the destination does not dominate the loop
792 : latch, then this thread would create an irreducible loop. */
793 2977367 : *creates_irreducible_loop = false;
794 2977367 : if (m_stats.threaded_through_latch
795 132686 : && loop == taken_edge->dest->loop_father
796 3099363 : && (determine_bb_domination_status (loop, taken_edge->dest)
797 : == DOMST_NONDOMINATING))
798 86645 : *creates_irreducible_loop = true;
799 :
800 : /* Threading is profitable if the path duplicated is hot but also
801 : in a case we separate cold path from hot path and permit optimization
802 : of the hot path later. Be on the aggressive side here. In some testcases,
803 : as in PR 78407 this leads to noticeable improvements. */
804 2977367 : if (m_speed_p
805 2977367 : && (optimize_edge_for_speed_p (taken_edge) || m_stats.contains_hot_bb))
806 : {
807 1799841 : if (probably_never_executed_edge_p (cfun, taken_edge))
808 : {
809 27526 : if (dump_file && (dump_flags & TDF_DETAILS))
810 3 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
811 : "path leads to probably never executed edge.\n");
812 : return false;
813 : }
814 : }
815 1177526 : else if (net_insns () > 1)
816 : {
817 210376 : if (dump_file && (dump_flags & TDF_DETAILS))
818 0 : fprintf (dump_file, " FAIL: Jump-thread path not considered: "
819 : "duplication of %i insns is needed and optimizing for size.\n",
820 : net_insns ());
821 : return false;
822 : }
823 :
824 : /* We avoid creating irreducible inner loops unless we thread through
825 : a multiway branch, in which case we have deemed it worth losing
826 : other loop optimizations later.
827 :
828 : We also consider it worth creating an irreducible inner loop after
829 : loop optimizations if the number of copied statement is low. */
830 2739465 : if (!m_threaded_multiway_branch
831 2732685 : && *creates_irreducible_loop
832 2820047 : && (!(cfun->curr_properties & PROP_loop_opts_done)
833 37469 : || (net_insns () * param_fsm_scale_path_stmts
834 37469 : >= param_max_jump_thread_duplication_stmts)))
835 : {
836 43113 : if (dump_file && (dump_flags & TDF_DETAILS))
837 1 : fprintf (dump_file,
838 : " FAIL: Would create irreducible loop early without "
839 : "threading multiway branch.\n");
840 : /* We compute creates_irreducible_loop only late. */
841 : return false;
842 : }
843 :
844 : /* The generic copier used by the backthreader does not re-use an
845 : existing threading path to reduce code duplication. So for that
846 : case, drastically reduce the number of statements we are allowed
847 : to copy. */
848 85121 : if (!(m_stats.threaded_through_latch && m_threaded_multiway_branch)
849 2696352 : && (net_insns () * param_fsm_scale_path_stmts
850 2693697 : >= param_max_jump_thread_duplication_stmts))
851 : {
852 0 : if (dump_file && (dump_flags & TDF_DETAILS))
853 0 : fprintf (dump_file,
854 : " FAIL: Did not thread around loop and would copy too "
855 : "many statements.\n");
856 : return false;
857 : }
858 :
859 : /* When there is a multi-way branch on the path, then threading can
860 : explode the CFG due to duplicating the edges for that multi-way
861 : branch. So like above, only allow a multi-way branch on the path
862 : if we actually thread a multi-way branch. */
863 2696352 : if (!m_threaded_multiway_branch && m_stats.multiway_branch_in_path)
864 : {
865 188 : if (dump_file && (dump_flags & TDF_DETAILS))
866 6 : fprintf (dump_file,
867 : " FAIL: Thread through multiway branch without threading "
868 : "a multiway branch.\n");
869 : return false;
870 : }
871 :
872 : /* Threading through an empty latch would cause code to be added to
873 : the latch. This could alter the loop form sufficiently to cause
874 : loop optimizations to fail. Disable these threads until after
875 : loop optimizations have run. */
876 2611048 : if ((m_stats.threaded_through_latch || taken_edge->dest == loop->latch)
877 697536 : && !(cfun->curr_properties & PROP_loop_opts_done)
878 3212308 : && empty_block_p (loop->latch))
879 : {
880 150044 : if (dump_file && (dump_flags & TDF_DETAILS))
881 15 : fprintf (dump_file,
882 : " FAIL: Thread through latch before loop opts would create "
883 : "non-empty latch\n");
884 : return false;
885 : }
886 2546120 : if (dump_file && (dump_flags & TDF_DETAILS))
887 131 : fputc ('\n', dump_file);
888 : return true;
889 : }
890 :
891 :
892 : /* The current path PATH is a vector of blocks forming a jump threading
893 : path in reverse order. TAKEN_EDGE is the edge taken from path[0].
894 :
895 : Convert the current path into the form used by register_jump_thread and
896 : register it.
897 :
898 : Return TRUE if successful or FALSE otherwise. */
899 :
900 : bool
901 2546120 : back_threader_registry::register_path (const vec<basic_block> &m_path,
902 : edge taken_edge)
903 : {
904 2546120 : vec<jump_thread_edge *> *jump_thread_path = allocate_thread_path ();
905 :
906 : // The generic copier ignores the edge type. We can build the
907 : // thread edges with any type.
908 8665688 : for (unsigned int j = 0; j + 1 < m_path.length (); j++)
909 : {
910 3573448 : basic_block bb1 = m_path[m_path.length () - j - 1];
911 3573448 : basic_block bb2 = m_path[m_path.length () - j - 2];
912 :
913 3573448 : edge e = find_edge (bb1, bb2);
914 3573448 : gcc_assert (e);
915 3573448 : push_edge (jump_thread_path, e, EDGE_COPY_SRC_BLOCK);
916 : }
917 :
918 2546120 : push_edge (jump_thread_path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
919 2546120 : return register_jump_thread (jump_thread_path);
920 : }
921 :
922 : // Return a new path solver for the search.
923 :
924 : path_range_query *
925 6523291 : back_threader::make_solver (gimple_ranger &ranger)
926 : {
927 6523291 : return new path_range_query (ranger, m_flags & BT_RESOLVE);
928 : }
929 :
930 : // Find the paths to thread in the current function.
931 :
932 : void
933 6523291 : back_threader::search ()
934 : {
935 6523291 : m_solver = make_solver (*m_ranger);
936 :
937 6523291 : basic_block bb;
938 63047021 : FOR_EACH_BB_FN (bb, m_fun)
939 83193765 : if (EDGE_COUNT (bb->succs) > 1)
940 26670035 : maybe_thread_block (bb);
941 :
942 : // The solver lives as long as the search: the IL changes after it.
943 6523291 : delete m_solver;
944 6523291 : m_solver = NULL;
945 6523291 : }
946 :
947 : // Thread the paths found. Return TODO_flags.
948 :
949 : unsigned int
950 6523291 : back_threader::apply ()
951 : {
952 6523291 : bool changed = m_registry.thread_through_all_blocks (true);
953 :
954 6523291 : if (m_flags & BT_SPEED)
955 3954356 : return changed ? TODO_cleanup_cfg : 0;
956 :
957 : return false;
958 : }
959 :
960 : // Thread all suitable paths in the current function.
961 : //
962 : // Return TODO_flags.
963 :
964 : unsigned int
965 6523291 : back_threader::thread_blocks ()
966 : {
967 6523291 : search ();
968 6523291 : return apply ();
969 : }
970 :
971 : namespace {
972 :
973 : const pass_data pass_data_early_thread_jumps =
974 : {
975 : GIMPLE_PASS,
976 : "ethread",
977 : OPTGROUP_NONE,
978 : TV_TREE_SSA_THREAD_JUMPS,
979 : ( PROP_cfg | PROP_ssa ),
980 : 0,
981 : 0,
982 : 0,
983 : ( TODO_cleanup_cfg | TODO_update_ssa ),
984 : };
985 :
986 : const pass_data pass_data_thread_jumps =
987 : {
988 : GIMPLE_PASS,
989 : "thread",
990 : OPTGROUP_NONE,
991 : TV_TREE_SSA_THREAD_JUMPS,
992 : ( PROP_cfg | PROP_ssa ),
993 : 0,
994 : 0,
995 : 0,
996 : TODO_update_ssa,
997 : };
998 :
999 : const pass_data pass_data_thread_jumps_full =
1000 : {
1001 : GIMPLE_PASS,
1002 : "threadfull",
1003 : OPTGROUP_NONE,
1004 : TV_TREE_SSA_THREAD_JUMPS,
1005 : ( PROP_cfg | PROP_ssa ),
1006 : 0,
1007 : 0,
1008 : 0,
1009 : TODO_update_ssa,
1010 : };
1011 :
1012 : // Early jump threading pass optimizing for size.
1013 : class pass_early_thread_jumps : public gimple_opt_pass
1014 : {
1015 : public:
1016 294536 : pass_early_thread_jumps (gcc::context *ctxt)
1017 589072 : : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
1018 : {}
1019 :
1020 0 : opt_pass * clone () override
1021 : {
1022 0 : return new pass_early_thread_jumps (m_ctxt);
1023 : }
1024 294536 : void set_pass_param (unsigned int, bool param) override
1025 : {
1026 294536 : m_first = param;
1027 294536 : }
1028 2569301 : bool gate (function *) override
1029 : {
1030 2569301 : return flag_thread_jumps;
1031 : }
1032 2568935 : unsigned int execute (function *fun) override
1033 : {
1034 2568935 : back_threader threader (fun, BT_NONE, m_first);
1035 2568935 : return threader.thread_blocks ();
1036 2568935 : }
1037 : private:
1038 : bool m_first;
1039 : };
1040 :
1041 : // Jump threading pass without resolving of unknown SSAs.
1042 : class pass_thread_jumps : public gimple_opt_pass
1043 : {
1044 : public:
1045 589072 : pass_thread_jumps (gcc::context *ctxt)
1046 1178144 : : gimple_opt_pass (pass_data_thread_jumps, ctxt)
1047 : {}
1048 294536 : opt_pass * clone (void) override
1049 : {
1050 294536 : return new pass_thread_jumps (m_ctxt);
1051 : }
1052 589072 : void set_pass_param (unsigned int, bool param) override
1053 : {
1054 589072 : m_first = param;
1055 589072 : }
1056 2136438 : bool gate (function *) override
1057 : {
1058 2136438 : return flag_thread_jumps && flag_expensive_optimizations;
1059 : }
1060 1977175 : unsigned int execute (function *fun) override
1061 : {
1062 1977175 : back_threader threader (fun, BT_SPEED, m_first);
1063 1977175 : return threader.thread_blocks ();
1064 1977175 : }
1065 : private:
1066 : bool m_first;
1067 : };
1068 :
1069 : // Jump threading pass that fully resolves unknown SSAs.
1070 : class pass_thread_jumps_full : public gimple_opt_pass
1071 : {
1072 : public:
1073 589072 : pass_thread_jumps_full (gcc::context *ctxt)
1074 1178144 : : gimple_opt_pass (pass_data_thread_jumps_full, ctxt)
1075 : {}
1076 294536 : opt_pass * clone (void) override
1077 : {
1078 294536 : return new pass_thread_jumps_full (m_ctxt);
1079 : }
1080 589072 : void set_pass_param (unsigned int, bool param) override
1081 : {
1082 589072 : m_first = param;
1083 589072 : }
1084 2136438 : bool gate (function *) override
1085 : {
1086 2136438 : return flag_thread_jumps && flag_expensive_optimizations;
1087 : }
1088 1977181 : unsigned int execute (function *fun) override
1089 : {
1090 1977181 : back_threader threader (fun, BT_SPEED | BT_RESOLVE, m_first);
1091 1977181 : return threader.thread_blocks ();
1092 1977181 : }
1093 : private:
1094 : bool m_first;
1095 : };
1096 :
1097 : } // namespace {
1098 :
1099 : gimple_opt_pass *
1100 294536 : make_pass_thread_jumps (gcc::context *ctxt)
1101 : {
1102 294536 : return new pass_thread_jumps (ctxt);
1103 : }
1104 :
1105 : gimple_opt_pass *
1106 294536 : make_pass_thread_jumps_full (gcc::context *ctxt)
1107 : {
1108 294536 : return new pass_thread_jumps_full (ctxt);
1109 : }
1110 :
1111 : gimple_opt_pass *
1112 294536 : make_pass_early_thread_jumps (gcc::context *ctxt)
1113 : {
1114 294536 : return new pass_early_thread_jumps (ctxt);
1115 : }
|
