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