Line data Source code
1 : /* SSA Jump Threading
2 : Copyright (C) 2005-2026 Free Software Foundation, Inc.
3 : Contributed by Jeff Law <law@redhat.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify
8 : it under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful,
13 : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : GNU General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "cfghooks.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "predict.h"
29 : #include "ssa.h"
30 : #include "fold-const.h"
31 : #include "cfgloop.h"
32 : #include "gimple-iterator.h"
33 : #include "tree-cfg.h"
34 : #include "tree-ssa-threadupdate.h"
35 : #include "tree-ssa-scopedtables.h"
36 : #include "tree-ssa-threadedge.h"
37 : #include "gimple-fold.h"
38 : #include "cfganal.h"
39 : #include "alloc-pool.h"
40 : #include "vr-values.h"
41 : #include "gimple-range.h"
42 : #include "gimple-range-path.h"
43 :
44 : /* To avoid code explosion due to jump threading, we limit the
45 : number of statements we are going to copy. This variable
46 : holds the number of statements currently seen that we'll have
47 : to copy as part of the jump threading process. */
48 : static int stmt_count;
49 :
50 : /* Array to record value-handles per SSA_NAME. */
51 : vec<tree> ssa_name_values;
52 :
53 : /* Set the value for the SSA name NAME to VALUE. */
54 :
55 : void
56 79782461 : set_ssa_name_value (tree name, tree value)
57 : {
58 79782461 : if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
59 3725600 : ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, true);
60 79782461 : if (value && TREE_OVERFLOW_P (value))
61 15 : value = drop_tree_overflow (value);
62 79782461 : ssa_name_values[SSA_NAME_VERSION (name)] = value;
63 79782461 : }
64 :
65 2125077 : jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
66 : {
67 : /* Initialize the per SSA_NAME value-handles array. */
68 2125077 : gcc_assert (!ssa_name_values.exists ());
69 4250154 : ssa_name_values.create (num_ssa_names);
70 :
71 2125077 : dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
72 : integer_zero_node, NULL, NULL);
73 :
74 2125077 : m_registry = new fwd_jt_path_registry ();
75 2125077 : m_simplifier = simplifier;
76 2125077 : m_state = state;
77 2125077 : }
78 :
79 2125077 : jump_threader::~jump_threader (void)
80 : {
81 2125077 : ssa_name_values.release ();
82 2125077 : ggc_free (dummy_cond);
83 2125077 : delete m_registry;
84 2125077 : }
85 :
86 : void
87 460612 : jump_threader::remove_jump_threads_including (edge_def *e)
88 : {
89 460612 : m_registry->remove_jump_threads_including (e);
90 460612 : }
91 :
92 : bool
93 2125077 : jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
94 : {
95 2125077 : return m_registry->thread_through_all_blocks (may_peel_loop_headers);
96 : }
97 :
98 : static inline bool
99 17247018 : has_phis_p (basic_block bb)
100 : {
101 5653159 : return !gsi_end_p (gsi_start_phis (bb));
102 : }
103 :
104 : /* Return TRUE for a block with PHIs but no statements. */
105 :
106 : static bool
107 32624190 : empty_block_with_phis_p (basic_block bb)
108 : {
109 38277349 : return gsi_end_p (gsi_start_nondebug_bb (bb)) && has_phis_p (bb);
110 : }
111 :
112 : /* Return TRUE if we may be able to thread an incoming edge into
113 : BB to an outgoing edge from BB. Return FALSE otherwise. */
114 :
115 : static bool
116 30040876 : potentially_threadable_block (basic_block bb)
117 : {
118 30040876 : gimple_stmt_iterator gsi;
119 :
120 : /* Special case. We can get blocks that are forwarders, but are
121 : not optimized away because they forward from outside a loop
122 : to the loop header. We want to thread through them as we can
123 : sometimes thread to the loop exit, which is obviously profitable.
124 : The interesting case here is when the block has PHIs. */
125 30040876 : if (empty_block_with_phis_p (bb))
126 : return true;
127 :
128 : /* If BB has a single successor or a single predecessor, then
129 : there is no threading opportunity. */
130 29690887 : if (single_succ_p (bb) || single_pred_p (bb))
131 : return false;
132 :
133 : /* If BB does not end with a conditional, switch or computed goto,
134 : then there is no threading opportunity. */
135 8795486 : gsi = gsi_last_bb (bb);
136 8795486 : if (gsi_end_p (gsi)
137 8788584 : || ! gsi_stmt (gsi)
138 8795486 : || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
139 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
140 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
141 1980594 : return false;
142 :
143 : return true;
144 : }
145 :
146 : /* Record temporary equivalences created by PHIs at the target of the
147 : edge E.
148 :
149 : If a PHI which prevents threading is encountered, then return FALSE
150 : indicating we should not thread this edge, else return TRUE. */
151 :
152 : bool
153 15841022 : jump_threader::record_temporary_equivalences_from_phis (edge e)
154 : {
155 15841022 : gphi_iterator gsi;
156 :
157 : /* Each PHI creates a temporary equivalence, record them.
158 : These are context sensitive equivalences and will be removed
159 : later. */
160 32882541 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
161 : {
162 17041519 : gphi *phi = gsi.phi ();
163 17041519 : tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
164 17041519 : tree dst = gimple_phi_result (phi);
165 :
166 : /* If the desired argument is not the same as this PHI's result
167 : and it is set by a PHI in E->dest, then we cannot thread
168 : through E->dest. */
169 17041519 : if (src != dst
170 17041519 : && TREE_CODE (src) == SSA_NAME
171 13905287 : && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
172 22643260 : && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
173 : return false;
174 :
175 : /* We consider any non-virtual PHI as a statement since it
176 : count result in a constant assignment or copy operation. */
177 34083038 : if (!virtual_operand_p (dst))
178 10410703 : stmt_count++;
179 :
180 17041519 : m_state->register_equiv (dst, src, /*update_range=*/true);
181 : }
182 : return true;
183 : }
184 :
185 : /* Valueize hook for gimple_fold_stmt_to_constant_1. */
186 :
187 : static tree
188 31271719 : threadedge_valueize (tree t)
189 : {
190 31271719 : if (TREE_CODE (t) == SSA_NAME)
191 : {
192 28374565 : tree tem = SSA_NAME_VALUE (t);
193 26981502 : if (tem)
194 7906891 : return tem;
195 : }
196 : return t;
197 : }
198 :
199 : /* Try to simplify each statement in E->dest, ultimately leading to
200 : a simplification of the COND_EXPR at the end of E->dest.
201 :
202 : Record unwind information for temporary equivalences onto STACK.
203 :
204 : Uses M_SIMPLIFIER to further simplify statements using pass specific
205 : information.
206 :
207 : We might consider marking just those statements which ultimately
208 : feed the COND_EXPR. It's not clear if the overhead of bookkeeping
209 : would be recovered by trying to simplify fewer statements.
210 :
211 : If we are able to simplify a statement into the form
212 : SSA_NAME = (SSA_NAME | gimple invariant), then we can record
213 : a context sensitive equivalence which may help us simplify
214 : later statements in E->dest. */
215 :
216 : gimple *
217 15841022 : jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
218 : {
219 15841022 : gimple *stmt = NULL;
220 15841022 : gimple_stmt_iterator gsi;
221 15841022 : int max_stmt_count;
222 :
223 15841022 : max_stmt_count = param_max_jump_thread_duplication_stmts;
224 :
225 : /* Walk through each statement in the block recording equivalences
226 : we discover. Note any equivalences we discover are context
227 : sensitive (ie, are dependent on traversing E) and must be unwound
228 : when we're finished processing E. */
229 190964412 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
230 : {
231 160638920 : stmt = gsi_stmt (gsi);
232 :
233 : /* Ignore empty statements and labels. */
234 160638920 : if (gimple_code (stmt) == GIMPLE_NOP
235 160638908 : || gimple_code (stmt) == GIMPLE_LABEL
236 320708483 : || is_gimple_debug (stmt))
237 110206929 : continue;
238 :
239 : /* If the statement has volatile operands, then we assume we
240 : cannot thread through this block. This is overly
241 : conservative in some ways. */
242 50431991 : if (gimple_code (stmt) == GIMPLE_ASM
243 50431991 : && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
244 : return NULL;
245 :
246 : /* If the statement is a unique builtin, we cannot thread
247 : through here. */
248 50416610 : if (gimple_code (stmt) == GIMPLE_CALL
249 5073356 : && gimple_call_internal_p (stmt)
250 50525990 : && gimple_call_internal_unique_p (stmt))
251 : return NULL;
252 :
253 : /* We cannot thread through __builtin_constant_p, because an
254 : expression that is constant on two threading paths may become
255 : non-constant (i.e.: phi) when they merge. */
256 50416610 : if (gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
257 : return NULL;
258 :
259 : /* If duplicating this block is going to cause too much code
260 : expansion, then do not thread through this block. */
261 50411140 : stmt_count++;
262 50411140 : if (stmt_count > max_stmt_count)
263 : {
264 : /* If any of the stmts in the PATH's dests are going to be
265 : killed due to threading, grow the max count
266 : accordingly. */
267 2268397 : if (max_stmt_count
268 2268397 : == param_max_jump_thread_duplication_stmts)
269 : {
270 1707332 : max_stmt_count += estimate_threading_killed_stmts (e->dest);
271 1707332 : if (dump_file)
272 47 : fprintf (dump_file, "threading bb %i up to %i stmts\n",
273 47 : e->dest->index, max_stmt_count);
274 : }
275 : /* If we're still past the limit, we're done. */
276 2268397 : if (stmt_count > max_stmt_count)
277 : return NULL;
278 : }
279 :
280 49075439 : m_state->record_ranges_from_stmt (stmt, true);
281 :
282 : /* If this is not a statement that sets an SSA_NAME to a new
283 : value, then do not try to simplify this statement as it will
284 : not simplify in any way that is helpful for jump threading. */
285 49075439 : if ((gimple_code (stmt) != GIMPLE_ASSIGN
286 34222989 : || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
287 58180861 : && (gimple_code (stmt) != GIMPLE_CALL
288 4885010 : || gimple_call_lhs (stmt) == NULL_TREE
289 2234182 : || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
290 22138066 : continue;
291 :
292 : /* The result of __builtin_object_size depends on all the arguments
293 : of a phi node. Temporarily using only one edge produces invalid
294 : results. For example
295 :
296 : if (x < 6)
297 : goto l;
298 : else
299 : goto l;
300 :
301 : l:
302 : r = PHI <&w[2].a[1](2), &a.a[6](3)>
303 : __builtin_object_size (r, 0)
304 :
305 : The result of __builtin_object_size is defined to be the maximum of
306 : remaining bytes. If we use only one edge on the phi, the result will
307 : change to be the remaining bytes for the corresponding phi argument.
308 :
309 : Similarly for __builtin_constant_p:
310 :
311 : r = PHI <1(2), 2(3)>
312 : __builtin_constant_p (r)
313 :
314 : Both PHI arguments are constant, but x ? 1 : 2 is still not
315 : constant. */
316 :
317 26937373 : if (is_gimple_call (stmt))
318 : {
319 1819806 : tree fndecl = gimple_call_fndecl (stmt);
320 1819806 : if (fndecl
321 1687315 : && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
322 2241589 : && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
323 421783 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
324 0 : continue;
325 : }
326 :
327 26937373 : m_state->register_equivs_stmt (stmt, e->src, m_simplifier);
328 : }
329 : return stmt;
330 : }
331 :
332 : /* Simplify the control statement at the end of the block E->dest.
333 :
334 : Use SIMPLIFY (a pointer to a callback function) to further simplify
335 : a condition using pass specific information.
336 :
337 : Return the simplified condition or NULL if simplification could
338 : not be performed. When simplifying a GIMPLE_SWITCH, we may return
339 : the CASE_LABEL_EXPR that will be taken. */
340 :
341 : tree
342 9851995 : jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
343 : {
344 9851995 : tree cond, cached_lhs;
345 9851995 : enum gimple_code code = gimple_code (stmt);
346 :
347 : /* For comparisons, we have to update both operands, then try
348 : to simplify the comparison. */
349 9851995 : if (code == GIMPLE_COND)
350 : {
351 9820047 : tree op0, op1;
352 9820047 : enum tree_code cond_code;
353 :
354 9820047 : op0 = gimple_cond_lhs (stmt);
355 9820047 : op1 = gimple_cond_rhs (stmt);
356 9820047 : cond_code = gimple_cond_code (stmt);
357 :
358 : /* Get the current value of both operands. */
359 9820047 : if (TREE_CODE (op0) == SSA_NAME)
360 : {
361 11839790 : for (int i = 0; i < 2; i++)
362 : {
363 11833949 : if (TREE_CODE (op0) == SSA_NAME
364 11833949 : && SSA_NAME_VALUE (op0))
365 2058039 : op0 = SSA_NAME_VALUE (op0);
366 : else
367 : break;
368 : }
369 : }
370 :
371 9820047 : if (TREE_CODE (op1) == SSA_NAME)
372 : {
373 3190382 : for (int i = 0; i < 2; i++)
374 : {
375 3189405 : if (TREE_CODE (op1) == SSA_NAME
376 3189405 : && SSA_NAME_VALUE (op1))
377 592046 : op1 = SSA_NAME_VALUE (op1);
378 : else
379 : break;
380 : }
381 : }
382 :
383 9820047 : const unsigned recursion_limit = 4;
384 :
385 9820047 : cached_lhs
386 9820047 : = simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
387 : recursion_limit);
388 :
389 : /* If we were testing an integer/pointer against a constant,
390 : then we can trace the value of the SSA_NAME. If a value is
391 : found, then the condition will collapse to a constant.
392 :
393 : Return the SSA_NAME we want to trace back rather than the full
394 : expression and give the threader a chance to find its value. */
395 9820047 : if (cached_lhs == NULL)
396 : {
397 : /* Recover the original operands. They may have been simplified
398 : using context sensitive equivalences. Those context sensitive
399 : equivalences may not be valid on paths. */
400 8562719 : tree op0 = gimple_cond_lhs (stmt);
401 8562719 : tree op1 = gimple_cond_rhs (stmt);
402 :
403 16984117 : if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
404 2084751 : || POINTER_TYPE_P (TREE_TYPE (op0)))
405 8392335 : && TREE_CODE (op0) == SSA_NAME
406 16954319 : && TREE_CODE (op1) == INTEGER_CST)
407 : return op0;
408 : }
409 :
410 4171123 : return cached_lhs;
411 : }
412 :
413 31948 : if (code == GIMPLE_SWITCH)
414 31545 : cond = gimple_switch_index (as_a <gswitch *> (stmt));
415 403 : else if (code == GIMPLE_GOTO)
416 403 : cond = gimple_goto_dest (stmt);
417 : else
418 0 : gcc_unreachable ();
419 :
420 : /* We can have conditionals which just test the state of a variable
421 : rather than use a relational operator. These are simpler to handle. */
422 31948 : if (TREE_CODE (cond) == SSA_NAME)
423 : {
424 : tree original_lhs = cond;
425 : cached_lhs = cond;
426 :
427 : /* Get the variable's current value from the equivalence chains.
428 :
429 : It is possible to get loops in the SSA_NAME_VALUE chains
430 : (consider threading the backedge of a loop where we have
431 : a loop invariant SSA_NAME used in the condition). */
432 : if (cached_lhs)
433 : {
434 39473 : for (int i = 0; i < 2; i++)
435 : {
436 39473 : if (TREE_CODE (cached_lhs) == SSA_NAME
437 39473 : && SSA_NAME_VALUE (cached_lhs))
438 7597 : cached_lhs = SSA_NAME_VALUE (cached_lhs);
439 : else
440 : break;
441 : }
442 : }
443 :
444 : /* If we haven't simplified to an invariant yet, then use the
445 : pass specific callback to try and simplify it further. */
446 31876 : if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
447 : {
448 30138 : if (code == GIMPLE_SWITCH)
449 : {
450 : /* Replace the index operand of the GIMPLE_SWITCH with any LHS
451 : we found before handing off to VRP. If simplification is
452 : possible, the simplified value will be a CASE_LABEL_EXPR of
453 : the label that is proven to be taken. */
454 29902 : gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
455 29902 : gimple_switch_set_index (dummy_switch, cached_lhs);
456 29902 : cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
457 : m_state);
458 29902 : ggc_free (dummy_switch);
459 : }
460 : else
461 236 : cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
462 : }
463 :
464 : /* We couldn't find an invariant. But, callers of this
465 : function may be able to do something useful with the
466 : unmodified destination. */
467 31876 : if (!cached_lhs)
468 29437 : cached_lhs = original_lhs;
469 : }
470 : else
471 : cached_lhs = NULL;
472 :
473 : return cached_lhs;
474 : }
475 :
476 : /* Recursive helper for simplify_control_stmt_condition. */
477 :
478 : tree
479 9820047 : jump_threader::simplify_control_stmt_condition_1
480 : (edge e,
481 : gimple *stmt,
482 : tree op0,
483 : enum tree_code cond_code,
484 : tree op1,
485 : unsigned limit)
486 : {
487 9820047 : if (limit == 0)
488 : return NULL_TREE;
489 :
490 : /* We may need to canonicalize the comparison. For
491 : example, op0 might be a constant while op1 is an
492 : SSA_NAME. Failure to canonicalize will cause us to
493 : miss threading opportunities. */
494 9820047 : if (tree_swap_operands_p (op0, op1))
495 : {
496 480355 : cond_code = swap_tree_comparison (cond_code);
497 480355 : std::swap (op0, op1);
498 : }
499 :
500 9820047 : gimple_cond_set_code (dummy_cond, cond_code);
501 9820047 : gimple_cond_set_lhs (dummy_cond, op0);
502 9820047 : gimple_cond_set_rhs (dummy_cond, op1);
503 :
504 9820047 : tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
505 9820047 : if (res)
506 1726918 : while (CONVERT_EXPR_P (res))
507 641 : res = TREE_OPERAND (res, 0);
508 :
509 : /* If we have not simplified the condition down to an invariant,
510 : then use the pass specific callback to simplify the condition. */
511 1726277 : if (!res
512 1726277 : || !is_gimple_min_invariant (res))
513 8913043 : res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
514 :
515 : return res;
516 : }
517 :
518 : /* Copy debug stmts from DEST's chain of single predecessors up to
519 : SRC, so that we don't lose the bindings as PHI nodes are introduced
520 : when DEST gains new predecessors. */
521 : void
522 1764895 : propagate_threaded_block_debug_into (basic_block dest, basic_block src)
523 : {
524 1764895 : if (!MAY_HAVE_DEBUG_BIND_STMTS)
525 1129712 : return;
526 :
527 1764895 : if (!single_pred_p (dest))
528 : return;
529 :
530 635183 : gcc_checking_assert (dest != src);
531 :
532 635183 : gimple_stmt_iterator gsi = gsi_after_labels (dest);
533 635183 : int i = 0;
534 635183 : const int alloc_count = 16; // ?? Should this be a PARAM?
535 :
536 : /* Estimate the number of debug vars overridden in the beginning of
537 : DEST, to tell how many we're going to need to begin with. */
538 635183 : for (gimple_stmt_iterator si = gsi;
539 2801123 : i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
540 : {
541 2659345 : gimple *stmt = gsi_stmt (si);
542 2659345 : if (!is_gimple_debug (stmt))
543 : break;
544 2165940 : if (gimple_debug_nonbind_marker_p (stmt))
545 390217 : continue;
546 1775723 : i++;
547 : }
548 :
549 635183 : auto_vec<tree, alloc_count> fewvars;
550 635183 : hash_set<tree> *vars = NULL;
551 :
552 : /* If we're already starting with 3/4 of alloc_count, go for a
553 : hash_set, otherwise start with an unordered stack-allocated
554 : VEC. */
555 635183 : if (i * 4 > alloc_count * 3)
556 66233 : vars = new hash_set<tree>;
557 :
558 : /* Now go through the initial debug stmts in DEST again, this time
559 : actually inserting in VARS or FEWVARS. Don't bother checking for
560 : duplicates in FEWVARS. */
561 3867463 : for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
562 : {
563 3790168 : gimple *stmt = gsi_stmt (si);
564 3790168 : if (!is_gimple_debug (stmt))
565 : break;
566 :
567 3232280 : tree var;
568 :
569 3232280 : if (gimple_debug_bind_p (stmt))
570 2699202 : var = gimple_debug_bind_get_var (stmt);
571 533078 : else if (gimple_debug_source_bind_p (stmt))
572 19746 : var = gimple_debug_source_bind_get_var (stmt);
573 513332 : else if (gimple_debug_nonbind_marker_p (stmt))
574 513332 : continue;
575 : else
576 0 : gcc_unreachable ();
577 :
578 2718948 : if (vars)
579 1804254 : vars->add (var);
580 : else
581 914694 : fewvars.quick_push (var);
582 : }
583 :
584 635183 : basic_block bb = dest;
585 :
586 658904 : do
587 : {
588 658904 : bb = single_pred (bb);
589 1317808 : for (gimple_stmt_iterator si = gsi_last_bb (bb);
590 8735538 : !gsi_end_p (si); gsi_prev (&si))
591 : {
592 7417730 : gimple *stmt = gsi_stmt (si);
593 7417730 : if (!is_gimple_debug (stmt))
594 5126420 : continue;
595 :
596 5893160 : tree var;
597 :
598 5893160 : if (gimple_debug_bind_p (stmt))
599 4785640 : var = gimple_debug_bind_get_var (stmt);
600 1107520 : else if (gimple_debug_source_bind_p (stmt))
601 29964 : var = gimple_debug_source_bind_get_var (stmt);
602 1077556 : else if (gimple_debug_nonbind_marker_p (stmt))
603 1077556 : continue;
604 : else
605 0 : gcc_unreachable ();
606 :
607 : /* Discard debug bind overlaps. Unlike stmts from src,
608 : copied into a new block that will precede BB, debug bind
609 : stmts in bypassed BBs may actually be discarded if
610 : they're overwritten by subsequent debug bind stmts. We
611 : want to copy binds for all modified variables, so that we
612 : retain a bind to the shared def if there is one, or to a
613 : newly introduced PHI node if there is one. Our bind will
614 : end up reset if the value is dead, but that implies the
615 : variable couldn't have survived, so it's fine. We are
616 : not actually running the code that performed the binds at
617 : this point, we're just adding binds so that they survive
618 : the new confluence, so markers should not be copied. */
619 4815604 : if (vars && vars->add (var))
620 1710073 : continue;
621 3105531 : else if (!vars)
622 : {
623 2547708 : int i = fewvars.length ();
624 15151431 : while (i--)
625 13417944 : if (fewvars[i] == var)
626 : break;
627 2547708 : if (i >= 0)
628 814221 : continue;
629 1733487 : else if (fewvars.length () < (unsigned) alloc_count)
630 1691709 : fewvars.quick_push (var);
631 : else
632 : {
633 41778 : vars = new hash_set<tree>;
634 752004 : for (i = 0; i < alloc_count; i++)
635 668448 : vars->add (fewvars[i]);
636 41778 : fewvars.release ();
637 41778 : vars->add (var);
638 : }
639 : }
640 :
641 2291310 : stmt = gimple_copy (stmt);
642 : /* ??? Should we drop the location of the copy to denote
643 : they're artificial bindings? */
644 2291310 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
645 : }
646 : }
647 1331504 : while (bb != src && single_pred_p (bb));
648 :
649 635183 : if (vars)
650 108011 : delete vars;
651 527172 : else if (fewvars.exists ())
652 527172 : fewvars.release ();
653 635183 : }
654 :
655 : /* See if TAKEN_EDGE->dest is a threadable block with no side effects (ie, it
656 : need not be duplicated as part of the CFG/SSA updating process).
657 :
658 : If it is threadable, add it to PATH and VISITED and recurse, ultimately
659 : returning TRUE from the toplevel call. Otherwise do nothing and
660 : return false. */
661 :
662 : bool
663 11168046 : jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
664 : edge taken_edge,
665 : bitmap visited, unsigned &limit)
666 : {
667 11594792 : basic_block bb = taken_edge->dest;
668 11594792 : gimple_stmt_iterator gsi;
669 11594792 : gimple *stmt;
670 11594792 : tree cond;
671 :
672 11594792 : if (limit == 0)
673 : return false;
674 11593859 : --limit;
675 :
676 : /* The key property of these blocks is that they need not be duplicated
677 : when threading. Thus they cannot have visible side effects such
678 : as PHI nodes. */
679 11593859 : if (has_phis_p (bb))
680 : return false;
681 :
682 : /* Skip over DEBUG statements at the start of the block. */
683 7672177 : gsi = gsi_start_nondebug_bb (bb);
684 :
685 : /* If the block has no statements, but does have a single successor, then
686 : it's just a forwarding block and we can thread through it trivially.
687 :
688 : However, note that just threading through empty blocks with single
689 : successors is not inherently profitable. For the jump thread to
690 : be profitable, we must avoid a runtime conditional.
691 :
692 : By taking the return value from the recursive call, we get the
693 : desired effect of returning TRUE when we found a profitable jump
694 : threading opportunity and FALSE otherwise.
695 :
696 : This is particularly important when this routine is called after
697 : processing a joiner block. Returning TRUE too aggressively in
698 : that case results in pointless duplication of the joiner block. */
699 7672177 : if (gsi_end_p (gsi))
700 : {
701 1782885 : if (single_succ_p (bb))
702 : {
703 1782885 : taken_edge = single_succ_edge (bb);
704 :
705 1782885 : if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
706 : return false;
707 :
708 426746 : if (!bitmap_bit_p (visited, taken_edge->dest->index))
709 : {
710 426746 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
711 426746 : m_state->append_path (taken_edge->dest);
712 426746 : bitmap_set_bit (visited, taken_edge->dest->index);
713 426746 : return thread_around_empty_blocks (path, taken_edge, visited,
714 426746 : limit);
715 : }
716 : }
717 :
718 : /* We have a block with no statements, but multiple successors? */
719 : return false;
720 : }
721 :
722 : /* The only real statements this block can have are a control
723 : flow altering statement. Anything else stops the thread. */
724 5889292 : stmt = gsi_stmt (gsi);
725 5889292 : if (gimple_code (stmt) != GIMPLE_COND
726 : && gimple_code (stmt) != GIMPLE_GOTO
727 : && gimple_code (stmt) != GIMPLE_SWITCH)
728 : return false;
729 :
730 : /* Extract and simplify the condition. */
731 558374 : cond = simplify_control_stmt_condition (taken_edge, stmt);
732 :
733 : /* If the condition can be statically computed and we have not already
734 : visited the destination edge, then add the taken edge to our thread
735 : path. */
736 558374 : if (cond != NULL_TREE
737 558374 : && (is_gimple_min_invariant (cond)
738 330635 : || TREE_CODE (cond) == CASE_LABEL_EXPR))
739 : {
740 100872 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
741 26 : taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
742 : else
743 100846 : taken_edge = find_taken_edge (bb, cond);
744 :
745 100872 : if (!taken_edge
746 100852 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
747 : return false;
748 :
749 100754 : if (bitmap_bit_p (visited, taken_edge->dest->index))
750 : return false;
751 100754 : bitmap_set_bit (visited, taken_edge->dest->index);
752 :
753 100754 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
754 100754 : m_state->append_path (taken_edge->dest);
755 :
756 100754 : thread_around_empty_blocks (path, taken_edge, visited, limit);
757 100754 : return true;
758 : }
759 :
760 : return false;
761 : }
762 :
763 : /* We are exiting E->src, see if E->dest ends with a conditional
764 : jump which has a known value when reached via E.
765 :
766 : E->dest can have arbitrary side effects which, if threading is
767 : successful, will be maintained.
768 :
769 : Special care is necessary if E is a back edge in the CFG as we
770 : may have already recorded equivalences for E->dest into our
771 : various tables, including the result of the conditional at
772 : the end of E->dest. Threading opportunities are severely
773 : limited in that case to avoid short-circuiting the loop
774 : incorrectly.
775 :
776 : Positive return value is success. Zero return value is failure, but
777 : the block can still be duplicated as a joiner in a jump thread path,
778 : negative indicates the block should not be duplicated and thus is not
779 : suitable for a joiner in a jump threading path. */
780 :
781 : int
782 15841981 : jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
783 : edge e, bitmap visited,
784 : unsigned &limit)
785 : {
786 15841981 : if (limit == 0)
787 : return 0;
788 15841022 : limit--;
789 :
790 15841022 : m_state->register_equivs_edge (e);
791 :
792 : /* PHIs create temporary equivalences.
793 : Note that if we found a PHI that made the block non-threadable, then
794 : we need to bubble that up to our caller in the same manner we do
795 : when we prematurely stop processing statements below. */
796 15841022 : if (!record_temporary_equivalences_from_phis (e))
797 : return -1;
798 :
799 : /* Now walk each statement recording any context sensitive
800 : temporary equivalences we can detect. */
801 15841022 : gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
802 :
803 : /* There's two reasons STMT might be null, and distinguishing
804 : between them is important.
805 :
806 : First the block may not have had any statements. For example, it
807 : might have some PHIs and unconditionally transfer control elsewhere.
808 : Such blocks are suitable for jump threading, particularly as a
809 : joiner block.
810 :
811 : The second reason would be if we did not process all the statements
812 : in the block (because there were too many to make duplicating the
813 : block profitable. If we did not look at all the statements, then
814 : we may not have invalidated everything needing invalidation. Thus
815 : we must signal to our caller that this block is not suitable for
816 : use as a joiner in a threading path. */
817 15841022 : if (!stmt)
818 : {
819 : /* First case. The statement simply doesn't have any instructions, but
820 : does have PHIs. */
821 2583314 : if (empty_block_with_phis_p (e->dest))
822 : return 0;
823 :
824 : /* Second case. */
825 2306082 : return -1;
826 : }
827 :
828 : /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
829 : will be taken. */
830 13257708 : if (gimple_code (stmt) == GIMPLE_COND
831 : || gimple_code (stmt) == GIMPLE_GOTO
832 : || gimple_code (stmt) == GIMPLE_SWITCH)
833 : {
834 9293621 : tree cond;
835 :
836 : /* Extract and simplify the condition. */
837 9293621 : cond = simplify_control_stmt_condition (e, stmt);
838 :
839 9293621 : if (!cond)
840 : return 0;
841 :
842 6506647 : if (is_gimple_min_invariant (cond)
843 6506647 : || TREE_CODE (cond) == CASE_LABEL_EXPR)
844 : {
845 1136770 : edge taken_edge;
846 1136770 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
847 675 : taken_edge = find_edge (e->dest,
848 675 : label_to_block (cfun, CASE_LABEL (cond)));
849 : else
850 1136095 : taken_edge = find_taken_edge (e->dest, cond);
851 :
852 1136770 : basic_block dest = (taken_edge ? taken_edge->dest : NULL);
853 :
854 : /* DEST could be NULL for a computed jump to an absolute
855 : address. */
856 1136724 : if (dest == NULL
857 1136724 : || dest == e->dest
858 1136724 : || (taken_edge->flags & EDGE_DFS_BACK) != 0
859 2272601 : || bitmap_bit_p (visited, dest->index))
860 : return 0;
861 :
862 : /* Only push the EDGE_START_JUMP_THREAD marker if this is
863 : first edge on the path. */
864 1135877 : if (path->length () == 0)
865 699283 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
866 :
867 1135877 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
868 1135877 : m_state->append_path (taken_edge->dest);
869 :
870 : /* See if we can thread through DEST as well, this helps capture
871 : secondary effects of threading without having to re-run DOM or
872 : VRP.
873 :
874 : We don't want to thread back to a block we have already
875 : visited. This may be overly conservative. */
876 1135877 : bitmap_set_bit (visited, dest->index);
877 1135877 : bitmap_set_bit (visited, e->dest->index);
878 1135877 : thread_around_empty_blocks (path, taken_edge, visited, limit);
879 1135877 : return 1;
880 : }
881 : }
882 : return 0;
883 : }
884 :
885 : /* There are basic blocks look like:
886 : <P0>
887 : p0 = a CMP b ; or p0 = (INT) (a CMP b)
888 : goto <X>;
889 :
890 : <P1>
891 : p1 = c CMP d
892 : goto <X>;
893 :
894 : <X>
895 : # phi = PHI <p0 (P0), p1 (P1)>
896 : if (phi != 0) goto <Y>; else goto <Z>;
897 :
898 : Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
899 : And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
900 :
901 : Return true if E is (P0,X) or (P1,X) */
902 :
903 : static bool
904 9443178 : edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
905 : {
906 9443178 : gcond *gs;
907 9443178 : gphi *phi;
908 9443178 : return (cond_on_phi_p (e->dest, &gs, &phi)
909 9443178 : && phi_arg_from_cmp_p (phi, e));
910 : }
911 :
912 : /* Return true if BB contains only a conditional jump on a PHI
913 : defined in it, compared against 0 or 1:
914 :
915 : <bb 5>:
916 : # t_1 = PHI <t_9(3), t_6(4)>
917 : if (t_1 != 0)
918 :
919 : The conditional and the PHI are returned in *COND_OUT and
920 : *PHI_OUT. */
921 :
922 : bool
923 17158466 : cond_on_phi_p (basic_block bb, gcond **cond_out, gphi **phi_out)
924 : {
925 17158466 : gcond *gs;
926 17158466 : if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (bb))))
927 : return false;
928 :
929 : /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
930 2112822 : tree cond = gimple_cond_lhs (gs);
931 2112822 : enum tree_code code = gimple_cond_code (gs);
932 2112822 : tree rhs = gimple_cond_rhs (gs);
933 2112822 : if (TREE_CODE (cond) != SSA_NAME
934 2112304 : || (code != NE_EXPR && code != EQ_EXPR)
935 3584026 : || (!integer_onep (rhs) && !integer_zerop (rhs)))
936 : return false;
937 987277 : gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
938 622255 : if (phi == NULL || gimple_bb (phi) != bb)
939 : return false;
940 :
941 495041 : *cond_out = gs;
942 495041 : *phi_out = phi;
943 495041 : return true;
944 : }
945 :
946 : /* Return true if PHI's incoming value on edge E is a single-use
947 : comparison, possibly through a single-use conversion:
948 :
949 : <bb 3>:
950 : t_9 = a < b;
951 : goto <bb 5>;
952 :
953 : <bb 5>:
954 : # t_1 = PHI <t_9(3), ...>
955 : */
956 :
957 : bool
958 786978 : phi_arg_from_cmp_p (gphi *phi, edge e)
959 : {
960 786978 : gassign *def;
961 786978 : tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
962 786978 : if (TREE_CODE (value) != SSA_NAME
963 525452 : || !has_single_use (value)
964 1024302 : || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
965 : return false;
966 :
967 : /* Or if it is (INT) (a CMP b). */
968 269186 : if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
969 : {
970 39201 : value = gimple_assign_rhs1 (def);
971 39201 : if (TREE_CODE (value) != SSA_NAME
972 39201 : || !has_single_use (value)
973 77210 : || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
974 : return false;
975 : }
976 :
977 246597 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
978 107418 : return false;
979 :
980 : return true;
981 : }
982 :
983 : /* We are exiting E->src, see if E->dest ends with a conditional jump
984 : which has a known value when reached via E. If so, thread the
985 : edge. */
986 :
987 : void
988 7164881 : jump_threader::thread_across_edge (edge e)
989 : {
990 7164881 : auto_bitmap visited;
991 :
992 7164881 : m_state->push (e);
993 :
994 7164881 : stmt_count = 0;
995 :
996 7164881 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
997 7164881 : bitmap_set_bit (visited, e->src->index);
998 7164881 : bitmap_set_bit (visited, e->dest->index);
999 :
1000 : /* Limit search space. */
1001 7164881 : unsigned limit = param_max_jump_thread_paths;
1002 :
1003 7164881 : int threaded = 0;
1004 7164881 : if ((e->flags & EDGE_DFS_BACK) == 0)
1005 5962209 : threaded = thread_through_normal_block (path, e, visited, limit);
1006 :
1007 5962209 : if (threaded > 0)
1008 : {
1009 699283 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1010 : e->dest);
1011 699283 : m_registry->register_jump_thread (path);
1012 699283 : m_state->pop ();
1013 699283 : return;
1014 : }
1015 :
1016 6465598 : gcc_checking_assert (path->length () == 0);
1017 6465598 : path->release ();
1018 :
1019 6465598 : if (threaded < 0)
1020 : {
1021 : /* The target block was deemed too big to duplicate. Just quit
1022 : now rather than trying to use the block as a joiner in a jump
1023 : threading path.
1024 :
1025 : This prevents unnecessary code growth, but more importantly if we
1026 : do not look at all the statements in the block, then we may have
1027 : missed some invalidations if we had traversed a backedge! */
1028 173375 : m_state->pop ();
1029 173375 : return;
1030 : }
1031 :
1032 : /* We were unable to determine what out edge from E->dest is taken. However,
1033 : we might still be able to thread through successors of E->dest. This
1034 : often occurs when E->dest is a joiner block which then fans back out
1035 : based on redundant tests.
1036 :
1037 : If so, we'll copy E->dest and redirect the appropriate predecessor to
1038 : the copy. Within the copy of E->dest, we'll thread one or more edges
1039 : to points deeper in the CFG.
1040 :
1041 : This is a stopgap until we have a more structured approach to path
1042 : isolation. */
1043 6292223 : {
1044 6292223 : edge taken_edge;
1045 6292223 : edge_iterator ei;
1046 6292223 : bool found;
1047 :
1048 : /* If E->dest has abnormal outgoing edges, then there's no guarantee
1049 : we can safely redirect any of the edges. Just punt those cases. */
1050 6292223 : if (!can_duplicate_block_on_edge_p (e))
1051 : {
1052 397 : m_state->pop ();
1053 397 : return;
1054 : }
1055 :
1056 : /* Look at each successor of E->dest to see if we can thread through it. */
1057 18685489 : FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1058 : {
1059 12393663 : if ((e->flags & EDGE_DFS_BACK) != 0
1060 9998014 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1061 2462248 : continue;
1062 :
1063 9931415 : m_state->push (taken_edge);
1064 :
1065 : /* Avoid threading to any block we have already visited. */
1066 9931415 : bitmap_clear (visited);
1067 9931415 : bitmap_set_bit (visited, e->src->index);
1068 9931415 : bitmap_set_bit (visited, e->dest->index);
1069 9931415 : bitmap_set_bit (visited, taken_edge->dest->index);
1070 :
1071 9931415 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1072 9931415 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
1073 9931415 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1074 :
1075 9931415 : found = thread_around_empty_blocks (path, taken_edge, visited, limit);
1076 :
1077 9931415 : if (!found)
1078 9879772 : found = thread_through_normal_block (path,
1079 9879772 : path->last ()->e, visited,
1080 : limit) > 0;
1081 :
1082 : /* If we were able to thread through a successor of E->dest, then
1083 : record the jump threading opportunity. */
1084 9879772 : if (found
1085 9879772 : || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1086 : {
1087 491366 : if (taken_edge->dest != path->last ()->e->dest)
1088 488239 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1089 : taken_edge->dest);
1090 491366 : m_registry->register_jump_thread (path);
1091 : }
1092 : else
1093 9440049 : path->release ();
1094 :
1095 9931415 : m_state->pop ();
1096 : }
1097 : }
1098 :
1099 6291826 : m_state->pop ();
1100 7164881 : }
1101 :
1102 : /* Return TRUE if BB has a single successor to a block with multiple
1103 : incoming and outgoing edges. */
1104 :
1105 : bool
1106 23956729 : single_succ_to_potentially_threadable_block (basic_block bb)
1107 : {
1108 23956729 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1109 23956729 : return (single_succ_p (bb)
1110 11853838 : && (single_succ_edge (bb)->flags & flags) == 0
1111 35274464 : && potentially_threadable_block (single_succ (bb)));
1112 : }
1113 :
1114 : /* Examine the outgoing edges from BB and conditionally
1115 : try to thread them. */
1116 :
1117 : void
1118 23958309 : jump_threader::thread_outgoing_edges (basic_block bb)
1119 : {
1120 23958309 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1121 :
1122 23958309 : if (!flag_thread_jumps)
1123 : return;
1124 :
1125 : /* If we have an outgoing edge to a block with multiple incoming and
1126 : outgoing edges, then we may be able to thread the edge, i.e., we
1127 : may be able to statically determine which of the outgoing edges
1128 : will be traversed when the incoming edge from BB is traversed. */
1129 23956729 : if (single_succ_to_potentially_threadable_block (bb))
1130 4451895 : thread_across_edge (single_succ_edge (bb));
1131 39009668 : else if (safe_is_a <gcond *> (*gsi_last_bb (bb))
1132 9236648 : && EDGE_COUNT (bb->succs) == 2
1133 9236648 : && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1134 26388980 : && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1135 : {
1136 9236648 : edge true_edge, false_edge;
1137 :
1138 9236648 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1139 :
1140 : /* Only try to thread the edge if it reaches a target block with
1141 : more than one predecessor and more than one successor. */
1142 9236648 : if (potentially_threadable_block (true_edge->dest))
1143 944893 : thread_across_edge (true_edge);
1144 :
1145 : /* Similarly for the ELSE arm. */
1146 9236648 : if (potentially_threadable_block (false_edge->dest))
1147 1768093 : thread_across_edge (false_edge);
1148 : }
1149 : }
1150 :
1151 : // Marker to keep track of the start of the current path.
1152 : const basic_block jt_state::BB_MARKER = (basic_block) -1;
1153 :
1154 : // Record that E is being crossed.
1155 :
1156 : void
1157 17096296 : jt_state::push (edge e)
1158 : {
1159 17096296 : m_blocks.safe_push (BB_MARKER);
1160 17096296 : if (m_blocks.length () == 1)
1161 7164881 : m_blocks.safe_push (e->src);
1162 17096296 : m_blocks.safe_push (e->dest);
1163 17096296 : }
1164 :
1165 : // Pop to the last pushed state.
1166 :
1167 : void
1168 17096296 : jt_state::pop ()
1169 : {
1170 17096296 : if (!m_blocks.is_empty ())
1171 : {
1172 43020850 : while (m_blocks.last () != BB_MARKER)
1173 25924554 : m_blocks.pop ();
1174 : // Pop marker.
1175 17096296 : m_blocks.pop ();
1176 : }
1177 17096296 : }
1178 :
1179 : // Add BB to the list of blocks seen.
1180 :
1181 : void
1182 1663377 : jt_state::append_path (basic_block bb)
1183 : {
1184 1663377 : gcc_checking_assert (!m_blocks.is_empty ());
1185 1663377 : m_blocks.safe_push (bb);
1186 1663377 : }
1187 :
1188 : void
1189 0 : jt_state::dump (FILE *out)
1190 : {
1191 0 : if (!m_blocks.is_empty ())
1192 : {
1193 0 : auto_vec<basic_block> path;
1194 0 : get_path (path);
1195 0 : dump_ranger (out, path);
1196 0 : }
1197 0 : }
1198 :
1199 : void
1200 0 : jt_state::debug ()
1201 : {
1202 0 : push_dump_file save (stderr, TDF_DETAILS);
1203 0 : dump (stderr);
1204 0 : }
1205 :
1206 : // Convert the current path in jt_state into a path suitable for the
1207 : // path solver. Return the resulting path in PATH.
1208 :
1209 : void
1210 8779442 : jt_state::get_path (vec<basic_block> &path)
1211 : {
1212 8779442 : path.truncate (0);
1213 :
1214 51958791 : for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
1215 : {
1216 34399907 : basic_block bb = m_blocks[i];
1217 :
1218 34399907 : if (bb != BB_MARKER)
1219 21745930 : path.safe_push (bb);
1220 : }
1221 8779442 : }
1222 :
1223 : // Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
1224 : // update the value range associated with DST.
1225 :
1226 : void
1227 0 : jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
1228 : tree src ATTRIBUTE_UNUSED,
1229 : bool update_range ATTRIBUTE_UNUSED)
1230 : {
1231 0 : }
1232 :
1233 : // Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
1234 : // this is a temporary equivalence and should be recorded into the
1235 : // unwind table, instead of the global table.
1236 :
1237 : void
1238 49075439 : jt_state::record_ranges_from_stmt (gimple *,
1239 : bool temporary ATTRIBUTE_UNUSED)
1240 : {
1241 49075439 : }
1242 :
1243 : // Record any equivalences created by traversing E.
1244 :
1245 : void
1246 0 : jt_state::register_equivs_edge (edge)
1247 : {
1248 0 : }
1249 :
1250 : void
1251 26937373 : jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
1252 : jt_simplifier *simplifier)
1253 : {
1254 : /* At this point we have a statement which assigns an RHS to an
1255 : SSA_VAR on the LHS. We want to try and simplify this statement
1256 : to expose more context sensitive equivalences which in turn may
1257 : allow us to simplify the condition at the end of the loop.
1258 :
1259 : Handle simple copy operations. */
1260 26937373 : tree cached_lhs = NULL;
1261 26937373 : if (gimple_assign_single_p (stmt)
1262 26937373 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
1263 : cached_lhs = gimple_assign_rhs1 (stmt);
1264 : else
1265 : {
1266 : /* A statement that is not a trivial copy.
1267 : Try to fold the new expression. Inserting the
1268 : expression into the hash table is unlikely to help. */
1269 : /* ??? The DOM callback below can be changed to setting
1270 : the mprts_hook around the call to thread_across_edge,
1271 : avoiding the use substitution. */
1272 25900488 : cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
1273 : threadedge_valueize);
1274 25900488 : if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
1275 25900488 : && (!cached_lhs
1276 3079936 : || (TREE_CODE (cached_lhs) != SSA_NAME
1277 2696989 : && !is_gimple_min_invariant (cached_lhs))))
1278 : {
1279 : /* We're going to temporarily copy propagate the operands
1280 : and see if that allows us to simplify this statement. */
1281 22948488 : tree *copy;
1282 22948488 : ssa_op_iter iter;
1283 22948488 : use_operand_p use_p;
1284 22948488 : unsigned int num, i = 0;
1285 :
1286 22948488 : num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
1287 22948488 : copy = XALLOCAVEC (tree, num);
1288 :
1289 : /* Make a copy of the uses & vuses into USES_COPY, then cprop into
1290 : the operands. */
1291 56564456 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1292 : {
1293 33615968 : tree tmp = NULL;
1294 33615968 : tree use = USE_FROM_PTR (use_p);
1295 :
1296 33615968 : copy[i++] = use;
1297 33615968 : if (TREE_CODE (use) == SSA_NAME)
1298 64920490 : tmp = SSA_NAME_VALUE (use);
1299 31304522 : if (tmp)
1300 8988911 : SET_USE (use_p, tmp);
1301 : }
1302 :
1303 : /* Do not pass state to avoid calling the ranger with the
1304 : temporarily altered IL. */
1305 22948488 : cached_lhs = simplifier->simplify (stmt, stmt, bb, /*state=*/NULL);
1306 :
1307 : /* Restore the statement's original uses/defs. */
1308 22948488 : i = 0;
1309 56564456 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1310 33615968 : SET_USE (use_p, copy[i++]);
1311 : }
1312 : }
1313 :
1314 : /* Record the context sensitive equivalence if we were able
1315 : to simplify this statement. */
1316 26937373 : if (cached_lhs
1317 26937373 : && (TREE_CODE (cached_lhs) == SSA_NAME
1318 2539684 : || is_gimple_min_invariant (cached_lhs)))
1319 4520199 : register_equiv (gimple_get_lhs (stmt), cached_lhs,
1320 : /*update_range=*/false);
1321 26937373 : }
1322 :
1323 : // Hybrid threader implementation.
1324 :
1325 2125077 : hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
1326 2125077 : path_range_query *q)
1327 : {
1328 2125077 : m_ranger = r;
1329 2125077 : m_query = q;
1330 2125077 : }
1331 :
1332 : tree
1333 8779442 : hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
1334 : jt_state *state)
1335 : {
1336 8779442 : auto_bitmap dependencies;
1337 8779442 : auto_vec<basic_block> path;
1338 :
1339 8779442 : state->get_path (path);
1340 8779442 : compute_exit_dependencies (dependencies, path, stmt);
1341 8779442 : m_query->reset_path (path, dependencies);
1342 :
1343 8779442 : if (gimple_code (stmt) == GIMPLE_COND
1344 8779442 : || gimple_code (stmt) == GIMPLE_ASSIGN)
1345 : {
1346 8749304 : value_range r (gimple_range_type (stmt));
1347 8749304 : tree ret;
1348 17498608 : if (m_query->range_of_stmt (r, stmt) && r.singleton_p (&ret))
1349 186585 : return ret;
1350 8749304 : }
1351 30138 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1352 : {
1353 29902 : int_range_max r;
1354 29902 : gswitch *switch_stmt = dyn_cast <gswitch *> (stmt);
1355 29902 : tree index = gimple_switch_index (switch_stmt);
1356 29902 : if (m_query->range_of_expr (r, index, stmt))
1357 29902 : return find_case_label_range (switch_stmt, &r);
1358 29902 : }
1359 : return NULL;
1360 8779442 : }
1361 :
1362 : // Calculate the set of exit dependencies for a path and statement to
1363 : // be simplified. This is different than the
1364 : // compute_exit_dependencies in the path solver because the forward
1365 : // threader asks questions about statements not necessarily in the
1366 : // path. Using the default compute_exit_dependencies in the path
1367 : // solver gets noticeably less threads.
1368 :
1369 : void
1370 8779442 : hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies,
1371 : const vec<basic_block> &path,
1372 : gimple *stmt)
1373 : {
1374 : // Start with the imports to the final conditional.
1375 8779442 : bitmap_copy (dependencies, m_ranger->gori_ssa ()->imports (path[0]));
1376 :
1377 : // Add any other interesting operands we may have missed.
1378 8779442 : if (gimple_bb (stmt) != path[0])
1379 : {
1380 43746520 : for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1381 : {
1382 34997216 : tree op = gimple_op (stmt, i);
1383 34997216 : if (op
1384 17498608 : && TREE_CODE (op) == SSA_NAME
1385 45939363 : && value_range::supports_type_p (TREE_TYPE (op)))
1386 10937833 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (op));
1387 : }
1388 : }
1389 8779442 : }
|
