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