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 80791466 : set_ssa_name_value (tree name, tree value)
57 : {
58 80791466 : if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
59 3756778 : ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, true);
60 80791466 : if (value && TREE_OVERFLOW_P (value))
61 15 : value = drop_tree_overflow (value);
62 80791466 : ssa_name_values[SSA_NAME_VERSION (name)] = value;
63 80791466 : }
64 :
65 2136688 : jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
66 : {
67 : /* Initialize the per SSA_NAME value-handles array. */
68 2136688 : gcc_assert (!ssa_name_values.exists ());
69 4273376 : ssa_name_values.create (num_ssa_names);
70 :
71 2136688 : dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
72 : integer_zero_node, NULL, NULL);
73 :
74 2136688 : m_registry = new fwd_jt_path_registry ();
75 2136688 : m_simplifier = simplifier;
76 2136688 : m_state = state;
77 2136688 : }
78 :
79 2136688 : jump_threader::~jump_threader (void)
80 : {
81 2136688 : ssa_name_values.release ();
82 2136688 : ggc_free (dummy_cond);
83 2136688 : delete m_registry;
84 2136688 : }
85 :
86 : void
87 467425 : jump_threader::remove_jump_threads_including (edge_def *e)
88 : {
89 467425 : m_registry->remove_jump_threads_including (e);
90 467425 : }
91 :
92 : bool
93 2136688 : jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
94 : {
95 2136688 : return m_registry->thread_through_all_blocks (may_peel_loop_headers);
96 : }
97 :
98 : static inline bool
99 17410626 : has_phis_p (basic_block bb)
100 : {
101 5692560 : 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 32934029 : empty_block_with_phis_p (basic_block bb)
108 : {
109 38626589 : 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 30347099 : potentially_threadable_block (basic_block bb)
117 : {
118 30347099 : 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 30347099 : 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 29993400 : 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 8902669 : gsi = gsi_last_bb (bb);
136 8902669 : if (gsi_end_p (gsi)
137 8895713 : || ! gsi_stmt (gsi)
138 8902669 : || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
139 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
140 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
141 2017102 : 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 16012996 : jump_threader::record_temporary_equivalences_from_phis (edge e)
154 : {
155 16012996 : 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 33213478 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
161 : {
162 17200482 : gphi *phi = gsi.phi ();
163 17200482 : tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
164 17200482 : 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 17200482 : if (src != dst
170 17200482 : && TREE_CODE (src) == SSA_NAME
171 14032905 : && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
172 22862411 : && 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 34400964 : if (!virtual_operand_p (dst))
178 10507943 : stmt_count++;
179 :
180 17200482 : 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 31521055 : threadedge_valueize (tree t)
189 : {
190 31521055 : if (TREE_CODE (t) == SSA_NAME)
191 : {
192 28577262 : tree tem = SSA_NAME_VALUE (t);
193 27174042 : if (tem)
194 7938085 : 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 16012996 : jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
218 : {
219 16012996 : gimple *stmt = NULL;
220 16012996 : gimple_stmt_iterator gsi;
221 16012996 : int max_stmt_count;
222 :
223 16012996 : 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 194198522 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
230 : {
231 163526873 : stmt = gsi_stmt (gsi);
232 :
233 : /* Ignore empty statements and labels. */
234 163526873 : if (gimple_code (stmt) == GIMPLE_NOP
235 163526861 : || gimple_code (stmt) == GIMPLE_LABEL
236 326474976 : || is_gimple_debug (stmt))
237 112651142 : 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 50875731 : if (gimple_code (stmt) == GIMPLE_ASM
243 50875731 : && 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 50860149 : if (gimple_code (stmt) == GIMPLE_CALL
249 5147176 : && gimple_call_internal_p (stmt)
250 50968499 : && 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 50860149 : 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 50854843 : stmt_count++;
262 50854843 : 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 2267004 : if (max_stmt_count
268 2267004 : == param_max_jump_thread_duplication_stmts)
269 : {
270 1706473 : max_stmt_count += estimate_threading_killed_stmts (e->dest);
271 1706473 : 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 2267004 : if (stmt_count > max_stmt_count)
277 : return NULL;
278 : }
279 :
280 49521388 : 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 49521388 : if ((gimple_code (stmt) != GIMPLE_ASSIGN
286 34480388 : || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
287 58718320 : && (gimple_code (stmt) != GIMPLE_CALL
288 4959342 : || gimple_call_lhs (stmt) == NULL_TREE
289 2263687 : || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
290 22390407 : 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 27130981 : if (is_gimple_call (stmt))
318 : {
319 1847525 : tree fndecl = gimple_call_fndecl (stmt);
320 1847525 : if (fndecl
321 1715598 : && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
322 2280491 : && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
323 432966 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
324 0 : continue;
325 : }
326 :
327 27130981 : 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 9972883 : jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
343 : {
344 9972883 : tree cond, cached_lhs;
345 9972883 : 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 9972883 : if (code == GIMPLE_COND)
350 : {
351 9939508 : tree op0, op1;
352 9939508 : enum tree_code cond_code;
353 :
354 9939508 : op0 = gimple_cond_lhs (stmt);
355 9939508 : op1 = gimple_cond_rhs (stmt);
356 9939508 : cond_code = gimple_cond_code (stmt);
357 :
358 : /* Get the current value of both operands. */
359 9939508 : if (TREE_CODE (op0) == SSA_NAME)
360 : {
361 11982548 : for (int i = 0; i < 2; i++)
362 : {
363 11976534 : if (TREE_CODE (op0) == SSA_NAME
364 11976534 : && SSA_NAME_VALUE (op0))
365 2081635 : op0 = SSA_NAME_VALUE (op0);
366 : else
367 : break;
368 : }
369 : }
370 :
371 9939508 : if (TREE_CODE (op1) == SSA_NAME)
372 : {
373 3217172 : for (int i = 0; i < 2; i++)
374 : {
375 3216345 : if (TREE_CODE (op1) == SSA_NAME
376 3216345 : && SSA_NAME_VALUE (op1))
377 593658 : op1 = SSA_NAME_VALUE (op1);
378 : else
379 : break;
380 : }
381 : }
382 :
383 9939508 : const unsigned recursion_limit = 4;
384 :
385 9939508 : cached_lhs
386 9939508 : = 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 9939508 : 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 8670427 : tree op0 = gimple_cond_lhs (stmt);
401 8670427 : tree op1 = gimple_cond_rhs (stmt);
402 :
403 17195301 : if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
404 2127485 : || POINTER_TYPE_P (TREE_TYPE (op0)))
405 8495742 : && TREE_CODE (op0) == SSA_NAME
406 17165434 : && TREE_CODE (op1) == INTEGER_CST)
407 : return op0;
408 : }
409 :
410 4218319 : return cached_lhs;
411 : }
412 :
413 33375 : if (code == GIMPLE_SWITCH)
414 32966 : cond = gimple_switch_index (as_a <gswitch *> (stmt));
415 409 : else if (code == GIMPLE_GOTO)
416 409 : 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 33375 : 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 40857 : for (int i = 0; i < 2; i++)
435 : {
436 40857 : if (TREE_CODE (cached_lhs) == SSA_NAME
437 40857 : && SSA_NAME_VALUE (cached_lhs))
438 7553 : 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 33304 : if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
447 : {
448 31525 : 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 31285 : gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
455 31285 : gimple_switch_set_index (dummy_switch, cached_lhs);
456 31285 : cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
457 : m_state);
458 31285 : ggc_free (dummy_switch);
459 : }
460 : else
461 240 : 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 33304 : if (!cached_lhs)
468 30766 : 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 9939508 : 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 9939508 : 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 9939508 : if (tree_swap_operands_p (op0, op1))
495 : {
496 484009 : cond_code = swap_tree_comparison (cond_code);
497 484009 : std::swap (op0, op1);
498 : }
499 :
500 9939508 : gimple_cond_set_code (dummy_cond, cond_code);
501 9939508 : gimple_cond_set_lhs (dummy_cond, op0);
502 9939508 : gimple_cond_set_rhs (dummy_cond, op1);
503 :
504 9939508 : tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
505 9939508 : if (res)
506 1738131 : while (CONVERT_EXPR_P (res))
507 649 : 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 1737482 : if (!res
512 1737482 : || !is_gimple_min_invariant (res))
513 9025402 : 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 1781520 : propagate_threaded_block_debug_into (basic_block dest, basic_block src)
523 : {
524 1781520 : if (!MAY_HAVE_DEBUG_BIND_STMTS)
525 1135626 : return;
526 :
527 1781520 : if (!single_pred_p (dest))
528 : return;
529 :
530 645894 : gcc_checking_assert (dest != src);
531 :
532 645894 : gimple_stmt_iterator gsi = gsi_after_labels (dest);
533 645894 : int i = 0;
534 645894 : 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 645894 : for (gimple_stmt_iterator si = gsi;
539 2869923 : i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
540 : {
541 2723574 : gimple *stmt = gsi_stmt (si);
542 2723574 : if (!is_gimple_debug (stmt))
543 : break;
544 2224029 : if (gimple_debug_nonbind_marker_p (stmt))
545 397621 : continue;
546 1826408 : i++;
547 : }
548 :
549 645894 : auto_vec<tree, alloc_count> fewvars;
550 645894 : 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 645894 : if (i * 4 > alloc_count * 3)
556 68573 : 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 3979540 : for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
562 : {
563 3899806 : gimple *stmt = gsi_stmt (si);
564 3899806 : if (!is_gimple_debug (stmt))
565 : break;
566 :
567 3333646 : tree var;
568 :
569 3333646 : if (gimple_debug_bind_p (stmt))
570 2788876 : var = gimple_debug_bind_get_var (stmt);
571 544770 : else if (gimple_debug_source_bind_p (stmt))
572 20580 : var = gimple_debug_source_bind_get_var (stmt);
573 524190 : else if (gimple_debug_nonbind_marker_p (stmt))
574 524190 : continue;
575 : else
576 0 : gcc_unreachable ();
577 :
578 2809456 : if (vars)
579 1874497 : vars->add (var);
580 : else
581 934959 : fewvars.quick_push (var);
582 : }
583 :
584 645894 : basic_block bb = dest;
585 :
586 669718 : do
587 : {
588 669718 : bb = single_pred (bb);
589 1339436 : for (gimple_stmt_iterator si = gsi_last_bb (bb);
590 8986683 : !gsi_end_p (si); gsi_prev (&si))
591 : {
592 7647247 : gimple *stmt = gsi_stmt (si);
593 7647247 : if (!is_gimple_debug (stmt))
594 5302002 : continue;
595 :
596 6093771 : tree var;
597 :
598 6093771 : if (gimple_debug_bind_p (stmt))
599 4940863 : var = gimple_debug_bind_get_var (stmt);
600 1152908 : else if (gimple_debug_source_bind_p (stmt))
601 31190 : var = gimple_debug_source_bind_get_var (stmt);
602 1121718 : else if (gimple_debug_nonbind_marker_p (stmt))
603 1121718 : 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 4972053 : if (vars && vars->add (var))
620 1789594 : continue;
621 3182459 : else if (!vars)
622 : {
623 2608270 : int i = fewvars.length ();
624 15535686 : while (i--)
625 13764630 : if (fewvars[i] == var)
626 : break;
627 2608270 : if (i >= 0)
628 837214 : continue;
629 1771056 : else if (fewvars.length () < (unsigned) alloc_count)
630 1727700 : fewvars.quick_push (var);
631 : else
632 : {
633 43356 : vars = new hash_set<tree>;
634 780408 : for (i = 0; i < alloc_count; i++)
635 693696 : vars->add (fewvars[i]);
636 43356 : fewvars.release ();
637 43356 : vars->add (var);
638 : }
639 : }
640 :
641 2345245 : stmt = gimple_copy (stmt);
642 : /* ??? Should we drop the location of the copy to denote
643 : they're artificial bindings? */
644 2345245 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
645 : }
646 : }
647 1353512 : while (bb != src && single_pred_p (bb));
648 :
649 645894 : if (vars)
650 111929 : delete vars;
651 533965 : else if (fewvars.exists ())
652 533965 : fewvars.release ();
653 645894 : }
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 11288954 : jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
664 : edge taken_edge,
665 : bitmap visited, unsigned &limit)
666 : {
667 11718999 : basic_block bb = taken_edge->dest;
668 11718999 : gimple_stmt_iterator gsi;
669 11718999 : gimple *stmt;
670 11718999 : tree cond;
671 :
672 11718999 : if (limit == 0)
673 : return false;
674 11718066 : --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 11718066 : if (has_phis_p (bb))
680 : return false;
681 :
682 : /* Skip over DEBUG statements at the start of the block. */
683 7762949 : 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 7762949 : if (gsi_end_p (gsi))
700 : {
701 1792489 : if (single_succ_p (bb))
702 : {
703 1792489 : taken_edge = single_succ_edge (bb);
704 :
705 1792489 : if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
706 : return false;
707 :
708 430045 : if (!bitmap_bit_p (visited, taken_edge->dest->index))
709 : {
710 430045 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
711 430045 : m_state->append_path (taken_edge->dest);
712 430045 : bitmap_set_bit (visited, taken_edge->dest->index);
713 430045 : return thread_around_empty_blocks (path, taken_edge, visited,
714 430045 : 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 5970460 : stmt = gsi_stmt (gsi);
725 5970460 : 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 568142 : 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 568142 : if (cond != NULL_TREE
737 568142 : && (is_gimple_min_invariant (cond)
738 337367 : || TREE_CODE (cond) == CASE_LABEL_EXPR))
739 : {
740 101609 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
741 26 : taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
742 : else
743 101583 : taken_edge = find_taken_edge (bb, cond);
744 :
745 101609 : if (!taken_edge
746 101589 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
747 : return false;
748 :
749 101491 : if (bitmap_bit_p (visited, taken_edge->dest->index))
750 : return false;
751 101491 : bitmap_set_bit (visited, taken_edge->dest->index);
752 :
753 101491 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
754 101491 : m_state->append_path (taken_edge->dest);
755 :
756 101491 : thread_around_empty_blocks (path, taken_edge, visited, limit);
757 101491 : 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 16013955 : jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
783 : edge e, bitmap visited,
784 : unsigned &limit)
785 : {
786 16013955 : if (limit == 0)
787 : return 0;
788 16012996 : limit--;
789 :
790 16012996 : 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 16012996 : 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 16012996 : 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 16012996 : if (!stmt)
818 : {
819 : /* First case. The statement simply doesn't have any instructions, but
820 : does have PHIs. */
821 2586930 : if (empty_block_with_phis_p (e->dest))
822 : return 0;
823 :
824 : /* Second case. */
825 2306759 : 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 13426066 : if (gimple_code (stmt) == GIMPLE_COND
831 : || gimple_code (stmt) == GIMPLE_GOTO
832 : || gimple_code (stmt) == GIMPLE_SWITCH)
833 : {
834 9404741 : tree cond;
835 :
836 : /* Extract and simplify the condition. */
837 9404741 : cond = simplify_control_stmt_condition (e, stmt);
838 :
839 9404741 : if (!cond)
840 : return 0;
841 :
842 6584624 : if (is_gimple_min_invariant (cond)
843 6584624 : || TREE_CODE (cond) == CASE_LABEL_EXPR)
844 : {
845 1147784 : edge taken_edge;
846 1147784 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
847 733 : taken_edge = find_edge (e->dest,
848 733 : label_to_block (cfun, CASE_LABEL (cond)));
849 : else
850 1147051 : taken_edge = find_taken_edge (e->dest, cond);
851 :
852 1147784 : 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 1147738 : if (dest == NULL
857 1147738 : || dest == e->dest
858 1147738 : || (taken_edge->flags & EDGE_DFS_BACK) != 0
859 2294635 : || 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 1146897 : if (path->length () == 0)
865 705759 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
866 :
867 1146897 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
868 1146897 : 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 1146897 : bitmap_set_bit (visited, dest->index);
877 1146897 : bitmap_set_bit (visited, e->dest->index);
878 1146897 : thread_around_empty_blocks (path, taken_edge, visited, limit);
879 1146897 : 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 9546952 : edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
905 : {
906 9546952 : gcond *gs;
907 9546952 : gphi *phi;
908 9546952 : return (cond_on_phi_p (e->dest, &gs, &phi)
909 9546952 : && 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 17361959 : cond_on_phi_p (basic_block bb, gcond **cond_out, gphi **phi_out)
924 : {
925 17361959 : gcond *gs;
926 17361959 : 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 2144782 : tree cond = gimple_cond_lhs (gs);
931 2144782 : enum tree_code code = gimple_cond_code (gs);
932 2144782 : tree rhs = gimple_cond_rhs (gs);
933 2144782 : if (TREE_CODE (cond) != SSA_NAME
934 2144264 : || (code != NE_EXPR && code != EQ_EXPR)
935 3635865 : || (!integer_onep (rhs) && !integer_zerop (rhs)))
936 : return false;
937 996786 : gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
938 630591 : if (phi == NULL || gimple_bb (phi) != bb)
939 : return false;
940 :
941 501999 : *cond_out = gs;
942 501999 : *phi_out = phi;
943 501999 : 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 796380 : phi_arg_from_cmp_p (gphi *phi, edge e)
959 : {
960 796380 : gassign *def;
961 796380 : tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
962 796380 : if (TREE_CODE (value) != SSA_NAME
963 534125 : || !has_single_use (value)
964 1039728 : || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
965 : return false;
966 :
967 : /* Or if it is (INT) (a CMP b). */
968 278162 : if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
969 : {
970 39128 : value = gimple_assign_rhs1 (def);
971 39128 : if (TREE_CODE (value) != SSA_NAME
972 39128 : || !has_single_use (value)
973 77072 : || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
974 : return false;
975 : }
976 :
977 255527 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
978 111840 : 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 7239266 : jump_threader::thread_across_edge (edge e)
989 : {
990 7239266 : auto_bitmap visited;
991 :
992 7239266 : m_state->push (e);
993 :
994 7239266 : stmt_count = 0;
995 :
996 7239266 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
997 7239266 : bitmap_set_bit (visited, e->src->index);
998 7239266 : bitmap_set_bit (visited, e->dest->index);
999 :
1000 : /* Limit search space. */
1001 7239266 : unsigned limit = param_max_jump_thread_paths;
1002 :
1003 7239266 : int threaded = 0;
1004 7239266 : if ((e->flags & EDGE_DFS_BACK) == 0)
1005 6025865 : threaded = thread_through_normal_block (path, e, visited, limit);
1006 :
1007 6025865 : if (threaded > 0)
1008 : {
1009 705759 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1010 : e->dest);
1011 705759 : m_registry->register_jump_thread (path);
1012 705759 : m_state->pop ();
1013 705759 : return;
1014 : }
1015 :
1016 6533507 : gcc_checking_assert (path->length () == 0);
1017 6533507 : path->release ();
1018 :
1019 6533507 : 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 174017 : m_state->pop ();
1029 174017 : 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 6359490 : {
1044 6359490 : edge taken_edge;
1045 6359490 : edge_iterator ei;
1046 6359490 : 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 6359490 : if (!can_duplicate_block_on_edge_p (e))
1051 : {
1052 407 : m_state->pop ();
1053 407 : return;
1054 : }
1055 :
1056 : /* Look at each successor of E->dest to see if we can thread through it. */
1057 18883547 : FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1058 : {
1059 12524464 : if ((e->flags & EDGE_DFS_BACK) != 0
1060 10108660 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1061 2483898 : continue;
1062 :
1063 10040566 : m_state->push (taken_edge);
1064 :
1065 : /* Avoid threading to any block we have already visited. */
1066 10040566 : bitmap_clear (visited);
1067 10040566 : bitmap_set_bit (visited, e->src->index);
1068 10040566 : bitmap_set_bit (visited, e->dest->index);
1069 10040566 : bitmap_set_bit (visited, taken_edge->dest->index);
1070 :
1071 10040566 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1072 10040566 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
1073 10040566 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1074 :
1075 10040566 : found = thread_around_empty_blocks (path, taken_edge, visited, limit);
1076 :
1077 10040566 : if (!found)
1078 9988090 : found = thread_through_normal_block (path,
1079 9988090 : 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 9988090 : if (found
1085 9988090 : || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1086 : {
1087 496607 : if (taken_edge->dest != path->last ()->e->dest)
1088 493620 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1089 : taken_edge->dest);
1090 496607 : m_registry->register_jump_thread (path);
1091 : }
1092 : else
1093 9543959 : path->release ();
1094 :
1095 10040566 : m_state->pop ();
1096 : }
1097 : }
1098 :
1099 6359083 : m_state->pop ();
1100 7239266 : }
1101 :
1102 : /* Return TRUE if BB has a single successor to a block with multiple
1103 : incoming and outgoing edges. */
1104 :
1105 : bool
1106 24279476 : single_succ_to_potentially_threadable_block (basic_block bb)
1107 : {
1108 24279476 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1109 24279476 : return (single_succ_p (bb)
1110 11999001 : && (single_succ_edge (bb)->flags & flags) == 0
1111 35718102 : && 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 24281176 : jump_threader::thread_outgoing_edges (basic_block bb)
1119 : {
1120 24281176 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1121 :
1122 24281176 : 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 24279476 : if (single_succ_to_potentially_threadable_block (bb))
1130 4493788 : thread_across_edge (single_succ_edge (bb));
1131 39571376 : else if (safe_is_a <gcond *> (*gsi_last_bb (bb))
1132 9326964 : && EDGE_COUNT (bb->succs) == 2
1133 9326964 : && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1134 26746764 : && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1135 : {
1136 9326964 : edge true_edge, false_edge;
1137 :
1138 9326964 : 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 9326964 : if (potentially_threadable_block (true_edge->dest))
1143 953952 : thread_across_edge (true_edge);
1144 :
1145 : /* Similarly for the ELSE arm. */
1146 9326964 : if (potentially_threadable_block (false_edge->dest))
1147 1791526 : 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 17279832 : jt_state::push (edge e)
1158 : {
1159 17279832 : m_blocks.safe_push (BB_MARKER);
1160 17279832 : if (m_blocks.length () == 1)
1161 7239266 : m_blocks.safe_push (e->src);
1162 17279832 : m_blocks.safe_push (e->dest);
1163 17279832 : }
1164 :
1165 : // Pop to the last pushed state.
1166 :
1167 : void
1168 17279832 : jt_state::pop ()
1169 : {
1170 17279832 : if (!m_blocks.is_empty ())
1171 : {
1172 43477363 : while (m_blocks.last () != BB_MARKER)
1173 26197531 : m_blocks.pop ();
1174 : // Pop marker.
1175 17279832 : m_blocks.pop ();
1176 : }
1177 17279832 : }
1178 :
1179 : // Add BB to the list of blocks seen.
1180 :
1181 : void
1182 1678433 : jt_state::append_path (basic_block bb)
1183 : {
1184 1678433 : gcc_checking_assert (!m_blocks.is_empty ());
1185 1678433 : m_blocks.safe_push (bb);
1186 1678433 : }
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 8895092 : jt_state::get_path (vec<basic_block> &path)
1211 : {
1212 8895092 : path.truncate (0);
1213 :
1214 52654995 : for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
1215 : {
1216 34864811 : basic_block bb = m_blocks[i];
1217 :
1218 34864811 : if (bb != BB_MARKER)
1219 22038103 : path.safe_push (bb);
1220 : }
1221 8895092 : }
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 49521388 : jt_state::record_ranges_from_stmt (gimple *,
1239 : bool temporary ATTRIBUTE_UNUSED)
1240 : {
1241 49521388 : }
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 27130981 : 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 27130981 : tree cached_lhs = NULL;
1261 27130981 : if (gimple_assign_single_p (stmt)
1262 27130981 : && 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 26112649 : cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
1273 : threadedge_valueize);
1274 26112649 : if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
1275 26112649 : && (!cached_lhs
1276 3096921 : || (TREE_CODE (cached_lhs) != SSA_NAME
1277 2714659 : && !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 23150277 : tree *copy;
1282 23150277 : ssa_op_iter iter;
1283 23150277 : use_operand_p use_p;
1284 23150277 : unsigned int num, i = 0;
1285 :
1286 23150277 : num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
1287 23150277 : copy = XALLOCAVEC (tree, num);
1288 :
1289 : /* Make a copy of the uses & vuses into USES_COPY, then cprop into
1290 : the operands. */
1291 57075819 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1292 : {
1293 33925542 : tree tmp = NULL;
1294 33925542 : tree use = USE_FROM_PTR (use_p);
1295 :
1296 33925542 : copy[i++] = use;
1297 33925542 : if (TREE_CODE (use) == SSA_NAME)
1298 65516969 : tmp = SSA_NAME_VALUE (use);
1299 31591427 : if (tmp)
1300 9060206 : SET_USE (use_p, tmp);
1301 : }
1302 :
1303 : /* Do not pass state to avoid calling the ranger with the
1304 : temporarily altered IL. */
1305 23150277 : cached_lhs = simplifier->simplify (stmt, stmt, bb, /*state=*/NULL);
1306 :
1307 : /* Restore the statement's original uses/defs. */
1308 23150277 : i = 0;
1309 57075819 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1310 33925542 : 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 27130981 : if (cached_lhs
1317 27130981 : && (TREE_CODE (cached_lhs) == SSA_NAME
1318 2548676 : || is_gimple_min_invariant (cached_lhs)))
1319 4514755 : register_equiv (gimple_get_lhs (stmt), cached_lhs,
1320 : /*update_range=*/false);
1321 27130981 : }
1322 :
1323 : // Hybrid threader implementation.
1324 :
1325 2136688 : hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
1326 2136688 : path_range_query *q)
1327 : {
1328 2136688 : m_ranger = r;
1329 2136688 : m_query = q;
1330 2136688 : }
1331 :
1332 : tree
1333 8895092 : hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
1334 : jt_state *state)
1335 : {
1336 8895092 : auto_bitmap dependencies;
1337 8895092 : auto_vec<basic_block> path;
1338 :
1339 8895092 : state->get_path (path);
1340 8895092 : compute_exit_dependencies (dependencies, path, stmt);
1341 8895092 : m_query->reset_path (path, dependencies);
1342 :
1343 8895092 : if (gimple_code (stmt) == GIMPLE_COND
1344 8895092 : || gimple_code (stmt) == GIMPLE_ASSIGN)
1345 : {
1346 8863567 : value_range r (gimple_range_type (stmt));
1347 8863567 : tree ret;
1348 17727134 : if (m_query->range_of_stmt (r, stmt) && r.singleton_p (&ret))
1349 193140 : return ret;
1350 8863567 : }
1351 31525 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1352 : {
1353 31285 : int_range_max r;
1354 31285 : gswitch *switch_stmt = dyn_cast <gswitch *> (stmt);
1355 31285 : tree index = gimple_switch_index (switch_stmt);
1356 31285 : if (m_query->range_of_expr (r, index, stmt))
1357 31285 : return find_case_label_range (switch_stmt, &r);
1358 31285 : }
1359 : return NULL;
1360 8895092 : }
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 8895092 : 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 8895092 : bitmap_copy (dependencies, m_ranger->gori_ssa ()->imports (path[0]));
1376 :
1377 : // Add any other interesting operands we may have missed.
1378 8895092 : if (gimple_bb (stmt) != path[0])
1379 : {
1380 44317835 : for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1381 : {
1382 35454268 : tree op = gimple_op (stmt, i);
1383 35454268 : if (op
1384 17727134 : && TREE_CODE (op) == SSA_NAME
1385 46534619 : && value_range::supports_type_p (TREE_TYPE (op)))
1386 11076024 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (op));
1387 : }
1388 : }
1389 8895092 : }
|
