2 Copyright (C) 2005-2014 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"
33 #include "hard-reg-set.h"
36 #include "dominance.h"
37 #include "basic-block.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
46 #include "gimple-iterator.h"
47 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-ssa-propagate.h"
54 #include "tree-ssa-threadupdate.h"
55 #include "langhooks.h"
57 #include "tree-ssa-threadedge.h"
60 /* To avoid code explosion due to jump threading, we limit the
61 number of statements we are going to copy. This variable
62 holds the number of statements currently seen that we'll have
63 to copy as part of the jump threading process. */
64 static int stmt_count
;
66 /* Array to record value-handles per SSA_NAME. */
67 vec
<tree
> ssa_name_values
;
69 /* Set the value for the SSA name NAME to VALUE. */
72 set_ssa_name_value (tree name
, tree value
)
74 if (SSA_NAME_VERSION (name
) >= ssa_name_values
.length ())
75 ssa_name_values
.safe_grow_cleared (SSA_NAME_VERSION (name
) + 1);
76 if (value
&& TREE_OVERFLOW_P (value
))
77 value
= drop_tree_overflow (value
);
78 ssa_name_values
[SSA_NAME_VERSION (name
)] = value
;
81 /* Initialize the per SSA_NAME value-handles array. Returns it. */
83 threadedge_initialize_values (void)
85 gcc_assert (!ssa_name_values
.exists ());
86 ssa_name_values
.create (num_ssa_names
);
89 /* Free the per SSA_NAME value-handle array. */
91 threadedge_finalize_values (void)
93 ssa_name_values
.release ();
96 /* Return TRUE if we may be able to thread an incoming edge into
97 BB to an outgoing edge from BB. Return FALSE otherwise. */
100 potentially_threadable_block (basic_block bb
)
102 gimple_stmt_iterator gsi
;
104 /* If BB has a single successor or a single predecessor, then
105 there is no threading opportunity. */
106 if (single_succ_p (bb
) || single_pred_p (bb
))
109 /* If BB does not end with a conditional, switch or computed goto,
110 then there is no threading opportunity. */
111 gsi
= gsi_last_bb (bb
);
114 || (gimple_code (gsi_stmt (gsi
)) != GIMPLE_COND
115 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_GOTO
116 && gimple_code (gsi_stmt (gsi
)) != GIMPLE_SWITCH
))
122 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
123 argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
124 BB. If no such ASSERT_EXPR is found, return OP. */
127 lhs_of_dominating_assert (tree op
, basic_block bb
, gimple stmt
)
129 imm_use_iterator imm_iter
;
133 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, op
)
135 use_stmt
= USE_STMT (use_p
);
137 && gimple_assign_single_p (use_stmt
)
138 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == ASSERT_EXPR
139 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt
), 0) == op
140 && dominated_by_p (CDI_DOMINATORS
, bb
, gimple_bb (use_stmt
)))
142 return gimple_assign_lhs (use_stmt
);
148 /* We record temporary equivalences created by PHI nodes or
149 statements within the target block. Doing so allows us to
150 identify more jump threading opportunities, even in blocks
153 We keep track of those temporary equivalences in a stack
154 structure so that we can unwind them when we're done processing
155 a particular edge. This routine handles unwinding the data
159 remove_temporary_equivalences (vec
<tree
> *stack
)
161 while (stack
->length () > 0)
163 tree prev_value
, dest
;
165 dest
= stack
->pop ();
167 /* A NULL value indicates we should stop unwinding, otherwise
168 pop off the next entry as they're recorded in pairs. */
172 prev_value
= stack
->pop ();
173 set_ssa_name_value (dest
, prev_value
);
177 /* Record a temporary equivalence, saving enough information so that
178 we can restore the state of recorded equivalences when we're
179 done processing the current edge. */
182 record_temporary_equivalence (tree x
, tree y
, vec
<tree
> *stack
)
184 tree prev_x
= SSA_NAME_VALUE (x
);
186 /* Y may be NULL if we are invalidating entries in the table. */
187 if (y
&& TREE_CODE (y
) == SSA_NAME
)
189 tree tmp
= SSA_NAME_VALUE (y
);
193 set_ssa_name_value (x
, y
);
195 stack
->quick_push (prev_x
);
196 stack
->quick_push (x
);
199 /* Record temporary equivalences created by PHIs at the target of the
200 edge E. Record unwind information for the equivalences onto STACK.
202 If a PHI which prevents threading is encountered, then return FALSE
203 indicating we should not thread this edge, else return TRUE.
205 If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs
206 of any equivalences recorded. We use this to make invalidation after
207 traversing back edges less painful. */
210 record_temporary_equivalences_from_phis (edge e
, vec
<tree
> *stack
)
214 /* Each PHI creates a temporary equivalence, record them.
215 These are context sensitive equivalences and will be removed
217 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
219 gphi
*phi
= gsi
.phi ();
220 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
221 tree dst
= gimple_phi_result (phi
);
223 /* If the desired argument is not the same as this PHI's result
224 and it is set by a PHI in E->dest, then we can not thread
227 && TREE_CODE (src
) == SSA_NAME
228 && gimple_code (SSA_NAME_DEF_STMT (src
)) == GIMPLE_PHI
229 && gimple_bb (SSA_NAME_DEF_STMT (src
)) == e
->dest
)
232 /* We consider any non-virtual PHI as a statement since it
233 count result in a constant assignment or copy operation. */
234 if (!virtual_operand_p (dst
))
237 record_temporary_equivalence (dst
, src
, stack
);
242 /* Fold the RHS of an assignment statement and return it as a tree.
243 May return NULL_TREE if no simplification is possible. */
246 fold_assignment_stmt (gimple stmt
)
248 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
250 switch (get_gimple_rhs_class (subcode
))
252 case GIMPLE_SINGLE_RHS
:
253 return fold (gimple_assign_rhs1 (stmt
));
255 case GIMPLE_UNARY_RHS
:
257 tree lhs
= gimple_assign_lhs (stmt
);
258 tree op0
= gimple_assign_rhs1 (stmt
);
259 return fold_unary (subcode
, TREE_TYPE (lhs
), op0
);
262 case GIMPLE_BINARY_RHS
:
264 tree lhs
= gimple_assign_lhs (stmt
);
265 tree op0
= gimple_assign_rhs1 (stmt
);
266 tree op1
= gimple_assign_rhs2 (stmt
);
267 return fold_binary (subcode
, TREE_TYPE (lhs
), op0
, op1
);
270 case GIMPLE_TERNARY_RHS
:
272 tree lhs
= gimple_assign_lhs (stmt
);
273 tree op0
= gimple_assign_rhs1 (stmt
);
274 tree op1
= gimple_assign_rhs2 (stmt
);
275 tree op2
= gimple_assign_rhs3 (stmt
);
277 /* Sadly, we have to handle conditional assignments specially
278 here, because fold expects all the operands of an expression
279 to be folded before the expression itself is folded, but we
280 can't just substitute the folded condition here. */
281 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
284 return fold_ternary (subcode
, TREE_TYPE (lhs
), op0
, op1
, op2
);
292 /* A new value has been assigned to LHS. If necessary, invalidate any
293 equivalences that are no longer valid. This includes invaliding
294 LHS and any objects that are currently equivalent to LHS.
296 Finding the objects that are currently marked as equivalent to LHS
297 is a bit tricky. We could walk the ssa names and see if any have
298 SSA_NAME_VALUE that is the same as LHS. That's expensive.
300 However, it's far more efficient to look at the unwinding stack as
301 that will have all context sensitive equivalences which are the only
302 ones that we really have to worry about here. */
304 invalidate_equivalences (tree lhs
, vec
<tree
> *stack
)
307 /* The stack is an unwinding stack. If the current element is NULL
308 then it's a "stop unwinding" marker. Else the current marker is
309 the SSA_NAME with an equivalence and the prior entry in the stack
310 is what the current element is equivalent to. */
311 for (int i
= stack
->length() - 1; i
>= 0; i
--)
313 /* Ignore the stop unwinding markers. */
314 if ((*stack
)[i
] == NULL
)
317 /* We want to check the current value of stack[i] to see if
318 it matches LHS. If so, then invalidate. */
319 if (SSA_NAME_VALUE ((*stack
)[i
]) == lhs
)
320 record_temporary_equivalence ((*stack
)[i
], NULL_TREE
, stack
);
322 /* Remember, we're dealing with two elements in this case. */
326 /* And invalidate any known value for LHS itself. */
327 if (SSA_NAME_VALUE (lhs
))
328 record_temporary_equivalence (lhs
, NULL_TREE
, stack
);
331 /* Try to simplify each statement in E->dest, ultimately leading to
332 a simplification of the COND_EXPR at the end of E->dest.
334 Record unwind information for temporary equivalences onto STACK.
336 Use SIMPLIFY (a pointer to a callback function) to further simplify
337 statements using pass specific information.
339 We might consider marking just those statements which ultimately
340 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
341 would be recovered by trying to simplify fewer statements.
343 If we are able to simplify a statement into the form
344 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
345 a context sensitive equivalence which may help us simplify
346 later statements in E->dest. */
349 record_temporary_equivalences_from_stmts_at_dest (edge e
,
351 tree (*simplify
) (gimple
,
356 gimple_stmt_iterator gsi
;
359 max_stmt_count
= PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS
);
361 /* Walk through each statement in the block recording equivalences
362 we discover. Note any equivalences we discover are context
363 sensitive (ie, are dependent on traversing E) and must be unwound
364 when we're finished processing E. */
365 for (gsi
= gsi_start_bb (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
367 tree cached_lhs
= NULL
;
369 stmt
= gsi_stmt (gsi
);
371 /* Ignore empty statements and labels. */
372 if (gimple_code (stmt
) == GIMPLE_NOP
373 || gimple_code (stmt
) == GIMPLE_LABEL
374 || is_gimple_debug (stmt
))
377 /* If the statement has volatile operands, then we assume we
378 can not thread through this block. This is overly
379 conservative in some ways. */
380 if (gimple_code (stmt
) == GIMPLE_ASM
381 && gimple_asm_volatile_p (as_a
<gasm
*> (stmt
)))
384 /* If duplicating this block is going to cause too much code
385 expansion, then do not thread through this block. */
387 if (stmt_count
> max_stmt_count
)
390 /* If this is not a statement that sets an SSA_NAME to a new
391 value, then do not try to simplify this statement as it will
392 not simplify in any way that is helpful for jump threading. */
393 if ((gimple_code (stmt
) != GIMPLE_ASSIGN
394 || TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
395 && (gimple_code (stmt
) != GIMPLE_CALL
396 || gimple_call_lhs (stmt
) == NULL_TREE
397 || TREE_CODE (gimple_call_lhs (stmt
)) != SSA_NAME
))
399 /* STMT might still have DEFS and we need to invalidate any known
400 equivalences for them.
402 Consider if STMT is a GIMPLE_ASM with one or more outputs that
403 feeds a conditional inside a loop. We might derive an equivalence
404 due to the conditional. */
409 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
410 invalidate_equivalences (op
, stack
);
415 /* The result of __builtin_object_size depends on all the arguments
416 of a phi node. Temporarily using only one edge produces invalid
425 r = PHI <&w[2].a[1](2), &a.a[6](3)>
426 __builtin_object_size (r, 0)
428 The result of __builtin_object_size is defined to be the maximum of
429 remaining bytes. If we use only one edge on the phi, the result will
430 change to be the remaining bytes for the corresponding phi argument.
432 Similarly for __builtin_constant_p:
435 __builtin_constant_p (r)
437 Both PHI arguments are constant, but x ? 1 : 2 is still not
440 if (is_gimple_call (stmt
))
442 tree fndecl
= gimple_call_fndecl (stmt
);
444 && (DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_OBJECT_SIZE
445 || DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
))
449 tree lhs
= gimple_get_lhs (stmt
);
450 invalidate_equivalences (lhs
, stack
);
456 /* At this point we have a statement which assigns an RHS to an
457 SSA_VAR on the LHS. We want to try and simplify this statement
458 to expose more context sensitive equivalences which in turn may
459 allow us to simplify the condition at the end of the loop.
461 Handle simple copy operations as well as implied copies from
463 if (gimple_assign_single_p (stmt
)
464 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
465 cached_lhs
= gimple_assign_rhs1 (stmt
);
466 else if (gimple_assign_single_p (stmt
)
467 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == ASSERT_EXPR
)
468 cached_lhs
= TREE_OPERAND (gimple_assign_rhs1 (stmt
), 0);
471 /* A statement that is not a trivial copy or ASSERT_EXPR.
472 We're going to temporarily copy propagate the operands
473 and see if that allows us to simplify this statement. */
477 unsigned int num
, i
= 0;
479 num
= NUM_SSA_OPERANDS (stmt
, (SSA_OP_USE
| SSA_OP_VUSE
));
480 copy
= XCNEWVEC (tree
, num
);
482 /* Make a copy of the uses & vuses into USES_COPY, then cprop into
484 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
487 tree use
= USE_FROM_PTR (use_p
);
490 if (TREE_CODE (use
) == SSA_NAME
)
491 tmp
= SSA_NAME_VALUE (use
);
493 SET_USE (use_p
, tmp
);
496 /* Try to fold/lookup the new expression. Inserting the
497 expression into the hash table is unlikely to help. */
498 if (is_gimple_call (stmt
))
499 cached_lhs
= fold_call_stmt (as_a
<gcall
*> (stmt
), false);
501 cached_lhs
= fold_assignment_stmt (stmt
);
504 || (TREE_CODE (cached_lhs
) != SSA_NAME
505 && !is_gimple_min_invariant (cached_lhs
)))
506 cached_lhs
= (*simplify
) (stmt
, stmt
);
508 /* Restore the statement's original uses/defs. */
510 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
| SSA_OP_VUSE
)
511 SET_USE (use_p
, copy
[i
++]);
516 /* Record the context sensitive equivalence if we were able
517 to simplify this statement.
519 If we have traversed a backedge at some point during threading,
520 then always enter something here. Either a real equivalence,
521 or a NULL_TREE equivalence which is effectively invalidation of
522 prior equivalences. */
524 && (TREE_CODE (cached_lhs
) == SSA_NAME
525 || is_gimple_min_invariant (cached_lhs
)))
526 record_temporary_equivalence (gimple_get_lhs (stmt
), cached_lhs
, stack
);
527 else if (backedge_seen
)
528 invalidate_equivalences (gimple_get_lhs (stmt
), stack
);
533 /* Once we have passed a backedge in the CFG when threading, we do not want to
534 utilize edge equivalences for simplification purpose. They are no longer
535 necessarily valid. We use this callback rather than the ones provided by
536 DOM/VRP to achieve that effect. */
538 dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED
, gimple stmt2 ATTRIBUTE_UNUSED
)
543 /* Simplify the control statement at the end of the block E->dest.
545 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
546 is available to use/clobber in DUMMY_COND.
548 Use SIMPLIFY (a pointer to a callback function) to further simplify
549 a condition using pass specific information.
551 Return the simplified condition or NULL if simplification could
555 simplify_control_stmt_condition (edge e
,
558 tree (*simplify
) (gimple
, gimple
),
559 bool handle_dominating_asserts
)
561 tree cond
, cached_lhs
;
562 enum gimple_code code
= gimple_code (stmt
);
564 /* For comparisons, we have to update both operands, then try
565 to simplify the comparison. */
566 if (code
== GIMPLE_COND
)
569 enum tree_code cond_code
;
571 op0
= gimple_cond_lhs (stmt
);
572 op1
= gimple_cond_rhs (stmt
);
573 cond_code
= gimple_cond_code (stmt
);
575 /* Get the current value of both operands. */
576 if (TREE_CODE (op0
) == SSA_NAME
)
578 for (int i
= 0; i
< 2; i
++)
580 if (TREE_CODE (op0
) == SSA_NAME
581 && SSA_NAME_VALUE (op0
))
582 op0
= SSA_NAME_VALUE (op0
);
588 if (TREE_CODE (op1
) == SSA_NAME
)
590 for (int i
= 0; i
< 2; i
++)
592 if (TREE_CODE (op1
) == SSA_NAME
593 && SSA_NAME_VALUE (op1
))
594 op1
= SSA_NAME_VALUE (op1
);
600 if (handle_dominating_asserts
)
602 /* Now see if the operand was consumed by an ASSERT_EXPR
603 which dominates E->src. If so, we want to replace the
604 operand with the LHS of the ASSERT_EXPR. */
605 if (TREE_CODE (op0
) == SSA_NAME
)
606 op0
= lhs_of_dominating_assert (op0
, e
->src
, stmt
);
608 if (TREE_CODE (op1
) == SSA_NAME
)
609 op1
= lhs_of_dominating_assert (op1
, e
->src
, stmt
);
612 /* We may need to canonicalize the comparison. For
613 example, op0 might be a constant while op1 is an
614 SSA_NAME. Failure to canonicalize will cause us to
615 miss threading opportunities. */
616 if (tree_swap_operands_p (op0
, op1
, false))
619 cond_code
= swap_tree_comparison (cond_code
);
625 /* Stuff the operator and operands into our dummy conditional
627 gimple_cond_set_code (dummy_cond
, cond_code
);
628 gimple_cond_set_lhs (dummy_cond
, op0
);
629 gimple_cond_set_rhs (dummy_cond
, op1
);
631 /* We absolutely do not care about any type conversions
632 we only care about a zero/nonzero value. */
633 fold_defer_overflow_warnings ();
635 cached_lhs
= fold_binary (cond_code
, boolean_type_node
, op0
, op1
);
637 while (CONVERT_EXPR_P (cached_lhs
))
638 cached_lhs
= TREE_OPERAND (cached_lhs
, 0);
640 fold_undefer_overflow_warnings ((cached_lhs
641 && is_gimple_min_invariant (cached_lhs
)),
642 stmt
, WARN_STRICT_OVERFLOW_CONDITIONAL
);
644 /* If we have not simplified the condition down to an invariant,
645 then use the pass specific callback to simplify the condition. */
647 || !is_gimple_min_invariant (cached_lhs
))
648 cached_lhs
= (*simplify
) (dummy_cond
, stmt
);
653 if (code
== GIMPLE_SWITCH
)
654 cond
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
655 else if (code
== GIMPLE_GOTO
)
656 cond
= gimple_goto_dest (stmt
);
660 /* We can have conditionals which just test the state of a variable
661 rather than use a relational operator. These are simpler to handle. */
662 if (TREE_CODE (cond
) == SSA_NAME
)
666 /* Get the variable's current value from the equivalence chains.
668 It is possible to get loops in the SSA_NAME_VALUE chains
669 (consider threading the backedge of a loop where we have
670 a loop invariant SSA_NAME used in the condition. */
673 for (int i
= 0; i
< 2; i
++)
675 if (TREE_CODE (cached_lhs
) == SSA_NAME
676 && SSA_NAME_VALUE (cached_lhs
))
677 cached_lhs
= SSA_NAME_VALUE (cached_lhs
);
683 /* If we're dominated by a suitable ASSERT_EXPR, then
684 update CACHED_LHS appropriately. */
685 if (handle_dominating_asserts
&& TREE_CODE (cached_lhs
) == SSA_NAME
)
686 cached_lhs
= lhs_of_dominating_assert (cached_lhs
, e
->src
, stmt
);
688 /* If we haven't simplified to an invariant yet, then use the
689 pass specific callback to try and simplify it further. */
690 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
691 cached_lhs
= (*simplify
) (stmt
, stmt
);
699 /* Copy debug stmts from DEST's chain of single predecessors up to
700 SRC, so that we don't lose the bindings as PHI nodes are introduced
701 when DEST gains new predecessors. */
703 propagate_threaded_block_debug_into (basic_block dest
, basic_block src
)
705 if (!MAY_HAVE_DEBUG_STMTS
)
708 if (!single_pred_p (dest
))
711 gcc_checking_assert (dest
!= src
);
713 gimple_stmt_iterator gsi
= gsi_after_labels (dest
);
715 const int alloc_count
= 16; // ?? Should this be a PARAM?
717 /* Estimate the number of debug vars overridden in the beginning of
718 DEST, to tell how many we're going to need to begin with. */
719 for (gimple_stmt_iterator si
= gsi
;
720 i
* 4 <= alloc_count
* 3 && !gsi_end_p (si
); gsi_next (&si
))
722 gimple stmt
= gsi_stmt (si
);
723 if (!is_gimple_debug (stmt
))
728 auto_vec
<tree
, alloc_count
> fewvars
;
729 hash_set
<tree
> *vars
= NULL
;
731 /* If we're already starting with 3/4 of alloc_count, go for a
732 hash_set, otherwise start with an unordered stack-allocated
734 if (i
* 4 > alloc_count
* 3)
735 vars
= new hash_set
<tree
>;
737 /* Now go through the initial debug stmts in DEST again, this time
738 actually inserting in VARS or FEWVARS. Don't bother checking for
739 duplicates in FEWVARS. */
740 for (gimple_stmt_iterator si
= gsi
; !gsi_end_p (si
); gsi_next (&si
))
742 gimple stmt
= gsi_stmt (si
);
743 if (!is_gimple_debug (stmt
))
748 if (gimple_debug_bind_p (stmt
))
749 var
= gimple_debug_bind_get_var (stmt
);
750 else if (gimple_debug_source_bind_p (stmt
))
751 var
= gimple_debug_source_bind_get_var (stmt
);
758 fewvars
.quick_push (var
);
761 basic_block bb
= dest
;
765 bb
= single_pred (bb
);
766 for (gimple_stmt_iterator si
= gsi_last_bb (bb
);
767 !gsi_end_p (si
); gsi_prev (&si
))
769 gimple stmt
= gsi_stmt (si
);
770 if (!is_gimple_debug (stmt
))
775 if (gimple_debug_bind_p (stmt
))
776 var
= gimple_debug_bind_get_var (stmt
);
777 else if (gimple_debug_source_bind_p (stmt
))
778 var
= gimple_debug_source_bind_get_var (stmt
);
782 /* Discard debug bind overlaps. ??? Unlike stmts from src,
783 copied into a new block that will precede BB, debug bind
784 stmts in bypassed BBs may actually be discarded if
785 they're overwritten by subsequent debug bind stmts, which
786 might be a problem once we introduce stmt frontier notes
787 or somesuch. Adding `&& bb == src' to the condition
788 below will preserve all potentially relevant debug
790 if (vars
&& vars
->add (var
))
794 int i
= fewvars
.length ();
796 if (fewvars
[i
] == var
)
801 if (fewvars
.length () < (unsigned) alloc_count
)
802 fewvars
.quick_push (var
);
805 vars
= new hash_set
<tree
>;
806 for (i
= 0; i
< alloc_count
; i
++)
807 vars
->add (fewvars
[i
]);
813 stmt
= gimple_copy (stmt
);
814 /* ??? Should we drop the location of the copy to denote
815 they're artificial bindings? */
816 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
819 while (bb
!= src
&& single_pred_p (bb
));
823 else if (fewvars
.exists ())
827 /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it
828 need not be duplicated as part of the CFG/SSA updating process).
830 If it is threadable, add it to PATH and VISITED and recurse, ultimately
831 returning TRUE from the toplevel call. Otherwise do nothing and
834 DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to
835 try and simplify the condition at the end of TAKEN_EDGE->dest. */
837 thread_around_empty_blocks (edge taken_edge
,
839 bool handle_dominating_asserts
,
840 tree (*simplify
) (gimple
, gimple
),
842 vec
<jump_thread_edge
*> *path
,
843 bool *backedge_seen_p
)
845 basic_block bb
= taken_edge
->dest
;
846 gimple_stmt_iterator gsi
;
850 /* The key property of these blocks is that they need not be duplicated
851 when threading. Thus they can not have visible side effects such
853 if (!gsi_end_p (gsi_start_phis (bb
)))
856 /* Skip over DEBUG statements at the start of the block. */
857 gsi
= gsi_start_nondebug_bb (bb
);
859 /* If the block has no statements, but does have a single successor, then
860 it's just a forwarding block and we can thread through it trivially.
862 However, note that just threading through empty blocks with single
863 successors is not inherently profitable. For the jump thread to
864 be profitable, we must avoid a runtime conditional.
866 By taking the return value from the recursive call, we get the
867 desired effect of returning TRUE when we found a profitable jump
868 threading opportunity and FALSE otherwise.
870 This is particularly important when this routine is called after
871 processing a joiner block. Returning TRUE too aggressively in
872 that case results in pointless duplication of the joiner block. */
875 if (single_succ_p (bb
))
877 taken_edge
= single_succ_edge (bb
);
878 if (!bitmap_bit_p (visited
, taken_edge
->dest
->index
))
881 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
883 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
884 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
885 if (*backedge_seen_p
)
886 simplify
= dummy_simplify
;
887 return thread_around_empty_blocks (taken_edge
,
889 handle_dominating_asserts
,
897 /* We have a block with no statements, but multiple successors? */
901 /* The only real statements this block can have are a control
902 flow altering statement. Anything else stops the thread. */
903 stmt
= gsi_stmt (gsi
);
904 if (gimple_code (stmt
) != GIMPLE_COND
905 && gimple_code (stmt
) != GIMPLE_GOTO
906 && gimple_code (stmt
) != GIMPLE_SWITCH
)
909 /* If we have traversed a backedge, then we do not want to look
910 at certain expressions in the table that can not be relied upon.
911 Luckily the only code that looked at those expressions is the
912 SIMPLIFY callback, which we replace if we can no longer use it. */
913 if (*backedge_seen_p
)
914 simplify
= dummy_simplify
;
916 /* Extract and simplify the condition. */
917 cond
= simplify_control_stmt_condition (taken_edge
, stmt
, dummy_cond
,
918 simplify
, handle_dominating_asserts
);
920 /* If the condition can be statically computed and we have not already
921 visited the destination edge, then add the taken edge to our thread
923 if (cond
&& is_gimple_min_invariant (cond
))
925 taken_edge
= find_taken_edge (bb
, cond
);
927 if (bitmap_bit_p (visited
, taken_edge
->dest
->index
))
929 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
932 = new jump_thread_edge (taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
934 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
935 if (*backedge_seen_p
)
936 simplify
= dummy_simplify
;
938 thread_around_empty_blocks (taken_edge
,
940 handle_dominating_asserts
,
951 /* We are exiting E->src, see if E->dest ends with a conditional
952 jump which has a known value when reached via E.
954 E->dest can have arbitrary side effects which, if threading is
955 successful, will be maintained.
957 Special care is necessary if E is a back edge in the CFG as we
958 may have already recorded equivalences for E->dest into our
959 various tables, including the result of the conditional at
960 the end of E->dest. Threading opportunities are severely
961 limited in that case to avoid short-circuiting the loop
964 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
965 to avoid allocating memory.
967 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
968 the simplified condition with left-hand sides of ASSERT_EXPRs they are
971 STACK is used to undo temporary equivalences created during the walk of
974 SIMPLIFY is a pass-specific function used to simplify statements.
976 Our caller is responsible for restoring the state of the expression
977 and const_and_copies stacks.
979 Positive return value is success. Zero return value is failure, but
980 the block can still be duplicated as a joiner in a jump thread path,
981 negative indicates the block should not be duplicated and thus is not
982 suitable for a joiner in a jump threading path. */
985 thread_through_normal_block (edge e
,
987 bool handle_dominating_asserts
,
989 tree (*simplify
) (gimple
, gimple
),
990 vec
<jump_thread_edge
*> *path
,
992 bool *backedge_seen_p
)
994 /* If we have traversed a backedge, then we do not want to look
995 at certain expressions in the table that can not be relied upon.
996 Luckily the only code that looked at those expressions is the
997 SIMPLIFY callback, which we replace if we can no longer use it. */
998 if (*backedge_seen_p
)
999 simplify
= dummy_simplify
;
1001 /* PHIs create temporary equivalences.
1002 Note that if we found a PHI that made the block non-threadable, then
1003 we need to bubble that up to our caller in the same manner we do
1004 when we prematurely stop processing statements below. */
1005 if (!record_temporary_equivalences_from_phis (e
, stack
))
1008 /* Now walk each statement recording any context sensitive
1009 temporary equivalences we can detect. */
1011 = record_temporary_equivalences_from_stmts_at_dest (e
, stack
, simplify
,
1014 /* If we didn't look at all the statements, the most likely reason is
1015 there were too many and thus duplicating this block is not profitable.
1017 Also note if we do not look at all the statements, then we may not
1018 have invalidated equivalences that are no longer valid if we threaded
1019 around a loop. Thus we must signal to our caller that this block
1020 is not suitable for use as a joiner in a threading path. */
1024 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1026 if (gimple_code (stmt
) == GIMPLE_COND
1027 || gimple_code (stmt
) == GIMPLE_GOTO
1028 || gimple_code (stmt
) == GIMPLE_SWITCH
)
1032 /* Extract and simplify the condition. */
1033 cond
= simplify_control_stmt_condition (e
, stmt
, dummy_cond
, simplify
,
1034 handle_dominating_asserts
);
1036 if (cond
&& is_gimple_min_invariant (cond
))
1038 edge taken_edge
= find_taken_edge (e
->dest
, cond
);
1039 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
1041 /* DEST could be NULL for a computed jump to an absolute
1045 || bitmap_bit_p (visited
, dest
->index
))
1048 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1049 first edge on the path. */
1050 if (path
->length () == 0)
1053 = new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1054 path
->safe_push (x
);
1055 *backedge_seen_p
|= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1059 = new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_BLOCK
);
1060 path
->safe_push (x
);
1061 *backedge_seen_p
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1062 if (*backedge_seen_p
)
1063 simplify
= dummy_simplify
;
1065 /* See if we can thread through DEST as well, this helps capture
1066 secondary effects of threading without having to re-run DOM or
1069 We don't want to thread back to a block we have already
1070 visited. This may be overly conservative. */
1071 bitmap_set_bit (visited
, dest
->index
);
1072 bitmap_set_bit (visited
, e
->dest
->index
);
1073 thread_around_empty_blocks (taken_edge
,
1075 handle_dominating_asserts
,
1086 /* We are exiting E->src, see if E->dest ends with a conditional
1087 jump which has a known value when reached via E.
1089 Special care is necessary if E is a back edge in the CFG as we
1090 may have already recorded equivalences for E->dest into our
1091 various tables, including the result of the conditional at
1092 the end of E->dest. Threading opportunities are severely
1093 limited in that case to avoid short-circuiting the loop
1096 Note it is quite common for the first block inside a loop to
1097 end with a conditional which is either always true or always
1098 false when reached via the loop backedge. Thus we do not want
1099 to blindly disable threading across a loop backedge.
1101 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1102 to avoid allocating memory.
1104 HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of
1105 the simplified condition with left-hand sides of ASSERT_EXPRs they are
1108 STACK is used to undo temporary equivalences created during the walk of
1111 SIMPLIFY is a pass-specific function used to simplify statements. */
1114 thread_across_edge (gcond
*dummy_cond
,
1116 bool handle_dominating_asserts
,
1118 tree (*simplify
) (gimple
, gimple
))
1120 bitmap visited
= BITMAP_ALLOC (NULL
);
1125 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1126 bitmap_clear (visited
);
1127 bitmap_set_bit (visited
, e
->src
->index
);
1128 bitmap_set_bit (visited
, e
->dest
->index
);
1129 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1131 simplify
= dummy_simplify
;
1133 int threaded
= thread_through_normal_block (e
, dummy_cond
,
1134 handle_dominating_asserts
,
1135 stack
, simplify
, path
,
1136 visited
, &backedge_seen
);
1139 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1141 remove_temporary_equivalences (stack
);
1142 BITMAP_FREE (visited
);
1143 register_jump_thread (path
);
1148 /* Negative and zero return values indicate no threading was possible,
1149 thus there should be no edges on the thread path and no need to walk
1150 through the vector entries. */
1151 gcc_assert (path
->length () == 0);
1154 /* A negative status indicates the target block was deemed too big to
1155 duplicate. Just quit now rather than trying to use the block as
1156 a joiner in a jump threading path.
1158 This prevents unnecessary code growth, but more importantly if we
1159 do not look at all the statements in the block, then we may have
1160 missed some invalidations if we had traversed a backedge! */
1163 BITMAP_FREE (visited
);
1164 remove_temporary_equivalences (stack
);
1169 /* We were unable to determine what out edge from E->dest is taken. However,
1170 we might still be able to thread through successors of E->dest. This
1171 often occurs when E->dest is a joiner block which then fans back out
1172 based on redundant tests.
1174 If so, we'll copy E->dest and redirect the appropriate predecessor to
1175 the copy. Within the copy of E->dest, we'll thread one or more edges
1176 to points deeper in the CFG.
1178 This is a stopgap until we have a more structured approach to path
1185 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1186 we can safely redirect any of the edges. Just punt those cases. */
1187 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1188 if (taken_edge
->flags
& EDGE_ABNORMAL
)
1190 remove_temporary_equivalences (stack
);
1191 BITMAP_FREE (visited
);
1195 /* Look at each successor of E->dest to see if we can thread through it. */
1196 FOR_EACH_EDGE (taken_edge
, ei
, e
->dest
->succs
)
1198 /* Push a fresh marker so we can unwind the equivalences created
1199 for each of E->dest's successors. */
1200 stack
->safe_push (NULL_TREE
);
1202 /* Avoid threading to any block we have already visited. */
1203 bitmap_clear (visited
);
1204 bitmap_set_bit (visited
, e
->src
->index
);
1205 bitmap_set_bit (visited
, e
->dest
->index
);
1206 bitmap_set_bit (visited
, taken_edge
->dest
->index
);
1207 vec
<jump_thread_edge
*> *path
= new vec
<jump_thread_edge
*> ();
1209 /* Record whether or not we were able to thread through a successor
1211 jump_thread_edge
*x
= new jump_thread_edge (e
, EDGE_START_JUMP_THREAD
);
1212 path
->safe_push (x
);
1214 x
= new jump_thread_edge (taken_edge
, EDGE_COPY_SRC_JOINER_BLOCK
);
1215 path
->safe_push (x
);
1217 backedge_seen
= ((e
->flags
& EDGE_DFS_BACK
) != 0);
1218 backedge_seen
|= ((taken_edge
->flags
& EDGE_DFS_BACK
) != 0);
1220 simplify
= dummy_simplify
;
1221 found
= thread_around_empty_blocks (taken_edge
,
1223 handle_dominating_asserts
,
1230 simplify
= dummy_simplify
;
1233 found
= thread_through_normal_block (path
->last ()->e
, dummy_cond
,
1234 handle_dominating_asserts
,
1235 stack
, simplify
, path
, visited
,
1236 &backedge_seen
) > 0;
1238 /* If we were able to thread through a successor of E->dest, then
1239 record the jump threading opportunity. */
1242 propagate_threaded_block_debug_into (path
->last ()->e
->dest
,
1244 register_jump_thread (path
);
1248 delete_jump_thread_path (path
);
1251 /* And unwind the equivalence table. */
1252 remove_temporary_equivalences (stack
);
1254 BITMAP_FREE (visited
);
1257 remove_temporary_equivalences (stack
);