1/* SSA Jump Threading
2 Copyright (C) 2005-2023 Free Software Foundation, Inc.
3 Contributed by Jeff Law <law@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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. */
47static int stmt_count;
48
49/* Array to record value-handles per SSA_NAME. */
50vec<tree> ssa_name_values;
51
52/* Set the value for the SSA name NAME to VALUE. */
53
54void
55set_ssa_name_value (tree name, tree value)
56{
57 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
58 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1, exact: true);
59 if (value && TREE_OVERFLOW_P (value))
60 value = drop_tree_overflow (value);
61 ssa_name_values[SSA_NAME_VERSION (name)] = value;
62}
63
64jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
65{
66 /* Initialize the per SSA_NAME value-handles array. */
67 gcc_assert (!ssa_name_values.exists ());
68 ssa_name_values.create (num_ssa_names);
69
70 dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
71 integer_zero_node, NULL, NULL);
72
73 m_registry = new fwd_jt_path_registry ();
74 m_simplifier = simplifier;
75 m_state = state;
76}
77
78jump_threader::~jump_threader (void)
79{
80 ssa_name_values.release ();
81 ggc_free (dummy_cond);
82 delete m_registry;
83}
84
85void
86jump_threader::remove_jump_threads_including (edge_def *e)
87{
88 m_registry->remove_jump_threads_including (e);
89}
90
91bool
92jump_threader::thread_through_all_blocks (bool may_peel_loop_headers)
93{
94 return m_registry->thread_through_all_blocks (peel_loop_headers: may_peel_loop_headers);
95}
96
97static inline bool
98has_phis_p (basic_block bb)
99{
100 return !gsi_end_p (i: gsi_start_phis (bb));
101}
102
103/* Return TRUE for a block with PHIs but no statements. */
104
105static bool
106empty_block_with_phis_p (basic_block bb)
107{
108 return gsi_end_p (i: 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
114static bool
115potentially_threadable_block (basic_block bb)
116{
117 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 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 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 gsi = gsi_last_bb (bb);
135 if (gsi_end_p (i: gsi)
136 || ! gsi_stmt (i: gsi)
137 || (gimple_code (g: gsi_stmt (i: gsi)) != GIMPLE_COND
138 && gimple_code (g: gsi_stmt (i: gsi)) != GIMPLE_GOTO
139 && gimple_code (g: gsi_stmt (i: 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
151bool
152jump_threader::record_temporary_equivalences_from_phis (edge e)
153{
154 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 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
160 {
161 gphi *phi = gsi.phi ();
162 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
163 tree dst = gimple_phi_result (gs: 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 if (src != dst
169 && TREE_CODE (src) == SSA_NAME
170 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
171 && 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 if (!virtual_operand_p (op: dst))
177 stmt_count++;
178
179 m_state->register_equiv (dest: dst, src, /*update_range=*/true);
180 }
181 return true;
182}
183
184/* Valueize hook for gimple_fold_stmt_to_constant_1. */
185
186static tree
187threadedge_valueize (tree t)
188{
189 if (TREE_CODE (t) == SSA_NAME)
190 {
191 tree tem = SSA_NAME_VALUE (t);
192 if (tem)
193 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
215gimple *
216jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
217{
218 gimple *stmt = NULL;
219 gimple_stmt_iterator gsi;
220 int max_stmt_count;
221
222 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 for (gsi = gsi_start_bb (bb: e->dest); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
229 {
230 stmt = gsi_stmt (i: gsi);
231
232 /* Ignore empty statements and labels. */
233 if (gimple_code (g: stmt) == GIMPLE_NOP
234 || gimple_code (g: stmt) == GIMPLE_LABEL
235 || is_gimple_debug (gs: stmt))
236 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 if (gimple_code (g: stmt) == GIMPLE_ASM
242 && gimple_asm_volatile_p (asm_stmt: as_a <gasm *> (p: stmt)))
243 return NULL;
244
245 /* If the statement is a unique builtin, we cannot thread
246 through here. */
247 if (gimple_code (g: stmt) == GIMPLE_CALL
248 && gimple_call_internal_p (gs: stmt)
249 && gimple_call_internal_unique_p (gs: 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 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 stmt_count++;
261 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 if (max_stmt_count
267 == param_max_jump_thread_duplication_stmts)
268 {
269 max_stmt_count += estimate_threading_killed_stmts (e->dest);
270 if (dump_file)
271 fprintf (stream: dump_file, format: "threading bb %i up to %i stmts\n",
272 e->dest->index, max_stmt_count);
273 }
274 /* If we're still past the limit, we're done. */
275 if (stmt_count > max_stmt_count)
276 return NULL;
277 }
278
279 m_state->record_ranges_from_stmt (stmt, temporary: 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 if ((gimple_code (g: stmt) != GIMPLE_ASSIGN
285 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
286 && (gimple_code (g: stmt) != GIMPLE_CALL
287 || gimple_call_lhs (gs: stmt) == NULL_TREE
288 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
289 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 if (is_gimple_call (gs: stmt))
317 {
318 tree fndecl = gimple_call_fndecl (gs: stmt);
319 if (fndecl
320 && fndecl_built_in_p (node: fndecl, klass: BUILT_IN_NORMAL)
321 && (DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_OBJECT_SIZE
322 || DECL_FUNCTION_CODE (decl: fndecl) == BUILT_IN_CONSTANT_P))
323 continue;
324 }
325
326 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
340tree
341jump_threader::simplify_control_stmt_condition (edge e, gimple *stmt)
342{
343 tree cond, cached_lhs;
344 enum gimple_code code = gimple_code (g: stmt);
345
346 /* For comparisons, we have to update both operands, then try
347 to simplify the comparison. */
348 if (code == GIMPLE_COND)
349 {
350 tree op0, op1;
351 enum tree_code cond_code;
352
353 op0 = gimple_cond_lhs (gs: stmt);
354 op1 = gimple_cond_rhs (gs: stmt);
355 cond_code = gimple_cond_code (gs: stmt);
356
357 /* Get the current value of both operands. */
358 if (TREE_CODE (op0) == SSA_NAME)
359 {
360 for (int i = 0; i < 2; i++)
361 {
362 if (TREE_CODE (op0) == SSA_NAME
363 && SSA_NAME_VALUE (op0))
364 op0 = SSA_NAME_VALUE (op0);
365 else
366 break;
367 }
368 }
369
370 if (TREE_CODE (op1) == SSA_NAME)
371 {
372 for (int i = 0; i < 2; i++)
373 {
374 if (TREE_CODE (op1) == SSA_NAME
375 && SSA_NAME_VALUE (op1))
376 op1 = SSA_NAME_VALUE (op1);
377 else
378 break;
379 }
380 }
381
382 const unsigned recursion_limit = 4;
383
384 cached_lhs
385 = simplify_control_stmt_condition_1 (e, stmt, op0, cond_code, op1,
386 limit: 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 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 tree op0 = gimple_cond_lhs (gs: stmt);
400 tree op1 = gimple_cond_rhs (gs: stmt);
401
402 if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
403 || POINTER_TYPE_P (TREE_TYPE (op0)))
404 && TREE_CODE (op0) == SSA_NAME
405 && TREE_CODE (op1) == INTEGER_CST)
406 return op0;
407 }
408
409 return cached_lhs;
410 }
411
412 if (code == GIMPLE_SWITCH)
413 cond = gimple_switch_index (gs: as_a <gswitch *> (p: stmt));
414 else if (code == GIMPLE_GOTO)
415 cond = gimple_goto_dest (gs: stmt);
416 else
417 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 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 for (int i = 0; i < 2; i++)
434 {
435 if (TREE_CODE (cached_lhs) == SSA_NAME
436 && SSA_NAME_VALUE (cached_lhs))
437 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 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
446 {
447 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 gswitch *dummy_switch = as_a<gswitch *> (p: gimple_copy (stmt));
454 gimple_switch_set_index (gs: dummy_switch, index: cached_lhs);
455 cached_lhs = m_simplifier->simplify (dummy_switch, stmt, e->src,
456 m_state);
457 ggc_free (dummy_switch);
458 }
459 else
460 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 if (!cached_lhs)
467 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
477tree
478jump_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 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 if (tree_swap_operands_p (op0, op1))
494 {
495 cond_code = swap_tree_comparison (cond_code);
496 std::swap (a&: op0, b&: 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 if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
504 && TREE_CODE (op0) == SSA_NAME
505 && integer_zerop (op1))
506 {
507 gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
508 if (gimple_code (g: def_stmt) != GIMPLE_ASSIGN)
509 ;
510 else if (gimple_assign_rhs_code (gs: def_stmt) == BIT_AND_EXPR
511 || gimple_assign_rhs_code (gs: def_stmt) == BIT_IOR_EXPR)
512 {
513 enum tree_code rhs_code = gimple_assign_rhs_code (gs: def_stmt);
514 const tree rhs1 = gimple_assign_rhs1 (gs: def_stmt);
515 const tree rhs2 = gimple_assign_rhs2 (gs: def_stmt);
516
517 /* Is A != 0 ? */
518 const tree res1
519 = simplify_control_stmt_condition_1 (e, stmt: def_stmt,
520 op0: rhs1, cond_code: NE_EXPR, op1,
521 limit: limit - 1);
522 if (res1 == NULL_TREE)
523 ;
524 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1))
525 {
526 /* If A == 0 then (A & B) != 0 is always false. */
527 if (cond_code == NE_EXPR)
528 return boolean_false_node;
529 /* If A == 0 then (A & B) == 0 is always true. */
530 if (cond_code == EQ_EXPR)
531 return boolean_true_node;
532 }
533 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1))
534 {
535 /* If A != 0 then (A | B) != 0 is always true. */
536 if (cond_code == NE_EXPR)
537 return boolean_true_node;
538 /* If A != 0 then (A | B) == 0 is always false. */
539 if (cond_code == EQ_EXPR)
540 return boolean_false_node;
541 }
542
543 /* Is B != 0 ? */
544 const tree res2
545 = simplify_control_stmt_condition_1 (e, stmt: def_stmt,
546 op0: rhs2, cond_code: NE_EXPR, op1,
547 limit: limit - 1);
548 if (res2 == NULL_TREE)
549 ;
550 else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2))
551 {
552 /* If B == 0 then (A & B) != 0 is always false. */
553 if (cond_code == NE_EXPR)
554 return boolean_false_node;
555 /* If B == 0 then (A & B) == 0 is always true. */
556 if (cond_code == EQ_EXPR)
557 return boolean_true_node;
558 }
559 else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2))
560 {
561 /* If B != 0 then (A | B) != 0 is always true. */
562 if (cond_code == NE_EXPR)
563 return boolean_true_node;
564 /* If B != 0 then (A | B) == 0 is always false. */
565 if (cond_code == EQ_EXPR)
566 return boolean_false_node;
567 }
568
569 if (res1 != NULL_TREE && res2 != NULL_TREE)
570 {
571 if (rhs_code == BIT_AND_EXPR
572 && TYPE_PRECISION (TREE_TYPE (op0)) == 1
573 && integer_nonzerop (res1)
574 && integer_nonzerop (res2))
575 {
576 /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */
577 if (cond_code == NE_EXPR)
578 return boolean_true_node;
579 /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
580 if (cond_code == EQ_EXPR)
581 return boolean_false_node;
582 }
583
584 if (rhs_code == BIT_IOR_EXPR
585 && integer_zerop (res1)
586 && integer_zerop (res2))
587 {
588 /* If A == 0 and B == 0 then (A | B) != 0 is false. */
589 if (cond_code == NE_EXPR)
590 return boolean_false_node;
591 /* If A == 0 and B == 0 then (A | B) == 0 is true. */
592 if (cond_code == EQ_EXPR)
593 return boolean_true_node;
594 }
595 }
596 }
597 /* Handle (A CMP B) CMP 0. */
598 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
599 == tcc_comparison)
600 {
601 tree rhs1 = gimple_assign_rhs1 (gs: def_stmt);
602 tree rhs2 = gimple_assign_rhs2 (gs: def_stmt);
603
604 tree_code new_cond = gimple_assign_rhs_code (gs: def_stmt);
605 if (cond_code == EQ_EXPR)
606 new_cond = invert_tree_comparison (new_cond, false);
607
608 tree res
609 = simplify_control_stmt_condition_1 (e, stmt: def_stmt,
610 op0: rhs1, cond_code: new_cond, op1: rhs2,
611 limit: limit - 1);
612 if (res != NULL_TREE && is_gimple_min_invariant (res))
613 return res;
614 }
615 }
616
617 gimple_cond_set_code (gs: dummy_cond, code: cond_code);
618 gimple_cond_set_lhs (gs: dummy_cond, lhs: op0);
619 gimple_cond_set_rhs (gs: dummy_cond, rhs: op1);
620
621 /* We absolutely do not care about any type conversions
622 we only care about a zero/nonzero value. */
623 fold_defer_overflow_warnings ();
624
625 tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
626 if (res)
627 while (CONVERT_EXPR_P (res))
628 res = TREE_OPERAND (res, 0);
629
630 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 if (!res
636 || !is_gimple_min_invariant (res))
637 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. */
645void
646propagate_threaded_block_debug_into (basic_block dest, basic_block src)
647{
648 if (!MAY_HAVE_DEBUG_BIND_STMTS)
649 return;
650
651 if (!single_pred_p (bb: dest))
652 return;
653
654 gcc_checking_assert (dest != src);
655
656 gimple_stmt_iterator gsi = gsi_after_labels (bb: dest);
657 int i = 0;
658 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 for (gimple_stmt_iterator si = gsi;
663 i * 4 <= alloc_count * 3 && !gsi_end_p (i: si); gsi_next (i: &si))
664 {
665 gimple *stmt = gsi_stmt (i: si);
666 if (!is_gimple_debug (gs: stmt))
667 break;
668 if (gimple_debug_nonbind_marker_p (s: stmt))
669 continue;
670 i++;
671 }
672
673 auto_vec<tree, alloc_count> fewvars;
674 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 if (i * 4 > alloc_count * 3)
680 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 for (gimple_stmt_iterator si = gsi; !gsi_end_p (i: si); gsi_next (i: &si))
686 {
687 gimple *stmt = gsi_stmt (i: si);
688 if (!is_gimple_debug (gs: stmt))
689 break;
690
691 tree var;
692
693 if (gimple_debug_bind_p (s: stmt))
694 var = gimple_debug_bind_get_var (dbg: stmt);
695 else if (gimple_debug_source_bind_p (s: stmt))
696 var = gimple_debug_source_bind_get_var (dbg: stmt);
697 else if (gimple_debug_nonbind_marker_p (s: stmt))
698 continue;
699 else
700 gcc_unreachable ();
701
702 if (vars)
703 vars->add (k: var);
704 else
705 fewvars.quick_push (obj: var);
706 }
707
708 basic_block bb = dest;
709
710 do
711 {
712 bb = single_pred (bb);
713 for (gimple_stmt_iterator si = gsi_last_bb (bb);
714 !gsi_end_p (i: si); gsi_prev (i: &si))
715 {
716 gimple *stmt = gsi_stmt (i: si);
717 if (!is_gimple_debug (gs: stmt))
718 continue;
719
720 tree var;
721
722 if (gimple_debug_bind_p (s: stmt))
723 var = gimple_debug_bind_get_var (dbg: stmt);
724 else if (gimple_debug_source_bind_p (s: stmt))
725 var = gimple_debug_source_bind_get_var (dbg: stmt);
726 else if (gimple_debug_nonbind_marker_p (s: stmt))
727 continue;
728 else
729 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 if (vars && vars->add (k: var))
744 continue;
745 else if (!vars)
746 {
747 int i = fewvars.length ();
748 while (i--)
749 if (fewvars[i] == var)
750 break;
751 if (i >= 0)
752 continue;
753 else if (fewvars.length () < (unsigned) alloc_count)
754 fewvars.quick_push (obj: var);
755 else
756 {
757 vars = new hash_set<tree>;
758 for (i = 0; i < alloc_count; i++)
759 vars->add (k: fewvars[i]);
760 fewvars.release ();
761 vars->add (k: var);
762 }
763 }
764
765 stmt = gimple_copy (stmt);
766 /* ??? Should we drop the location of the copy to denote
767 they're artificial bindings? */
768 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
769 }
770 }
771 while (bb != src && single_pred_p (bb));
772
773 if (vars)
774 delete vars;
775 else if (fewvars.exists ())
776 fewvars.release ();
777}
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
786bool
787jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
788 edge taken_edge,
789 bitmap visited)
790{
791 basic_block bb = taken_edge->dest;
792 gimple_stmt_iterator gsi;
793 gimple *stmt;
794 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 if (has_phis_p (bb))
800 return false;
801
802 /* Skip over DEBUG statements at the start of the block. */
803 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 if (gsi_end_p (i: gsi))
820 {
821 if (single_succ_p (bb))
822 {
823 taken_edge = single_succ_edge (bb);
824
825 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
826 return false;
827
828 if (!bitmap_bit_p (visited, taken_edge->dest->index))
829 {
830 m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
831 m_state->append_path (taken_edge->dest);
832 bitmap_set_bit (visited, taken_edge->dest->index);
833 return thread_around_empty_blocks (path, taken_edge, visited);
834 }
835 }
836
837 /* We have a block with no statements, but multiple successors? */
838 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 stmt = gsi_stmt (i: gsi);
844 if (gimple_code (g: stmt) != GIMPLE_COND
845 && gimple_code (g: stmt) != GIMPLE_GOTO
846 && gimple_code (g: stmt) != GIMPLE_SWITCH)
847 return false;
848
849 /* Extract and simplify the condition. */
850 cond = simplify_control_stmt_condition (e: 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 if (cond != NULL_TREE
856 && (is_gimple_min_invariant (cond)
857 || TREE_CODE (cond) == CASE_LABEL_EXPR))
858 {
859 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
860 taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
861 else
862 taken_edge = find_taken_edge (bb, cond);
863
864 if (!taken_edge
865 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
866 return false;
867
868 if (bitmap_bit_p (visited, taken_edge->dest->index))
869 return false;
870 bitmap_set_bit (visited, taken_edge->dest->index);
871
872 m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
873 m_state->append_path (taken_edge->dest);
874
875 thread_around_empty_blocks (path, taken_edge, visited);
876 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
900int
901jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
902 edge e, bitmap visited)
903{
904 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 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 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 if (!stmt)
932 {
933 /* First case. The statement simply doesn't have any instructions, but
934 does have PHIs. */
935 if (empty_block_with_phis_p (bb: 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 if (gimple_code (g: stmt) == GIMPLE_COND
945 || gimple_code (g: stmt) == GIMPLE_GOTO
946 || gimple_code (g: stmt) == GIMPLE_SWITCH)
947 {
948 tree cond;
949
950 /* Extract and simplify the condition. */
951 cond = simplify_control_stmt_condition (e, stmt);
952
953 if (!cond)
954 return 0;
955
956 if (is_gimple_min_invariant (cond)
957 || TREE_CODE (cond) == CASE_LABEL_EXPR)
958 {
959 edge taken_edge;
960 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
961 taken_edge = find_edge (e->dest,
962 label_to_block (cfun, CASE_LABEL (cond)));
963 else
964 taken_edge = find_taken_edge (e->dest, cond);
965
966 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 if (dest == NULL
971 || dest == e->dest
972 || (taken_edge->flags & EDGE_DFS_BACK) != 0
973 || bitmap_bit_p (visited, dest->index))
974 return 0;
975
976 /* Only push the EDGE_START_JUMP_THREAD marker if this is
977 first edge on the path. */
978 if (path->length () == 0)
979 m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
980
981 m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
982 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 bitmap_set_bit (visited, dest->index);
991 bitmap_set_bit (visited, e->dest->index);
992 thread_around_empty_blocks (path, taken_edge, visited);
993 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
1017bool
1018edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
1019{
1020 /* See if there is only one stmt which is gcond. */
1021 gcond *gs;
1022 if (!(gs = safe_dyn_cast<gcond *> (p: 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 tree cond = gimple_cond_lhs (gs);
1027 enum tree_code code = gimple_cond_code (gs);
1028 tree rhs = gimple_cond_rhs (gs);
1029 if (TREE_CODE (cond) != SSA_NAME
1030 || (code != NE_EXPR && code != EQ_EXPR)
1031 || (!integer_onep (rhs) && !integer_zerop (rhs)))
1032 return false;
1033 gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
1034 if (phi == NULL || gimple_bb (g: phi) != e->dest)
1035 return false;
1036
1037 /* Check if phi's incoming value is CMP. */
1038 gassign *def;
1039 tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
1040 if (TREE_CODE (value) != SSA_NAME
1041 || !has_single_use (var: value)
1042 || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
1043 return false;
1044
1045 /* Or if it is (INT) (a CMP b). */
1046 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
1047 {
1048 value = gimple_assign_rhs1 (gs: def);
1049 if (TREE_CODE (value) != SSA_NAME
1050 || !has_single_use (var: value)
1051 || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
1052 return false;
1053 }
1054
1055 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
1065void
1066jump_threader::thread_across_edge (edge e)
1067{
1068 auto_bitmap visited;
1069
1070 m_state->push (e);
1071
1072 stmt_count = 0;
1073
1074 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1075 bitmap_set_bit (visited, e->src->index);
1076 bitmap_set_bit (visited, e->dest->index);
1077
1078 int threaded = 0;
1079 if ((e->flags & EDGE_DFS_BACK) == 0)
1080 threaded = thread_through_normal_block (path, e, visited);
1081
1082 if (threaded > 0)
1083 {
1084 propagate_threaded_block_debug_into (dest: path->last ()->e->dest,
1085 src: e->dest);
1086 m_registry->register_jump_thread (path);
1087 m_state->pop ();
1088 return;
1089 }
1090
1091 gcc_checking_assert (path->length () == 0);
1092 path->release ();
1093
1094 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 m_state->pop ();
1104 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 {
1119 edge taken_edge;
1120 edge_iterator ei;
1121 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 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1126 if (taken_edge->flags & EDGE_COMPLEX)
1127 {
1128 m_state->pop ();
1129 return;
1130 }
1131
1132 /* Look at each successor of E->dest to see if we can thread through it. */
1133 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1134 {
1135 if ((e->flags & EDGE_DFS_BACK) != 0
1136 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1137 continue;
1138
1139 m_state->push (taken_edge);
1140
1141 /* Avoid threading to any block we have already visited. */
1142 bitmap_clear (visited);
1143 bitmap_set_bit (visited, e->src->index);
1144 bitmap_set_bit (visited, e->dest->index);
1145 bitmap_set_bit (visited, taken_edge->dest->index);
1146
1147 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1148 m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
1149 m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1150
1151 found = thread_around_empty_blocks (path, taken_edge, visited);
1152
1153 if (!found)
1154 found = thread_through_normal_block (path,
1155 e: 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 if (found
1160 || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1161 {
1162 if (taken_edge->dest != path->last ()->e->dest)
1163 propagate_threaded_block_debug_into (dest: path->last ()->e->dest,
1164 src: taken_edge->dest);
1165 m_registry->register_jump_thread (path);
1166 }
1167 else
1168 path->release ();
1169
1170 m_state->pop ();
1171 }
1172 }
1173
1174 m_state->pop ();
1175}
1176
1177/* Return TRUE if BB has a single successor to a block with multiple
1178 incoming and outgoing edges. */
1179
1180bool
1181single_succ_to_potentially_threadable_block (basic_block bb)
1182{
1183 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1184 return (single_succ_p (bb)
1185 && (single_succ_edge (bb)->flags & flags) == 0
1186 && potentially_threadable_block (bb: single_succ (bb)));
1187}
1188
1189/* Examine the outgoing edges from BB and conditionally
1190 try to thread them. */
1191
1192void
1193jump_threader::thread_outgoing_edges (basic_block bb)
1194{
1195 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1196
1197 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 if (single_succ_to_potentially_threadable_block (bb))
1205 thread_across_edge (e: single_succ_edge (bb));
1206 else if (safe_is_a <gcond *> (p: *gsi_last_bb (bb))
1207 && EDGE_COUNT (bb->succs) == 2
1208 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1209 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1210 {
1211 edge true_edge, false_edge;
1212
1213 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 if (potentially_threadable_block (bb: true_edge->dest))
1218 thread_across_edge (e: true_edge);
1219
1220 /* Similarly for the ELSE arm. */
1221 if (potentially_threadable_block (bb: false_edge->dest))
1222 thread_across_edge (e: false_edge);
1223 }
1224}
1225
1226// Marker to keep track of the start of the current path.
1227const basic_block jt_state::BB_MARKER = (basic_block) -1;
1228
1229// Record that E is being crossed.
1230
1231void
1232jt_state::push (edge e)
1233{
1234 m_blocks.safe_push (obj: BB_MARKER);
1235 if (m_blocks.length () == 1)
1236 m_blocks.safe_push (obj: e->src);
1237 m_blocks.safe_push (obj: e->dest);
1238}
1239
1240// Pop to the last pushed state.
1241
1242void
1243jt_state::pop ()
1244{
1245 if (!m_blocks.is_empty ())
1246 {
1247 while (m_blocks.last () != BB_MARKER)
1248 m_blocks.pop ();
1249 // Pop marker.
1250 m_blocks.pop ();
1251 }
1252}
1253
1254// Add BB to the list of blocks seen.
1255
1256void
1257jt_state::append_path (basic_block bb)
1258{
1259 gcc_checking_assert (!m_blocks.is_empty ());
1260 m_blocks.safe_push (obj: bb);
1261}
1262
1263void
1264jt_state::dump (FILE *out)
1265{
1266 if (!m_blocks.is_empty ())
1267 {
1268 auto_vec<basic_block> path;
1269 get_path (path);
1270 dump_ranger (out, path);
1271 }
1272}
1273
1274void
1275jt_state::debug ()
1276{
1277 push_dump_file save (stderr, TDF_DETAILS);
1278 dump (stderr);
1279}
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
1284void
1285jt_state::get_path (vec<basic_block> &path)
1286{
1287 path.truncate (size: 0);
1288
1289 for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
1290 {
1291 basic_block bb = m_blocks[i];
1292
1293 if (bb != BB_MARKER)
1294 path.safe_push (obj: bb);
1295 }
1296}
1297
1298// Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
1299// update the value range associated with DST.
1300
1301void
1302jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
1303 tree src ATTRIBUTE_UNUSED,
1304 bool update_range ATTRIBUTE_UNUSED)
1305{
1306}
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
1312void
1313jt_state::record_ranges_from_stmt (gimple *,
1314 bool temporary ATTRIBUTE_UNUSED)
1315{
1316}
1317
1318// Record any equivalences created by traversing E.
1319
1320void
1321jt_state::register_equivs_edge (edge)
1322{
1323}
1324
1325void
1326jt_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 tree cached_lhs = NULL;
1336 if (gimple_assign_single_p (gs: stmt)
1337 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
1338 cached_lhs = gimple_assign_rhs1 (gs: 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 cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
1348 threadedge_valueize);
1349 if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
1350 && (!cached_lhs
1351 || (TREE_CODE (cached_lhs) != SSA_NAME
1352 && !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 tree *copy;
1357 ssa_op_iter iter;
1358 use_operand_p use_p;
1359 unsigned int num, i = 0;
1360
1361 num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
1362 copy = XALLOCAVEC (tree, num);
1363
1364 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
1365 the operands. */
1366 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1367 {
1368 tree tmp = NULL;
1369 tree use = USE_FROM_PTR (use_p);
1370
1371 copy[i++] = use;
1372 if (TREE_CODE (use) == SSA_NAME)
1373 tmp = SSA_NAME_VALUE (use);
1374 if (tmp)
1375 SET_USE (use_p, tmp);
1376 }
1377
1378 /* Do not pass state to avoid calling the ranger with the
1379 temporarily altered IL. */
1380 cached_lhs = simplifier->simplify (stmt, stmt, bb, /*state=*/NULL);
1381
1382 /* Restore the statement's original uses/defs. */
1383 i = 0;
1384 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1385 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 if (cached_lhs
1392 && (TREE_CODE (cached_lhs) == SSA_NAME
1393 || is_gimple_min_invariant (cached_lhs)))
1394 register_equiv (dest: gimple_get_lhs (stmt), src: cached_lhs,
1395 /*update_range=*/false);
1396}
1397
1398// Hybrid threader implementation.
1399
1400hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
1401 path_range_query *q)
1402{
1403 m_ranger = r;
1404 m_query = q;
1405}
1406
1407tree
1408hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
1409 jt_state *state)
1410{
1411 auto_bitmap dependencies;
1412 auto_vec<basic_block> path;
1413
1414 state->get_path (path);
1415 compute_exit_dependencies (dependencies, path, stmt);
1416 m_query->reset_path (path, dependencies);
1417
1418 if (gimple_code (g: stmt) == GIMPLE_COND
1419 || gimple_code (g: stmt) == GIMPLE_ASSIGN)
1420 {
1421 Value_Range r (gimple_range_type (s: stmt));
1422 tree ret;
1423 if (m_query->range_of_stmt (r, stmt) && r.singleton_p (result: &ret))
1424 return ret;
1425 }
1426 else if (gimple_code (g: stmt) == GIMPLE_SWITCH)
1427 {
1428 int_range_max r;
1429 gswitch *switch_stmt = dyn_cast <gswitch *> (p: stmt);
1430 tree index = gimple_switch_index (gs: switch_stmt);
1431 if (m_query->range_of_expr (r, name: index, stmt))
1432 return find_case_label_range (switch_stmt, vr: &r);
1433 }
1434 return NULL;
1435}
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
1444void
1445hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies,
1446 const vec<basic_block> &path,
1447 gimple *stmt)
1448{
1449 gori_compute &gori = m_ranger->gori ();
1450
1451 // Start with the imports to the final conditional.
1452 bitmap_copy (dependencies, gori.imports (bb: path[0]));
1453
1454 // Add any other interesting operands we may have missed.
1455 if (gimple_bb (g: stmt) != path[0])
1456 {
1457 for (unsigned i = 0; i < gimple_num_ops (gs: stmt); ++i)
1458 {
1459 tree op = gimple_op (gs: stmt, i);
1460 if (op
1461 && TREE_CODE (op) == SSA_NAME
1462 && Value_Range::supports_type_p (TREE_TYPE (op)))
1463 bitmap_set_bit (dependencies, SSA_NAME_VERSION (op));
1464 }
1465 }
1466}
1467

source code of gcc/tree-ssa-threadedge.cc