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 /* Set the value for the SSA name NAME to VALUE. */
62 set_ssa_name_value (tree name
, tree value
)
64 if (SSA_NAME_VERSION (name
) >= ssa_name_values
.length ())
65 ssa_name_values
.safe_grow_cleared (SSA_NAME_VERSION (name
) + 1);
66 if (value
&& TREE_OVERFLOW_P (value
))
67 value
= drop_tree_overflow (value
);
68 ssa_name_values
[SSA_NAME_VERSION (name
)] = value
;
71 /* Initialize the per SSA_NAME value-handles array. Returns it. */
73 threadedge_initialize_values (void)
75 gcc_assert (!ssa_name_values
.exists ());
76 ssa_name_values
.create (num_ssa_names
);
79 /* Free the per SSA_NAME value-handle array. */
81 threadedge_finalize_values (void)
83 ssa_name_values
.release ();
86 /* Return TRUE if we may be able to thread an incoming edge into
87 BB to an outgoing edge from BB. Return FALSE otherwise. */
90 potentially_threadable_block (basic_block bb
)
92 gimple_stmt_iterator gsi
;
94 /* Special case. We can get blocks that are forwarders, but are
95 not optimized away because they forward from outside a loop
96 to the loop header. We want to thread through them as we can
97 sometimes thread to the loop exit, which is obviously profitable.
98 the interesting case here is when the block has PHIs. */
99 if (gsi_end_p (gsi_start_nondebug_bb (bb
))
100 && !gsi_end_p (gsi_start_phis (bb
)))
103 /* If BB has a single successor or a single predecessor, then
104 there is no threading opportunity. */
105 if (single_succ_p (bb
) || single_pred_p (bb
))
108 /* If BB does not end with a conditional, switch or computed goto,
109 then there is no threading opportunity. */
110 gsi
= gsi_last_bb (bb
);
113 || (gimple_code (gsi_stmt (gsi
)) != GIMPLE_COND
114 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_GOTO
115 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_SWITCH
))
121 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
122 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
123 BB. If no such ASSERT_EXPR is found, return OP. */
126 lhs_of_dominating_assert (tree op
, basic_block bb
, gimple stmt
)
128 imm_use_iterator imm_iter
;
132 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, op
)
134 use_stmt
= USE_STMT (use_p
);
136 && gimple_assign_single_p (use_stmt
)
137 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == ASSERT_EXPR
138 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0) == op
139 && dominated_by_p (CDI_DOMINATORS
, bb
, gimple_bb (use_stmt
)))
141 return gimple_assign_lhs (use_stmt
);
147 /* Record temporary equivalences created by PHIs at the target of the
148 edge E. Record unwind information for the equivalences onto STACK.
150 If a PHI which prevents threading is encountered, then return FALSE
151 indicating we should not thread this edge, else return TRUE.
153 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
154 of any equivalences recorded. We use this to make invalidation after
155 traversing back edges less painful. */
158 record_temporary_equivalences_from_phis (edge e
, const_and_copies
*const_and_copies
)
162 /* Each PHI creates a temporary equivalence, record them.
163 These are context sensitive equivalences and will be removed
165 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
167 gphi
*phi
= gsi
.phi ();
168 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
169 tree dst
= gimple_phi_result (phi
);
171 /* If the desired argument is not the same as this PHI's result
172 and it is set by a PHI in E->dest, then we can not thread
175 && TREE_CODE (src
) == SSA_NAME
176 && gimple_code (SSA_NAME_DEF_STMT (src
)) == GIMPLE_PHI
177 && gimple_bb (SSA_NAME_DEF_STMT (src
)) == e
->dest
)
180 /* We consider any non-virtual PHI as a statement since it
181 count result in a constant assignment or copy operation. */
182 if (!virtual_operand_p (dst
))
185 const_and_copies
->record_const_or_copy (dst
, src
);
190 /* Fold the RHS of an assignment statement and return it as a tree.
191 May return NULL_TREE if no simplification is possible. */
194 fold_assignment_stmt (gimple stmt
)
196 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
198 switch (get_gimple_rhs_class (subcode
))
200 case GIMPLE_SINGLE_RHS
:
201 return fold (gimple_assign_rhs1 (stmt
));
203 case GIMPLE_UNARY_RHS
:
205 tree lhs
= gimple_assign_lhs (stmt
);
206 tree op0
= gimple_assign_rhs1 (stmt
);
207 return fold_unary (subcode
, TREE_TYPE (lhs
), op0
);
210 case GIMPLE_BINARY_RHS
:
212 tree lhs
= gimple_assign_lhs (stmt
);
213 tree op0
= gimple_assign_rhs1 (stmt
);
214 tree op1
= gimple_assign_rhs2 (stmt
);
215 return fold_binary (subcode
, TREE_TYPE (lhs
), op0
, op1
);
218 case GIMPLE_TERNARY_RHS
:
220 tree lhs
= gimple_assign_lhs (stmt
);
221 tree op0
= gimple_assign_rhs1 (stmt
);
222 tree op1
= gimple_assign_rhs2 (stmt
);
223 tree op2
= gimple_assign_rhs3 (stmt
);
225 /* Sadly, we have to handle conditional assignments specially
226 here, because fold expects all the operands of an expression
227 to be folded before the expression itself is folded, but we
228 can't just substitute the folded condition here. */
229 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
232 return fold_ternary (subcode
, TREE_TYPE (lhs
), op0
, op1
, op2
);
240 /* Try to simplify each statement in E->dest, ultimately leading to
241 a simplification of the COND_EXPR at the end of E->dest.
243 Record unwind information for temporary equivalences onto STACK.
245 Use SIMPLIFY (a pointer to a callback function) to further simplify
246 statements using pass specific information.
248 We might consider marking just those statements which ultimately
249 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
250 would be recovered by trying to simplify fewer statements.
252 If we are able to simplify a statement into the form
253 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
254 a context sensitive equivalence which may help us simplify
255 later statements in E->dest. */
258 record_temporary_equivalences_from_stmts_at_dest (edge e
,
259 const_and_copies
*const_and_copies
,
260 tree (*simplify
) (gimple
,
265 gimple_stmt_iterator gsi
;
268 max_stmt_count
= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
);
270 /* Walk through each statement in the block recording equivalences
271 we discover. Note any equivalences we discover are context
272 sensitive (ie, are dependent on traversing E) and must be unwound
273 when we're finished processing E. */
274 for (gsi
= gsi_start_bb (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
276 tree cached_lhs
= NULL
;
278 stmt
= gsi_stmt (gsi
);
280 /* Ignore empty statements and labels. */
281 if (gimple_code (stmt
) == GIMPLE_NOP
282 || gimple_code (stmt
) == GIMPLE_LABEL
283 || is_gimple_debug (stmt
))
286 /* If the statement has volatile operands, then we assume we
287 can not thread through this block. This is overly
288 conservative in some ways. */
289 if (gimple_code (stmt
) == GIMPLE_ASM
290 && gimple_asm_volatile_p (as_a
<gasm
*> (stmt
)))
293 /* If duplicating this block is going to cause too much code
294 expansion, then do not thread through this block. */
296 if (stmt_count
> max_stmt_count
)
299 /* If this is not a statement that sets an SSA_NAME to a new
300 value, then do not try to simplify this statement as it will
301 not simplify in any way that is helpful for jump threading. */
302 if ((gimple_code (stmt
) != GIMPLE_ASSIGN
303 || TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
304 && (gimple_code (stmt
) != GIMPLE_CALL
305 || gimple_call_lhs (stmt
) == NULL_TREE
306 || TREE_CODE (gimple_call_lhs (stmt
)) != SSA_NAME
))
308 /* STMT might still have DEFS and we need to invalidate any known
309 equivalences for them.
311 Consider if STMT is a GIMPLE_ASM with one or more outputs that
312 feeds a conditional inside a loop. We might derive an equivalence
313 due to the conditional. */
318 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
319 const_and_copies
->invalidate (op
);
324 /* The result of __builtin_object_size depends on all the arguments
325 of a phi node. Temporarily using only one edge produces invalid
334 r = PHI <&w[2].a[1](2), &a.a[6](3)>
335 __builtin_object_size (r, 0)
337 The result of __builtin_object_size is defined to be the maximum of
338 remaining bytes. If we use only one edge on the phi, the result will
339 change to be the remaining bytes for the corresponding phi argument.
341 Similarly for __builtin_constant_p:
344 __builtin_constant_p (r)
346 Both PHI arguments are constant, but x ? 1 : 2 is still not
349 if (is_gimple_call (stmt
))
351 tree fndecl
= gimple_call_fndecl (stmt
);
353 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_OBJECT_SIZE
354 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
))
358 tree lhs
= gimple_get_lhs (stmt
);
359 const_and_copies
->invalidate (lhs
);
365 /* At this point we have a statement which assigns an RHS to an
366 SSA_VAR on the LHS. We want to try and simplify this statement
367 to expose more context sensitive equivalences which in turn may
368 allow us to simplify the condition at the end of the loop.
370 Handle simple copy operations as well as implied copies from
372 if (gimple_assign_single_p (stmt
)
373 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
374 cached_lhs
= gimple_assign_rhs1 (stmt
);
375 else if (gimple_assign_single_p (stmt
)
376 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
377 cached_lhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
380 /* A statement that is not a trivial copy or ASSERT_EXPR.
381 We're going to temporarily copy propagate the operands
382 and see if that allows us to simplify this statement. */
386 unsigned int num
, i
= 0;
388 num
= NUM_SSA_OPERANDS (stmt
, (SSA_OP_USE
| SSA_OP_VUSE
));
389 copy
= XCNEWVEC (tree
, num
);
391 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
393 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
396 tree use
= USE_FROM_PTR (use_p
);
399 if (TREE_CODE (use
) == SSA_NAME
)
400 tmp
= SSA_NAME_VALUE (use
);
402 SET_USE (use_p
, tmp
);
405 /* Try to fold/lookup the new expression. Inserting the
406 expression into the hash table is unlikely to help. */
407 if (is_gimple_call (stmt
))
408 cached_lhs
= fold_call_stmt (as_a
<gcall
*> (stmt
), false);
410 cached_lhs
= fold_assignment_stmt (stmt
);
413 || (TREE_CODE (cached_lhs
) != SSA_NAME
414 && !is_gimple_min_invariant (cached_lhs
)))
415 cached_lhs
= (*simplify
) (stmt
, stmt
);
417 /* Restore the statement's original uses/defs. */
419 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
420 SET_USE (use_p
, copy
[i
++]);
425 /* Record the context sensitive equivalence if we were able
426 to simplify this statement.
428 If we have traversed a backedge at some point during threading,
429 then always enter something here. Either a real equivalence,
430 or a NULL_TREE equivalence which is effectively invalidation of
431 prior equivalences. */
433 && (TREE_CODE (cached_lhs
) == SSA_NAME
434 || is_gimple_min_invariant (cached_lhs
)))
435 const_and_copies
->record_const_or_copy (gimple_get_lhs (stmt
), cached_lhs
);
436 else if (backedge_seen
)
437 const_and_copies
->invalidate (gimple_get_lhs (stmt
));
442 /* Once we have passed a backedge in the CFG when threading, we do not want to
443 utilize edge equivalences for simplification purpose. They are no longer
444 necessarily valid. We use this callback rather than the ones provided by
445 DOM/VRP to achieve that effect. */
447 dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED
, gimple stmt2 ATTRIBUTE_UNUSED
)
452 /* Simplify the control statement at the end of the block E->dest.
454 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
455 is available to use/clobber in DUMMY_COND.
457 Use SIMPLIFY (a pointer to a callback function) to further simplify
458 a condition using pass specific information.
460 Return the simplified condition or NULL if simplification could
464 simplify_control_stmt_condition (edge e
,
467 tree (*simplify
) (gimple
, gimple
),
468 bool handle_dominating_asserts
)
470 tree cond
, cached_lhs
;
471 enum gimple_code code
= gimple_code (stmt
);
473 /* For comparisons, we have to update both operands, then try
474 to simplify the comparison. */
475 if (code
== GIMPLE_COND
)
478 enum tree_code cond_code
;
480 op0
= gimple_cond_lhs (stmt
);
481 op1
= gimple_cond_rhs (stmt
);
482 cond_code
= gimple_cond_code (stmt
);
484 /* Get the current value of both operands. */
485 if (TREE_CODE (op0
) == SSA_NAME
)
487 for (int i
= 0; i
< 2; i
++)
489 if (TREE_CODE (op0
) == SSA_NAME
490 && SSA_NAME_VALUE (op0
))
491 op0
= SSA_NAME_VALUE (op0
);
497 if (TREE_CODE (op1
) == SSA_NAME
)
499 for (int i
= 0; i
< 2; i
++)
501 if (TREE_CODE (op1
) == SSA_NAME
502 && SSA_NAME_VALUE (op1
))
503 op1
= SSA_NAME_VALUE (op1
);
509 if (handle_dominating_asserts
)
511 /* Now see if the operand was consumed by an ASSERT_EXPR
512 which dominates E->src. If so, we want to replace the
513 operand with the LHS of the ASSERT_EXPR. */
514 if (TREE_CODE (op0
) == SSA_NAME
)
515 op0
= lhs_of_dominating_assert (op0
, e
->src
, stmt
);
517 if (TREE_CODE (op1
) == SSA_NAME
)
518 op1
= lhs_of_dominating_assert (op1
, e
->src
, stmt
);
521 /* We may need to canonicalize the comparison. For
522 example, op0 might be a constant while op1 is an
523 SSA_NAME. Failure to canonicalize will cause us to
524 miss threading opportunities. */
525 if (tree_swap_operands_p (op0
, op1
, false))
527 cond_code
= swap_tree_comparison (cond_code
);
528 std::swap (op0
, op1
);
531 /* Stuff the operator and operands into our dummy conditional
533 gimple_cond_set_code (dummy_cond
, cond_code
);
534 gimple_cond_set_lhs (dummy_cond
, op0
);
535 gimple_cond_set_rhs (dummy_cond
, op1
);
537 /* We absolutely do not care about any type conversions
538 we only care about a zero/nonzero value. */
539 fold_defer_overflow_warnings ();
541 cached_lhs
= fold_binary (cond_code
, boolean_type_node
, op0
, op1
);
543 while (CONVERT_EXPR_P (cached_lhs
))
544 cached_lhs
= TREE_OPERAND (cached_lhs
, 0);
546 fold_undefer_overflow_warnings ((cached_lhs
547 && is_gimple_min_invariant (cached_lhs
)),
548 stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
550 /* If we have not simplified the condition down to an invariant,
551 then use the pass specific callback to simplify the condition. */
553 || !is_gimple_min_invariant (cached_lhs
))
554 cached_lhs
= (*simplify
) (dummy_cond
, stmt
);
559 if (code
== GIMPLE_SWITCH
)
560 cond
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
561 else if (code
== GIMPLE_GOTO
)
562 cond
= gimple_goto_dest (stmt
);
566 /* We can have conditionals which just test the state of a variable
567 rather than use a relational operator. These are simpler to handle. */
568 if (TREE_CODE (cond
) == SSA_NAME
)
570 tree original_lhs
= cond
;
573 /* Get the variable's current value from the equivalence chains.
575 It is possible to get loops in the SSA_NAME_VALUE chains
576 (consider threading the backedge of a loop where we have
577 a loop invariant SSA_NAME used in the condition. */
580 for (int i
= 0; i
< 2; i
++)
582 if (TREE_CODE (cached_lhs
) == SSA_NAME
583 && SSA_NAME_VALUE (cached_lhs
))
584 cached_lhs
= SSA_NAME_VALUE (cached_lhs
);
590 /* If we're dominated by a suitable ASSERT_EXPR, then
591 update CACHED_LHS appropriately. */
592 if (handle_dominating_asserts
&& TREE_CODE (cached_lhs
) == SSA_NAME
)
593 cached_lhs
= lhs_of_dominating_assert (cached_lhs
, e
->src
, stmt
);
595 /* If we haven't simplified to an invariant yet, then use the
596 pass specific callback to try and simplify it further. */
597 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
598 cached_lhs
= (*simplify
) (stmt
, stmt
);
600 /* We couldn't find an invariant. But, callers of this
601 function may be able to do something useful with the
602 unmodified destination. */
604 cached_lhs
= original_lhs
;
612 /* Copy debug stmts from DEST's chain of single predecessors up to
613 SRC, so that we don't lose the bindings as PHI nodes are introduced
614 when DEST gains new predecessors. */
616 propagate_threaded_block_debug_into (basic_block dest
, basic_block src
)
618 if (!MAY_HAVE_DEBUG_STMTS
)
621 if (!single_pred_p (dest
))
624 gcc_checking_assert (dest
!= src
);
626 gimple_stmt_iterator gsi
= gsi_after_labels (dest
);
628 const int alloc_count
= 16; // ?? Should this be a PARAM?
630 /* Estimate the number of debug vars overridden in the beginning of
631 DEST, to tell how many we're going to need to begin with. */
632 for (gimple_stmt_iterator si
= gsi
;
633 i
* 4 <= alloc_count
* 3 && !gsi_end_p (si
); gsi_next (&si
))
635 gimple stmt
= gsi_stmt (si
);
636 if (!is_gimple_debug (stmt
))
641 auto_vec
<tree
, alloc_count
> fewvars
;
642 hash_set
<tree
> *vars
= NULL
;
644 /* If we're already starting with 3/4 of alloc_count, go for a
645 hash_set, otherwise start with an unordered stack-allocated
647 if (i
* 4 > alloc_count
* 3)
648 vars
= new hash_set
<tree
>;
650 /* Now go through the initial debug stmts in DEST again, this time
651 actually inserting in VARS or FEWVARS. Don't bother checking for
652 duplicates in FEWVARS. */
653 for (gimple_stmt_iterator si
= gsi
; !gsi_end_p (si
); gsi_next (&si
))
655 gimple stmt
= gsi_stmt (si
);
656 if (!is_gimple_debug (stmt
))
661 if (gimple_debug_bind_p (stmt
))
662 var
= gimple_debug_bind_get_var (stmt
);
663 else if (gimple_debug_source_bind_p (stmt
))
664 var
= gimple_debug_source_bind_get_var (stmt
);
671 fewvars
.quick_push (var
);
674 basic_block bb
= dest
;
678 bb
= single_pred (bb
);
679 for (gimple_stmt_iterator si
= gsi_last_bb (bb
);
680 !gsi_end_p (si
); gsi_prev (&si
))
682 gimple stmt
= gsi_stmt (si
);
683 if (!is_gimple_debug (stmt
))
688 if (gimple_debug_bind_p (stmt
))
689 var
= gimple_debug_bind_get_var (stmt
);
690 else if (gimple_debug_source_bind_p (stmt
))
691 var
= gimple_debug_source_bind_get_var (stmt
);
695 /* Discard debug bind overlaps. ??? Unlike stmts from src,
696 copied into a new block that will precede BB, debug bind
697 stmts in bypassed BBs may actually be discarded if
698 they're overwritten by subsequent debug bind stmts, which
699 might be a problem once we introduce stmt frontier notes
700 or somesuch. Adding `&& bb == src' to the condition
701 below will preserve all potentially relevant debug
703 if (vars
&& vars
->add (var
))
707 int i
= fewvars
.length ();
709 if (fewvars
[i
] == var
)
714 if (fewvars
.length () < (unsigned) alloc_count
)
715 fewvars
.quick_push (var
);
718 vars
= new hash_set
<tree
>;
719 for (i
= 0; i
< alloc_count
; i
++)
720 vars
->add (fewvars
[i
]);
726 stmt
= gimple_copy (stmt
);
727 /* ??? Should we drop the location of the copy to denote
728 they're artificial bindings? */
729 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
732 while (bb
!= src
&& single_pred_p (bb
));
736 else if (fewvars
.exists ())
740 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
741 need not be duplicated as part of the CFG/SSA updating process).
743 If it is threadable, add it to PATH and VISITED and recurse, ultimately
744 returning TRUE from the toplevel call. Otherwise do nothing and
747 DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
748 try and simplify the condition at the end of TAKEN_EDGE->dest. */
750 thread_around_empty_blocks (edge taken_edge
,
752 bool handle_dominating_asserts
,
753 tree (*simplify
) (gimple
, gimple
),
755 vec
<jump_thread_edge
*> *path
,
756 bool *backedge_seen_p
)
758 basic_block bb
= taken_edge
->dest
;
759 gimple_stmt_iterator gsi
;
763 /* The key property of these blocks is that they need not be duplicated
764 when threading. Thus they can not have visible side effects such
766 if (!gsi_end_p (gsi_start_phis (bb
)))
769 /* Skip over DEBUG statements at the start of the block. */
770 gsi
= gsi_start_nondebug_bb (bb
);
772 /* If the block has no statements, but does have a single successor, then
773 it's just a forwarding block and we can thread through it trivially.
775 However, note that just threading through empty blocks with single
776 successors is not inherently profitable. For the jump thread to
777 be profitable, we must avoid a runtime conditional.
779 By taking the return value from the recursive call, we get the
780 desired effect of returning TRUE when we found a profitable jump
781 threading opportunity and FALSE otherwise.
783 This is particularly important when this routine is called after
784 processing a joiner block. Returning TRUE too aggressively in
785 that case results in pointless duplication of the joiner block. */
788 if (single_succ_p (bb
))
790 taken_edge
= single_succ_edge (bb
);
791 if (!bitmap_bit_p (visited
, taken_edge
->dest
->index
))
794 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
796 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
797 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
798 if (*backedge_seen_p
)
799 simplify
= dummy_simplify
;
800 return thread_around_empty_blocks (taken_edge
,
802 handle_dominating_asserts
,
810 /* We have a block with no statements, but multiple successors? */
814 /* The only real statements this block can have are a control
815 flow altering statement. Anything else stops the thread. */
816 stmt
= gsi_stmt (gsi
);
817 if (gimple_code (stmt
) != GIMPLE_COND
818 && gimple_code (stmt
) != GIMPLE_GOTO
819 && gimple_code (stmt
) != GIMPLE_SWITCH
)
822 /* If we have traversed a backedge, then we do not want to look
823 at certain expressions in the table that can not be relied upon.
824 Luckily the only code that looked at those expressions is the
825 SIMPLIFY callback, which we replace if we can no longer use it. */
826 if (*backedge_seen_p
)
827 simplify
= dummy_simplify
;
829 /* Extract and simplify the condition. */
830 cond
= simplify_control_stmt_condition (taken_edge
, stmt
, dummy_cond
,
831 simplify
, handle_dominating_asserts
);
833 /* If the condition can be statically computed and we have not already
834 visited the destination edge, then add the taken edge to our thread
836 if (cond
&& is_gimple_min_invariant (cond
))
838 taken_edge
= find_taken_edge (bb
, cond
);
840 if (bitmap_bit_p (visited
, taken_edge
->dest
->index
))
842 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
845 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
847 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
848 if (*backedge_seen_p
)
849 simplify
= dummy_simplify
;
851 thread_around_empty_blocks (taken_edge
,
853 handle_dominating_asserts
,
864 /* Return true if the CFG contains at least one path from START_BB to END_BB.
865 When a path is found, record in PATH the blocks from END_BB to START_BB.
866 VISITED_BBS is used to make sure we don't fall into an infinite loop. Bound
867 the recursion to basic blocks belonging to LOOP. */
870 fsm_find_thread_path (basic_block start_bb
, basic_block end_bb
,
871 vec
<basic_block
, va_gc
> *&path
,
872 hash_set
<basic_block
> *visited_bbs
, loop_p loop
)
874 if (loop
!= start_bb
->loop_father
)
877 if (start_bb
== end_bb
)
879 vec_safe_push (path
, start_bb
);
883 if (!visited_bbs
->add (start_bb
))
887 FOR_EACH_EDGE (e
, ei
, start_bb
->succs
)
888 if (fsm_find_thread_path (e
->dest
, end_bb
, path
, visited_bbs
, loop
))
890 vec_safe_push (path
, start_bb
);
898 static int max_threaded_paths
;
900 /* We trace the value of the variable EXPR back through any phi nodes looking
901 for places where it gets a constant value and save the path. Stop after
902 having recorded MAX_PATHS jump threading paths. */
905 fsm_find_control_statement_thread_paths (tree expr
,
906 hash_set
<basic_block
> *visited_bbs
,
907 vec
<basic_block
, va_gc
> *&path
,
910 tree var
= SSA_NAME_VAR (expr
);
911 gimple def_stmt
= SSA_NAME_DEF_STMT (expr
);
912 basic_block var_bb
= gimple_bb (def_stmt
);
914 if (var
== NULL
|| var_bb
== NULL
)
917 /* For the moment we assume that an SSA chain only contains phi nodes, and
918 eventually one of the phi arguments will be an integer constant. In the
919 future, this could be extended to also handle simple assignments of
920 arithmetic operations. */
921 if (gimple_code (def_stmt
) != GIMPLE_PHI
)
924 /* Avoid infinite recursion. */
925 if (visited_bbs
->add (var_bb
))
928 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
929 int next_path_length
= 0;
930 basic_block last_bb_in_path
= path
->last ();
932 if (loop_containing_stmt (phi
)->header
== gimple_bb (phi
))
934 /* Do not walk through more than one loop PHI node. */
937 seen_loop_phi
= true;
940 /* Following the chain of SSA_NAME definitions, we jumped from a definition in
941 LAST_BB_IN_PATH to a definition in VAR_BB. When these basic blocks are
942 different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB. */
943 if (var_bb
!= last_bb_in_path
)
948 vec
<basic_block
, va_gc
> *next_path
;
949 vec_alloc (next_path
, n_basic_blocks_for_fn (cfun
));
951 FOR_EACH_EDGE (e
, ei
, last_bb_in_path
->preds
)
953 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
955 if (fsm_find_thread_path (var_bb
, e
->src
, next_path
, visited_bbs
,
956 e
->src
->loop_father
))
961 /* If there is more than one path, stop. */
964 vec_free (next_path
);
969 /* Stop if we have not found a path: this could occur when the recursion
970 is stopped by one of the bounds. */
973 vec_free (next_path
);
977 /* Append all the nodes from NEXT_PATH to PATH. */
978 vec_safe_splice (path
, next_path
);
979 next_path_length
= next_path
->length ();
980 vec_free (next_path
);
983 gcc_assert (path
->last () == var_bb
);
985 /* Iterate over the arguments of PHI. */
987 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
989 tree arg
= gimple_phi_arg_def (phi
, i
);
990 basic_block bbi
= gimple_phi_arg_edge (phi
, i
)->src
;
992 /* Skip edges pointing outside the current loop. */
993 if (!arg
|| var_bb
->loop_father
!= bbi
->loop_father
)
996 if (TREE_CODE (arg
) == SSA_NAME
)
998 vec_safe_push (path
, bbi
);
999 /* Recursively follow SSA_NAMEs looking for a constant definition. */
1000 fsm_find_control_statement_thread_paths (arg
, visited_bbs
, path
,
1007 if (TREE_CODE (arg
) != INTEGER_CST
)
1010 int path_length
= path
->length ();
1011 /* A path with less than 2 basic blocks should not be jump-threaded. */
1012 if (path_length
< 2)
1015 if (path_length
> PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH
))
1017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1018 fprintf (dump_file
, "FSM jump-thread path not considered: "
1019 "the number of basic blocks on the path "
1020 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
1024 if (max_threaded_paths
<= 0)
1026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1027 fprintf (dump_file
, "FSM jump-thread path not considered: "
1028 "the number of previously recorded FSM paths to thread "
1029 "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
1033 /* Add BBI to the path. */
1034 vec_safe_push (path
, bbi
);
1038 gimple_stmt_iterator gsi
;
1040 loop_p loop
= (*path
)[0]->loop_father
;
1041 bool path_crosses_loops
= false;
1043 /* Count the number of instructions on the path: as these instructions
1044 will have to be duplicated, we will not record the path if there are
1045 too many instructions on the path. Also check that all the blocks in
1046 the path belong to a single loop. */
1047 for (j
= 1; j
< path_length
- 1; j
++)
1049 basic_block bb
= (*path
)[j
];
1051 if (bb
->loop_father
!= loop
)
1053 path_crosses_loops
= true;
1057 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1059 gimple stmt
= gsi_stmt (gsi
);
1060 /* Do not count empty statements and labels. */
1061 if (gimple_code (stmt
) != GIMPLE_NOP
1062 && gimple_code (stmt
) != GIMPLE_LABEL
1063 && !is_gimple_debug (stmt
))
1068 if (path_crosses_loops
)
1070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1071 fprintf (dump_file
, "FSM jump-thread path not considered: "
1072 "the path crosses loops.\n");
1077 if (n_insns
>= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS
))
1079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1080 fprintf (dump_file
, "FSM jump-thread path not considered: "
1081 "the number of instructions on the path "
1082 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
1087 vec
<jump_thread_edge
*> *jump_thread_path
1088 = new vec
<jump_thread_edge
*> ();
1090 /* Record the edges between the blocks in PATH. */
1091 for (j
= 0; j
< path_length
- 1; j
++)
1093 edge e
= find_edge ((*path
)[path_length
- j
- 1],
1094 (*path
)[path_length
- j
- 2]);
1096 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_FSM_THREAD
);
1097 jump_thread_path
->safe_push (x
);
1100 /* Add the edge taken when the control variable has value ARG. */
1101 edge taken_edge
= find_taken_edge ((*path
)[0], arg
);
1103 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
1104 jump_thread_path
->safe_push (x
);
1106 register_jump_thread (jump_thread_path
);
1107 --max_threaded_paths
;
1109 /* Remove BBI from the path. */
1113 /* Remove all the nodes that we added from NEXT_PATH. */
1114 if (next_path_length
)
1115 vec_safe_truncate (path
, (path
->length () - next_path_length
));
1118 /* We are exiting E->src, see if E->dest ends with a conditional
1119 jump which has a known value when reached via E.
1121 E->dest can have arbitrary side effects which, if threading is
1122 successful, will be maintained.
1124 Special care is necessary if E is a back edge in the CFG as we
1125 may have already recorded equivalences for E->dest into our
1126 various tables, including the result of the conditional at
1127 the end of E->dest. Threading opportunities are severely
1128 limited in that case to avoid short-circuiting the loop
1131 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1132 to avoid allocating memory.
1134 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1135 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1138 STACK is used to undo temporary equivalences created during the walk of
1141 SIMPLIFY is a pass-specific function used to simplify statements.
1143 Our caller is responsible for restoring the state of the expression
1144 and const_and_copies stacks.
1146 Positive return value is success. Zero return value is failure, but
1147 the block can still be duplicated as a joiner in a jump thread path,
1148 negative indicates the block should not be duplicated and thus is not
1149 suitable for a joiner in a jump threading path. */
1152 thread_through_normal_block (edge e
,
1154 bool handle_dominating_asserts
,
1155 const_and_copies
*const_and_copies
,
1156 tree (*simplify
) (gimple
, gimple
),
1157 vec
<jump_thread_edge
*> *path
,
1159 bool *backedge_seen_p
)
1161 /* If we have traversed a backedge, then we do not want to look
1162 at certain expressions in the table that can not be relied upon.
1163 Luckily the only code that looked at those expressions is the
1164 SIMPLIFY callback, which we replace if we can no longer use it. */
1165 if (*backedge_seen_p
)
1166 simplify
= dummy_simplify
;
1168 /* PHIs create temporary equivalences.
1169 Note that if we found a PHI that made the block non-threadable, then
1170 we need to bubble that up to our caller in the same manner we do
1171 when we prematurely stop processing statements below. */
1172 if (!record_temporary_equivalences_from_phis (e
, const_and_copies
))
1175 /* Now walk each statement recording any context sensitive
1176 temporary equivalences we can detect. */
1178 = record_temporary_equivalences_from_stmts_at_dest (e
, const_and_copies
, simplify
,
1181 /* There's two reasons STMT might be null, and distinguishing
1182 between them is important.
1184 First the block may not have had any statements. For example, it
1185 might have some PHIs and unconditionally transfer control elsewhere.
1186 Such blocks are suitable for jump threading, particularly as a
1189 The second reason would be if we did not process all the statements
1190 in the block (because there were too many to make duplicating the
1191 block profitable. If we did not look at all the statements, then
1192 we may not have invalidated everything needing invalidation. Thus
1193 we must signal to our caller that this block is not suitable for
1194 use as a joiner in a threading path. */
1197 /* First case. The statement simply doesn't have any instructions, but
1199 if (gsi_end_p (gsi_start_nondebug_bb (e
->dest
))
1200 && !gsi_end_p (gsi_start_phis (e
->dest
)))
1207 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1209 if (gimple_code (stmt
) == GIMPLE_COND
1210 || gimple_code (stmt
) == GIMPLE_GOTO
1211 || gimple_code (stmt
) == GIMPLE_SWITCH
)
1215 /* Extract and simplify the condition. */
1216 cond
= simplify_control_stmt_condition (e
, stmt
, dummy_cond
, simplify
,
1217 handle_dominating_asserts
);
1222 if (is_gimple_min_invariant (cond
))
1224 edge taken_edge
= find_taken_edge (e
->dest
, cond
);
1225 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
1227 /* DEST could be NULL for a computed jump to an absolute
1231 || bitmap_bit_p (visited
, dest
->index
))
1234 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1235 first edge on the path. */
1236 if (path
->length () == 0)
1239 = new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1240 path
->safe_push (x
);
1241 *backedge_seen_p
|= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1245 = new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_BLOCK
);
1246 path
->safe_push (x
);
1247 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1248 if (*backedge_seen_p
)
1249 simplify
= dummy_simplify
;
1251 /* See if we can thread through DEST as well, this helps capture
1252 secondary effects of threading without having to re-run DOM or
1255 We don't want to thread back to a block we have already
1256 visited. This may be overly conservative. */
1257 bitmap_set_bit (visited
, dest
->index
);
1258 bitmap_set_bit (visited
, e
->dest
->index
);
1259 thread_around_empty_blocks (taken_edge
,
1261 handle_dominating_asserts
,
1269 if (!flag_expensive_optimizations
1270 || optimize_function_for_size_p (cfun
)
1271 || TREE_CODE (cond
) != SSA_NAME
1272 || e
->dest
->loop_father
!= e
->src
->loop_father
1273 || loop_depth (e
->dest
->loop_father
) == 0)
1276 /* When COND cannot be simplified, try to find paths from a control
1277 statement back through the PHI nodes which would affect that control
1279 vec
<basic_block
, va_gc
> *bb_path
;
1280 vec_alloc (bb_path
, n_basic_blocks_for_fn (cfun
));
1281 vec_safe_push (bb_path
, e
->dest
);
1282 hash_set
<basic_block
> *visited_bbs
= new hash_set
<basic_block
>;
1284 max_threaded_paths
= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS
);
1285 fsm_find_control_statement_thread_paths (cond
, visited_bbs
, bb_path
,
1294 /* We are exiting E->src, see if E->dest ends with a conditional
1295 jump which has a known value when reached via E.
1297 Special care is necessary if E is a back edge in the CFG as we
1298 may have already recorded equivalences for E->dest into our
1299 various tables, including the result of the conditional at
1300 the end of E->dest. Threading opportunities are severely
1301 limited in that case to avoid short-circuiting the loop
1304 Note it is quite common for the first block inside a loop to
1305 end with a conditional which is either always true or always
1306 false when reached via the loop backedge. Thus we do not want
1307 to blindly disable threading across a loop backedge.
1309 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1310 to avoid allocating memory.
1312 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1313 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1316 STACK is used to undo temporary equivalences created during the walk of
1319 SIMPLIFY is a pass-specific function used to simplify statements. */
1322 thread_across_edge (gcond
*dummy_cond
,
1324 bool handle_dominating_asserts
,
1325 const_and_copies
*const_and_copies
,
1326 tree (*simplify
) (gimple
, gimple
))
1328 bitmap visited
= BITMAP_ALLOC (NULL
);
1333 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1334 bitmap_clear (visited
);
1335 bitmap_set_bit (visited
, e
->src
->index
);
1336 bitmap_set_bit (visited
, e
->dest
->index
);
1337 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1339 simplify
= dummy_simplify
;
1341 int threaded
= thread_through_normal_block (e
, dummy_cond
,
1342 handle_dominating_asserts
,
1343 const_and_copies
, simplify
, path
,
1344 visited
, &backedge_seen
);
1347 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1349 const_and_copies
->pop_to_marker ();
1350 BITMAP_FREE (visited
);
1351 register_jump_thread (path
);
1356 /* Negative and zero return values indicate no threading was possible,
1357 thus there should be no edges on the thread path and no need to walk
1358 through the vector entries. */
1359 gcc_assert (path
->length () == 0);
1363 /* A negative status indicates the target block was deemed too big to
1364 duplicate. Just quit now rather than trying to use the block as
1365 a joiner in a jump threading path.
1367 This prevents unnecessary code growth, but more importantly if we
1368 do not look at all the statements in the block, then we may have
1369 missed some invalidations if we had traversed a backedge! */
1372 BITMAP_FREE (visited
);
1373 const_and_copies
->pop_to_marker ();
1378 /* We were unable to determine what out edge from E->dest is taken. However,
1379 we might still be able to thread through successors of E->dest. This
1380 often occurs when E->dest is a joiner block which then fans back out
1381 based on redundant tests.
1383 If so, we'll copy E->dest and redirect the appropriate predecessor to
1384 the copy. Within the copy of E->dest, we'll thread one or more edges
1385 to points deeper in the CFG.
1387 This is a stopgap until we have a more structured approach to path
1394 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1395 we can safely redirect any of the edges. Just punt those cases. */
1396 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1397 if (taken_edge
->flags
& EDGE_ABNORMAL
)
1399 const_and_copies
->pop_to_marker ();
1400 BITMAP_FREE (visited
);
1404 /* Look at each successor of E->dest to see if we can thread through it. */
1405 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1407 /* Push a fresh marker so we can unwind the equivalences created
1408 for each of E->dest's successors. */
1409 const_and_copies
->push_marker ();
1411 /* Avoid threading to any block we have already visited. */
1412 bitmap_clear (visited
);
1413 bitmap_set_bit (visited
, e
->src
->index
);
1414 bitmap_set_bit (visited
, e
->dest
->index
);
1415 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
1416 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1418 /* Record whether or not we were able to thread through a successor
1420 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1421 path
->safe_push (x
);
1423 x
= new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_JOINER_BLOCK
);
1424 path
->safe_push (x
);
1426 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1427 backedge_seen
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1429 simplify
= dummy_simplify
;
1430 found
= thread_around_empty_blocks (taken_edge
,
1432 handle_dominating_asserts
,
1439 simplify
= dummy_simplify
;
1442 found
= thread_through_normal_block (path
->last ()->e
, dummy_cond
,
1443 handle_dominating_asserts
,
1444 const_and_copies
, simplify
, path
, visited
,
1445 &backedge_seen
) > 0;
1447 /* If we were able to thread through a successor of E->dest, then
1448 record the jump threading opportunity. */
1451 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1453 register_jump_thread (path
);
1457 delete_jump_thread_path (path
);
1460 /* And unwind the equivalence table. */
1461 const_and_copies
->pop_to_marker ();
1463 BITMAP_FREE (visited
);
1466 const_and_copies
->pop_to_marker ();