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