1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
28 #include "fold-const.h"
29 #include "stor-layout.h"
32 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
37 #include "gimple-pretty-print.h"
38 #include "tree-ssa-alias.h"
39 #include "internal-fn.h"
40 #include "gimple-fold.h"
42 #include "gimple-expr.h"
46 #include "gimple-iterator.h"
47 #include "gimplify-me.h"
48 #include "gimple-ssa.h"
50 #include "tree-phinodes.h"
51 #include "ssa-iterators.h"
52 #include "stringpool.h"
53 #include "tree-ssanames.h"
56 #include "insn-config.h"
66 #include "tree-pass.h"
67 #include "langhooks.h"
68 #include "diagnostic.h"
70 #include "insn-codes.h"
72 #include "tree-ssa-propagate.h"
73 #include "tree-ssa-dom.h"
75 #include "tree-cfgcleanup.h"
76 #include "tree-into-ssa.h"
79 /* This pass propagates the RHS of assignment statements into use
80 sites of the LHS of the assignment. It's basically a specialized
81 form of tree combination. It is hoped all of this can disappear
82 when we have a generalized tree combiner.
84 One class of common cases we handle is forward propagating a single use
85 variable into a COND_EXPR.
89 if (x) goto ... else goto ...
91 Will be transformed into:
94 if (a COND b) goto ... else goto ...
96 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
98 Or (assuming c1 and c2 are constants):
102 if (x EQ/NEQ c2) goto ... else goto ...
104 Will be transformed into:
107 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
109 Similarly for x = a - c1.
115 if (x) goto ... else goto ...
117 Will be transformed into:
120 if (a == 0) goto ... else goto ...
122 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
123 For these cases, we propagate A into all, possibly more than one,
124 COND_EXPRs that use X.
130 if (x) goto ... else goto ...
132 Will be transformed into:
135 if (a != 0) goto ... else goto ...
137 (Assuming a is an integral type and x is a boolean or x is an
138 integral and a is a boolean.)
140 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
141 For these cases, we propagate A into all, possibly more than one,
142 COND_EXPRs that use X.
144 In addition to eliminating the variable and the statement which assigns
145 a value to the variable, we may be able to later thread the jump without
146 adding insane complexity in the dominator optimizer.
148 Also note these transformations can cascade. We handle this by having
149 a worklist of COND_EXPR statements to examine. As we make a change to
150 a statement, we put it back on the worklist to examine on the next
151 iteration of the main loop.
153 A second class of propagation opportunities arises for ADDR_EXPR
164 ptr = (type1*)&type2var;
167 Will get turned into (if type1 and type2 are the same size
168 and neither have volatile on them):
169 res = VIEW_CONVERT_EXPR<type1>(type2var)
174 ptr2 = ptr + <constant>;
178 ptr2 = &x[constant/elementsize];
183 offset = index * element_size;
184 offset_p = (pointer) offset;
185 ptr2 = ptr + offset_p
187 Will get turned into:
195 Provided that decl has known alignment >= 2, will get turned into
199 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
200 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
203 This will (of course) be extended as other needs arise. */
205 static bool forward_propagate_addr_expr (tree
, tree
, bool);
207 /* Set to true if we delete dead edges during the optimization. */
208 static bool cfg_changed
;
210 static tree
rhs_to_tree (tree type
, gimple stmt
);
212 static bitmap to_purge
;
214 /* Const-and-copy lattice. */
215 static vec
<tree
> lattice
;
217 /* Set the lattice entry for NAME to VAL. */
219 fwprop_set_lattice_val (tree name
, tree val
)
221 if (TREE_CODE (name
) == SSA_NAME
)
223 if (SSA_NAME_VERSION (name
) >= lattice
.length ())
225 lattice
.reserve (num_ssa_names
- lattice
.length ());
226 lattice
.quick_grow_cleared (num_ssa_names
);
228 lattice
[SSA_NAME_VERSION (name
)] = val
;
232 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
234 fwprop_invalidate_lattice (tree name
)
237 && TREE_CODE (name
) == SSA_NAME
238 && SSA_NAME_VERSION (name
) < lattice
.length ())
239 lattice
[SSA_NAME_VERSION (name
)] = NULL_TREE
;
243 /* Get the statement we can propagate from into NAME skipping
244 trivial copies. Returns the statement which defines the
245 propagation source or NULL_TREE if there is no such one.
246 If SINGLE_USE_ONLY is set considers only sources which have
247 a single use chain up to NAME. If SINGLE_USE_P is non-null,
248 it is set to whether the chain to NAME is a single use chain
249 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
252 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
254 bool single_use
= true;
257 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
259 if (!has_single_use (name
))
266 /* If name is defined by a PHI node or is the default def, bail out. */
267 if (!is_gimple_assign (def_stmt
))
270 /* If def_stmt is a simple copy, continue looking. */
271 if (gimple_assign_rhs_code (def_stmt
) == SSA_NAME
)
272 name
= gimple_assign_rhs1 (def_stmt
);
275 if (!single_use_only
&& single_use_p
)
276 *single_use_p
= single_use
;
283 /* Checks if the destination ssa name in DEF_STMT can be used as
284 propagation source. Returns true if so, otherwise false. */
287 can_propagate_from (gimple def_stmt
)
289 gcc_assert (is_gimple_assign (def_stmt
));
291 /* If the rhs has side-effects we cannot propagate from it. */
292 if (gimple_has_volatile_ops (def_stmt
))
295 /* If the rhs is a load we cannot propagate from it. */
296 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_reference
297 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_declaration
)
300 /* Constants can be always propagated. */
301 if (gimple_assign_single_p (def_stmt
)
302 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
305 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
306 if (stmt_references_abnormal_ssa_name (def_stmt
))
309 /* If the definition is a conversion of a pointer to a function type,
310 then we can not apply optimizations as some targets require
311 function pointers to be canonicalized and in this case this
312 optimization could eliminate a necessary canonicalization. */
313 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
315 tree rhs
= gimple_assign_rhs1 (def_stmt
);
316 if (POINTER_TYPE_P (TREE_TYPE (rhs
))
317 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs
))) == FUNCTION_TYPE
)
324 /* Remove a chain of dead statements starting at the definition of
325 NAME. The chain is linked via the first operand of the defining statements.
326 If NAME was replaced in its only use then this function can be used
327 to clean up dead stmts. The function handles already released SSA
329 Returns true if cleanup-cfg has to run. */
332 remove_prop_source_from_use (tree name
)
334 gimple_stmt_iterator gsi
;
336 bool cfg_changed
= false;
341 if (SSA_NAME_IN_FREE_LIST (name
)
342 || SSA_NAME_IS_DEFAULT_DEF (name
)
343 || !has_zero_uses (name
))
346 stmt
= SSA_NAME_DEF_STMT (name
);
347 if (gimple_code (stmt
) == GIMPLE_PHI
348 || gimple_has_side_effects (stmt
))
351 bb
= gimple_bb (stmt
);
352 gsi
= gsi_for_stmt (stmt
);
353 unlink_stmt_vdef (stmt
);
354 if (gsi_remove (&gsi
, true))
355 bitmap_set_bit (to_purge
, bb
->index
);
356 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
359 name
= is_gimple_assign (stmt
) ? gimple_assign_rhs1 (stmt
) : NULL_TREE
;
360 } while (name
&& TREE_CODE (name
) == SSA_NAME
);
365 /* Return the rhs of a gassign *STMT in a form of a single tree,
366 converted to type TYPE.
368 This should disappear, but is needed so we can combine expressions and use
369 the fold() interfaces. Long term, we need to develop folding and combine
370 routines that deal with gimple exclusively . */
373 rhs_to_tree (tree type
, gimple stmt
)
375 location_t loc
= gimple_location (stmt
);
376 enum tree_code code
= gimple_assign_rhs_code (stmt
);
377 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
378 return fold_build3_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
379 gimple_assign_rhs2 (stmt
),
380 gimple_assign_rhs3 (stmt
));
381 else if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
382 return fold_build2_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
383 gimple_assign_rhs2 (stmt
));
384 else if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
385 return build1 (code
, type
, gimple_assign_rhs1 (stmt
));
386 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
387 return gimple_assign_rhs1 (stmt
);
392 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
393 the folded result in a form suitable for COND_EXPR_COND or
394 NULL_TREE, if there is no suitable simplified form. If
395 INVARIANT_ONLY is true only gimple_min_invariant results are
396 considered simplified. */
399 combine_cond_expr_cond (gimple stmt
, enum tree_code code
, tree type
,
400 tree op0
, tree op1
, bool invariant_only
)
404 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
406 fold_defer_overflow_warnings ();
407 t
= fold_binary_loc (gimple_location (stmt
), code
, type
, op0
, op1
);
410 fold_undefer_overflow_warnings (false, NULL
, 0);
414 /* Require that we got a boolean type out if we put one in. */
415 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
417 /* Canonicalize the combined condition for use in a COND_EXPR. */
418 t
= canonicalize_cond_expr_cond (t
);
420 /* Bail out if we required an invariant but didn't get one. */
421 if (!t
|| (invariant_only
&& !is_gimple_min_invariant (t
)))
423 fold_undefer_overflow_warnings (false, NULL
, 0);
427 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt
), stmt
, 0);
432 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
433 of its operand. Return a new comparison tree or NULL_TREE if there
434 were no simplifying combines. */
437 forward_propagate_into_comparison_1 (gimple stmt
,
438 enum tree_code code
, tree type
,
441 tree tmp
= NULL_TREE
;
442 tree rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
443 bool single_use0_p
= false, single_use1_p
= false;
445 /* For comparisons use the first operand, that is likely to
446 simplify comparisons against constants. */
447 if (TREE_CODE (op0
) == SSA_NAME
)
449 gimple def_stmt
= get_prop_source_stmt (op0
, false, &single_use0_p
);
450 if (def_stmt
&& can_propagate_from (def_stmt
))
452 enum tree_code def_code
= gimple_assign_rhs_code (def_stmt
);
453 bool invariant_only_p
= !single_use0_p
;
455 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
457 /* Always combine comparisons or conversions from booleans. */
458 if (TREE_CODE (op1
) == INTEGER_CST
459 && ((CONVERT_EXPR_CODE_P (def_code
)
460 && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0
, 0)))
462 || TREE_CODE_CLASS (def_code
) == tcc_comparison
))
463 invariant_only_p
= false;
465 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
466 rhs0
, op1
, invariant_only_p
);
472 /* If that wasn't successful, try the second operand. */
473 if (TREE_CODE (op1
) == SSA_NAME
)
475 gimple def_stmt
= get_prop_source_stmt (op1
, false, &single_use1_p
);
476 if (def_stmt
&& can_propagate_from (def_stmt
))
478 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
479 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
480 op0
, rhs1
, !single_use1_p
);
486 /* If that wasn't successful either, try both operands. */
487 if (rhs0
!= NULL_TREE
488 && rhs1
!= NULL_TREE
)
489 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
491 !(single_use0_p
&& single_use1_p
));
496 /* Propagate from the ssa name definition statements of the assignment
497 from a comparison at *GSI into the conditional if that simplifies it.
498 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
499 otherwise returns 0. */
502 forward_propagate_into_comparison (gimple_stmt_iterator
*gsi
)
504 gimple stmt
= gsi_stmt (*gsi
);
506 bool cfg_changed
= false;
507 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
508 tree rhs1
= gimple_assign_rhs1 (stmt
);
509 tree rhs2
= gimple_assign_rhs2 (stmt
);
511 /* Combine the comparison with defining statements. */
512 tmp
= forward_propagate_into_comparison_1 (stmt
,
513 gimple_assign_rhs_code (stmt
),
515 if (tmp
&& useless_type_conversion_p (type
, TREE_TYPE (tmp
)))
517 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
519 update_stmt (gsi_stmt (*gsi
));
521 if (TREE_CODE (rhs1
) == SSA_NAME
)
522 cfg_changed
|= remove_prop_source_from_use (rhs1
);
523 if (TREE_CODE (rhs2
) == SSA_NAME
)
524 cfg_changed
|= remove_prop_source_from_use (rhs2
);
525 return cfg_changed
? 2 : 1;
531 /* Propagate from the ssa name definition statements of COND_EXPR
532 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
533 Returns zero if no statement was changed, one if there were
534 changes and two if cfg_cleanup needs to run.
536 This must be kept in sync with forward_propagate_into_cond. */
539 forward_propagate_into_gimple_cond (gcond
*stmt
)
542 enum tree_code code
= gimple_cond_code (stmt
);
543 bool cfg_changed
= false;
544 tree rhs1
= gimple_cond_lhs (stmt
);
545 tree rhs2
= gimple_cond_rhs (stmt
);
547 /* We can do tree combining on SSA_NAME and comparison expressions. */
548 if (TREE_CODE_CLASS (gimple_cond_code (stmt
)) != tcc_comparison
)
551 tmp
= forward_propagate_into_comparison_1 (stmt
, code
,
556 if (dump_file
&& tmp
)
558 fprintf (dump_file
, " Replaced '");
559 print_gimple_expr (dump_file
, stmt
, 0, 0);
560 fprintf (dump_file
, "' with '");
561 print_generic_expr (dump_file
, tmp
, 0);
562 fprintf (dump_file
, "'\n");
565 gimple_cond_set_condition_from_tree (stmt
, unshare_expr (tmp
));
568 if (TREE_CODE (rhs1
) == SSA_NAME
)
569 cfg_changed
|= remove_prop_source_from_use (rhs1
);
570 if (TREE_CODE (rhs2
) == SSA_NAME
)
571 cfg_changed
|= remove_prop_source_from_use (rhs2
);
572 return (cfg_changed
|| is_gimple_min_invariant (tmp
)) ? 2 : 1;
575 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
576 if ((TREE_CODE (TREE_TYPE (rhs1
)) == BOOLEAN_TYPE
577 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
578 && TYPE_PRECISION (TREE_TYPE (rhs1
)) == 1))
580 && integer_zerop (rhs2
))
582 && integer_onep (rhs2
))))
584 basic_block bb
= gimple_bb (stmt
);
585 gimple_cond_set_code (stmt
, NE_EXPR
);
586 gimple_cond_set_rhs (stmt
, build_zero_cst (TREE_TYPE (rhs1
)));
587 EDGE_SUCC (bb
, 0)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
588 EDGE_SUCC (bb
, 1)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
596 /* Propagate from the ssa name definition statements of COND_EXPR
597 in the rhs of statement STMT into the conditional if that simplifies it.
598 Returns true zero if the stmt was changed. */
601 forward_propagate_into_cond (gimple_stmt_iterator
*gsi_p
)
603 gimple stmt
= gsi_stmt (*gsi_p
);
604 tree tmp
= NULL_TREE
;
605 tree cond
= gimple_assign_rhs1 (stmt
);
606 enum tree_code code
= gimple_assign_rhs_code (stmt
);
608 /* We can do tree combining on SSA_NAME and comparison expressions. */
609 if (COMPARISON_CLASS_P (cond
))
610 tmp
= forward_propagate_into_comparison_1 (stmt
, TREE_CODE (cond
),
612 TREE_OPERAND (cond
, 0),
613 TREE_OPERAND (cond
, 1));
614 else if (TREE_CODE (cond
) == SSA_NAME
)
616 enum tree_code def_code
;
618 gimple def_stmt
= get_prop_source_stmt (name
, true, NULL
);
619 if (!def_stmt
|| !can_propagate_from (def_stmt
))
622 def_code
= gimple_assign_rhs_code (def_stmt
);
623 if (TREE_CODE_CLASS (def_code
) == tcc_comparison
)
624 tmp
= fold_build2_loc (gimple_location (def_stmt
),
627 gimple_assign_rhs1 (def_stmt
),
628 gimple_assign_rhs2 (def_stmt
));
632 && is_gimple_condexpr (tmp
))
634 if (dump_file
&& tmp
)
636 fprintf (dump_file
, " Replaced '");
637 print_generic_expr (dump_file
, cond
, 0);
638 fprintf (dump_file
, "' with '");
639 print_generic_expr (dump_file
, tmp
, 0);
640 fprintf (dump_file
, "'\n");
643 if ((code
== VEC_COND_EXPR
) ? integer_all_onesp (tmp
)
644 : integer_onep (tmp
))
645 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs2 (stmt
));
646 else if (integer_zerop (tmp
))
647 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs3 (stmt
));
649 gimple_assign_set_rhs1 (stmt
, unshare_expr (tmp
));
650 stmt
= gsi_stmt (*gsi_p
);
659 /* We've just substituted an ADDR_EXPR into stmt. Update all the
660 relevant data structures to match. */
663 tidy_after_forward_propagate_addr (gimple stmt
)
665 /* We may have turned a trapping insn into a non-trapping insn. */
666 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
667 bitmap_set_bit (to_purge
, gimple_bb (stmt
)->index
);
669 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
670 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
673 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
674 ADDR_EXPR <whatever>.
676 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
677 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
678 node or for recovery of array indexing from pointer arithmetic.
680 Return true if the propagation was successful (the propagation can
681 be not totally successful, yet things may have been changed). */
684 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
,
685 gimple_stmt_iterator
*use_stmt_gsi
,
688 tree lhs
, rhs
, rhs2
, array_ref
;
689 gimple use_stmt
= gsi_stmt (*use_stmt_gsi
);
690 enum tree_code rhs_code
;
693 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
695 lhs
= gimple_assign_lhs (use_stmt
);
696 rhs_code
= gimple_assign_rhs_code (use_stmt
);
697 rhs
= gimple_assign_rhs1 (use_stmt
);
699 /* Do not perform copy-propagation but recurse through copy chains. */
700 if (TREE_CODE (lhs
) == SSA_NAME
701 && rhs_code
== SSA_NAME
)
702 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
704 /* The use statement could be a conversion. Recurse to the uses of the
705 lhs as copyprop does not copy through pointer to integer to pointer
706 conversions and FRE does not catch all cases either.
707 Treat the case of a single-use name and
708 a conversion to def_rhs type separate, though. */
709 if (TREE_CODE (lhs
) == SSA_NAME
710 && CONVERT_EXPR_CODE_P (rhs_code
))
712 /* If there is a point in a conversion chain where the types match
713 so we can remove a conversion re-materialize the address here
716 && useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
718 gimple_assign_set_rhs1 (use_stmt
, unshare_expr (def_rhs
));
719 gimple_assign_set_rhs_code (use_stmt
, TREE_CODE (def_rhs
));
723 /* Else recurse if the conversion preserves the address value. */
724 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
725 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
726 && (TYPE_PRECISION (TREE_TYPE (lhs
))
727 >= TYPE_PRECISION (TREE_TYPE (def_rhs
))))
728 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
733 /* If this isn't a conversion chain from this on we only can propagate
734 into compatible pointer contexts. */
735 if (!types_compatible_p (TREE_TYPE (name
), TREE_TYPE (def_rhs
)))
738 /* Propagate through constant pointer adjustments. */
739 if (TREE_CODE (lhs
) == SSA_NAME
740 && rhs_code
== POINTER_PLUS_EXPR
742 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
)
745 /* As we come here with non-invariant addresses in def_rhs we need
746 to make sure we can build a valid constant offsetted address
747 for further propagation. Simply rely on fold building that
748 and check after the fact. */
749 new_def_rhs
= fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (rhs
)),
751 fold_convert (ptr_type_node
,
752 gimple_assign_rhs2 (use_stmt
)));
753 if (TREE_CODE (new_def_rhs
) == MEM_REF
754 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs
, 0)))
756 new_def_rhs
= build_fold_addr_expr_with_type (new_def_rhs
,
759 /* Recurse. If we could propagate into all uses of lhs do not
760 bother to replace into the current use but just pretend we did. */
761 if (TREE_CODE (new_def_rhs
) == ADDR_EXPR
762 && forward_propagate_addr_expr (lhs
, new_def_rhs
, single_use_p
))
765 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (new_def_rhs
)))
766 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, TREE_CODE (new_def_rhs
),
768 else if (is_gimple_min_invariant (new_def_rhs
))
769 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, NOP_EXPR
, new_def_rhs
);
772 gcc_assert (gsi_stmt (*use_stmt_gsi
) == use_stmt
);
773 update_stmt (use_stmt
);
777 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
778 ADDR_EXPR will not appear on the LHS. */
779 tree
*lhsp
= gimple_assign_lhs_ptr (use_stmt
);
780 while (handled_component_p (*lhsp
))
781 lhsp
= &TREE_OPERAND (*lhsp
, 0);
784 /* Now see if the LHS node is a MEM_REF using NAME. If so,
785 propagate the ADDR_EXPR into the use of NAME and fold the result. */
786 if (TREE_CODE (lhs
) == MEM_REF
787 && TREE_OPERAND (lhs
, 0) == name
)
790 HOST_WIDE_INT def_rhs_offset
;
791 /* If the address is invariant we can always fold it. */
792 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
795 offset_int off
= mem_ref_offset (lhs
);
797 off
+= def_rhs_offset
;
798 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
800 off
+= mem_ref_offset (def_rhs_base
);
801 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
804 new_ptr
= build_fold_addr_expr (def_rhs_base
);
805 TREE_OPERAND (lhs
, 0) = new_ptr
;
806 TREE_OPERAND (lhs
, 1)
807 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs
, 1)), off
);
808 tidy_after_forward_propagate_addr (use_stmt
);
809 /* Continue propagating into the RHS if this was not the only use. */
813 /* If the LHS is a plain dereference and the value type is the same as
814 that of the pointed-to type of the address we can put the
815 dereferenced address on the LHS preserving the original alias-type. */
816 else if (integer_zerop (TREE_OPERAND (lhs
, 1))
817 && ((gimple_assign_lhs (use_stmt
) == lhs
818 && useless_type_conversion_p
819 (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)),
820 TREE_TYPE (gimple_assign_rhs1 (use_stmt
))))
821 || types_compatible_p (TREE_TYPE (lhs
),
822 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
823 /* Don't forward anything into clobber stmts if it would result
824 in the lhs no longer being a MEM_REF. */
825 && (!gimple_clobber_p (use_stmt
)
826 || TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == MEM_REF
))
828 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
829 tree new_offset
, new_base
, saved
, new_lhs
;
830 while (handled_component_p (*def_rhs_basep
))
831 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
832 saved
= *def_rhs_basep
;
833 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
835 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
836 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (lhs
, 1)),
837 TREE_OPERAND (*def_rhs_basep
, 1));
841 new_base
= build_fold_addr_expr (*def_rhs_basep
);
842 new_offset
= TREE_OPERAND (lhs
, 1);
844 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
845 new_base
, new_offset
);
846 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (lhs
);
847 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (lhs
);
848 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (lhs
);
849 new_lhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
851 TREE_THIS_VOLATILE (new_lhs
) = TREE_THIS_VOLATILE (lhs
);
852 TREE_SIDE_EFFECTS (new_lhs
) = TREE_SIDE_EFFECTS (lhs
);
853 *def_rhs_basep
= saved
;
854 tidy_after_forward_propagate_addr (use_stmt
);
855 /* Continue propagating into the RHS if this was not the
861 /* We can have a struct assignment dereferencing our name twice.
862 Note that we didn't propagate into the lhs to not falsely
863 claim we did when propagating into the rhs. */
867 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
868 nodes from the RHS. */
869 tree
*rhsp
= gimple_assign_rhs1_ptr (use_stmt
);
870 if (TREE_CODE (*rhsp
) == ADDR_EXPR
)
871 rhsp
= &TREE_OPERAND (*rhsp
, 0);
872 while (handled_component_p (*rhsp
))
873 rhsp
= &TREE_OPERAND (*rhsp
, 0);
876 /* Now see if the RHS node is a MEM_REF using NAME. If so,
877 propagate the ADDR_EXPR into the use of NAME and fold the result. */
878 if (TREE_CODE (rhs
) == MEM_REF
879 && TREE_OPERAND (rhs
, 0) == name
)
882 HOST_WIDE_INT def_rhs_offset
;
883 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
886 offset_int off
= mem_ref_offset (rhs
);
888 off
+= def_rhs_offset
;
889 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
891 off
+= mem_ref_offset (def_rhs_base
);
892 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
895 new_ptr
= build_fold_addr_expr (def_rhs_base
);
896 TREE_OPERAND (rhs
, 0) = new_ptr
;
897 TREE_OPERAND (rhs
, 1)
898 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs
, 1)), off
);
899 fold_stmt_inplace (use_stmt_gsi
);
900 tidy_after_forward_propagate_addr (use_stmt
);
903 /* If the RHS is a plain dereference and the value type is the same as
904 that of the pointed-to type of the address we can put the
905 dereferenced address on the RHS preserving the original alias-type. */
906 else if (integer_zerop (TREE_OPERAND (rhs
, 1))
907 && ((gimple_assign_rhs1 (use_stmt
) == rhs
908 && useless_type_conversion_p
909 (TREE_TYPE (gimple_assign_lhs (use_stmt
)),
910 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
911 || types_compatible_p (TREE_TYPE (rhs
),
912 TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))))
914 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
915 tree new_offset
, new_base
, saved
, new_rhs
;
916 while (handled_component_p (*def_rhs_basep
))
917 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
918 saved
= *def_rhs_basep
;
919 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
921 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
922 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (rhs
, 1)),
923 TREE_OPERAND (*def_rhs_basep
, 1));
927 new_base
= build_fold_addr_expr (*def_rhs_basep
);
928 new_offset
= TREE_OPERAND (rhs
, 1);
930 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
931 new_base
, new_offset
);
932 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (rhs
);
933 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (rhs
);
934 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (rhs
);
935 new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
937 TREE_THIS_VOLATILE (new_rhs
) = TREE_THIS_VOLATILE (rhs
);
938 TREE_SIDE_EFFECTS (new_rhs
) = TREE_SIDE_EFFECTS (rhs
);
939 *def_rhs_basep
= saved
;
940 fold_stmt_inplace (use_stmt_gsi
);
941 tidy_after_forward_propagate_addr (use_stmt
);
946 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
948 if (gimple_assign_rhs_code (use_stmt
) != POINTER_PLUS_EXPR
949 || gimple_assign_rhs1 (use_stmt
) != name
)
952 /* The remaining cases are all for turning pointer arithmetic into
953 array indexing. They only apply when we have the address of
954 element zero in an array. If that is not the case then there
956 array_ref
= TREE_OPERAND (def_rhs
, 0);
957 if ((TREE_CODE (array_ref
) != ARRAY_REF
958 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
959 || TREE_CODE (TREE_OPERAND (array_ref
, 1)) != INTEGER_CST
)
960 && TREE_CODE (TREE_TYPE (array_ref
)) != ARRAY_TYPE
)
963 rhs2
= gimple_assign_rhs2 (use_stmt
);
964 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
965 if (TREE_CODE (rhs2
) == INTEGER_CST
)
967 tree new_rhs
= build1_loc (gimple_location (use_stmt
),
968 ADDR_EXPR
, TREE_TYPE (def_rhs
),
969 fold_build2 (MEM_REF
,
970 TREE_TYPE (TREE_TYPE (def_rhs
)),
971 unshare_expr (def_rhs
),
972 fold_convert (ptr_type_node
,
974 gimple_assign_set_rhs_from_tree (use_stmt_gsi
, new_rhs
);
975 use_stmt
= gsi_stmt (*use_stmt_gsi
);
976 update_stmt (use_stmt
);
977 tidy_after_forward_propagate_addr (use_stmt
);
984 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
986 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
987 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
988 node or for recovery of array indexing from pointer arithmetic.
990 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
991 the single use in the previous invocation. Pass true when calling
994 Returns true, if all uses have been propagated into. */
997 forward_propagate_addr_expr (tree name
, tree rhs
, bool parent_single_use_p
)
999 imm_use_iterator iter
;
1002 bool single_use_p
= parent_single_use_p
&& has_single_use (name
);
1004 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
1009 /* If the use is not in a simple assignment statement, then
1010 there is nothing we can do. */
1011 if (!is_gimple_assign (use_stmt
))
1013 if (!is_gimple_debug (use_stmt
))
1018 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1019 result
= forward_propagate_addr_expr_1 (name
, rhs
, &gsi
,
1021 /* If the use has moved to a different statement adjust
1022 the update machinery for the old statement too. */
1023 if (use_stmt
!= gsi_stmt (gsi
))
1025 update_stmt (use_stmt
);
1026 use_stmt
= gsi_stmt (gsi
);
1028 update_stmt (use_stmt
);
1031 /* Remove intermediate now unused copy and conversion chains. */
1032 use_rhs
= gimple_assign_rhs1 (use_stmt
);
1034 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
1035 && TREE_CODE (use_rhs
) == SSA_NAME
1036 && has_zero_uses (gimple_assign_lhs (use_stmt
)))
1038 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1039 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt
));
1040 release_defs (use_stmt
);
1041 gsi_remove (&gsi
, true);
1045 return all
&& has_zero_uses (name
);
1049 /* Helper function for simplify_gimple_switch. Remove case labels that
1050 have values outside the range of the new type. */
1053 simplify_gimple_switch_label_vec (gswitch
*stmt
, tree index_type
)
1055 unsigned int branch_num
= gimple_switch_num_labels (stmt
);
1056 auto_vec
<tree
> labels (branch_num
);
1057 unsigned int i
, len
;
1059 /* Collect the existing case labels in a VEC, and preprocess it as if
1060 we are gimplifying a GENERIC SWITCH_EXPR. */
1061 for (i
= 1; i
< branch_num
; i
++)
1062 labels
.quick_push (gimple_switch_label (stmt
, i
));
1063 preprocess_case_label_vec_for_gimple (labels
, index_type
, NULL
);
1065 /* If any labels were removed, replace the existing case labels
1066 in the GIMPLE_SWITCH statement with the correct ones.
1067 Note that the type updates were done in-place on the case labels,
1068 so we only have to replace the case labels in the GIMPLE_SWITCH
1069 if the number of labels changed. */
1070 len
= labels
.length ();
1071 if (len
< branch_num
- 1)
1073 bitmap target_blocks
;
1077 /* Corner case: *all* case labels have been removed as being
1078 out-of-range for INDEX_TYPE. Push one label and let the
1079 CFG cleanups deal with this further. */
1084 label
= CASE_LABEL (gimple_switch_default_label (stmt
));
1085 elt
= build_case_label (build_int_cst (index_type
, 0), NULL
, label
);
1086 labels
.quick_push (elt
);
1090 for (i
= 0; i
< labels
.length (); i
++)
1091 gimple_switch_set_label (stmt
, i
+ 1, labels
[i
]);
1092 for (i
++ ; i
< branch_num
; i
++)
1093 gimple_switch_set_label (stmt
, i
, NULL_TREE
);
1094 gimple_switch_set_num_labels (stmt
, len
+ 1);
1096 /* Cleanup any edges that are now dead. */
1097 target_blocks
= BITMAP_ALLOC (NULL
);
1098 for (i
= 0; i
< gimple_switch_num_labels (stmt
); i
++)
1100 tree elt
= gimple_switch_label (stmt
, i
);
1101 basic_block target
= label_to_block (CASE_LABEL (elt
));
1102 bitmap_set_bit (target_blocks
, target
->index
);
1104 for (ei
= ei_start (gimple_bb (stmt
)->succs
); (e
= ei_safe_edge (ei
)); )
1106 if (! bitmap_bit_p (target_blocks
, e
->dest
->index
))
1110 free_dominance_info (CDI_DOMINATORS
);
1115 BITMAP_FREE (target_blocks
);
1119 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1120 the condition which we may be able to optimize better. */
1123 simplify_gimple_switch (gswitch
*stmt
)
1125 /* The optimization that we really care about is removing unnecessary
1126 casts. That will let us do much better in propagating the inferred
1127 constant at the switch target. */
1128 tree cond
= gimple_switch_index (stmt
);
1129 if (TREE_CODE (cond
) == SSA_NAME
)
1131 gimple def_stmt
= SSA_NAME_DEF_STMT (cond
);
1132 if (gimple_assign_cast_p (def_stmt
))
1134 tree def
= gimple_assign_rhs1 (def_stmt
);
1135 if (TREE_CODE (def
) != SSA_NAME
)
1138 /* If we have an extension or sign-change that preserves the
1139 values we check against then we can copy the source value into
1141 tree ti
= TREE_TYPE (def
);
1142 if (INTEGRAL_TYPE_P (ti
)
1143 && TYPE_PRECISION (ti
) <= TYPE_PRECISION (TREE_TYPE (cond
)))
1145 size_t n
= gimple_switch_num_labels (stmt
);
1146 tree min
= NULL_TREE
, max
= NULL_TREE
;
1149 min
= CASE_LOW (gimple_switch_label (stmt
, 1));
1150 if (CASE_HIGH (gimple_switch_label (stmt
, n
- 1)))
1151 max
= CASE_HIGH (gimple_switch_label (stmt
, n
- 1));
1153 max
= CASE_LOW (gimple_switch_label (stmt
, n
- 1));
1155 if ((!min
|| int_fits_type_p (min
, ti
))
1156 && (!max
|| int_fits_type_p (max
, ti
)))
1158 gimple_switch_set_index (stmt
, def
);
1159 simplify_gimple_switch_label_vec (stmt
, ti
);
1170 /* For pointers p2 and p1 return p2 - p1 if the
1171 difference is known and constant, otherwise return NULL. */
1174 constant_pointer_difference (tree p1
, tree p2
)
1177 #define CPD_ITERATIONS 5
1178 tree exps
[2][CPD_ITERATIONS
];
1179 tree offs
[2][CPD_ITERATIONS
];
1182 for (i
= 0; i
< 2; i
++)
1184 tree p
= i
? p1
: p2
;
1185 tree off
= size_zero_node
;
1187 enum tree_code code
;
1189 /* For each of p1 and p2 we need to iterate at least
1190 twice, to handle ADDR_EXPR directly in p1/p2,
1191 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1192 on definition's stmt RHS. Iterate a few extra times. */
1196 if (!POINTER_TYPE_P (TREE_TYPE (p
)))
1198 if (TREE_CODE (p
) == ADDR_EXPR
)
1200 tree q
= TREE_OPERAND (p
, 0);
1201 HOST_WIDE_INT offset
;
1202 tree base
= get_addr_base_and_unit_offset (q
, &offset
);
1207 off
= size_binop (PLUS_EXPR
, off
, size_int (offset
));
1209 if (TREE_CODE (q
) == MEM_REF
1210 && TREE_CODE (TREE_OPERAND (q
, 0)) == SSA_NAME
)
1212 p
= TREE_OPERAND (q
, 0);
1213 off
= size_binop (PLUS_EXPR
, off
,
1214 wide_int_to_tree (sizetype
,
1215 mem_ref_offset (q
)));
1224 if (TREE_CODE (p
) != SSA_NAME
)
1228 if (j
== CPD_ITERATIONS
)
1230 stmt
= SSA_NAME_DEF_STMT (p
);
1231 if (!is_gimple_assign (stmt
) || gimple_assign_lhs (stmt
) != p
)
1233 code
= gimple_assign_rhs_code (stmt
);
1234 if (code
== POINTER_PLUS_EXPR
)
1236 if (TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)
1238 off
= size_binop (PLUS_EXPR
, off
, gimple_assign_rhs2 (stmt
));
1239 p
= gimple_assign_rhs1 (stmt
);
1241 else if (code
== ADDR_EXPR
|| CONVERT_EXPR_CODE_P (code
))
1242 p
= gimple_assign_rhs1 (stmt
);
1250 for (i
= 0; i
< cnt
[0]; i
++)
1251 for (j
= 0; j
< cnt
[1]; j
++)
1252 if (exps
[0][i
] == exps
[1][j
])
1253 return size_binop (MINUS_EXPR
, offs
[0][i
], offs
[1][j
]);
1258 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1260 memcpy (p, "abcd", 4);
1261 memset (p + 4, ' ', 3);
1263 memcpy (p, "abcd ", 7);
1264 call if the latter can be stored by pieces during expansion. */
1267 simplify_builtin_call (gimple_stmt_iterator
*gsi_p
, tree callee2
)
1269 gimple stmt1
, stmt2
= gsi_stmt (*gsi_p
);
1270 tree vuse
= gimple_vuse (stmt2
);
1273 stmt1
= SSA_NAME_DEF_STMT (vuse
);
1275 switch (DECL_FUNCTION_CODE (callee2
))
1277 case BUILT_IN_MEMSET
:
1278 if (gimple_call_num_args (stmt2
) != 3
1279 || gimple_call_lhs (stmt2
)
1281 || BITS_PER_UNIT
!= 8)
1286 tree ptr1
, src1
, str1
, off1
, len1
, lhs1
;
1287 tree ptr2
= gimple_call_arg (stmt2
, 0);
1288 tree val2
= gimple_call_arg (stmt2
, 1);
1289 tree len2
= gimple_call_arg (stmt2
, 2);
1290 tree diff
, vdef
, new_str_cst
;
1292 unsigned int ptr1_align
;
1293 unsigned HOST_WIDE_INT src_len
;
1295 use_operand_p use_p
;
1297 if (!tree_fits_shwi_p (val2
)
1298 || !tree_fits_uhwi_p (len2
)
1299 || compare_tree_int (len2
, 1024) == 1)
1301 if (is_gimple_call (stmt1
))
1303 /* If first stmt is a call, it needs to be memcpy
1304 or mempcpy, with string literal as second argument and
1306 callee1
= gimple_call_fndecl (stmt1
);
1307 if (callee1
== NULL_TREE
1308 || DECL_BUILT_IN_CLASS (callee1
) != BUILT_IN_NORMAL
1309 || gimple_call_num_args (stmt1
) != 3)
1311 if (DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMCPY
1312 && DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMPCPY
)
1314 ptr1
= gimple_call_arg (stmt1
, 0);
1315 src1
= gimple_call_arg (stmt1
, 1);
1316 len1
= gimple_call_arg (stmt1
, 2);
1317 lhs1
= gimple_call_lhs (stmt1
);
1318 if (!tree_fits_uhwi_p (len1
))
1320 str1
= string_constant (src1
, &off1
);
1321 if (str1
== NULL_TREE
)
1323 if (!tree_fits_uhwi_p (off1
)
1324 || compare_tree_int (off1
, TREE_STRING_LENGTH (str1
) - 1) > 0
1325 || compare_tree_int (len1
, TREE_STRING_LENGTH (str1
)
1326 - tree_to_uhwi (off1
)) > 0
1327 || TREE_CODE (TREE_TYPE (str1
)) != ARRAY_TYPE
1328 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1
)))
1329 != TYPE_MODE (char_type_node
))
1332 else if (gimple_assign_single_p (stmt1
))
1334 /* Otherwise look for length 1 memcpy optimized into
1336 ptr1
= gimple_assign_lhs (stmt1
);
1337 src1
= gimple_assign_rhs1 (stmt1
);
1338 if (TREE_CODE (ptr1
) != MEM_REF
1339 || TYPE_MODE (TREE_TYPE (ptr1
)) != TYPE_MODE (char_type_node
)
1340 || !tree_fits_shwi_p (src1
))
1342 ptr1
= build_fold_addr_expr (ptr1
);
1343 callee1
= NULL_TREE
;
1344 len1
= size_one_node
;
1346 off1
= size_zero_node
;
1352 diff
= constant_pointer_difference (ptr1
, ptr2
);
1353 if (diff
== NULL
&& lhs1
!= NULL
)
1355 diff
= constant_pointer_difference (lhs1
, ptr2
);
1356 if (DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1358 diff
= size_binop (PLUS_EXPR
, diff
,
1359 fold_convert (sizetype
, len1
));
1361 /* If the difference between the second and first destination pointer
1362 is not constant, or is bigger than memcpy length, bail out. */
1364 || !tree_fits_uhwi_p (diff
)
1365 || tree_int_cst_lt (len1
, diff
)
1366 || compare_tree_int (diff
, 1024) == 1)
1369 /* Use maximum of difference plus memset length and memcpy length
1370 as the new memcpy length, if it is too big, bail out. */
1371 src_len
= tree_to_uhwi (diff
);
1372 src_len
+= tree_to_uhwi (len2
);
1373 if (src_len
< tree_to_uhwi (len1
))
1374 src_len
= tree_to_uhwi (len1
);
1378 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1379 with bigger length will return different result. */
1380 if (lhs1
!= NULL_TREE
1381 && DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1382 && (TREE_CODE (lhs1
) != SSA_NAME
1383 || !single_imm_use (lhs1
, &use_p
, &use_stmt
)
1384 || use_stmt
!= stmt2
))
1387 /* If anything reads memory in between memcpy and memset
1388 call, the modified memcpy call might change it. */
1389 vdef
= gimple_vdef (stmt1
);
1391 && (!single_imm_use (vdef
, &use_p
, &use_stmt
)
1392 || use_stmt
!= stmt2
))
1395 ptr1_align
= get_pointer_alignment (ptr1
);
1396 /* Construct the new source string literal. */
1397 src_buf
= XALLOCAVEC (char, src_len
+ 1);
1400 TREE_STRING_POINTER (str1
) + tree_to_uhwi (off1
),
1401 tree_to_uhwi (len1
));
1403 src_buf
[0] = tree_to_shwi (src1
);
1404 memset (src_buf
+ tree_to_uhwi (diff
),
1405 tree_to_shwi (val2
), tree_to_uhwi (len2
));
1406 src_buf
[src_len
] = '\0';
1407 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1408 handle embedded '\0's. */
1409 if (strlen (src_buf
) != src_len
)
1411 rtl_profile_for_bb (gimple_bb (stmt2
));
1412 /* If the new memcpy wouldn't be emitted by storing the literal
1413 by pieces, this optimization might enlarge .rodata too much,
1414 as commonly used string literals couldn't be shared any
1416 if (!can_store_by_pieces (src_len
,
1417 builtin_strncpy_read_str
,
1418 src_buf
, ptr1_align
, false))
1421 new_str_cst
= build_string_literal (src_len
, src_buf
);
1424 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1426 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1427 gimple_call_set_lhs (stmt1
, NULL_TREE
);
1428 gimple_call_set_arg (stmt1
, 1, new_str_cst
);
1429 gimple_call_set_arg (stmt1
, 2,
1430 build_int_cst (TREE_TYPE (len1
), src_len
));
1431 update_stmt (stmt1
);
1432 unlink_stmt_vdef (stmt2
);
1433 gsi_remove (gsi_p
, true);
1434 fwprop_invalidate_lattice (gimple_get_lhs (stmt2
));
1435 release_defs (stmt2
);
1436 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1438 fwprop_invalidate_lattice (lhs1
);
1439 release_ssa_name (lhs1
);
1445 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1446 assignment, remove STMT1 and change memset call into
1448 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt1
);
1450 if (!is_gimple_val (ptr1
))
1451 ptr1
= force_gimple_operand_gsi (gsi_p
, ptr1
, true, NULL_TREE
,
1452 true, GSI_SAME_STMT
);
1453 gimple_call_set_fndecl (stmt2
,
1454 builtin_decl_explicit (BUILT_IN_MEMCPY
));
1455 gimple_call_set_arg (stmt2
, 0, ptr1
);
1456 gimple_call_set_arg (stmt2
, 1, new_str_cst
);
1457 gimple_call_set_arg (stmt2
, 2,
1458 build_int_cst (TREE_TYPE (len2
), src_len
));
1459 unlink_stmt_vdef (stmt1
);
1460 gsi_remove (&gsi
, true);
1461 fwprop_invalidate_lattice (gimple_get_lhs (stmt1
));
1462 release_defs (stmt1
);
1463 update_stmt (stmt2
);
1474 /* Given a ssa_name in NAME see if it was defined by an assignment and
1475 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1476 to the second operand on the rhs. */
1479 defcodefor_name (tree name
, enum tree_code
*code
, tree
*arg1
, tree
*arg2
)
1482 enum tree_code code1
;
1486 enum gimple_rhs_class grhs_class
;
1488 code1
= TREE_CODE (name
);
1491 grhs_class
= get_gimple_rhs_class (code1
);
1493 if (code1
== SSA_NAME
)
1495 def
= SSA_NAME_DEF_STMT (name
);
1497 if (def
&& is_gimple_assign (def
)
1498 && can_propagate_from (def
))
1500 code1
= gimple_assign_rhs_code (def
);
1501 arg11
= gimple_assign_rhs1 (def
);
1502 arg21
= gimple_assign_rhs2 (def
);
1503 arg31
= gimple_assign_rhs2 (def
);
1506 else if (grhs_class
== GIMPLE_TERNARY_RHS
1507 || GIMPLE_BINARY_RHS
1509 || GIMPLE_SINGLE_RHS
)
1510 extract_ops_from_tree_1 (name
, &code1
, &arg11
, &arg21
, &arg31
);
1516 /* Ignore arg3 currently. */
1520 /* Recognize rotation patterns. Return true if a transformation
1521 applied, otherwise return false.
1523 We are looking for X with unsigned type T with bitsize B, OP being
1524 +, | or ^, some type T2 wider than T and
1525 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1526 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1527 (X << Y) OP (X >> (B - Y))
1528 (X << (int) Y) OP (X >> (int) (B - Y))
1529 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1530 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1531 (X << Y) | (X >> ((-Y) & (B - 1)))
1532 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1533 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1534 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1536 and transform these into:
1540 Note, in the patterns with T2 type, the type of OP operands
1541 might be even a signed type, but should have precision B. */
1544 simplify_rotate (gimple_stmt_iterator
*gsi
)
1546 gimple stmt
= gsi_stmt (*gsi
);
1547 tree arg
[2], rtype
, rotcnt
= NULL_TREE
;
1548 tree def_arg1
[2], def_arg2
[2];
1549 enum tree_code def_code
[2];
1552 bool swapped_p
= false;
1555 arg
[0] = gimple_assign_rhs1 (stmt
);
1556 arg
[1] = gimple_assign_rhs2 (stmt
);
1557 rtype
= TREE_TYPE (arg
[0]);
1559 /* Only create rotates in complete modes. Other cases are not
1560 expanded properly. */
1561 if (!INTEGRAL_TYPE_P (rtype
)
1562 || TYPE_PRECISION (rtype
) != GET_MODE_PRECISION (TYPE_MODE (rtype
)))
1565 for (i
= 0; i
< 2; i
++)
1566 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1568 /* Look through narrowing conversions. */
1569 if (CONVERT_EXPR_CODE_P (def_code
[0])
1570 && CONVERT_EXPR_CODE_P (def_code
[1])
1571 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[0]))
1572 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[1]))
1573 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0]))
1574 == TYPE_PRECISION (TREE_TYPE (def_arg1
[1]))
1575 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) > TYPE_PRECISION (rtype
)
1576 && has_single_use (arg
[0])
1577 && has_single_use (arg
[1]))
1579 for (i
= 0; i
< 2; i
++)
1581 arg
[i
] = def_arg1
[i
];
1582 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1586 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1587 for (i
= 0; i
< 2; i
++)
1588 if (def_code
[i
] != LSHIFT_EXPR
&& def_code
[i
] != RSHIFT_EXPR
)
1590 else if (!has_single_use (arg
[i
]))
1592 if (def_code
[0] == def_code
[1])
1595 /* If we've looked through narrowing conversions before, look through
1596 widening conversions from unsigned type with the same precision
1598 if (TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) != TYPE_PRECISION (rtype
))
1599 for (i
= 0; i
< 2; i
++)
1602 enum tree_code code
;
1603 defcodefor_name (def_arg1
[i
], &code
, &tem
, NULL
);
1604 if (!CONVERT_EXPR_CODE_P (code
)
1605 || !INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1606 || TYPE_PRECISION (TREE_TYPE (tem
)) != TYPE_PRECISION (rtype
))
1610 /* Both shifts have to use the same first operand. */
1611 if (TREE_CODE (def_arg1
[0]) != SSA_NAME
|| def_arg1
[0] != def_arg1
[1])
1613 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1
[0])))
1616 /* CNT1 + CNT2 == B case above. */
1617 if (tree_fits_uhwi_p (def_arg2
[0])
1618 && tree_fits_uhwi_p (def_arg2
[1])
1619 && tree_to_uhwi (def_arg2
[0])
1620 + tree_to_uhwi (def_arg2
[1]) == TYPE_PRECISION (rtype
))
1621 rotcnt
= def_arg2
[0];
1622 else if (TREE_CODE (def_arg2
[0]) != SSA_NAME
1623 || TREE_CODE (def_arg2
[1]) != SSA_NAME
)
1627 tree cdef_arg1
[2], cdef_arg2
[2], def_arg2_alt
[2];
1628 enum tree_code cdef_code
[2];
1629 /* Look through conversion of the shift count argument.
1630 The C/C++ FE cast any shift count argument to integer_type_node.
1631 The only problem might be if the shift count type maximum value
1632 is equal or smaller than number of bits in rtype. */
1633 for (i
= 0; i
< 2; i
++)
1635 def_arg2_alt
[i
] = def_arg2
[i
];
1636 defcodefor_name (def_arg2
[i
], &cdef_code
[i
],
1637 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1638 if (CONVERT_EXPR_CODE_P (cdef_code
[i
])
1639 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1
[i
]))
1640 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
1641 > floor_log2 (TYPE_PRECISION (rtype
))
1642 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
1643 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (cdef_arg1
[i
]))))
1645 def_arg2_alt
[i
] = cdef_arg1
[i
];
1646 defcodefor_name (def_arg2_alt
[i
], &cdef_code
[i
],
1647 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1650 for (i
= 0; i
< 2; i
++)
1651 /* Check for one shift count being Y and the other B - Y,
1652 with optional casts. */
1653 if (cdef_code
[i
] == MINUS_EXPR
1654 && tree_fits_shwi_p (cdef_arg1
[i
])
1655 && tree_to_shwi (cdef_arg1
[i
]) == TYPE_PRECISION (rtype
)
1656 && TREE_CODE (cdef_arg2
[i
]) == SSA_NAME
)
1659 enum tree_code code
;
1661 if (cdef_arg2
[i
] == def_arg2
[1 - i
]
1662 || cdef_arg2
[i
] == def_arg2_alt
[1 - i
])
1664 rotcnt
= cdef_arg2
[i
];
1667 defcodefor_name (cdef_arg2
[i
], &code
, &tem
, NULL
);
1668 if (CONVERT_EXPR_CODE_P (code
)
1669 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1670 && TYPE_PRECISION (TREE_TYPE (tem
))
1671 > floor_log2 (TYPE_PRECISION (rtype
))
1672 && TYPE_PRECISION (TREE_TYPE (tem
))
1673 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
1674 && (tem
== def_arg2
[1 - i
]
1675 || tem
== def_arg2_alt
[1 - i
]))
1681 /* The above sequence isn't safe for Y being 0,
1682 because then one of the shifts triggers undefined behavior.
1683 This alternative is safe even for rotation count of 0.
1684 One shift count is Y and the other (-Y) & (B - 1). */
1685 else if (cdef_code
[i
] == BIT_AND_EXPR
1686 && tree_fits_shwi_p (cdef_arg2
[i
])
1687 && tree_to_shwi (cdef_arg2
[i
])
1688 == TYPE_PRECISION (rtype
) - 1
1689 && TREE_CODE (cdef_arg1
[i
]) == SSA_NAME
1690 && gimple_assign_rhs_code (stmt
) == BIT_IOR_EXPR
)
1693 enum tree_code code
;
1695 defcodefor_name (cdef_arg1
[i
], &code
, &tem
, NULL
);
1696 if (CONVERT_EXPR_CODE_P (code
)
1697 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1698 && TYPE_PRECISION (TREE_TYPE (tem
))
1699 > floor_log2 (TYPE_PRECISION (rtype
))
1700 && TYPE_PRECISION (TREE_TYPE (tem
))
1701 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
))))
1702 defcodefor_name (tem
, &code
, &tem
, NULL
);
1704 if (code
== NEGATE_EXPR
)
1706 if (tem
== def_arg2
[1 - i
] || tem
== def_arg2_alt
[1 - i
])
1711 defcodefor_name (tem
, &code
, &tem
, NULL
);
1712 if (CONVERT_EXPR_CODE_P (code
)
1713 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1714 && TYPE_PRECISION (TREE_TYPE (tem
))
1715 > floor_log2 (TYPE_PRECISION (rtype
))
1716 && TYPE_PRECISION (TREE_TYPE (tem
))
1717 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
1718 && (tem
== def_arg2
[1 - i
]
1719 || tem
== def_arg2_alt
[1 - i
]))
1726 if (rotcnt
== NULL_TREE
)
1731 if (!useless_type_conversion_p (TREE_TYPE (def_arg2
[0]),
1732 TREE_TYPE (rotcnt
)))
1734 g
= gimple_build_assign (make_ssa_name (TREE_TYPE (def_arg2
[0])),
1736 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1737 rotcnt
= gimple_assign_lhs (g
);
1739 lhs
= gimple_assign_lhs (stmt
);
1740 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1741 lhs
= make_ssa_name (TREE_TYPE (def_arg1
[0]));
1742 g
= gimple_build_assign (lhs
,
1743 ((def_code
[0] == LSHIFT_EXPR
) ^ swapped_p
)
1744 ? LROTATE_EXPR
: RROTATE_EXPR
, def_arg1
[0], rotcnt
);
1745 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1747 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1748 g
= gimple_build_assign (gimple_assign_lhs (stmt
), NOP_EXPR
, lhs
);
1750 gsi_replace (gsi
, g
, false);
1754 /* Combine an element access with a shuffle. Returns true if there were
1755 any changes made, else it returns false. */
1758 simplify_bitfield_ref (gimple_stmt_iterator
*gsi
)
1760 gimple stmt
= gsi_stmt (*gsi
);
1762 tree op
, op0
, op1
, op2
;
1764 unsigned idx
, n
, size
;
1765 enum tree_code code
;
1767 op
= gimple_assign_rhs1 (stmt
);
1768 gcc_checking_assert (TREE_CODE (op
) == BIT_FIELD_REF
);
1770 op0
= TREE_OPERAND (op
, 0);
1771 if (TREE_CODE (op0
) != SSA_NAME
1772 || TREE_CODE (TREE_TYPE (op0
)) != VECTOR_TYPE
)
1775 def_stmt
= get_prop_source_stmt (op0
, false, NULL
);
1776 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1779 op1
= TREE_OPERAND (op
, 1);
1780 op2
= TREE_OPERAND (op
, 2);
1781 code
= gimple_assign_rhs_code (def_stmt
);
1783 if (code
== CONSTRUCTOR
)
1785 tree tem
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (op
),
1786 gimple_assign_rhs1 (def_stmt
), op1
, op2
);
1787 if (!tem
|| !valid_gimple_rhs_p (tem
))
1789 gimple_assign_set_rhs_from_tree (gsi
, tem
);
1790 update_stmt (gsi_stmt (*gsi
));
1794 elem_type
= TREE_TYPE (TREE_TYPE (op0
));
1795 if (TREE_TYPE (op
) != elem_type
)
1798 size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
1799 n
= TREE_INT_CST_LOW (op1
) / size
;
1802 idx
= TREE_INT_CST_LOW (op2
) / size
;
1804 if (code
== VEC_PERM_EXPR
)
1806 tree p
, m
, index
, tem
;
1808 m
= gimple_assign_rhs3 (def_stmt
);
1809 if (TREE_CODE (m
) != VECTOR_CST
)
1811 nelts
= VECTOR_CST_NELTS (m
);
1812 idx
= TREE_INT_CST_LOW (VECTOR_CST_ELT (m
, idx
));
1816 p
= gimple_assign_rhs1 (def_stmt
);
1820 p
= gimple_assign_rhs2 (def_stmt
);
1823 index
= build_int_cst (TREE_TYPE (TREE_TYPE (m
)), idx
* size
);
1824 tem
= build3 (BIT_FIELD_REF
, TREE_TYPE (op
),
1825 unshare_expr (p
), op1
, index
);
1826 gimple_assign_set_rhs1 (stmt
, tem
);
1828 update_stmt (gsi_stmt (*gsi
));
1835 /* Determine whether applying the 2 permutations (mask1 then mask2)
1836 gives back one of the input. */
1839 is_combined_permutation_identity (tree mask1
, tree mask2
)
1842 unsigned int nelts
, i
, j
;
1843 bool maybe_identity1
= true;
1844 bool maybe_identity2
= true;
1846 gcc_checking_assert (TREE_CODE (mask1
) == VECTOR_CST
1847 && TREE_CODE (mask2
) == VECTOR_CST
);
1848 mask
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (mask1
), mask1
, mask1
, mask2
);
1849 gcc_assert (TREE_CODE (mask
) == VECTOR_CST
);
1851 nelts
= VECTOR_CST_NELTS (mask
);
1852 for (i
= 0; i
< nelts
; i
++)
1854 tree val
= VECTOR_CST_ELT (mask
, i
);
1855 gcc_assert (TREE_CODE (val
) == INTEGER_CST
);
1856 j
= TREE_INT_CST_LOW (val
) & (2 * nelts
- 1);
1858 maybe_identity2
= false;
1859 else if (j
== i
+ nelts
)
1860 maybe_identity1
= false;
1864 return maybe_identity1
? 1 : maybe_identity2
? 2 : 0;
1867 /* Combine a shuffle with its arguments. Returns 1 if there were any
1868 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
1871 simplify_permutation (gimple_stmt_iterator
*gsi
)
1873 gimple stmt
= gsi_stmt (*gsi
);
1875 tree op0
, op1
, op2
, op3
, arg0
, arg1
;
1876 enum tree_code code
;
1877 bool single_use_op0
= false;
1879 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == VEC_PERM_EXPR
);
1881 op0
= gimple_assign_rhs1 (stmt
);
1882 op1
= gimple_assign_rhs2 (stmt
);
1883 op2
= gimple_assign_rhs3 (stmt
);
1885 if (TREE_CODE (op2
) != VECTOR_CST
)
1888 if (TREE_CODE (op0
) == VECTOR_CST
)
1893 else if (TREE_CODE (op0
) == SSA_NAME
)
1895 def_stmt
= get_prop_source_stmt (op0
, false, &single_use_op0
);
1896 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1899 code
= gimple_assign_rhs_code (def_stmt
);
1900 arg0
= gimple_assign_rhs1 (def_stmt
);
1905 /* Two consecutive shuffles. */
1906 if (code
== VEC_PERM_EXPR
)
1913 op3
= gimple_assign_rhs3 (def_stmt
);
1914 if (TREE_CODE (op3
) != VECTOR_CST
)
1916 ident
= is_combined_permutation_identity (op3
, op2
);
1919 orig
= (ident
== 1) ? gimple_assign_rhs1 (def_stmt
)
1920 : gimple_assign_rhs2 (def_stmt
);
1921 gimple_assign_set_rhs1 (stmt
, unshare_expr (orig
));
1922 gimple_assign_set_rhs_code (stmt
, TREE_CODE (orig
));
1923 gimple_set_num_ops (stmt
, 2);
1925 return remove_prop_source_from_use (op0
) ? 2 : 1;
1928 /* Shuffle of a constructor. */
1929 else if (code
== CONSTRUCTOR
|| code
== VECTOR_CST
)
1935 if (TREE_CODE (op0
) == SSA_NAME
&& !single_use_op0
)
1938 if (TREE_CODE (op1
) == VECTOR_CST
)
1940 else if (TREE_CODE (op1
) == SSA_NAME
)
1942 enum tree_code code2
;
1944 gimple def_stmt2
= get_prop_source_stmt (op1
, true, NULL
);
1945 if (!def_stmt2
|| !can_propagate_from (def_stmt2
))
1948 code2
= gimple_assign_rhs_code (def_stmt2
);
1949 if (code2
!= CONSTRUCTOR
&& code2
!= VECTOR_CST
)
1951 arg1
= gimple_assign_rhs1 (def_stmt2
);
1958 /* Already used twice in this statement. */
1959 if (TREE_CODE (op0
) == SSA_NAME
&& num_imm_uses (op0
) > 2)
1963 opt
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (op0
), arg0
, arg1
, op2
);
1965 || (TREE_CODE (opt
) != CONSTRUCTOR
&& TREE_CODE (opt
) != VECTOR_CST
))
1967 gimple_assign_set_rhs_from_tree (gsi
, opt
);
1968 update_stmt (gsi_stmt (*gsi
));
1969 if (TREE_CODE (op0
) == SSA_NAME
)
1970 ret
= remove_prop_source_from_use (op0
);
1971 if (op0
!= op1
&& TREE_CODE (op1
) == SSA_NAME
)
1972 ret
|= remove_prop_source_from_use (op1
);
1979 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
1982 simplify_vector_constructor (gimple_stmt_iterator
*gsi
)
1984 gimple stmt
= gsi_stmt (*gsi
);
1986 tree op
, op2
, orig
, type
, elem_type
;
1987 unsigned elem_size
, nelts
, i
;
1988 enum tree_code code
;
1989 constructor_elt
*elt
;
1993 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
);
1995 op
= gimple_assign_rhs1 (stmt
);
1996 type
= TREE_TYPE (op
);
1997 gcc_checking_assert (TREE_CODE (type
) == VECTOR_TYPE
);
1999 nelts
= TYPE_VECTOR_SUBPARTS (type
);
2000 elem_type
= TREE_TYPE (type
);
2001 elem_size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
2003 sel
= XALLOCAVEC (unsigned char, nelts
);
2006 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op
), i
, elt
)
2013 if (TREE_CODE (elt
->value
) != SSA_NAME
)
2015 def_stmt
= get_prop_source_stmt (elt
->value
, false, NULL
);
2018 code
= gimple_assign_rhs_code (def_stmt
);
2019 if (code
!= BIT_FIELD_REF
)
2021 op1
= gimple_assign_rhs1 (def_stmt
);
2022 ref
= TREE_OPERAND (op1
, 0);
2030 if (TREE_CODE (ref
) != SSA_NAME
)
2032 if (!useless_type_conversion_p (type
, TREE_TYPE (ref
)))
2036 if (TREE_INT_CST_LOW (TREE_OPERAND (op1
, 1)) != elem_size
)
2038 sel
[i
] = TREE_INT_CST_LOW (TREE_OPERAND (op1
, 2)) / elem_size
;
2039 if (sel
[i
] != i
) maybe_ident
= false;
2045 gimple_assign_set_rhs_from_tree (gsi
, orig
);
2048 tree mask_type
, *mask_elts
;
2050 if (!can_vec_perm_p (TYPE_MODE (type
), false, sel
))
2053 = build_vector_type (build_nonstandard_integer_type (elem_size
, 1),
2055 if (GET_MODE_CLASS (TYPE_MODE (mask_type
)) != MODE_VECTOR_INT
2056 || GET_MODE_SIZE (TYPE_MODE (mask_type
))
2057 != GET_MODE_SIZE (TYPE_MODE (type
)))
2059 mask_elts
= XALLOCAVEC (tree
, nelts
);
2060 for (i
= 0; i
< nelts
; i
++)
2061 mask_elts
[i
] = build_int_cst (TREE_TYPE (mask_type
), sel
[i
]);
2062 op2
= build_vector (mask_type
, mask_elts
);
2063 gimple_assign_set_rhs_with_ops (gsi
, VEC_PERM_EXPR
, orig
, orig
, op2
);
2065 update_stmt (gsi_stmt (*gsi
));
2070 /* Primitive "lattice" function for gimple_simplify. */
2073 fwprop_ssa_val (tree name
)
2075 /* First valueize NAME. */
2076 if (TREE_CODE (name
) == SSA_NAME
2077 && SSA_NAME_VERSION (name
) < lattice
.length ())
2079 tree val
= lattice
[SSA_NAME_VERSION (name
)];
2083 /* We continue matching along SSA use-def edges for SSA names
2084 that are not single-use. Currently there are no patterns
2085 that would cause any issues with that. */
2089 /* Main entry point for the forward propagation and statement combine
2094 const pass_data pass_data_forwprop
=
2096 GIMPLE_PASS
, /* type */
2097 "forwprop", /* name */
2098 OPTGROUP_NONE
, /* optinfo_flags */
2099 TV_TREE_FORWPROP
, /* tv_id */
2100 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2101 0, /* properties_provided */
2102 0, /* properties_destroyed */
2103 0, /* todo_flags_start */
2104 TODO_update_ssa
, /* todo_flags_finish */
2107 class pass_forwprop
: public gimple_opt_pass
2110 pass_forwprop (gcc::context
*ctxt
)
2111 : gimple_opt_pass (pass_data_forwprop
, ctxt
)
2114 /* opt_pass methods: */
2115 opt_pass
* clone () { return new pass_forwprop (m_ctxt
); }
2116 virtual bool gate (function
*) { return flag_tree_forwprop
; }
2117 virtual unsigned int execute (function
*);
2119 }; // class pass_forwprop
2122 pass_forwprop::execute (function
*fun
)
2124 unsigned int todoflags
= 0;
2126 cfg_changed
= false;
2128 /* Combine stmts with the stmts defining their operands. Do that
2129 in an order that guarantees visiting SSA defs before SSA uses. */
2130 lattice
.create (num_ssa_names
);
2131 lattice
.quick_grow_cleared (num_ssa_names
);
2132 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
2133 int postorder_num
= inverted_post_order_compute (postorder
);
2134 auto_vec
<gimple
, 4> to_fixup
;
2135 to_purge
= BITMAP_ALLOC (NULL
);
2136 for (int i
= 0; i
< postorder_num
; ++i
)
2138 gimple_stmt_iterator gsi
;
2139 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, postorder
[i
]);
2141 /* Apply forward propagation to all stmts in the basic-block.
2142 Note we update GSI within the loop as necessary. */
2143 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2145 gimple stmt
= gsi_stmt (gsi
);
2147 enum tree_code code
;
2149 if (!is_gimple_assign (stmt
))
2155 lhs
= gimple_assign_lhs (stmt
);
2156 rhs
= gimple_assign_rhs1 (stmt
);
2157 code
= gimple_assign_rhs_code (stmt
);
2158 if (TREE_CODE (lhs
) != SSA_NAME
2159 || has_zero_uses (lhs
))
2165 /* If this statement sets an SSA_NAME to an address,
2166 try to propagate the address into the uses of the SSA_NAME. */
2167 if (code
== ADDR_EXPR
2168 /* Handle pointer conversions on invariant addresses
2169 as well, as this is valid gimple. */
2170 || (CONVERT_EXPR_CODE_P (code
)
2171 && TREE_CODE (rhs
) == ADDR_EXPR
2172 && POINTER_TYPE_P (TREE_TYPE (lhs
))))
2174 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2177 || decl_address_invariant_p (base
))
2178 && !stmt_references_abnormal_ssa_name (stmt
)
2179 && forward_propagate_addr_expr (lhs
, rhs
, true))
2181 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2182 release_defs (stmt
);
2183 gsi_remove (&gsi
, true);
2188 else if (code
== POINTER_PLUS_EXPR
)
2190 tree off
= gimple_assign_rhs2 (stmt
);
2191 if (TREE_CODE (off
) == INTEGER_CST
2192 && can_propagate_from (stmt
)
2193 && !simple_iv_increment_p (stmt
)
2194 /* ??? Better adjust the interface to that function
2195 instead of building new trees here. */
2196 && forward_propagate_addr_expr
2198 build1_loc (gimple_location (stmt
),
2199 ADDR_EXPR
, TREE_TYPE (rhs
),
2200 fold_build2 (MEM_REF
,
2201 TREE_TYPE (TREE_TYPE (rhs
)),
2203 fold_convert (ptr_type_node
,
2206 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2207 release_defs (stmt
);
2208 gsi_remove (&gsi
, true);
2210 else if (is_gimple_min_invariant (rhs
))
2212 /* Make sure to fold &a[0] + off_1 here. */
2213 fold_stmt_inplace (&gsi
);
2215 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2221 else if (TREE_CODE (TREE_TYPE (lhs
)) == COMPLEX_TYPE
2222 && gimple_assign_load_p (stmt
)
2223 && !gimple_has_volatile_ops (stmt
)
2224 && (TREE_CODE (gimple_assign_rhs1 (stmt
))
2226 && !stmt_can_throw_internal (stmt
))
2228 /* Rewrite loads used only in real/imagpart extractions to
2229 component-wise loads. */
2230 use_operand_p use_p
;
2231 imm_use_iterator iter
;
2232 bool rewrite
= true;
2233 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
2235 gimple use_stmt
= USE_STMT (use_p
);
2236 if (is_gimple_debug (use_stmt
))
2238 if (!is_gimple_assign (use_stmt
)
2239 || (gimple_assign_rhs_code (use_stmt
) != REALPART_EXPR
2240 && gimple_assign_rhs_code (use_stmt
) != IMAGPART_EXPR
))
2249 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2251 if (is_gimple_debug (use_stmt
))
2253 if (gimple_debug_bind_p (use_stmt
))
2255 gimple_debug_bind_reset_value (use_stmt
);
2256 update_stmt (use_stmt
);
2261 tree new_rhs
= build1 (gimple_assign_rhs_code (use_stmt
),
2262 TREE_TYPE (TREE_TYPE (rhs
)),
2263 unshare_expr (rhs
));
2265 = gimple_build_assign (gimple_assign_lhs (use_stmt
),
2268 location_t loc
= gimple_location (use_stmt
);
2269 gimple_set_location (new_stmt
, loc
);
2270 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2271 unlink_stmt_vdef (use_stmt
);
2272 gsi_remove (&gsi2
, true);
2274 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
2277 release_defs (stmt
);
2278 gsi_remove (&gsi
, true);
2283 else if (code
== COMPLEX_EXPR
)
2285 /* Rewrite stores of a single-use complex build expression
2286 to component-wise stores. */
2287 use_operand_p use_p
;
2289 if (single_imm_use (lhs
, &use_p
, &use_stmt
)
2290 && gimple_store_p (use_stmt
)
2291 && !gimple_has_volatile_ops (use_stmt
)
2292 && is_gimple_assign (use_stmt
)
2293 && (TREE_CODE (gimple_assign_lhs (use_stmt
))
2296 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2297 tree new_lhs
= build1 (REALPART_EXPR
,
2298 TREE_TYPE (TREE_TYPE (use_lhs
)),
2299 unshare_expr (use_lhs
));
2300 gimple new_stmt
= gimple_build_assign (new_lhs
, rhs
);
2301 location_t loc
= gimple_location (use_stmt
);
2302 gimple_set_location (new_stmt
, loc
);
2303 gimple_set_vuse (new_stmt
, gimple_vuse (use_stmt
));
2304 gimple_set_vdef (new_stmt
, make_ssa_name (gimple_vop (cfun
)));
2305 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt
)) = new_stmt
;
2306 gimple_set_vuse (use_stmt
, gimple_vdef (new_stmt
));
2307 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2308 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
2310 new_lhs
= build1 (IMAGPART_EXPR
,
2311 TREE_TYPE (TREE_TYPE (use_lhs
)),
2312 unshare_expr (use_lhs
));
2313 gimple_assign_set_lhs (use_stmt
, new_lhs
);
2314 gimple_assign_set_rhs1 (use_stmt
, gimple_assign_rhs2 (stmt
));
2315 update_stmt (use_stmt
);
2317 release_defs (stmt
);
2318 gsi_remove (&gsi
, true);
2327 /* Combine stmts with the stmts defining their operands.
2328 Note we update GSI within the loop as necessary. */
2329 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2331 gimple stmt
= gsi_stmt (gsi
);
2332 gimple orig_stmt
= stmt
;
2333 bool changed
= false;
2334 bool was_noreturn
= (is_gimple_call (stmt
)
2335 && gimple_call_noreturn_p (stmt
));
2337 /* Mark stmt as potentially needing revisiting. */
2338 gimple_set_plf (stmt
, GF_PLF_1
, false);
2340 if (fold_stmt (&gsi
, fwprop_ssa_val
))
2343 stmt
= gsi_stmt (gsi
);
2344 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
2345 bitmap_set_bit (to_purge
, bb
->index
);
2347 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
2348 to_fixup
.safe_push (stmt
);
2349 /* Cleanup the CFG if we simplified a condition to
2351 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2352 if (gimple_cond_true_p (cond
)
2353 || gimple_cond_false_p (cond
))
2358 switch (gimple_code (stmt
))
2362 tree rhs1
= gimple_assign_rhs1 (stmt
);
2363 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2365 if (code
== COND_EXPR
2366 || code
== VEC_COND_EXPR
)
2368 /* In this case the entire COND_EXPR is in rhs1. */
2369 if (forward_propagate_into_cond (&gsi
))
2372 stmt
= gsi_stmt (gsi
);
2375 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2378 did_something
= forward_propagate_into_comparison (&gsi
);
2379 if (did_something
== 2)
2381 changed
= did_something
!= 0;
2383 else if ((code
== PLUS_EXPR
2384 || code
== BIT_IOR_EXPR
2385 || code
== BIT_XOR_EXPR
)
2386 && simplify_rotate (&gsi
))
2388 else if (code
== VEC_PERM_EXPR
)
2390 int did_something
= simplify_permutation (&gsi
);
2391 if (did_something
== 2)
2393 changed
= did_something
!= 0;
2395 else if (code
== BIT_FIELD_REF
)
2396 changed
= simplify_bitfield_ref (&gsi
);
2397 else if (code
== CONSTRUCTOR
2398 && TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
2399 changed
= simplify_vector_constructor (&gsi
);
2404 changed
= simplify_gimple_switch (as_a
<gswitch
*> (stmt
));
2410 = forward_propagate_into_gimple_cond (as_a
<gcond
*> (stmt
));
2411 if (did_something
== 2)
2413 changed
= did_something
!= 0;
2419 tree callee
= gimple_call_fndecl (stmt
);
2420 if (callee
!= NULL_TREE
2421 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2422 changed
= simplify_builtin_call (&gsi
, callee
);
2431 /* If the stmt changed then re-visit it and the statements
2432 inserted before it. */
2433 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2434 if (gimple_plf (gsi_stmt (gsi
), GF_PLF_1
))
2436 if (gsi_end_p (gsi
))
2437 gsi
= gsi_start_bb (bb
);
2443 /* Stmt no longer needs to be revisited. */
2444 gimple_set_plf (stmt
, GF_PLF_1
, true);
2446 /* Fill up the lattice. */
2447 if (gimple_assign_single_p (stmt
))
2449 tree lhs
= gimple_assign_lhs (stmt
);
2450 tree rhs
= gimple_assign_rhs1 (stmt
);
2451 if (TREE_CODE (lhs
) == SSA_NAME
)
2454 if (TREE_CODE (rhs
) == SSA_NAME
)
2455 val
= fwprop_ssa_val (rhs
);
2456 else if (is_gimple_min_invariant (rhs
))
2458 fwprop_set_lattice_val (lhs
, val
);
2469 /* Fixup stmts that became noreturn calls. This may require splitting
2470 blocks and thus isn't possible during the walk. Do this
2471 in reverse order so we don't inadvertedly remove a stmt we want to
2472 fixup by visiting a dominating now noreturn call first. */
2473 while (!to_fixup
.is_empty ())
2475 gimple stmt
= to_fixup
.pop ();
2476 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2478 fprintf (dump_file
, "Fixing up noreturn call ");
2479 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2480 fprintf (dump_file
, "\n");
2482 cfg_changed
|= fixup_noreturn_call (stmt
);
2485 cfg_changed
|= gimple_purge_all_dead_eh_edges (to_purge
);
2486 BITMAP_FREE (to_purge
);
2489 todoflags
|= TODO_cleanup_cfg
;
2497 make_pass_forwprop (gcc::context
*ctxt
)
2499 return new pass_forwprop (ctxt
);