2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
3 Contributed by Jeff Law <law@redhat.com>
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
31 #include "fold-const.h"
37 #include "internal-fn.h"
38 #include "gimple-iterator.h"
40 #include "tree-ssa-propagate.h"
41 #include "tree-ssa-threadupdate.h"
42 #include "langhooks.h"
44 #include "tree-ssa-scopedtables.h"
45 #include "tree-ssa-threadedge.h"
46 #include "tree-ssa-loop.h"
50 /* To avoid code explosion due to jump threading, we limit the
51 number of statements we are going to copy. This variable
52 holds the number of statements currently seen that we'll have
53 to copy as part of the jump threading process. */
54 static int stmt_count
;
56 /* Array to record value-handles per SSA_NAME. */
57 vec
<tree
> ssa_name_values
;
59 typedef tree (pfn_simplify
) (gimple
*, gimple
*, class avail_exprs_stack
*);
61 /* Set the value for the SSA name NAME to VALUE. */
64 set_ssa_name_value (tree name
, tree value
)
66 if (SSA_NAME_VERSION (name
) >= ssa_name_values
.length ())
67 ssa_name_values
.safe_grow_cleared (SSA_NAME_VERSION (name
) + 1);
68 if (value
&& TREE_OVERFLOW_P (value
))
69 value
= drop_tree_overflow (value
);
70 ssa_name_values
[SSA_NAME_VERSION (name
)] = value
;
73 /* Initialize the per SSA_NAME value-handles array. Returns it. */
75 threadedge_initialize_values (void)
77 gcc_assert (!ssa_name_values
.exists ());
78 ssa_name_values
.create (num_ssa_names
);
81 /* Free the per SSA_NAME value-handle array. */
83 threadedge_finalize_values (void)
85 ssa_name_values
.release ();
88 /* Return TRUE if we may be able to thread an incoming edge into
89 BB to an outgoing edge from BB. Return FALSE otherwise. */
92 potentially_threadable_block (basic_block bb
)
94 gimple_stmt_iterator gsi
;
96 /* Special case. We can get blocks that are forwarders, but are
97 not optimized away because they forward from outside a loop
98 to the loop header. We want to thread through them as we can
99 sometimes thread to the loop exit, which is obviously profitable.
100 the interesting case here is when the block has PHIs. */
101 if (gsi_end_p (gsi_start_nondebug_bb (bb
))
102 && !gsi_end_p (gsi_start_phis (bb
)))
105 /* If BB has a single successor or a single predecessor, then
106 there is no threading opportunity. */
107 if (single_succ_p (bb
) || single_pred_p (bb
))
110 /* If BB does not end with a conditional, switch or computed goto,
111 then there is no threading opportunity. */
112 gsi
= gsi_last_bb (bb
);
115 || (gimple_code (gsi_stmt (gsi
)) != GIMPLE_COND
116 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_GOTO
117 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_SWITCH
))
123 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
124 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
125 BB. If no such ASSERT_EXPR is found, return OP. */
128 lhs_of_dominating_assert (tree op
, basic_block bb
, gimple
*stmt
)
130 imm_use_iterator imm_iter
;
134 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, op
)
136 use_stmt
= USE_STMT (use_p
);
138 && gimple_assign_single_p (use_stmt
)
139 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == ASSERT_EXPR
140 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0) == op
141 && dominated_by_p (CDI_DOMINATORS
, bb
, gimple_bb (use_stmt
)))
143 return gimple_assign_lhs (use_stmt
);
149 /* Record temporary equivalences created by PHIs at the target of the
150 edge E. Record unwind information for the equivalences onto STACK.
152 If a PHI which prevents threading is encountered, then return FALSE
153 indicating we should not thread this edge, else return TRUE.
155 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
156 of any equivalences recorded. We use this to make invalidation after
157 traversing back edges less painful. */
160 record_temporary_equivalences_from_phis (edge e
, const_and_copies
*const_and_copies
)
164 /* Each PHI creates a temporary equivalence, record them.
165 These are context sensitive equivalences and will be removed
167 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
169 gphi
*phi
= gsi
.phi ();
170 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
171 tree dst
= gimple_phi_result (phi
);
173 /* If the desired argument is not the same as this PHI's result
174 and it is set by a PHI in E->dest, then we can not thread
177 && TREE_CODE (src
) == SSA_NAME
178 && gimple_code (SSA_NAME_DEF_STMT (src
)) == GIMPLE_PHI
179 && gimple_bb (SSA_NAME_DEF_STMT (src
)) == e
->dest
)
182 /* We consider any non-virtual PHI as a statement since it
183 count result in a constant assignment or copy operation. */
184 if (!virtual_operand_p (dst
))
187 const_and_copies
->record_const_or_copy (dst
, src
);
192 /* Fold the RHS of an assignment statement and return it as a tree.
193 May return NULL_TREE if no simplification is possible. */
196 fold_assignment_stmt (gimple
*stmt
)
198 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
200 switch (get_gimple_rhs_class (subcode
))
202 case GIMPLE_SINGLE_RHS
:
203 return fold (gimple_assign_rhs1 (stmt
));
205 case GIMPLE_UNARY_RHS
:
207 tree lhs
= gimple_assign_lhs (stmt
);
208 tree op0
= gimple_assign_rhs1 (stmt
);
209 return fold_unary (subcode
, TREE_TYPE (lhs
), op0
);
212 case GIMPLE_BINARY_RHS
:
214 tree lhs
= gimple_assign_lhs (stmt
);
215 tree op0
= gimple_assign_rhs1 (stmt
);
216 tree op1
= gimple_assign_rhs2 (stmt
);
217 return fold_binary (subcode
, TREE_TYPE (lhs
), op0
, op1
);
220 case GIMPLE_TERNARY_RHS
:
222 tree lhs
= gimple_assign_lhs (stmt
);
223 tree op0
= gimple_assign_rhs1 (stmt
);
224 tree op1
= gimple_assign_rhs2 (stmt
);
225 tree op2
= gimple_assign_rhs3 (stmt
);
227 /* Sadly, we have to handle conditional assignments specially
228 here, because fold expects all the operands of an expression
229 to be folded before the expression itself is folded, but we
230 can't just substitute the folded condition here. */
231 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
234 return fold_ternary (subcode
, TREE_TYPE (lhs
), op0
, op1
, op2
);
242 /* Try to simplify each statement in E->dest, ultimately leading to
243 a simplification of the COND_EXPR at the end of E->dest.
245 Record unwind information for temporary equivalences onto STACK.
247 Use SIMPLIFY (a pointer to a callback function) to further simplify
248 statements using pass specific information.
250 We might consider marking just those statements which ultimately
251 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
252 would be recovered by trying to simplify fewer statements.
254 If we are able to simplify a statement into the form
255 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
256 a context sensitive equivalence which may help us simplify
257 later statements in E->dest. */
260 record_temporary_equivalences_from_stmts_at_dest (edge e
,
261 const_and_copies
*const_and_copies
,
262 avail_exprs_stack
*avail_exprs_stack
,
263 pfn_simplify simplify
,
267 gimple_stmt_iterator gsi
;
270 max_stmt_count
= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
);
272 /* Walk through each statement in the block recording equivalences
273 we discover. Note any equivalences we discover are context
274 sensitive (ie, are dependent on traversing E) and must be unwound
275 when we're finished processing E. */
276 for (gsi
= gsi_start_bb (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
278 tree cached_lhs
= NULL
;
280 stmt
= gsi_stmt (gsi
);
282 /* Ignore empty statements and labels. */
283 if (gimple_code (stmt
) == GIMPLE_NOP
284 || gimple_code (stmt
) == GIMPLE_LABEL
285 || is_gimple_debug (stmt
))
288 /* If the statement has volatile operands, then we assume we
289 can not thread through this block. This is overly
290 conservative in some ways. */
291 if (gimple_code (stmt
) == GIMPLE_ASM
292 && gimple_asm_volatile_p (as_a
<gasm
*> (stmt
)))
295 /* If duplicating this block is going to cause too much code
296 expansion, then do not thread through this block. */
298 if (stmt_count
> max_stmt_count
)
301 /* If this is not a statement that sets an SSA_NAME to a new
302 value, then do not try to simplify this statement as it will
303 not simplify in any way that is helpful for jump threading. */
304 if ((gimple_code (stmt
) != GIMPLE_ASSIGN
305 || TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
306 && (gimple_code (stmt
) != GIMPLE_CALL
307 || gimple_call_lhs (stmt
) == NULL_TREE
308 || TREE_CODE (gimple_call_lhs (stmt
)) != SSA_NAME
))
310 /* STMT might still have DEFS and we need to invalidate any known
311 equivalences for them.
313 Consider if STMT is a GIMPLE_ASM with one or more outputs that
314 feeds a conditional inside a loop. We might derive an equivalence
315 due to the conditional. */
320 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
321 const_and_copies
->invalidate (op
);
326 /* The result of __builtin_object_size depends on all the arguments
327 of a phi node. Temporarily using only one edge produces invalid
336 r = PHI <&w[2].a[1](2), &a.a[6](3)>
337 __builtin_object_size (r, 0)
339 The result of __builtin_object_size is defined to be the maximum of
340 remaining bytes. If we use only one edge on the phi, the result will
341 change to be the remaining bytes for the corresponding phi argument.
343 Similarly for __builtin_constant_p:
346 __builtin_constant_p (r)
348 Both PHI arguments are constant, but x ? 1 : 2 is still not
351 if (is_gimple_call (stmt
))
353 tree fndecl
= gimple_call_fndecl (stmt
);
355 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_OBJECT_SIZE
356 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
))
360 tree lhs
= gimple_get_lhs (stmt
);
361 const_and_copies
->invalidate (lhs
);
367 /* At this point we have a statement which assigns an RHS to an
368 SSA_VAR on the LHS. We want to try and simplify this statement
369 to expose more context sensitive equivalences which in turn may
370 allow us to simplify the condition at the end of the loop.
372 Handle simple copy operations as well as implied copies from
374 if (gimple_assign_single_p (stmt
)
375 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
376 cached_lhs
= gimple_assign_rhs1 (stmt
);
377 else if (gimple_assign_single_p (stmt
)
378 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
379 cached_lhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
382 /* A statement that is not a trivial copy or ASSERT_EXPR.
383 We're going to temporarily copy propagate the operands
384 and see if that allows us to simplify this statement. */
388 unsigned int num
, i
= 0;
390 num
= NUM_SSA_OPERANDS (stmt
, (SSA_OP_USE
| SSA_OP_VUSE
));
391 copy
= XCNEWVEC (tree
, num
);
393 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
395 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
398 tree use
= USE_FROM_PTR (use_p
);
401 if (TREE_CODE (use
) == SSA_NAME
)
402 tmp
= SSA_NAME_VALUE (use
);
404 SET_USE (use_p
, tmp
);
407 /* Try to fold/lookup the new expression. Inserting the
408 expression into the hash table is unlikely to help. */
409 if (is_gimple_call (stmt
))
410 cached_lhs
= fold_call_stmt (as_a
<gcall
*> (stmt
), false);
412 cached_lhs
= fold_assignment_stmt (stmt
);
415 || (TREE_CODE (cached_lhs
) != SSA_NAME
416 && !is_gimple_min_invariant (cached_lhs
)))
417 cached_lhs
= (*simplify
) (stmt
, stmt
, avail_exprs_stack
);
419 /* Restore the statement's original uses/defs. */
421 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
422 SET_USE (use_p
, copy
[i
++]);
427 /* Record the context sensitive equivalence if we were able
428 to simplify this statement.
430 If we have traversed a backedge at some point during threading,
431 then always enter something here. Either a real equivalence,
432 or a NULL_TREE equivalence which is effectively invalidation of
433 prior equivalences. */
435 && (TREE_CODE (cached_lhs
) == SSA_NAME
436 || is_gimple_min_invariant (cached_lhs
)))
437 const_and_copies
->record_const_or_copy (gimple_get_lhs (stmt
),
439 else if (backedge_seen
)
440 const_and_copies
->invalidate (gimple_get_lhs (stmt
));
445 /* Once we have passed a backedge in the CFG when threading, we do not want to
446 utilize edge equivalences for simplification purpose. They are no longer
447 necessarily valid. We use this callback rather than the ones provided by
448 DOM/VRP to achieve that effect. */
450 dummy_simplify (gimple
*stmt1 ATTRIBUTE_UNUSED
, gimple
*stmt2 ATTRIBUTE_UNUSED
,
451 class avail_exprs_stack
*avail_exprs_stack ATTRIBUTE_UNUSED
)
456 /* Simplify the control statement at the end of the block E->dest.
458 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
459 is available to use/clobber in DUMMY_COND.
461 Use SIMPLIFY (a pointer to a callback function) to further simplify
462 a condition using pass specific information.
464 Return the simplified condition or NULL if simplification could
467 The available expression table is referenced via AVAIL_EXPRS_STACK. */
470 simplify_control_stmt_condition (edge e
,
472 class avail_exprs_stack
*avail_exprs_stack
,
474 pfn_simplify simplify
,
475 bool handle_dominating_asserts
)
477 tree cond
, cached_lhs
;
478 enum gimple_code code
= gimple_code (stmt
);
480 /* For comparisons, we have to update both operands, then try
481 to simplify the comparison. */
482 if (code
== GIMPLE_COND
)
485 enum tree_code cond_code
;
487 op0
= gimple_cond_lhs (stmt
);
488 op1
= gimple_cond_rhs (stmt
);
489 cond_code
= gimple_cond_code (stmt
);
491 /* Get the current value of both operands. */
492 if (TREE_CODE (op0
) == SSA_NAME
)
494 for (int i
= 0; i
< 2; i
++)
496 if (TREE_CODE (op0
) == SSA_NAME
497 && SSA_NAME_VALUE (op0
))
498 op0
= SSA_NAME_VALUE (op0
);
504 if (TREE_CODE (op1
) == SSA_NAME
)
506 for (int i
= 0; i
< 2; i
++)
508 if (TREE_CODE (op1
) == SSA_NAME
509 && SSA_NAME_VALUE (op1
))
510 op1
= SSA_NAME_VALUE (op1
);
516 if (handle_dominating_asserts
)
518 /* Now see if the operand was consumed by an ASSERT_EXPR
519 which dominates E->src. If so, we want to replace the
520 operand with the LHS of the ASSERT_EXPR. */
521 if (TREE_CODE (op0
) == SSA_NAME
)
522 op0
= lhs_of_dominating_assert (op0
, e
->src
, stmt
);
524 if (TREE_CODE (op1
) == SSA_NAME
)
525 op1
= lhs_of_dominating_assert (op1
, e
->src
, stmt
);
528 /* We may need to canonicalize the comparison. For
529 example, op0 might be a constant while op1 is an
530 SSA_NAME. Failure to canonicalize will cause us to
531 miss threading opportunities. */
532 if (tree_swap_operands_p (op0
, op1
, false))
534 cond_code
= swap_tree_comparison (cond_code
);
535 std::swap (op0
, op1
);
538 /* Stuff the operator and operands into our dummy conditional
540 gimple_cond_set_code (dummy_cond
, cond_code
);
541 gimple_cond_set_lhs (dummy_cond
, op0
);
542 gimple_cond_set_rhs (dummy_cond
, op1
);
544 /* We absolutely do not care about any type conversions
545 we only care about a zero/nonzero value. */
546 fold_defer_overflow_warnings ();
548 cached_lhs
= fold_binary (cond_code
, boolean_type_node
, op0
, op1
);
550 while (CONVERT_EXPR_P (cached_lhs
))
551 cached_lhs
= TREE_OPERAND (cached_lhs
, 0);
553 fold_undefer_overflow_warnings ((cached_lhs
554 && is_gimple_min_invariant (cached_lhs
)),
555 stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
557 /* If we have not simplified the condition down to an invariant,
558 then use the pass specific callback to simplify the condition. */
560 || !is_gimple_min_invariant (cached_lhs
))
561 cached_lhs
= (*simplify
) (dummy_cond
, stmt
, avail_exprs_stack
);
563 /* If we were just testing that an integral type was != 0, and that
564 failed, just return the first operand. This gives the FSM code a
565 chance to optimize the path. */
566 if (cached_lhs
== NULL
567 && cond_code
== NE_EXPR
)
569 /* Recover the original operands. They may have been simplified
570 using context sensitive equivalences. Those context sensitive
571 equivalences may not be valid on paths found by the FSM optimizer. */
572 tree op0
= gimple_cond_lhs (stmt
);
573 tree op1
= gimple_cond_rhs (stmt
);
575 if (INTEGRAL_TYPE_P (TREE_TYPE (op0
))
576 && TREE_CODE (op0
) == SSA_NAME
577 && integer_zerop (op1
))
584 if (code
== GIMPLE_SWITCH
)
585 cond
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
586 else if (code
== GIMPLE_GOTO
)
587 cond
= gimple_goto_dest (stmt
);
591 /* We can have conditionals which just test the state of a variable
592 rather than use a relational operator. These are simpler to handle. */
593 if (TREE_CODE (cond
) == SSA_NAME
)
595 tree original_lhs
= cond
;
598 /* Get the variable's current value from the equivalence chains.
600 It is possible to get loops in the SSA_NAME_VALUE chains
601 (consider threading the backedge of a loop where we have
602 a loop invariant SSA_NAME used in the condition. */
605 for (int i
= 0; i
< 2; i
++)
607 if (TREE_CODE (cached_lhs
) == SSA_NAME
608 && SSA_NAME_VALUE (cached_lhs
))
609 cached_lhs
= SSA_NAME_VALUE (cached_lhs
);
615 /* If we're dominated by a suitable ASSERT_EXPR, then
616 update CACHED_LHS appropriately. */
617 if (handle_dominating_asserts
&& TREE_CODE (cached_lhs
) == SSA_NAME
)
618 cached_lhs
= lhs_of_dominating_assert (cached_lhs
, e
->src
, stmt
);
620 /* If we haven't simplified to an invariant yet, then use the
621 pass specific callback to try and simplify it further. */
622 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
623 cached_lhs
= (*simplify
) (stmt
, stmt
, avail_exprs_stack
);
625 /* We couldn't find an invariant. But, callers of this
626 function may be able to do something useful with the
627 unmodified destination. */
629 cached_lhs
= original_lhs
;
637 /* Copy debug stmts from DEST's chain of single predecessors up to
638 SRC, so that we don't lose the bindings as PHI nodes are introduced
639 when DEST gains new predecessors. */
641 propagate_threaded_block_debug_into (basic_block dest
, basic_block src
)
643 if (!MAY_HAVE_DEBUG_STMTS
)
646 if (!single_pred_p (dest
))
649 gcc_checking_assert (dest
!= src
);
651 gimple_stmt_iterator gsi
= gsi_after_labels (dest
);
653 const int alloc_count
= 16; // ?? Should this be a PARAM?
655 /* Estimate the number of debug vars overridden in the beginning of
656 DEST, to tell how many we're going to need to begin with. */
657 for (gimple_stmt_iterator si
= gsi
;
658 i
* 4 <= alloc_count
* 3 && !gsi_end_p (si
); gsi_next (&si
))
660 gimple
*stmt
= gsi_stmt (si
);
661 if (!is_gimple_debug (stmt
))
666 auto_vec
<tree
, alloc_count
> fewvars
;
667 hash_set
<tree
> *vars
= NULL
;
669 /* If we're already starting with 3/4 of alloc_count, go for a
670 hash_set, otherwise start with an unordered stack-allocated
672 if (i
* 4 > alloc_count
* 3)
673 vars
= new hash_set
<tree
>;
675 /* Now go through the initial debug stmts in DEST again, this time
676 actually inserting in VARS or FEWVARS. Don't bother checking for
677 duplicates in FEWVARS. */
678 for (gimple_stmt_iterator si
= gsi
; !gsi_end_p (si
); gsi_next (&si
))
680 gimple
*stmt
= gsi_stmt (si
);
681 if (!is_gimple_debug (stmt
))
686 if (gimple_debug_bind_p (stmt
))
687 var
= gimple_debug_bind_get_var (stmt
);
688 else if (gimple_debug_source_bind_p (stmt
))
689 var
= gimple_debug_source_bind_get_var (stmt
);
696 fewvars
.quick_push (var
);
699 basic_block bb
= dest
;
703 bb
= single_pred (bb
);
704 for (gimple_stmt_iterator si
= gsi_last_bb (bb
);
705 !gsi_end_p (si
); gsi_prev (&si
))
707 gimple
*stmt
= gsi_stmt (si
);
708 if (!is_gimple_debug (stmt
))
713 if (gimple_debug_bind_p (stmt
))
714 var
= gimple_debug_bind_get_var (stmt
);
715 else if (gimple_debug_source_bind_p (stmt
))
716 var
= gimple_debug_source_bind_get_var (stmt
);
720 /* Discard debug bind overlaps. ??? Unlike stmts from src,
721 copied into a new block that will precede BB, debug bind
722 stmts in bypassed BBs may actually be discarded if
723 they're overwritten by subsequent debug bind stmts, which
724 might be a problem once we introduce stmt frontier notes
725 or somesuch. Adding `&& bb == src' to the condition
726 below will preserve all potentially relevant debug
728 if (vars
&& vars
->add (var
))
732 int i
= fewvars
.length ();
734 if (fewvars
[i
] == var
)
739 if (fewvars
.length () < (unsigned) alloc_count
)
740 fewvars
.quick_push (var
);
743 vars
= new hash_set
<tree
>;
744 for (i
= 0; i
< alloc_count
; i
++)
745 vars
->add (fewvars
[i
]);
751 stmt
= gimple_copy (stmt
);
752 /* ??? Should we drop the location of the copy to denote
753 they're artificial bindings? */
754 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
757 while (bb
!= src
&& single_pred_p (bb
));
761 else if (fewvars
.exists ())
765 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
766 need not be duplicated as part of the CFG/SSA updating process).
768 If it is threadable, add it to PATH and VISITED and recurse, ultimately
769 returning TRUE from the toplevel call. Otherwise do nothing and
772 DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
773 try and simplify the condition at the end of TAKEN_EDGE->dest.
775 The available expression table is referenced via AVAIL_EXPRS_STACK. */
778 thread_around_empty_blocks (edge taken_edge
,
780 class avail_exprs_stack
*avail_exprs_stack
,
781 bool handle_dominating_asserts
,
782 pfn_simplify simplify
,
784 vec
<jump_thread_edge
*> *path
,
785 bool *backedge_seen_p
)
787 basic_block bb
= taken_edge
->dest
;
788 gimple_stmt_iterator gsi
;
792 /* The key property of these blocks is that they need not be duplicated
793 when threading. Thus they can not have visible side effects such
795 if (!gsi_end_p (gsi_start_phis (bb
)))
798 /* Skip over DEBUG statements at the start of the block. */
799 gsi
= gsi_start_nondebug_bb (bb
);
801 /* If the block has no statements, but does have a single successor, then
802 it's just a forwarding block and we can thread through it trivially.
804 However, note that just threading through empty blocks with single
805 successors is not inherently profitable. For the jump thread to
806 be profitable, we must avoid a runtime conditional.
808 By taking the return value from the recursive call, we get the
809 desired effect of returning TRUE when we found a profitable jump
810 threading opportunity and FALSE otherwise.
812 This is particularly important when this routine is called after
813 processing a joiner block. Returning TRUE too aggressively in
814 that case results in pointless duplication of the joiner block. */
817 if (single_succ_p (bb
))
819 taken_edge
= single_succ_edge (bb
);
820 if (!bitmap_bit_p (visited
, taken_edge
->dest
->index
))
823 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
825 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
826 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
827 if (*backedge_seen_p
)
828 simplify
= dummy_simplify
;
829 return thread_around_empty_blocks (taken_edge
,
832 handle_dominating_asserts
,
840 /* We have a block with no statements, but multiple successors? */
844 /* The only real statements this block can have are a control
845 flow altering statement. Anything else stops the thread. */
846 stmt
= gsi_stmt (gsi
);
847 if (gimple_code (stmt
) != GIMPLE_COND
848 && gimple_code (stmt
) != GIMPLE_GOTO
849 && gimple_code (stmt
) != GIMPLE_SWITCH
)
852 /* If we have traversed a backedge, then we do not want to look
853 at certain expressions in the table that can not be relied upon.
854 Luckily the only code that looked at those expressions is the
855 SIMPLIFY callback, which we replace if we can no longer use it. */
856 if (*backedge_seen_p
)
857 simplify
= dummy_simplify
;
859 /* Extract and simplify the condition. */
860 cond
= simplify_control_stmt_condition (taken_edge
, stmt
,
861 avail_exprs_stack
, dummy_cond
,
862 simplify
, handle_dominating_asserts
);
864 /* If the condition can be statically computed and we have not already
865 visited the destination edge, then add the taken edge to our thread
867 if (cond
&& is_gimple_min_invariant (cond
))
869 taken_edge
= find_taken_edge (bb
, cond
);
871 if (bitmap_bit_p (visited
, taken_edge
->dest
->index
))
873 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
876 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
878 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
879 if (*backedge_seen_p
)
880 simplify
= dummy_simplify
;
882 thread_around_empty_blocks (taken_edge
,
885 handle_dominating_asserts
,
896 /* Return true if the CFG contains at least one path from START_BB to END_BB.
897 When a path is found, record in PATH the blocks from END_BB to START_BB.
898 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
899 the recursion to basic blocks belonging to LOOP. */
902 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
903 vec
<basic_block
, va_gc
> *&path
,
904 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
906 if (loop
!= start_bb
->loop_father
)
909 if (start_bb
== end_bb
)
911 vec_safe_push (path
, start_bb
);
915 if (!visited_bbs
->add (start_bb
))
919 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
920 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
922 vec_safe_push (path
, start_bb
);
930 static int max_threaded_paths
;
932 /* We trace the value of the variable EXPR back through any phi nodes looking
933 for places where it gets a constant value and save the path. Stop after
934 having recorded MAX_PATHS jump threading paths. */
937 fsm_find_control_statement_thread_paths (tree expr
,
938 hash_set
<basic_block
> *visited_bbs
,
939 vec
<basic_block
, va_gc
> *&path
,
942 tree var
= SSA_NAME_VAR (expr
);
943 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
944 basic_block var_bb
= gimple_bb (def_stmt
);
946 if (var
== NULL
|| var_bb
== NULL
)
949 /* For the moment we assume that an SSA chain only contains phi nodes, and
950 eventually one of the phi arguments will be an integer constant. In the
951 future, this could be extended to also handle simple assignments of
952 arithmetic operations. */
953 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
956 /* Avoid infinite recursion. */
957 if (visited_bbs
->add (var_bb
))
960 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
961 int next_path_length
= 0;
962 basic_block last_bb_in_path
= path
->last ();
964 if (loop_containing_stmt (phi
)->header
== gimple_bb (phi
))
966 /* Do not walk through more than one loop PHI node. */
969 seen_loop_phi
= true;
972 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
973 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
974 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
975 if (var_bb
!= last_bb_in_path
)
980 vec
<basic_block
, va_gc
> *next_path
;
981 vec_alloc (next_path
, n_basic_blocks_for_fn (cfun
));
983 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
985 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
987 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
988 e
->src
->loop_father
))
993 /* If there is more than one path, stop. */
996 vec_free (next_path
);
1001 /* Stop if we have not found a path: this could occur when the recursion
1002 is stopped by one of the bounds. */
1005 vec_free (next_path
);
1009 /* Make sure we haven't already visited any of the nodes in
1010 NEXT_PATH. Don't add them here to avoid pollution. */
1011 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
1013 if (visited_bbs
->contains ((*next_path
)[i
]))
1015 vec_free (next_path
);
1020 /* Now add the nodes to VISISTED_BBS. */
1021 for (unsigned int i
= 0; i
< next_path
->length () - 1; i
++)
1022 visited_bbs
->add ((*next_path
)[i
]);
1024 /* Append all the nodes from NEXT_PATH to PATH. */
1025 vec_safe_splice (path
, next_path
);
1026 next_path_length
= next_path
->length ();
1027 vec_free (next_path
);
1030 gcc_assert (path
->last () == var_bb
);
1032 /* Iterate over the arguments of PHI. */
1034 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1036 tree arg
= gimple_phi_arg_def (phi
, i
);
1037 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
1039 /* Skip edges pointing outside the current loop. */
1040 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
1043 if (TREE_CODE (arg
) == SSA_NAME
)
1045 vec_safe_push (path
, bbi
);
1046 /* Recursively follow SSA_NAMEs looking for a constant definition. */
1047 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
1054 if (TREE_CODE (arg
) != INTEGER_CST
)
1057 int path_length
= path
->length ();
1058 /* A path with less than 2 basic blocks should not be jump-threaded. */
1059 if (path_length
< 2)
1062 if (path_length
> PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
1064 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1065 fprintf (dump_file
, "FSM jump-thread path not considered: "
1066 "the number of basic blocks on the path "
1067 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
1071 if (max_threaded_paths
<= 0)
1073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1074 fprintf (dump_file
, "FSM jump-thread path not considered: "
1075 "the number of previously recorded FSM paths to thread "
1076 "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
1080 /* Add BBI to the path. */
1081 vec_safe_push (path
, bbi
);
1085 gimple_stmt_iterator gsi
;
1087 loop_p loop
= (*path
)[0]->loop_father
;
1088 bool path_crosses_loops
= false;
1090 /* Count the number of instructions on the path: as these instructions
1091 will have to be duplicated, we will not record the path if there are
1092 too many instructions on the path. Also check that all the blocks in
1093 the path belong to a single loop. */
1094 for (j
= 1; j
< path_length
- 1; j
++)
1096 basic_block bb
= (*path
)[j
];
1098 if (bb
->loop_father
!= loop
)
1100 path_crosses_loops
= true;
1104 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1106 gimple
*stmt
= gsi_stmt (gsi
);
1107 /* Do not count empty statements and labels. */
1108 if (gimple_code (stmt
) != GIMPLE_NOP
1109 && gimple_code (stmt
) != GIMPLE_LABEL
1110 && !is_gimple_debug (stmt
))
1115 if (path_crosses_loops
)
1117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1118 fprintf (dump_file
, "FSM jump-thread path not considered: "
1119 "the path crosses loops.\n");
1124 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
1126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1127 fprintf (dump_file
, "FSM jump-thread path not considered: "
1128 "the number of instructions on the path "
1129 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
1134 vec
<jump_thread_edge
*> *jump_thread_path
1135 = new vec
<jump_thread_edge
*> ();
1137 /* Record the edges between the blocks in PATH. */
1138 for (j
= 0; j
< path_length
- 1; j
++)
1140 edge e
= find_edge ((*path
)[path_length
- j
- 1],
1141 (*path
)[path_length
- j
- 2]);
1143 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
1144 jump_thread_path
->safe_push (x
);
1147 /* Add the edge taken when the control variable has value ARG. */
1148 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
1150 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
1151 jump_thread_path
->safe_push (x
);
1153 register_jump_thread (jump_thread_path
);
1154 --max_threaded_paths
;
1156 /* Remove BBI from the path. */
1160 /* Remove all the nodes that we added from NEXT_PATH. */
1161 if (next_path_length
)
1162 vec_safe_truncate (path
, (path
->length () - next_path_length
));
1165 /* We are exiting E->src, see if E->dest ends with a conditional
1166 jump which has a known value when reached via E.
1168 E->dest can have arbitrary side effects which, if threading is
1169 successful, will be maintained.
1171 Special care is necessary if E is a back edge in the CFG as we
1172 may have already recorded equivalences for E->dest into our
1173 various tables, including the result of the conditional at
1174 the end of E->dest. Threading opportunities are severely
1175 limited in that case to avoid short-circuiting the loop
1178 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1179 to avoid allocating memory.
1181 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1182 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1185 STACK is used to undo temporary equivalences created during the walk of
1188 SIMPLIFY is a pass-specific function used to simplify statements.
1190 Our caller is responsible for restoring the state of the expression
1191 and const_and_copies stacks.
1193 Positive return value is success. Zero return value is failure, but
1194 the block can still be duplicated as a joiner in a jump thread path,
1195 negative indicates the block should not be duplicated and thus is not
1196 suitable for a joiner in a jump threading path. */
1199 thread_through_normal_block (edge e
,
1201 bool handle_dominating_asserts
,
1202 const_and_copies
*const_and_copies
,
1203 avail_exprs_stack
*avail_exprs_stack
,
1204 pfn_simplify simplify
,
1205 vec
<jump_thread_edge
*> *path
,
1207 bool *backedge_seen_p
)
1209 /* If we have traversed a backedge, then we do not want to look
1210 at certain expressions in the table that can not be relied upon.
1211 Luckily the only code that looked at those expressions is the
1212 SIMPLIFY callback, which we replace if we can no longer use it. */
1213 if (*backedge_seen_p
)
1214 simplify
= dummy_simplify
;
1216 /* PHIs create temporary equivalences.
1217 Note that if we found a PHI that made the block non-threadable, then
1218 we need to bubble that up to our caller in the same manner we do
1219 when we prematurely stop processing statements below. */
1220 if (!record_temporary_equivalences_from_phis (e
, const_and_copies
))
1223 /* Now walk each statement recording any context sensitive
1224 temporary equivalences we can detect. */
1226 = record_temporary_equivalences_from_stmts_at_dest (e
, const_and_copies
,
1231 /* There's two reasons STMT might be null, and distinguishing
1232 between them is important.
1234 First the block may not have had any statements. For example, it
1235 might have some PHIs and unconditionally transfer control elsewhere.
1236 Such blocks are suitable for jump threading, particularly as a
1239 The second reason would be if we did not process all the statements
1240 in the block (because there were too many to make duplicating the
1241 block profitable. If we did not look at all the statements, then
1242 we may not have invalidated everything needing invalidation. Thus
1243 we must signal to our caller that this block is not suitable for
1244 use as a joiner in a threading path. */
1247 /* First case. The statement simply doesn't have any instructions, but
1249 if (gsi_end_p (gsi_start_nondebug_bb (e
->dest
))
1250 && !gsi_end_p (gsi_start_phis (e
->dest
)))
1257 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1259 if (gimple_code (stmt
) == GIMPLE_COND
1260 || gimple_code (stmt
) == GIMPLE_GOTO
1261 || gimple_code (stmt
) == GIMPLE_SWITCH
)
1265 /* Extract and simplify the condition. */
1266 cond
= simplify_control_stmt_condition (e
, stmt
, avail_exprs_stack
,
1267 dummy_cond
, simplify
,
1268 handle_dominating_asserts
);
1273 if (is_gimple_min_invariant (cond
))
1275 edge taken_edge
= find_taken_edge (e
->dest
, cond
);
1276 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
1278 /* DEST could be NULL for a computed jump to an absolute
1282 || bitmap_bit_p (visited
, dest
->index
))
1285 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1286 first edge on the path. */
1287 if (path
->length () == 0)
1290 = new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1291 path
->safe_push (x
);
1292 *backedge_seen_p
|= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1296 = new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_BLOCK
);
1297 path
->safe_push (x
);
1298 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1299 if (*backedge_seen_p
)
1300 simplify
= dummy_simplify
;
1302 /* See if we can thread through DEST as well, this helps capture
1303 secondary effects of threading without having to re-run DOM or
1306 We don't want to thread back to a block we have already
1307 visited. This may be overly conservative. */
1308 bitmap_set_bit (visited
, dest
->index
);
1309 bitmap_set_bit (visited
, e
->dest
->index
);
1310 thread_around_empty_blocks (taken_edge
,
1313 handle_dominating_asserts
,
1321 if (!flag_expensive_optimizations
1322 || optimize_function_for_size_p (cfun
)
1323 || TREE_CODE (cond
) != SSA_NAME
1324 || e
->dest
->loop_father
!= e
->src
->loop_father
1325 || loop_depth (e
->dest
->loop_father
) == 0)
1328 /* When COND cannot be simplified, try to find paths from a control
1329 statement back through the PHI nodes which would affect that control
1331 vec
<basic_block
, va_gc
> *bb_path
;
1332 vec_alloc (bb_path
, n_basic_blocks_for_fn (cfun
));
1333 vec_safe_push (bb_path
, e
->dest
);
1334 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
1336 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
1337 fsm_find_control_statement_thread_paths (cond
, visited_bbs
, bb_path
,
1346 /* We are exiting E->src, see if E->dest ends with a conditional
1347 jump which has a known value when reached via E.
1349 Special care is necessary if E is a back edge in the CFG as we
1350 may have already recorded equivalences for E->dest into our
1351 various tables, including the result of the conditional at
1352 the end of E->dest. Threading opportunities are severely
1353 limited in that case to avoid short-circuiting the loop
1356 Note it is quite common for the first block inside a loop to
1357 end with a conditional which is either always true or always
1358 false when reached via the loop backedge. Thus we do not want
1359 to blindly disable threading across a loop backedge.
1361 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1362 to avoid allocating memory.
1364 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1365 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1368 CONST_AND_COPIES is used to undo temporary equivalences created during the
1371 The available expression table is referenced vai AVAIL_EXPRS_STACK.
1373 SIMPLIFY is a pass-specific function used to simplify statements. */
1376 thread_across_edge (gcond
*dummy_cond
,
1378 bool handle_dominating_asserts
,
1379 class const_and_copies
*const_and_copies
,
1380 class avail_exprs_stack
*avail_exprs_stack
,
1381 tree (*simplify
) (gimple
*, gimple
*,
1382 class avail_exprs_stack
*))
1384 bitmap visited
= BITMAP_ALLOC (NULL
);
1389 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1390 bitmap_clear (visited
);
1391 bitmap_set_bit (visited
, e
->src
->index
);
1392 bitmap_set_bit (visited
, e
->dest
->index
);
1393 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1395 simplify
= dummy_simplify
;
1397 int threaded
= thread_through_normal_block (e
, dummy_cond
,
1398 handle_dominating_asserts
,
1402 visited
, &backedge_seen
);
1405 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1407 const_and_copies
->pop_to_marker ();
1408 BITMAP_FREE (visited
);
1409 register_jump_thread (path
);
1414 /* Negative and zero return values indicate no threading was possible,
1415 thus there should be no edges on the thread path and no need to walk
1416 through the vector entries. */
1417 gcc_assert (path
->length () == 0);
1421 /* A negative status indicates the target block was deemed too big to
1422 duplicate. Just quit now rather than trying to use the block as
1423 a joiner in a jump threading path.
1425 This prevents unnecessary code growth, but more importantly if we
1426 do not look at all the statements in the block, then we may have
1427 missed some invalidations if we had traversed a backedge! */
1430 BITMAP_FREE (visited
);
1431 const_and_copies
->pop_to_marker ();
1436 /* We were unable to determine what out edge from E->dest is taken. However,
1437 we might still be able to thread through successors of E->dest. This
1438 often occurs when E->dest is a joiner block which then fans back out
1439 based on redundant tests.
1441 If so, we'll copy E->dest and redirect the appropriate predecessor to
1442 the copy. Within the copy of E->dest, we'll thread one or more edges
1443 to points deeper in the CFG.
1445 This is a stopgap until we have a more structured approach to path
1452 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1453 we can safely redirect any of the edges. Just punt those cases. */
1454 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1455 if (taken_edge
->flags
& EDGE_ABNORMAL
)
1457 const_and_copies
->pop_to_marker ();
1458 BITMAP_FREE (visited
);
1462 /* Look at each successor of E->dest to see if we can thread through it. */
1463 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1465 /* Push a fresh marker so we can unwind the equivalences created
1466 for each of E->dest's successors. */
1467 const_and_copies
->push_marker ();
1468 if (avail_exprs_stack
)
1469 avail_exprs_stack
->push_marker ();
1471 /* Avoid threading to any block we have already visited. */
1472 bitmap_clear (visited
);
1473 bitmap_set_bit (visited
, e
->src
->index
);
1474 bitmap_set_bit (visited
, e
->dest
->index
);
1475 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
1476 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1478 /* Record whether or not we were able to thread through a successor
1480 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1481 path
->safe_push (x
);
1483 x
= new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_JOINER_BLOCK
);
1484 path
->safe_push (x
);
1486 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1487 backedge_seen
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1489 simplify
= dummy_simplify
;
1490 found
= thread_around_empty_blocks (taken_edge
,
1493 handle_dominating_asserts
,
1500 simplify
= dummy_simplify
;
1503 found
= thread_through_normal_block (path
->last ()->e
, dummy_cond
,
1504 handle_dominating_asserts
,
1508 visited
, &backedge_seen
) > 0;
1510 /* If we were able to thread through a successor of E->dest, then
1511 record the jump threading opportunity. */
1514 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1516 register_jump_thread (path
);
1520 delete_jump_thread_path (path
);
1523 /* And unwind the equivalence table. */
1524 if (avail_exprs_stack
)
1525 avail_exprs_stack
->pop_to_marker ();
1526 const_and_copies
->pop_to_marker ();
1528 BITMAP_FREE (visited
);
1531 const_and_copies
->pop_to_marker ();