1/* SSA Jump Threading
2 Copyright (C) 2005-2025 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 gimple_cond_set_code (gs: dummy_cond, code: cond_code);
500 gimple_cond_set_lhs (gs: dummy_cond, lhs: op0);
501 gimple_cond_set_rhs (gs: dummy_cond, rhs: op1);
502
503 /* We absolutely do not care about any type conversions
504 we only care about a zero/nonzero value. */
505 fold_defer_overflow_warnings ();
506
507 tree res = fold_binary (cond_code, boolean_type_node, op0, op1);
508 if (res)
509 while (CONVERT_EXPR_P (res))
510 res = TREE_OPERAND (res, 0);
511
512 fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)),
513 stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
514
515 /* If we have not simplified the condition down to an invariant,
516 then use the pass specific callback to simplify the condition. */
517 if (!res
518 || !is_gimple_min_invariant (res))
519 res = m_simplifier->simplify (dummy_cond, stmt, e->src, m_state);
520
521 return res;
522}
523
524/* Copy debug stmts from DEST's chain of single predecessors up to
525 SRC, so that we don't lose the bindings as PHI nodes are introduced
526 when DEST gains new predecessors. */
527void
528propagate_threaded_block_debug_into (basic_block dest, basic_block src)
529{
530 if (!MAY_HAVE_DEBUG_BIND_STMTS)
531 return;
532
533 if (!single_pred_p (bb: dest))
534 return;
535
536 gcc_checking_assert (dest != src);
537
538 gimple_stmt_iterator gsi = gsi_after_labels (bb: dest);
539 int i = 0;
540 const int alloc_count = 16; // ?? Should this be a PARAM?
541
542 /* Estimate the number of debug vars overridden in the beginning of
543 DEST, to tell how many we're going to need to begin with. */
544 for (gimple_stmt_iterator si = gsi;
545 i * 4 <= alloc_count * 3 && !gsi_end_p (i: si); gsi_next (i: &si))
546 {
547 gimple *stmt = gsi_stmt (i: si);
548 if (!is_gimple_debug (gs: stmt))
549 break;
550 if (gimple_debug_nonbind_marker_p (s: stmt))
551 continue;
552 i++;
553 }
554
555 auto_vec<tree, alloc_count> fewvars;
556 hash_set<tree> *vars = NULL;
557
558 /* If we're already starting with 3/4 of alloc_count, go for a
559 hash_set, otherwise start with an unordered stack-allocated
560 VEC. */
561 if (i * 4 > alloc_count * 3)
562 vars = new hash_set<tree>;
563
564 /* Now go through the initial debug stmts in DEST again, this time
565 actually inserting in VARS or FEWVARS. Don't bother checking for
566 duplicates in FEWVARS. */
567 for (gimple_stmt_iterator si = gsi; !gsi_end_p (i: si); gsi_next (i: &si))
568 {
569 gimple *stmt = gsi_stmt (i: si);
570 if (!is_gimple_debug (gs: stmt))
571 break;
572
573 tree var;
574
575 if (gimple_debug_bind_p (s: stmt))
576 var = gimple_debug_bind_get_var (dbg: stmt);
577 else if (gimple_debug_source_bind_p (s: stmt))
578 var = gimple_debug_source_bind_get_var (dbg: stmt);
579 else if (gimple_debug_nonbind_marker_p (s: stmt))
580 continue;
581 else
582 gcc_unreachable ();
583
584 if (vars)
585 vars->add (k: var);
586 else
587 fewvars.quick_push (obj: var);
588 }
589
590 basic_block bb = dest;
591
592 do
593 {
594 bb = single_pred (bb);
595 for (gimple_stmt_iterator si = gsi_last_bb (bb);
596 !gsi_end_p (i: si); gsi_prev (i: &si))
597 {
598 gimple *stmt = gsi_stmt (i: si);
599 if (!is_gimple_debug (gs: stmt))
600 continue;
601
602 tree var;
603
604 if (gimple_debug_bind_p (s: stmt))
605 var = gimple_debug_bind_get_var (dbg: stmt);
606 else if (gimple_debug_source_bind_p (s: stmt))
607 var = gimple_debug_source_bind_get_var (dbg: stmt);
608 else if (gimple_debug_nonbind_marker_p (s: stmt))
609 continue;
610 else
611 gcc_unreachable ();
612
613 /* Discard debug bind overlaps. Unlike stmts from src,
614 copied into a new block that will precede BB, debug bind
615 stmts in bypassed BBs may actually be discarded if
616 they're overwritten by subsequent debug bind stmts. We
617 want to copy binds for all modified variables, so that we
618 retain a bind to the shared def if there is one, or to a
619 newly introduced PHI node if there is one. Our bind will
620 end up reset if the value is dead, but that implies the
621 variable couldn't have survived, so it's fine. We are
622 not actually running the code that performed the binds at
623 this point, we're just adding binds so that they survive
624 the new confluence, so markers should not be copied. */
625 if (vars && vars->add (k: var))
626 continue;
627 else if (!vars)
628 {
629 int i = fewvars.length ();
630 while (i--)
631 if (fewvars[i] == var)
632 break;
633 if (i >= 0)
634 continue;
635 else if (fewvars.length () < (unsigned) alloc_count)
636 fewvars.quick_push (obj: var);
637 else
638 {
639 vars = new hash_set<tree>;
640 for (i = 0; i < alloc_count; i++)
641 vars->add (k: fewvars[i]);
642 fewvars.release ();
643 vars->add (k: var);
644 }
645 }
646
647 stmt = gimple_copy (stmt);
648 /* ??? Should we drop the location of the copy to denote
649 they're artificial bindings? */
650 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
651 }
652 }
653 while (bb != src && single_pred_p (bb));
654
655 if (vars)
656 delete vars;
657 else if (fewvars.exists ())
658 fewvars.release ();
659}
660
661/* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
662 need not be duplicated as part of the CFG/SSA updating process).
663
664 If it is threadable, add it to PATH and VISITED and recurse, ultimately
665 returning TRUE from the toplevel call. Otherwise do nothing and
666 return false. */
667
668bool
669jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
670 edge taken_edge,
671 bitmap visited, unsigned &limit)
672{
673 basic_block bb = taken_edge->dest;
674 gimple_stmt_iterator gsi;
675 gimple *stmt;
676 tree cond;
677
678 if (limit == 0)
679 return false;
680 --limit;
681
682 /* The key property of these blocks is that they need not be duplicated
683 when threading. Thus they cannot have visible side effects such
684 as PHI nodes. */
685 if (has_phis_p (bb))
686 return false;
687
688 /* Skip over DEBUG statements at the start of the block. */
689 gsi = gsi_start_nondebug_bb (bb);
690
691 /* If the block has no statements, but does have a single successor, then
692 it's just a forwarding block and we can thread through it trivially.
693
694 However, note that just threading through empty blocks with single
695 successors is not inherently profitable. For the jump thread to
696 be profitable, we must avoid a runtime conditional.
697
698 By taking the return value from the recursive call, we get the
699 desired effect of returning TRUE when we found a profitable jump
700 threading opportunity and FALSE otherwise.
701
702 This is particularly important when this routine is called after
703 processing a joiner block. Returning TRUE too aggressively in
704 that case results in pointless duplication of the joiner block. */
705 if (gsi_end_p (i: gsi))
706 {
707 if (single_succ_p (bb))
708 {
709 taken_edge = single_succ_edge (bb);
710
711 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
712 return false;
713
714 if (!bitmap_bit_p (visited, taken_edge->dest->index))
715 {
716 m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
717 m_state->append_path (taken_edge->dest);
718 bitmap_set_bit (visited, taken_edge->dest->index);
719 return thread_around_empty_blocks (path, taken_edge, visited,
720 limit);
721 }
722 }
723
724 /* We have a block with no statements, but multiple successors? */
725 return false;
726 }
727
728 /* The only real statements this block can have are a control
729 flow altering statement. Anything else stops the thread. */
730 stmt = gsi_stmt (i: gsi);
731 if (gimple_code (g: stmt) != GIMPLE_COND
732 && gimple_code (g: stmt) != GIMPLE_GOTO
733 && gimple_code (g: stmt) != GIMPLE_SWITCH)
734 return false;
735
736 /* Extract and simplify the condition. */
737 cond = simplify_control_stmt_condition (e: taken_edge, stmt);
738
739 /* If the condition can be statically computed and we have not already
740 visited the destination edge, then add the taken edge to our thread
741 path. */
742 if (cond != NULL_TREE
743 && (is_gimple_min_invariant (cond)
744 || TREE_CODE (cond) == CASE_LABEL_EXPR))
745 {
746 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
747 taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond)));
748 else
749 taken_edge = find_taken_edge (bb, cond);
750
751 if (!taken_edge
752 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
753 return false;
754
755 if (bitmap_bit_p (visited, taken_edge->dest->index))
756 return false;
757 bitmap_set_bit (visited, taken_edge->dest->index);
758
759 m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
760 m_state->append_path (taken_edge->dest);
761
762 thread_around_empty_blocks (path, taken_edge, visited, limit);
763 return true;
764 }
765
766 return false;
767}
768
769/* We are exiting E->src, see if E->dest ends with a conditional
770 jump which has a known value when reached via E.
771
772 E->dest can have arbitrary side effects which, if threading is
773 successful, will be maintained.
774
775 Special care is necessary if E is a back edge in the CFG as we
776 may have already recorded equivalences for E->dest into our
777 various tables, including the result of the conditional at
778 the end of E->dest. Threading opportunities are severely
779 limited in that case to avoid short-circuiting the loop
780 incorrectly.
781
782 Positive return value is success. Zero return value is failure, but
783 the block can still be duplicated as a joiner in a jump thread path,
784 negative indicates the block should not be duplicated and thus is not
785 suitable for a joiner in a jump threading path. */
786
787int
788jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
789 edge e, bitmap visited,
790 unsigned &limit)
791{
792 if (limit == 0)
793 return 0;
794 limit--;
795
796 m_state->register_equivs_edge (e);
797
798 /* PHIs create temporary equivalences.
799 Note that if we found a PHI that made the block non-threadable, then
800 we need to bubble that up to our caller in the same manner we do
801 when we prematurely stop processing statements below. */
802 if (!record_temporary_equivalences_from_phis (e))
803 return -1;
804
805 /* Now walk each statement recording any context sensitive
806 temporary equivalences we can detect. */
807 gimple *stmt = record_temporary_equivalences_from_stmts_at_dest (e);
808
809 /* There's two reasons STMT might be null, and distinguishing
810 between them is important.
811
812 First the block may not have had any statements. For example, it
813 might have some PHIs and unconditionally transfer control elsewhere.
814 Such blocks are suitable for jump threading, particularly as a
815 joiner block.
816
817 The second reason would be if we did not process all the statements
818 in the block (because there were too many to make duplicating the
819 block profitable. If we did not look at all the statements, then
820 we may not have invalidated everything needing invalidation. Thus
821 we must signal to our caller that this block is not suitable for
822 use as a joiner in a threading path. */
823 if (!stmt)
824 {
825 /* First case. The statement simply doesn't have any instructions, but
826 does have PHIs. */
827 if (empty_block_with_phis_p (bb: e->dest))
828 return 0;
829
830 /* Second case. */
831 return -1;
832 }
833
834 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
835 will be taken. */
836 if (gimple_code (g: stmt) == GIMPLE_COND
837 || gimple_code (g: stmt) == GIMPLE_GOTO
838 || gimple_code (g: stmt) == GIMPLE_SWITCH)
839 {
840 tree cond;
841
842 /* Extract and simplify the condition. */
843 cond = simplify_control_stmt_condition (e, stmt);
844
845 if (!cond)
846 return 0;
847
848 if (is_gimple_min_invariant (cond)
849 || TREE_CODE (cond) == CASE_LABEL_EXPR)
850 {
851 edge taken_edge;
852 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
853 taken_edge = find_edge (e->dest,
854 label_to_block (cfun, CASE_LABEL (cond)));
855 else
856 taken_edge = find_taken_edge (e->dest, cond);
857
858 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
859
860 /* DEST could be NULL for a computed jump to an absolute
861 address. */
862 if (dest == NULL
863 || dest == e->dest
864 || (taken_edge->flags & EDGE_DFS_BACK) != 0
865 || bitmap_bit_p (visited, dest->index))
866 return 0;
867
868 /* Only push the EDGE_START_JUMP_THREAD marker if this is
869 first edge on the path. */
870 if (path->length () == 0)
871 m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
872
873 m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
874 m_state->append_path (taken_edge->dest);
875
876 /* See if we can thread through DEST as well, this helps capture
877 secondary effects of threading without having to re-run DOM or
878 VRP.
879
880 We don't want to thread back to a block we have already
881 visited. This may be overly conservative. */
882 bitmap_set_bit (visited, dest->index);
883 bitmap_set_bit (visited, e->dest->index);
884 thread_around_empty_blocks (path, taken_edge, visited, limit);
885 return 1;
886 }
887 }
888 return 0;
889}
890
891/* There are basic blocks look like:
892 <P0>
893 p0 = a CMP b ; or p0 = (INT) (a CMP b)
894 goto <X>;
895
896 <P1>
897 p1 = c CMP d
898 goto <X>;
899
900 <X>
901 # phi = PHI <p0 (P0), p1 (P1)>
902 if (phi != 0) goto <Y>; else goto <Z>;
903
904 Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD
905 And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK
906
907 Return true if E is (P0,X) or (P1,X) */
908
909bool
910edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e)
911{
912 /* See if there is only one stmt which is gcond. */
913 gcond *gs;
914 if (!(gs = safe_dyn_cast<gcond *> (p: last_and_only_stmt (e->dest))))
915 return false;
916
917 /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */
918 tree cond = gimple_cond_lhs (gs);
919 enum tree_code code = gimple_cond_code (gs);
920 tree rhs = gimple_cond_rhs (gs);
921 if (TREE_CODE (cond) != SSA_NAME
922 || (code != NE_EXPR && code != EQ_EXPR)
923 || (!integer_onep (rhs) && !integer_zerop (rhs)))
924 return false;
925 gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond));
926 if (phi == NULL || gimple_bb (g: phi) != e->dest)
927 return false;
928
929 /* Check if phi's incoming value is CMP. */
930 gassign *def;
931 tree value = PHI_ARG_DEF_FROM_EDGE (phi, e);
932 if (TREE_CODE (value) != SSA_NAME
933 || !has_single_use (var: value)
934 || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value))))
935 return false;
936
937 /* Or if it is (INT) (a CMP b). */
938 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
939 {
940 value = gimple_assign_rhs1 (gs: def);
941 if (TREE_CODE (value) != SSA_NAME
942 || !has_single_use (var: value)
943 || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value))))
944 return false;
945 }
946
947 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
948 return false;
949
950 return true;
951}
952
953/* We are exiting E->src, see if E->dest ends with a conditional jump
954 which has a known value when reached via E. If so, thread the
955 edge. */
956
957void
958jump_threader::thread_across_edge (edge e)
959{
960 auto_bitmap visited;
961
962 m_state->push (e);
963
964 stmt_count = 0;
965
966 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
967 bitmap_set_bit (visited, e->src->index);
968 bitmap_set_bit (visited, e->dest->index);
969
970 /* Limit search space. */
971 unsigned limit = param_max_jump_thread_paths;
972
973 int threaded = 0;
974 if ((e->flags & EDGE_DFS_BACK) == 0)
975 threaded = thread_through_normal_block (path, e, visited, limit);
976
977 if (threaded > 0)
978 {
979 propagate_threaded_block_debug_into (dest: path->last ()->e->dest,
980 src: e->dest);
981 m_registry->register_jump_thread (path);
982 m_state->pop ();
983 return;
984 }
985
986 gcc_checking_assert (path->length () == 0);
987 path->release ();
988
989 if (threaded < 0)
990 {
991 /* The target block was deemed too big to duplicate. Just quit
992 now rather than trying to use the block as a joiner in a jump
993 threading path.
994
995 This prevents unnecessary code growth, but more importantly if we
996 do not look at all the statements in the block, then we may have
997 missed some invalidations if we had traversed a backedge! */
998 m_state->pop ();
999 return;
1000 }
1001
1002 /* We were unable to determine what out edge from E->dest is taken. However,
1003 we might still be able to thread through successors of E->dest. This
1004 often occurs when E->dest is a joiner block which then fans back out
1005 based on redundant tests.
1006
1007 If so, we'll copy E->dest and redirect the appropriate predecessor to
1008 the copy. Within the copy of E->dest, we'll thread one or more edges
1009 to points deeper in the CFG.
1010
1011 This is a stopgap until we have a more structured approach to path
1012 isolation. */
1013 {
1014 edge taken_edge;
1015 edge_iterator ei;
1016 bool found;
1017
1018 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1019 we can safely redirect any of the edges. Just punt those cases. */
1020 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1021 if (taken_edge->flags & EDGE_COMPLEX)
1022 {
1023 m_state->pop ();
1024 return;
1025 }
1026
1027 /* Look at each successor of E->dest to see if we can thread through it. */
1028 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1029 {
1030 if ((e->flags & EDGE_DFS_BACK) != 0
1031 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1032 continue;
1033
1034 m_state->push (taken_edge);
1035
1036 /* Avoid threading to any block we have already visited. */
1037 bitmap_clear (visited);
1038 bitmap_set_bit (visited, e->src->index);
1039 bitmap_set_bit (visited, e->dest->index);
1040 bitmap_set_bit (visited, taken_edge->dest->index);
1041
1042 vec<jump_thread_edge *> *path = m_registry->allocate_thread_path ();
1043 m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
1044 m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1045
1046 found = thread_around_empty_blocks (path, taken_edge, visited, limit);
1047
1048 if (!found)
1049 found = thread_through_normal_block (path,
1050 e: path->last ()->e, visited,
1051 limit) > 0;
1052
1053 /* If we were able to thread through a successor of E->dest, then
1054 record the jump threading opportunity. */
1055 if (found
1056 || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e))
1057 {
1058 if (taken_edge->dest != path->last ()->e->dest)
1059 propagate_threaded_block_debug_into (dest: path->last ()->e->dest,
1060 src: taken_edge->dest);
1061 m_registry->register_jump_thread (path);
1062 }
1063 else
1064 path->release ();
1065
1066 m_state->pop ();
1067 }
1068 }
1069
1070 m_state->pop ();
1071}
1072
1073/* Return TRUE if BB has a single successor to a block with multiple
1074 incoming and outgoing edges. */
1075
1076bool
1077single_succ_to_potentially_threadable_block (basic_block bb)
1078{
1079 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1080 return (single_succ_p (bb)
1081 && (single_succ_edge (bb)->flags & flags) == 0
1082 && potentially_threadable_block (bb: single_succ (bb)));
1083}
1084
1085/* Examine the outgoing edges from BB and conditionally
1086 try to thread them. */
1087
1088void
1089jump_threader::thread_outgoing_edges (basic_block bb)
1090{
1091 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1092
1093 if (!flag_thread_jumps)
1094 return;
1095
1096 /* If we have an outgoing edge to a block with multiple incoming and
1097 outgoing edges, then we may be able to thread the edge, i.e., we
1098 may be able to statically determine which of the outgoing edges
1099 will be traversed when the incoming edge from BB is traversed. */
1100 if (single_succ_to_potentially_threadable_block (bb))
1101 thread_across_edge (e: single_succ_edge (bb));
1102 else if (safe_is_a <gcond *> (p: *gsi_last_bb (bb))
1103 && EDGE_COUNT (bb->succs) == 2
1104 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1105 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1106 {
1107 edge true_edge, false_edge;
1108
1109 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1110
1111 /* Only try to thread the edge if it reaches a target block with
1112 more than one predecessor and more than one successor. */
1113 if (potentially_threadable_block (bb: true_edge->dest))
1114 thread_across_edge (e: true_edge);
1115
1116 /* Similarly for the ELSE arm. */
1117 if (potentially_threadable_block (bb: false_edge->dest))
1118 thread_across_edge (e: false_edge);
1119 }
1120}
1121
1122// Marker to keep track of the start of the current path.
1123const basic_block jt_state::BB_MARKER = (basic_block) -1;
1124
1125// Record that E is being crossed.
1126
1127void
1128jt_state::push (edge e)
1129{
1130 m_blocks.safe_push (obj: BB_MARKER);
1131 if (m_blocks.length () == 1)
1132 m_blocks.safe_push (obj: e->src);
1133 m_blocks.safe_push (obj: e->dest);
1134}
1135
1136// Pop to the last pushed state.
1137
1138void
1139jt_state::pop ()
1140{
1141 if (!m_blocks.is_empty ())
1142 {
1143 while (m_blocks.last () != BB_MARKER)
1144 m_blocks.pop ();
1145 // Pop marker.
1146 m_blocks.pop ();
1147 }
1148}
1149
1150// Add BB to the list of blocks seen.
1151
1152void
1153jt_state::append_path (basic_block bb)
1154{
1155 gcc_checking_assert (!m_blocks.is_empty ());
1156 m_blocks.safe_push (obj: bb);
1157}
1158
1159void
1160jt_state::dump (FILE *out)
1161{
1162 if (!m_blocks.is_empty ())
1163 {
1164 auto_vec<basic_block> path;
1165 get_path (path);
1166 dump_ranger (out, path);
1167 }
1168}
1169
1170void
1171jt_state::debug ()
1172{
1173 push_dump_file save (stderr, TDF_DETAILS);
1174 dump (stderr);
1175}
1176
1177// Convert the current path in jt_state into a path suitable for the
1178// path solver. Return the resulting path in PATH.
1179
1180void
1181jt_state::get_path (vec<basic_block> &path)
1182{
1183 path.truncate (size: 0);
1184
1185 for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
1186 {
1187 basic_block bb = m_blocks[i];
1188
1189 if (bb != BB_MARKER)
1190 path.safe_push (obj: bb);
1191 }
1192}
1193
1194// Record an equivalence from DST to SRC. If UPDATE_RANGE is TRUE,
1195// update the value range associated with DST.
1196
1197void
1198jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
1199 tree src ATTRIBUTE_UNUSED,
1200 bool update_range ATTRIBUTE_UNUSED)
1201{
1202}
1203
1204// Record any ranges calculated in STMT. If TEMPORARY is TRUE, then
1205// this is a temporary equivalence and should be recorded into the
1206// unwind table, instead of the global table.
1207
1208void
1209jt_state::record_ranges_from_stmt (gimple *,
1210 bool temporary ATTRIBUTE_UNUSED)
1211{
1212}
1213
1214// Record any equivalences created by traversing E.
1215
1216void
1217jt_state::register_equivs_edge (edge)
1218{
1219}
1220
1221void
1222jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
1223 jt_simplifier *simplifier)
1224{
1225 /* At this point we have a statement which assigns an RHS to an
1226 SSA_VAR on the LHS. We want to try and simplify this statement
1227 to expose more context sensitive equivalences which in turn may
1228 allow us to simplify the condition at the end of the loop.
1229
1230 Handle simple copy operations. */
1231 tree cached_lhs = NULL;
1232 if (gimple_assign_single_p (gs: stmt)
1233 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
1234 cached_lhs = gimple_assign_rhs1 (gs: stmt);
1235 else
1236 {
1237 /* A statement that is not a trivial copy.
1238 Try to fold the new expression. Inserting the
1239 expression into the hash table is unlikely to help. */
1240 /* ??? The DOM callback below can be changed to setting
1241 the mprts_hook around the call to thread_across_edge,
1242 avoiding the use substitution. */
1243 cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
1244 threadedge_valueize);
1245 if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
1246 && (!cached_lhs
1247 || (TREE_CODE (cached_lhs) != SSA_NAME
1248 && !is_gimple_min_invariant (cached_lhs))))
1249 {
1250 /* We're going to temporarily copy propagate the operands
1251 and see if that allows us to simplify this statement. */
1252 tree *copy;
1253 ssa_op_iter iter;
1254 use_operand_p use_p;
1255 unsigned int num, i = 0;
1256
1257 num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
1258 copy = XALLOCAVEC (tree, num);
1259
1260 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
1261 the operands. */
1262 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1263 {
1264 tree tmp = NULL;
1265 tree use = USE_FROM_PTR (use_p);
1266
1267 copy[i++] = use;
1268 if (TREE_CODE (use) == SSA_NAME)
1269 tmp = SSA_NAME_VALUE (use);
1270 if (tmp)
1271 SET_USE (use_p, tmp);
1272 }
1273
1274 /* Do not pass state to avoid calling the ranger with the
1275 temporarily altered IL. */
1276 cached_lhs = simplifier->simplify (stmt, stmt, bb, /*state=*/NULL);
1277
1278 /* Restore the statement's original uses/defs. */
1279 i = 0;
1280 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
1281 SET_USE (use_p, copy[i++]);
1282 }
1283 }
1284
1285 /* Record the context sensitive equivalence if we were able
1286 to simplify this statement. */
1287 if (cached_lhs
1288 && (TREE_CODE (cached_lhs) == SSA_NAME
1289 || is_gimple_min_invariant (cached_lhs)))
1290 register_equiv (dest: gimple_get_lhs (stmt), src: cached_lhs,
1291 /*update_range=*/false);
1292}
1293
1294// Hybrid threader implementation.
1295
1296hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r,
1297 path_range_query *q)
1298{
1299 m_ranger = r;
1300 m_query = q;
1301}
1302
1303tree
1304hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block,
1305 jt_state *state)
1306{
1307 auto_bitmap dependencies;
1308 auto_vec<basic_block> path;
1309
1310 state->get_path (path);
1311 compute_exit_dependencies (dependencies, path, stmt);
1312 m_query->reset_path (path, dependencies);
1313
1314 if (gimple_code (g: stmt) == GIMPLE_COND
1315 || gimple_code (g: stmt) == GIMPLE_ASSIGN)
1316 {
1317 value_range r (gimple_range_type (s: stmt));
1318 tree ret;
1319 if (m_query->range_of_stmt (r, stmt) && r.singleton_p (result: &ret))
1320 return ret;
1321 }
1322 else if (gimple_code (g: stmt) == GIMPLE_SWITCH)
1323 {
1324 int_range_max r;
1325 gswitch *switch_stmt = dyn_cast <gswitch *> (p: stmt);
1326 tree index = gimple_switch_index (gs: switch_stmt);
1327 if (m_query->range_of_expr (r, name: index, stmt))
1328 return find_case_label_range (switch_stmt, vr: &r);
1329 }
1330 return NULL;
1331}
1332
1333// Calculate the set of exit dependencies for a path and statement to
1334// be simplified. This is different than the
1335// compute_exit_dependencies in the path solver because the forward
1336// threader asks questions about statements not necessarily in the
1337// path. Using the default compute_exit_dependencies in the path
1338// solver gets noticeably less threads.
1339
1340void
1341hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies,
1342 const vec<basic_block> &path,
1343 gimple *stmt)
1344{
1345 // Start with the imports to the final conditional.
1346 bitmap_copy (dependencies, m_ranger->gori_ssa ()->imports (bb: path[0]));
1347
1348 // Add any other interesting operands we may have missed.
1349 if (gimple_bb (g: stmt) != path[0])
1350 {
1351 for (unsigned i = 0; i < gimple_num_ops (gs: stmt); ++i)
1352 {
1353 tree op = gimple_op (gs: stmt, i);
1354 if (op
1355 && TREE_CODE (op) == SSA_NAME
1356 && value_range::supports_type_p (TREE_TYPE (op)))
1357 bitmap_set_bit (dependencies, SSA_NAME_VERSION (op));
1358 }
1359 }
1360}
1361

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