Branch data Line data Source code
1 : : /* SSA Jump Threading
2 : : Copyright (C) 2005-2024 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 : 69838958 : set_ssa_name_value (tree name, tree value)
56 : : {
57 : 139677916 : if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
58 : 3432940 : ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, true);
59 : 69838958 : if (value && TREE_OVERFLOW_P (value))
60 : 15 : value = drop_tree_overflow (value);
61 : 69838958 : ssa_name_values[SSA_NAME_VERSION (name)] = value;
62 : 69838958 : }
63 : :
64 : 1951518 : jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
65 : : {
66 : : /* Initialize the per SSA_NAME value-handles array. */
67 : 1951518 : gcc_assert (!ssa_name_values.exists ());
68 : 3903036 : ssa_name_values.create (num_ssa_names);
69 : :
70 : 1951518 : dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
71 : : integer_zero_node, NULL, NULL);
72 : :
73 : 1951518 : m_registry = new fwd_jt_path_registry ();
74 : 1951518 : m_simplifier = simplifier;
75 : 1951518 : m_state = state;
76 : 1951518 : }
77 : :
78 : 1951518 : jump_threader::~jump_threader (void)
79 : : {
80 : 1951518 : ssa_name_values.release ();
81 : 1951518 : ggc_free (dummy_cond);
82 : 1951518 : delete m_registry;
83 : 1951518 : }
84 : :
85 : : void
86 : 183241 : jump_threader::remove_jump_threads_including (edge_def *e)
87 : : {
88 : 183241 : m_registry->remove_jump_threads_including (e);
89 : 183241 : }
90 : :
91 : : bool
92 : 1951518 : jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
93 : : {
94 : 1951518 : return m_registry->thread_through_all_blocks (may_peel_loop_headers);
95 : : }
96 : :
97 : : static inline bool
98 : 15848874 : has_phis_p (basic_block bb)
99 : : {
100 : 5975939 : 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 : 28723122 : empty_block_with_phis_p (basic_block bb)
107 : : {
108 : 34699061 : 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 : 25982959 : potentially_threadable_block (basic_block bb)
116 : : {
117 : 25982959 : 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 : 25982959 : 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 : 25188156 : 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 : 7306248 : gsi = gsi_last_bb (bb);
135 : 7306248 : if (gsi_end_p (gsi)
136 : 7300210 : || ! gsi_stmt (gsi)
137 : 7306248 : || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
138 : 1765085 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
139 : 1764579 : && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
140 : 1749737 : 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 : 13899881 : jump_threader::record_temporary_equivalences_from_phis (edge e)
153 : : {
154 : 13899881 : 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 : 29431335 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
160 : : {
161 : 15531454 : gphi *phi = gsi.phi ();
162 : 15531454 : tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
163 : 15531454 : 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 : 15531454 : if (src != dst
169 : 15531454 : && TREE_CODE (src) == SSA_NAME
170 : 12651559 : && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
171 : 20874047 : && 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 : 31062908 : if (!virtual_operand_p (dst))
177 : 9122175 : stmt_count++;
178 : :
179 : 15531454 : 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 : 25990077 : threadedge_valueize (tree t)
188 : : {
189 : 25990077 : if (TREE_CODE (t) == SSA_NAME)
190 : : {
191 : 23582634 : tree tem = SSA_NAME_VALUE (t);
192 : 22361656 : if (tem)
193 : 6458344 : 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 : 13899881 : jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
217 : : {
218 : 13899881 : gimple *stmt = NULL;
219 : 13899881 : gimple_stmt_iterator gsi;
220 : 13899881 : int max_stmt_count;
221 : :
222 : 13899881 : 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 : 144535782 : for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
229 : : {
230 : 117905204 : stmt = gsi_stmt (gsi);
231 : :
232 : : /* Ignore empty statements and labels. */
233 : 117905204 : if (gimple_code (stmt) == GIMPLE_NOP
234 : 117905194 : || gimple_code (stmt) == GIMPLE_LABEL
235 : 235362020 : || is_gimple_debug (stmt))
236 : 75018283 : 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 : 42886921 : if (gimple_code (stmt) == GIMPLE_ASM
242 : 42886921 : && 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 : 42874300 : if (gimple_code (stmt) == GIMPLE_CALL
248 : 4351264 : && gimple_call_internal_p (stmt)
249 : 42939763 : && 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 : 42874300 : 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 : 42874297 : stmt_count++;
261 : 42874297 : 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 : 1961349 : if (max_stmt_count
267 : 1961349 : == param_max_jump_thread_duplication_stmts)
268 : : {
269 : 1463989 : max_stmt_count += estimate_threading_killed_stmts (e->dest);
270 : 1463989 : if (dump_file)
271 : 41 : fprintf (dump_file, "threading bb %i up to %i stmts\n",
272 : 41 : e->dest->index, max_stmt_count);
273 : : }
274 : : /* If we're still past the limit, we're done. */
275 : 1961349 : if (stmt_count > max_stmt_count)
276 : : return NULL;
277 : : }
278 : :
279 : 41717737 : 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 : 41717737 : if ((gimple_code (stmt) != GIMPLE_ASSIGN
285 : 29293771 : || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
286 : 49842298 : && (gimple_code (stmt) != GIMPLE_CALL
287 : 4180996 : || gimple_call_lhs (stmt) == NULL_TREE
288 : 1931775 : || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
289 : 18994934 : 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 : 22722803 : if (is_gimple_call (stmt))
317 : : {
318 : 1553593 : tree fndecl = gimple_call_fndecl (stmt);
319 : 1553593 : if (fndecl
320 : 1440885 : && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL)
321 : 1920784 : && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
322 : 367191 : || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
323 : 0 : continue;
324 : : }
325 : :
326 : 22722803 : 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 : 7944891 : jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
342 : : {
343 : 7944891 : tree cond, cached_lhs;
344 : 7944891 : 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 : 7944891 : if (code == GIMPLE_COND)
349 : : {
350 : 7918338 : tree op0, op1;
351 : 7918338 : enum tree_code cond_code;
352 : :
353 : 7918338 : op0 = gimple_cond_lhs (stmt);
354 : 7918338 : op1 = gimple_cond_rhs (stmt);
355 : 7918338 : cond_code = gimple_cond_code (stmt);
356 : :
357 : : /* Get the current value of both operands. */
358 : 7918338 : if (TREE_CODE (op0) == SSA_NAME)
359 : : {
360 : 9377487 : for (int i = 0; i < 2; i++)
361 : : {
362 : 9375483 : if (TREE_CODE (op0) == SSA_NAME
363 : 9375483 : && SSA_NAME_VALUE (op0))
364 : 1653868 : op0 = SSA_NAME_VALUE (op0);
365 : : else
366 : : break;
367 : : }
368 : : }
369 : :
370 : 7918338 : if (TREE_CODE (op1) == SSA_NAME)
371 : : {
372 : 2685086 : for (int i = 0; i < 2; i++)
373 : : {
374 : 2684458 : if (TREE_CODE (op1) == SSA_NAME
375 : 2684458 : && SSA_NAME_VALUE (op1))
376 : 470984 : op1 = SSA_NAME_VALUE (op1);
377 : : else
378 : : break;
379 : : }
380 : : }
381 : :
382 : 7918338 : const unsigned recursion_limit = 4;
383 : :
384 : 7918338 : cached_lhs
385 : 7918338 : = 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 : 7918338 : 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 : 6967038 : tree op0 = gimple_cond_lhs (stmt);
400 : 6967038 : tree op1 = gimple_cond_rhs (stmt);
401 : :
402 : 13802806 : if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
403 : 1628075 : || POINTER_TYPE_P (TREE_TYPE (op0)))
404 : 6831217 : && TREE_CODE (op0) == SSA_NAME
405 : 13642050 : && TREE_CODE (op1) == INTEGER_CST)
406 : : return op0;
407 : : }
408 : :
409 : 3242786 : return cached_lhs;
410 : : }
411 : :
412 : 26553 : if (code == GIMPLE_SWITCH)
413 : 26159 : cond = gimple_switch_index (as_a <gswitch *> (stmt));
414 : 394 : else if (code == GIMPLE_GOTO)
415 : 394 : 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 : 26553 : 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 : 33624 : for (int i = 0; i < 2; i++)
434 : : {
435 : 33624 : if (TREE_CODE (cached_lhs) == SSA_NAME
436 : 33624 : && SSA_NAME_VALUE (cached_lhs))
437 : 7089 : 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 : 26535 : if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
446 : : {
447 : 24631 : 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 : 24409 : gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
454 : 24409 : gimple_switch_set_index (dummy_switch, cached_lhs);
455 : 24409 : cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
456 : : m_state);
457 : 24409 : ggc_free (dummy_switch);
458 : : }
459 : : else
460 : 222 : 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 : 26535 : if (!cached_lhs)
467 : 24525 : 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 : 9410534 : 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 : 9410534 : 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 : 9393728 : if (tree_swap_operands_p (op0, op1))
494 : : {
495 : 375646 : cond_code = swap_tree_comparison (cond_code);
496 : 375646 : std::swap (op0, op1);
497 : : }
498 : :
499 : : /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then
500 : : recurse into the LHS to see if there is a simplification that
501 : : makes this condition always true or always false along the edge
502 : : E. */
503 : 9393728 : if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
504 : 7143059 : && TREE_CODE (op0) == SSA_NAME
505 : 15530100 : && integer_zerop (op1))
506 : : {
507 : 3998074 : gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
508 : 3998074 : if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
509 : : ;
510 : 3155506 : else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR
511 : 3155506 : || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
512 : : {
513 : 474801 : enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt);
514 : 474801 : const tree rhs1 = gimple_assign_rhs1 (def_stmt);
515 : 474801 : const tree rhs2 = gimple_assign_rhs2 (def_stmt);
516 : :
517 : : /* Is A != 0 ? */
518 : 474801 : const tree res1
519 : 474801 : = simplify_control_stmt_condition_1 (e, def_stmt,
520 : : rhs1, NE_EXPR, op1,
521 : : limit - 1);
522 : 474801 : if (res1 == NULL_TREE)
523 : : ;
524 : 47252 : else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
525 : : {
526 : : /* If A == 0 then (A & B) != 0 is always false. */
527 : 363 : if (cond_code == NE_EXPR)
528 : 351 : return boolean_false_node;
529 : : /* If A == 0 then (A & B) == 0 is always true. */
530 : 12 : if (cond_code == EQ_EXPR)
531 : 12 : return boolean_true_node;
532 : : }
533 : 46889 : else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
534 : : {
535 : : /* If A != 0 then (A | B) != 0 is always true. */
536 : 504 : if (cond_code == NE_EXPR)
537 : 473 : return boolean_true_node;
538 : : /* If A != 0 then (A | B) == 0 is always false. */
539 : 31 : if (cond_code == EQ_EXPR)
540 : 31 : return boolean_false_node;
541 : : }
542 : :
543 : : /* Is B != 0 ? */
544 : 473934 : const tree res2
545 : 473934 : = simplify_control_stmt_condition_1 (e, def_stmt,
546 : : rhs2, NE_EXPR, op1,
547 : : limit - 1);
548 : 473934 : if (res2 == NULL_TREE)
549 : : ;
550 : 180397 : else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
551 : : {
552 : : /* If B == 0 then (A & B) != 0 is always false. */
553 : 501 : if (cond_code == NE_EXPR)
554 : 501 : return boolean_false_node;
555 : : /* If B == 0 then (A & B) == 0 is always true. */
556 : 0 : if (cond_code == EQ_EXPR)
557 : 0 : return boolean_true_node;
558 : : }
559 : 179896 : else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
560 : : {
561 : : /* If B != 0 then (A | B) != 0 is always true. */
562 : 672 : if (cond_code == NE_EXPR)
563 : 616 : return boolean_true_node;
564 : : /* If B != 0 then (A | B) == 0 is always false. */
565 : 56 : if (cond_code == EQ_EXPR)
566 : 56 : return boolean_false_node;
567 : : }
568 : :
569 : 472761 : if (res1 != NULL_TREE && res2 != NULL_TREE)
570 : : {
571 : 37927 : if (rhs_code == BIT_AND_EXPR
572 : 37615 : && TYPE_PRECISION (TREE_TYPE (op0)) == 1
573 : 985 : && integer_nonzerop (res1)
574 : 38912 : && integer_nonzerop (res2))
575 : : {
576 : : /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
577 : 985 : if (cond_code == NE_EXPR)
578 : 985 : return boolean_true_node;
579 : : /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
580 : 0 : if (cond_code == EQ_EXPR)
581 : 0 : return boolean_false_node;
582 : : }
583 : :
584 : 36942 : if (rhs_code == BIT_IOR_EXPR
585 : 312 : && integer_zerop (res1)
586 : 37252 : && integer_zerop (res2))
587 : : {
588 : : /* If A == 0 and B == 0 then (A | B) != 0 is false. */
589 : 310 : if (cond_code == NE_EXPR)
590 : 308 : return boolean_false_node;
591 : : /* If A == 0 and B == 0 then (A | B) == 0 is true. */
592 : 2 : if (cond_code == EQ_EXPR)
593 : 2 : return boolean_true_node;
594 : : }
595 : : }
596 : : }
597 : : /* Handle (A CMP B) CMP 0. */
598 : 2680705 : else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
599 : : == tcc_comparison)
600 : : {
601 : 543461 : tree rhs1 = gimple_assign_rhs1 (def_stmt);
602 : 543461 : tree rhs2 = gimple_assign_rhs2 (def_stmt);
603 : :
604 : 543461 : tree_code new_cond = gimple_assign_rhs_code (def_stmt);
605 : 543461 : if (cond_code == EQ_EXPR)
606 : 3531 : new_cond = invert_tree_comparison (new_cond, false);
607 : :
608 : 543461 : tree res
609 : 543461 : = simplify_control_stmt_condition_1 (e, def_stmt,
610 : : rhs1, new_cond, rhs2,
611 : : limit - 1);
612 : 543461 : if (res != NULL_TREE && is_gimple_min_invariant (res))
613 : : return res;
614 : : }
615 : : }
616 : :
617 : 9376439 : gimple_cond_set_code (dummy_cond, cond_code);
618 : 9376439 : gimple_cond_set_lhs (dummy_cond, op0);
619 : 9376439 : gimple_cond_set_rhs (dummy_cond, op1);
620 : :
621 : : /* We absolutely do not care about any type conversions
622 : : we only care about a zero/nonzero value. */
623 : 9376439 : fold_defer_overflow_warnings ();
624 : :
625 : 9376439 : tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
626 : 9376439 : if (res)
627 : 2117520 : while (CONVERT_EXPR_P (res))
628 : 224 : res = TREE_OPERAND (res, 0);
629 : :
630 : 9376439 : fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
631 : : stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
632 : :
633 : : /* If we have not simplified the condition down to an invariant,
634 : : then use the pass specific callback to simplify the condition. */
635 : 9376439 : if (!res
636 : 9376439 : || !is_gimple_min_invariant (res))
637 : 8445045 : res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
638 : :
639 : : return res;
640 : : }
641 : :
642 : : /* Copy debug stmts from DEST's chain of single predecessors up to
643 : : SRC, so that we don't lose the bindings as PHI nodes are introduced
644 : : when DEST gains new predecessors. */
645 : : void
646 : 1374999 : propagate_threaded_block_debug_into (basic_block dest, basic_block src)
647 : : {
648 : 1374999 : if (!MAY_HAVE_DEBUG_BIND_STMTS)
649 : 984114 : return;
650 : :
651 : 1209708 : if (!single_pred_p (dest))
652 : : return;
653 : :
654 : 390885 : gcc_checking_assert (dest != src);
655 : :
656 : 390885 : gimple_stmt_iterator gsi = gsi_after_labels (dest);
657 : 390885 : int i = 0;
658 : 390885 : const int alloc_count = 16; // ?? Should this be a PARAM?
659 : :
660 : : /* Estimate the number of debug vars overridden in the beginning of
661 : : DEST, to tell how many we're going to need to begin with. */
662 : 390885 : for (gimple_stmt_iterator si = gsi;
663 : 1459606 : i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
664 : : {
665 : 1370174 : gimple *stmt = gsi_stmt (si);
666 : 1370174 : if (!is_gimple_debug (stmt))
667 : : break;
668 : 1068721 : if (gimple_debug_nonbind_marker_p (stmt))
669 : 177909 : continue;
670 : 890812 : i++;
671 : : }
672 : :
673 : 390885 : auto_vec<tree, alloc_count> fewvars;
674 : 390885 : hash_set<tree> *vars = NULL;
675 : :
676 : : /* If we're already starting with 3/4 of alloc_count, go for a
677 : : hash_set, otherwise start with an unordered stack-allocated
678 : : VEC. */
679 : 390885 : if (i * 4 > alloc_count * 3)
680 : 24508 : vars = new hash_set<tree>;
681 : :
682 : : /* Now go through the initial debug stmts in DEST again, this time
683 : : actually inserting in VARS or FEWVARS. Don't bother checking for
684 : : duplicates in FEWVARS. */
685 : 1715636 : for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si))
686 : : {
687 : 1648802 : gimple *stmt = gsi_stmt (si);
688 : 1648802 : if (!is_gimple_debug (stmt))
689 : : break;
690 : :
691 : 1324751 : tree var;
692 : :
693 : 1324751 : if (gimple_debug_bind_p (stmt))
694 : 1108211 : var = gimple_debug_bind_get_var (stmt);
695 : 216540 : else if (gimple_debug_source_bind_p (stmt))
696 : 3617 : var = gimple_debug_source_bind_get_var (stmt);
697 : 212923 : else if (gimple_debug_nonbind_marker_p (stmt))
698 : 212923 : continue;
699 : : else
700 : 0 : gcc_unreachable ();
701 : :
702 : 1111828 : if (vars)
703 : 539620 : vars->add (var);
704 : : else
705 : 572208 : fewvars.quick_push (var);
706 : : }
707 : :
708 : : basic_block bb = dest;
709 : :
710 : 401998 : do
711 : : {
712 : 401998 : bb = single_pred (bb);
713 : 401998 : for (gimple_stmt_iterator si = gsi_last_bb (bb);
714 : 6265206 : !gsi_end_p (si); gsi_prev (&si))
715 : : {
716 : 2931604 : gimple *stmt = gsi_stmt (si);
717 : 2931604 : if (!is_gimple_debug (stmt))
718 : 2142446 : continue;
719 : :
720 : 2034904 : tree var;
721 : :
722 : 2034904 : if (gimple_debug_bind_p (stmt))
723 : 1621599 : var = gimple_debug_bind_get_var (stmt);
724 : 413305 : else if (gimple_debug_source_bind_p (stmt))
725 : 6505 : var = gimple_debug_source_bind_get_var (stmt);
726 : 406800 : else if (gimple_debug_nonbind_marker_p (stmt))
727 : 406800 : continue;
728 : : else
729 : 0 : gcc_unreachable ();
730 : :
731 : : /* Discard debug bind overlaps. Unlike stmts from src,
732 : : copied into a new block that will precede BB, debug bind
733 : : stmts in bypassed BBs may actually be discarded if
734 : : they're overwritten by subsequent debug bind stmts. We
735 : : want to copy binds for all modified variables, so that we
736 : : retain a bind to the shared def if there is one, or to a
737 : : newly introduced PHI node if there is one. Our bind will
738 : : end up reset if the value is dead, but that implies the
739 : : variable couldn't have survived, so it's fine. We are
740 : : not actually running the code that performed the binds at
741 : : this point, we're just adding binds so that they survive
742 : : the new confluence, so markers should not be copied. */
743 : 1628104 : if (vars && vars->add (var))
744 : 410194 : continue;
745 : 1217910 : else if (!vars)
746 : : {
747 : 1121871 : int i = fewvars.length ();
748 : 5204216 : while (i--)
749 : 4511097 : if (fewvars[i] == var)
750 : : break;
751 : 1121871 : if (i >= 0)
752 : 428752 : continue;
753 : 693119 : else if (fewvars.length () < (unsigned) alloc_count)
754 : 684471 : fewvars.quick_push (var);
755 : : else
756 : : {
757 : 8648 : vars = new hash_set<tree>;
758 : 155664 : for (i = 0; i < alloc_count; i++)
759 : 138368 : vars->add (fewvars[i]);
760 : 8648 : fewvars.release ();
761 : 8648 : vars->add (var);
762 : : }
763 : : }
764 : :
765 : 789158 : stmt = gimple_copy (stmt);
766 : : /* ??? Should we drop the location of the copy to denote
767 : : they're artificial bindings? */
768 : 789158 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
769 : : }
770 : : }
771 : 811045 : while (bb != src && single_pred_p (bb));
772 : :
773 : 390885 : if (vars)
774 : 33156 : delete vars;
775 : 357729 : else if (fewvars.exists ())
776 : 357729 : fewvars.release ();
777 : 390885 : }
778 : :
779 : : /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
780 : : need not be duplicated as part of the CFG/SSA updating process).
781 : :
782 : : If it is threadable, add it to PATH and VISITED and recurse, ultimately
783 : : returning TRUE from the toplevel call. Otherwise do nothing and
784 : : return false. */
785 : :
786 : : bool
787 : 9529762 : jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
788 : : edge taken_edge,
789 : : bitmap visited)
790 : : {
791 : 9872935 : basic_block bb = taken_edge->dest;
792 : 9872935 : gimple_stmt_iterator gsi;
793 : 9872935 : gimple *stmt;
794 : 9872935 : tree cond;
795 : :
796 : : /* The key property of these blocks is that they need not be duplicated
797 : : when threading. Thus they cannot have visible side effects such
798 : : as PHI nodes. */
799 : 9872935 : if (has_phis_p (bb))
800 : : return false;
801 : :
802 : : /* Skip over DEBUG statements at the start of the block. */
803 : 6201032 : gsi = gsi_start_nondebug_bb (bb);
804 : :
805 : : /* If the block has no statements, but does have a single successor, then
806 : : it's just a forwarding block and we can thread through it trivially.
807 : :
808 : : However, note that just threading through empty blocks with single
809 : : successors is not inherently profitable. For the jump thread to
810 : : be profitable, we must avoid a runtime conditional.
811 : :
812 : : By taking the return value from the recursive call, we get the
813 : : desired effect of returning TRUE when we found a profitable jump
814 : : threading opportunity and FALSE otherwise.
815 : :
816 : : This is particularly important when this routine is called after
817 : : processing a joiner block. Returning TRUE too aggressively in
818 : : that case results in pointless duplication of the joiner block. */
819 : 6201032 : if (gsi_end_p (gsi))
820 : : {
821 : 1437554 : if (single_succ_p (bb))
822 : : {
823 : 1437554 : taken_edge = single_succ_edge (bb);
824 : :
825 : 1437554 : if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
826 : : return false;
827 : :
828 : 343173 : if (!bitmap_bit_p (visited, taken_edge->dest->index))
829 : : {
830 : 343173 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
831 : 343173 : m_state->append_path (taken_edge->dest);
832 : 343173 : bitmap_set_bit (visited, taken_edge->dest->index);
833 : 343173 : return thread_around_empty_blocks (path, taken_edge, visited);
834 : : }
835 : : }
836 : :
837 : : /* We have a block with no statements, but multiple successors? */
838 : 0 : return false;
839 : : }
840 : :
841 : : /* The only real statements this block can have are a control
842 : : flow altering statement. Anything else stops the thread. */
843 : 4763478 : stmt = gsi_stmt (gsi);
844 : 4763478 : if (gimple_code (stmt) != GIMPLE_COND
845 : : && gimple_code (stmt) != GIMPLE_GOTO
846 : : && gimple_code (stmt) != GIMPLE_SWITCH)
847 : : return false;
848 : :
849 : : /* Extract and simplify the condition. */
850 : 391037 : cond = simplify_control_stmt_condition (taken_edge, stmt);
851 : :
852 : : /* If the condition can be statically computed and we have not already
853 : : visited the destination edge, then add the taken edge to our thread
854 : : path. */
855 : 391037 : if (cond != NULL_TREE
856 : 391037 : && (is_gimple_min_invariant (cond)
857 : 219208 : || TREE_CODE (cond) == CASE_LABEL_EXPR))
858 : : {
859 : 73596 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
860 : 16 : taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
861 : : else
862 : 73580 : taken_edge = find_taken_edge (bb, cond);
863 : :
864 : 73596 : if (!taken_edge
865 : 73576 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
866 : : return false;
867 : :
868 : 73527 : if (bitmap_bit_p (visited, taken_edge->dest->index))
869 : : return false;
870 : 73527 : bitmap_set_bit (visited, taken_edge->dest->index);
871 : :
872 : 73527 : m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
873 : 73527 : m_state->append_path (taken_edge->dest);
874 : :
875 : 73527 : thread_around_empty_blocks (path, taken_edge, visited);
876 : 73527 : return true;
877 : : }
878 : :
879 : : return false;
880 : : }
881 : :
882 : : /* We are exiting E->src, see if E->dest ends with a conditional
883 : : jump which has a known value when reached via E.
884 : :
885 : : E->dest can have arbitrary side effects which, if threading is
886 : : successful, will be maintained.
887 : :
888 : : Special care is necessary if E is a back edge in the CFG as we
889 : : may have already recorded equivalences for E->dest into our
890 : : various tables, including the result of the conditional at
891 : : the end of E->dest. Threading opportunities are severely
892 : : limited in that case to avoid short-circuiting the loop
893 : : incorrectly.
894 : :
895 : : Positive return value is success. Zero return value is failure, but
896 : : the block can still be duplicated as a joiner in a jump thread path,
897 : : negative indicates the block should not be duplicated and thus is not
898 : : suitable for a joiner in a jump threading path. */
899 : :
900 : : int
901 : 13899881 : jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
902 : : edge e, bitmap visited)
903 : : {
904 : 13899881 : m_state->register_equivs_edge (e);
905 : :
906 : : /* PHIs create temporary equivalences.
907 : : Note that if we found a PHI that made the block non-threadable, then
908 : : we need to bubble that up to our caller in the same manner we do
909 : : when we prematurely stop processing statements below. */
910 : 13899881 : if (!record_temporary_equivalences_from_phis (e))
911 : : return -1;
912 : :
913 : : /* Now walk each statement recording any context sensitive
914 : : temporary equivalences we can detect. */
915 : 13899881 : gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
916 : :
917 : : /* There's two reasons STMT might be null, and distinguishing
918 : : between them is important.
919 : :
920 : : First the block may not have had any statements. For example, it
921 : : might have some PHIs and unconditionally transfer control elsewhere.
922 : : Such blocks are suitable for jump threading, particularly as a
923 : : joiner block.
924 : :
925 : : The second reason would be if we did not process all the statements
926 : : in the block (because there were too many to make duplicating the
927 : : block profitable. If we did not look at all the statements, then
928 : : we may not have invalidated everything needing invalidation. Thus
929 : : we must signal to our caller that this block is not suitable for
930 : : use as a joiner in a threading path. */
931 : 13899881 : if (!stmt)
932 : : {
933 : : /* First case. The statement simply doesn't have any instructions, but
934 : : does have PHIs. */
935 : 2740163 : if (empty_block_with_phis_p (e->dest))
936 : : return 0;
937 : :
938 : : /* Second case. */
939 : : return -1;
940 : : }
941 : :
942 : : /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
943 : : will be taken. */
944 : 11159718 : if (gimple_code (stmt) == GIMPLE_COND
945 : : || gimple_code (stmt) == GIMPLE_GOTO
946 : : || gimple_code (stmt) == GIMPLE_SWITCH)
947 : : {
948 : 7553854 : tree cond;
949 : :
950 : : /* Extract and simplify the condition. */
951 : 7553854 : cond = simplify_control_stmt_condition (e, stmt);
952 : :
953 : 7553854 : if (!cond)
954 : : return 0;
955 : :
956 : 5360599 : if (is_gimple_min_invariant (cond)
957 : 5360599 : || TREE_CODE (cond) == CASE_LABEL_EXPR)
958 : : {
959 : 862145 : edge taken_edge;
960 : 862145 : if (TREE_CODE (cond) == CASE_LABEL_EXPR)
961 : 90 : taken_edge = find_edge (e->dest,
962 : 90 : label_to_block (cfun, CASE_LABEL (cond)));
963 : : else
964 : 862055 : taken_edge = find_taken_edge (e->dest, cond);
965 : :
966 : 862145 : basic_block dest = (taken_edge ? taken_edge->dest : NULL);
967 : :
968 : : /* DEST could be NULL for a computed jump to an absolute
969 : : address. */
970 : 862099 : if (dest == NULL
971 : 862099 : || dest == e->dest
972 : 862099 : || (taken_edge->flags & EDGE_DFS_BACK) != 0
973 : 1723853 : || bitmap_bit_p (visited, dest->index))
974 : 391 : return 0;
975 : :
976 : : /* Only push the EDGE_START_JUMP_THREAD marker if this is
977 : : first edge on the path. */
978 : 861754 : if (path->length () == 0)
979 : 537436 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
980 : :
981 : 861754 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
982 : 861754 : m_state->append_path (taken_edge->dest);
983 : :
984 : : /* See if we can thread through DEST as well, this helps capture
985 : : secondary effects of threading without having to re-run DOM or
986 : : VRP.
987 : :
988 : : We don't want to thread back to a block we have already
989 : : visited. This may be overly conservative. */
990 : 861754 : bitmap_set_bit (visited, dest->index);
991 : 861754 : bitmap_set_bit (visited, e->dest->index);
992 : 861754 : thread_around_empty_blocks (path, taken_edge, visited);
993 : 861754 : return 1;
994 : : }
995 : : }
996 : : return 0;
997 : : }
998 : :
999 : : /* There are basic blocks look like:
1000 : : <P0>
1001 : : p0 = a CMP b ; or p0 = (INT) (a CMP b)
1002 : : goto <X>;
1003 : :
1004 : : <P1>
1005 : : p1 = c CMP d
1006 : : goto <X>;
1007 : :
1008 : : <X>
1009 : : # phi = PHI <p0 (P0), p1 (P1)>
1010 : : if (phi != 0) goto <Y>; else goto <Z>;
1011 : :
1012 : : Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
1013 : : And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
1014 : :
1015 : : Return true if E is (P0,X) or (P1,X) */
1016 : :
1017 : : bool
1018 : 8226735 : edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
1019 : : {
1020 : : /* See if there is only one stmt which is gcond. */
1021 : 8226735 : gcond *gs;
1022 : 9421647 : if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (e->dest))))
1023 : : return false;
1024 : :
1025 : : /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
1026 : 1206242 : tree cond = gimple_cond_lhs (gs);
1027 : 1206242 : enum tree_code code = gimple_cond_code (gs);
1028 : 1206242 : tree rhs = gimple_cond_rhs (gs);
1029 : 1206242 : if (TREE_CODE (cond) != SSA_NAME
1030 : 1187019 : || (code != NE_EXPR && code != EQ_EXPR)
1031 : 1979913 : || (!integer_onep (rhs) && !integer_zerop (rhs)))
1032 : 680282 : return false;
1033 : 525960 : gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
1034 : 321684 : if (phi == NULL || gimple_bb (phi) != e->dest)
1035 : : return false;
1036 : :
1037 : : /* Check if phi's incoming value is CMP. */
1038 : 239922 : gassign *def;
1039 : 239922 : tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
1040 : 239922 : if (TREE_CODE (value) != SSA_NAME
1041 : 239744 : || !has_single_use (value)
1042 : 374626 : || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
1043 : : return false;
1044 : :
1045 : : /* Or if it is (INT) (a CMP b). */
1046 : 161578 : if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
1047 : : {
1048 : 26152 : value = gimple_assign_rhs1 (def);
1049 : 26152 : if (TREE_CODE (value) != SSA_NAME
1050 : 26152 : || !has_single_use (value)
1051 : 8225117 : || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
1052 : : return false;
1053 : : }
1054 : :
1055 : 147006 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
1056 : : return false;
1057 : :
1058 : : return true;
1059 : : }
1060 : :
1061 : : /* We are exiting E->src, see if E->dest ends with a conditional jump
1062 : : which has a known value when reached via E. If so, thread the
1063 : : edge. */
1064 : :
1065 : : void
1066 : 6351314 : jump_threader::thread_across_edge (edge e)
1067 : : {
1068 : 6351314 : auto_bitmap visited;
1069 : :
1070 : 6351314 : m_state->push (e);
1071 : :
1072 : 6351314 : stmt_count = 0;
1073 : :
1074 : 6351314 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1075 : 6351314 : bitmap_set_bit (visited, e->src->index);
1076 : 6351314 : bitmap_set_bit (visited, e->dest->index);
1077 : :
1078 : 6351314 : int threaded = 0;
1079 : 6351314 : if ((e->flags & EDGE_DFS_BACK) == 0)
1080 : 5348828 : threaded = thread_through_normal_block (path, e, visited);
1081 : :
1082 : 5348828 : if (threaded > 0)
1083 : : {
1084 : 537436 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1085 : : e->dest);
1086 : 537436 : m_registry->register_jump_thread (path);
1087 : 537436 : m_state->pop ();
1088 : 537436 : return;
1089 : : }
1090 : :
1091 : 5813878 : gcc_checking_assert (path->length () == 0);
1092 : 5813878 : path->release ();
1093 : :
1094 : 5813878 : if (threaded < 0)
1095 : : {
1096 : : /* The target block was deemed too big to duplicate. Just quit
1097 : : now rather than trying to use the block as a joiner in a jump
1098 : : threading path.
1099 : :
1100 : : This prevents unnecessary code growth, but more importantly if we
1101 : : do not look at all the statements in the block, then we may have
1102 : : missed some invalidations if we had traversed a backedge! */
1103 : 155083 : m_state->pop ();
1104 : 155083 : return;
1105 : : }
1106 : :
1107 : : /* We were unable to determine what out edge from E->dest is taken. However,
1108 : : we might still be able to thread through successors of E->dest. This
1109 : : often occurs when E->dest is a joiner block which then fans back out
1110 : : based on redundant tests.
1111 : :
1112 : : If so, we'll copy E->dest and redirect the appropriate predecessor to
1113 : : the copy. Within the copy of E->dest, we'll thread one or more edges
1114 : : to points deeper in the CFG.
1115 : :
1116 : : This is a stopgap until we have a more structured approach to path
1117 : : isolation. */
1118 : 5658795 : {
1119 : 5658795 : edge taken_edge;
1120 : 5658795 : edge_iterator ei;
1121 : 5658795 : bool found;
1122 : :
1123 : : /* If E->dest has abnormal outgoing edges, then there's no guarantee
1124 : : we can safely redirect any of the edges. Just punt those cases. */
1125 : 16302398 : FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1126 : 10644038 : if (taken_edge->flags & EDGE_COMPLEX)
1127 : : {
1128 : 435 : m_state->pop ();
1129 : 435 : return;
1130 : : }
1131 : :
1132 : : /* Look at each successor of E->dest to see if we can thread through it. */
1133 : 16301951 : FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1134 : : {
1135 : 10643591 : if ((e->flags & EDGE_DFS_BACK) != 0
1136 : 8651109 : || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1137 : 2049110 : continue;
1138 : :
1139 : 8594481 : m_state->push (taken_edge);
1140 : :
1141 : : /* Avoid threading to any block we have already visited. */
1142 : 8594481 : bitmap_clear (visited);
1143 : 8594481 : bitmap_set_bit (visited, e->src->index);
1144 : 8594481 : bitmap_set_bit (visited, e->dest->index);
1145 : 8594481 : bitmap_set_bit (visited, taken_edge->dest->index);
1146 : :
1147 : 8594481 : vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1148 : 8594481 : m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
1149 : 8594481 : m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1150 : :
1151 : 8594481 : found = thread_around_empty_blocks (path, taken_edge, visited);
1152 : :
1153 : 8594481 : if (!found)
1154 : 8551053 : found = thread_through_normal_block (path,
1155 : 8551053 : path->last ()->e, visited) > 0;
1156 : :
1157 : : /* If we were able to thread through a successor of E->dest, then
1158 : : record the jump threading opportunity. */
1159 : 8551053 : if (found
1160 : 8551053 : || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1161 : : {
1162 : 405900 : if (taken_edge->dest != path->last ()->e->dest)
1163 : 368307 : propagate_threaded_block_debug_into (path->last ()->e->dest,
1164 : : taken_edge->dest);
1165 : 405900 : m_registry->register_jump_thread (path);
1166 : : }
1167 : : else
1168 : 8188581 : path->release ();
1169 : :
1170 : 8594481 : m_state->pop ();
1171 : : }
1172 : : }
1173 : :
1174 : 5658360 : m_state->pop ();
1175 : 6351314 : }
1176 : :
1177 : : /* Return TRUE if BB has a single successor to a block with multiple
1178 : : incoming and outgoing edges. */
1179 : :
1180 : : bool
1181 : 21050605 : single_succ_to_potentially_threadable_block (basic_block bb)
1182 : : {
1183 : 21050605 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1184 : 21050605 : return (single_succ_p (bb)
1185 : 10720013 : && (single_succ_edge (bb)->flags & flags) == 0
1186 : 31303931 : && potentially_threadable_block (single_succ (bb)));
1187 : : }
1188 : :
1189 : : /* Examine the outgoing edges from BB and conditionally
1190 : : try to thread them. */
1191 : :
1192 : : void
1193 : 21051845 : jump_threader::thread_outgoing_edges (basic_block bb)
1194 : : {
1195 : 21051845 : int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1196 : :
1197 : 21051845 : if (!flag_thread_jumps)
1198 : : return;
1199 : :
1200 : : /* If we have an outgoing edge to a block with multiple incoming and
1201 : : outgoing edges, then we may be able to thread the edge, i.e., we
1202 : : may be able to statically determine which of the outgoing edges
1203 : : will be traversed when the incoming edge from BB is traversed. */
1204 : 21050605 : if (single_succ_to_potentially_threadable_block (bb))
1205 : 3873666 : thread_across_edge (single_succ_edge (bb));
1206 : 34353878 : else if (safe_is_a <gcond *> (*gsi_last_bb (bb))
1207 : 7767619 : && EDGE_COUNT (bb->succs) == 2
1208 : 7767619 : && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1209 : 22710481 : && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1210 : : {
1211 : 7767619 : edge true_edge, false_edge;
1212 : :
1213 : 7767619 : extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1214 : :
1215 : : /* Only try to thread the edge if it reaches a target block with
1216 : : more than one predecessor and more than one successor. */
1217 : 7767619 : if (potentially_threadable_block (true_edge->dest))
1218 : 875062 : thread_across_edge (true_edge);
1219 : :
1220 : : /* Similarly for the ELSE arm. */
1221 : 7767619 : if (potentially_threadable_block (false_edge->dest))
1222 : 1602586 : thread_across_edge (false_edge);
1223 : : }
1224 : : }
1225 : :
1226 : : // Marker to keep track of the start of the current path.
1227 : : const basic_block jt_state::BB_MARKER = (basic_block) -1;
1228 : :
1229 : : // Record that E is being crossed.
1230 : :
1231 : : void
1232 : 14945795 : jt_state::push (edge e)
1233 : : {
1234 : 14945795 : m_blocks.safe_push (BB_MARKER);
1235 : 14945795 : if (m_blocks.length () == 1)
1236 : 6351314 : m_blocks.safe_push (e->src);
1237 : 14945795 : m_blocks.safe_push (e->dest);
1238 : 14945795 : }
1239 : :
1240 : : // Pop to the last pushed state.
1241 : :
1242 : : void
1243 : 14945795 : jt_state::pop ()
1244 : : {
1245 : 14945795 : if (!m_blocks.is_empty ())
1246 : : {
1247 : 37521358 : while (m_blocks.last () != BB_MARKER)
1248 : 22575563 : m_blocks.pop ();
1249 : : // Pop marker.
1250 : 14945795 : m_blocks.pop ();
1251 : : }
1252 : 14945795 : }
1253 : :
1254 : : // Add BB to the list of blocks seen.
1255 : :
1256 : : void
1257 : 1278454 : jt_state::append_path (basic_block bb)
1258 : : {
1259 : 1278454 : gcc_checking_assert (!m_blocks.is_empty ());
1260 : 1278454 : m_blocks.safe_push (bb);
1261 : 1278454 : }
1262 : :
1263 : : void
1264 : 0 : jt_state::dump (FILE *out)
1265 : : {
1266 : 0 : if (!m_blocks.is_empty ())
1267 : : {
1268 : 0 : auto_vec<basic_block> path;
1269 : 0 : get_path (path);
1270 : 0 : dump_ranger (out, path);
1271 : 0 : }
1272 : 0 : }
1273 : :
1274 : : void
1275 : 0 : jt_state::debug ()
1276 : : {
1277 : 0 : push_dump_file save (stderr, TDF_DETAILS);
1278 : 0 : dump (stderr);
1279 : 0 : }
1280 : :
1281 : : // Convert the current path in jt_state into a path suitable for the
1282 : : // path solver. Return the resulting path in PATH.
1283 : :
1284 : : void
1285 : 8310747 : jt_state::get_path (vec<basic_block> &path)
1286 : : {
1287 : 8310747 : path.truncate (0);
1288 : :
1289 : 49179608 : for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
1290 : : {
1291 : 32558114 : basic_block bb = m_blocks[i];
1292 : :
1293 : 32558114 : if (bb != BB_MARKER)
1294 : 20554356 : path.safe_push (bb);
1295 : : }
1296 : 8310747 : }
1297 : :
1298 : : // Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
1299 : : // update the value range associated with DST.
1300 : :
1301 : : void
1302 : 0 : jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
1303 : : tree src ATTRIBUTE_UNUSED,
1304 : : bool update_range ATTRIBUTE_UNUSED)
1305 : : {
1306 : 0 : }
1307 : :
1308 : : // Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
1309 : : // this is a temporary equivalence and should be recorded into the
1310 : : // unwind table, instead of the global table.
1311 : :
1312 : : void
1313 : 41717737 : jt_state::record_ranges_from_stmt (gimple *,
1314 : : bool temporary ATTRIBUTE_UNUSED)
1315 : : {
1316 : 41717737 : }
1317 : :
1318 : : // Record any equivalences created by traversing E.
1319 : :
1320 : : void
1321 : 0 : jt_state::register_equivs_edge (edge)
1322 : : {
1323 : 0 : }
1324 : :
1325 : : void
1326 : 22722803 : jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
1327 : : jt_simplifier *simplifier)
1328 : : {
1329 : : /* At this point we have a statement which assigns an RHS to an
1330 : : SSA_VAR on the LHS. We want to try and simplify this statement
1331 : : to expose more context sensitive equivalences which in turn may
1332 : : allow us to simplify the condition at the end of the loop.
1333 : :
1334 : : Handle simple copy operations. */
1335 : 22722803 : tree cached_lhs = NULL;
1336 : 22722803 : if (gimple_assign_single_p (stmt)
1337 : 22722803 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
1338 : : cached_lhs = gimple_assign_rhs1 (stmt);
1339 : : else
1340 : : {
1341 : : /* A statement that is not a trivial copy.
1342 : : Try to fold the new expression. Inserting the
1343 : : expression into the hash table is unlikely to help. */
1344 : : /* ??? The DOM callback below can be changed to setting
1345 : : the mprts_hook around the call to thread_across_edge,
1346 : : avoiding the use substitution. */
1347 : 21890861 : cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
1348 : : threadedge_valueize);
1349 : 21890861 : if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
1350 : 21890861 : && (!cached_lhs
1351 : 2588464 : || (TREE_CODE (cached_lhs) != SSA_NAME
1352 : 2266547 : && !is_gimple_min_invariant (cached_lhs))))
1353 : : {
1354 : : /* We're going to temporarily copy propagate the operands
1355 : : and see if that allows us to simplify this statement. */
1356 : 19431328 : tree *copy;
1357 : 19431328 : ssa_op_iter iter;
1358 : 19431328 : use_operand_p use_p;
1359 : 19431328 : unsigned int num, i = 0;
1360 : :
1361 : 19431328 : num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
1362 : 19431328 : copy = XALLOCAVEC (tree, num);
1363 : :
1364 : : /* Make a copy of the uses & vuses into USES_COPY, then cprop into
1365 : : the operands. */
1366 : 47757662 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1367 : : {
1368 : 28326334 : tree tmp = NULL;
1369 : 28326334 : tree use = USE_FROM_PTR (use_p);
1370 : :
1371 : 28326334 : copy[i++] = use;
1372 : 28326334 : if (TREE_CODE (use) == SSA_NAME)
1373 : 54461621 : tmp = SSA_NAME_VALUE (use);
1374 : 26135287 : if (tmp)
1375 : 7079336 : SET_USE (use_p, tmp);
1376 : : }
1377 : :
1378 : : /* Do not pass state to avoid calling the ranger with the
1379 : : temporarily altered IL. */
1380 : 19431328 : cached_lhs = simplifier->simplify (stmt, stmt, bb, /*state=*/NULL);
1381 : :
1382 : : /* Restore the statement's original uses/defs. */
1383 : 19431328 : i = 0;
1384 : 47757662 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1385 : 28326334 : SET_USE (use_p, copy[i++]);
1386 : : }
1387 : : }
1388 : :
1389 : : /* Record the context sensitive equivalence if we were able
1390 : : to simplify this statement. */
1391 : 22722803 : if (cached_lhs
1392 : 22722803 : && (TREE_CODE (cached_lhs) == SSA_NAME
1393 : 2108112 : || is_gimple_min_invariant (cached_lhs)))
1394 : 3645543 : register_equiv (gimple_get_lhs (stmt), cached_lhs,
1395 : : /*update_range=*/false);
1396 : 22722803 : }
1397 : :
1398 : : // Hybrid threader implementation.
1399 : :
1400 : 1951518 : hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
1401 : 1951518 : path_range_query *q)
1402 : : {
1403 : 1951518 : m_ranger = r;
1404 : 1951518 : m_query = q;
1405 : 1951518 : }
1406 : :
1407 : : tree
1408 : 8310747 : hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
1409 : : jt_state *state)
1410 : : {
1411 : 8310747 : auto_bitmap dependencies;
1412 : 8310747 : auto_vec<basic_block> path;
1413 : :
1414 : 8310747 : state->get_path (path);
1415 : 8310747 : compute_exit_dependencies (dependencies, path, stmt);
1416 : 8310747 : m_query->reset_path (path, dependencies);
1417 : :
1418 : 8310747 : if (gimple_code (stmt) == GIMPLE_COND
1419 : 8310747 : || gimple_code (stmt) == GIMPLE_ASSIGN)
1420 : : {
1421 : 8286116 : Value_Range r (gimple_range_type (stmt));
1422 : 8286116 : tree ret;
1423 : 16572232 : if (m_query->range_of_stmt (r, stmt) && r.singleton_p (&ret))
1424 : 130203 : return ret;
1425 : 8286116 : }
1426 : 24631 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1427 : : {
1428 : 24409 : int_range_max r;
1429 : 24409 : gswitch *switch_stmt = dyn_cast <gswitch *> (stmt);
1430 : 24409 : tree index = gimple_switch_index (switch_stmt);
1431 : 24409 : if (m_query->range_of_expr (r, index, stmt))
1432 : 24409 : return find_case_label_range (switch_stmt, &r);
1433 : 24409 : }
1434 : : return NULL;
1435 : 8310747 : }
1436 : :
1437 : : // Calculate the set of exit dependencies for a path and statement to
1438 : : // be simplified. This is different than the
1439 : : // compute_exit_dependencies in the path solver because the forward
1440 : : // threader asks questions about statements not necessarily in the
1441 : : // path. Using the default compute_exit_dependencies in the path
1442 : : // solver gets noticeably less threads.
1443 : :
1444 : : void
1445 : 8310747 : hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies,
1446 : : const vec<basic_block> &path,
1447 : : gimple *stmt)
1448 : : {
1449 : 8310747 : gori_compute &gori = m_ranger->gori ();
1450 : :
1451 : : // Start with the imports to the final conditional.
1452 : 8310747 : bitmap_copy (dependencies, gori.imports (path[0]));
1453 : :
1454 : : // Add any other interesting operands we may have missed.
1455 : 8310747 : if (gimple_bb (stmt) != path[0])
1456 : : {
1457 : 41430580 : for (unsigned i = 0; i < gimple_num_ops (stmt); ++i)
1458 : : {
1459 : 33144464 : tree op = gimple_op (stmt, i);
1460 : 33144464 : if (op
1461 : 16572232 : && TREE_CODE (op) == SSA_NAME
1462 : 43255964 : && Value_Range::supports_type_p (TREE_TYPE (op)))
1463 : 10093859 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (op));
1464 : : }
1465 : : }
1466 : 8310747 : }
|