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"
27 #include "double-int.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
38 #include "hard-reg-set.h"
41 #include "dominance.h"
43 #include "basic-block.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-ssa-alias.h"
46 #include "internal-fn.h"
47 #include "gimple-fold.h"
49 #include "gimple-expr.h"
53 #include "gimple-iterator.h"
54 #include "gimplify-me.h"
55 #include "gimple-ssa.h"
57 #include "tree-phinodes.h"
58 #include "ssa-iterators.h"
59 #include "stringpool.h"
60 #include "tree-ssanames.h"
63 #include "tree-pass.h"
64 #include "langhooks.h"
66 #include "diagnostic.h"
69 #include "insn-codes.h"
71 #include "tree-ssa-propagate.h"
72 #include "tree-ssa-dom.h"
74 #include "tree-cfgcleanup.h"
75 #include "tree-into-ssa.h"
78 /* This pass propagates the RHS of assignment statements into use
79 sites of the LHS of the assignment. It's basically a specialized
80 form of tree combination. It is hoped all of this can disappear
81 when we have a generalized tree combiner.
83 One class of common cases we handle is forward propagating a single use
84 variable into a COND_EXPR.
88 if (x) goto ... else goto ...
90 Will be transformed into:
93 if (a COND b) goto ... else goto ...
95 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
97 Or (assuming c1 and c2 are constants):
101 if (x EQ/NEQ c2) goto ... else goto ...
103 Will be transformed into:
106 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
108 Similarly for x = a - c1.
114 if (x) goto ... else goto ...
116 Will be transformed into:
119 if (a == 0) goto ... else goto ...
121 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
122 For these cases, we propagate A into all, possibly more than one,
123 COND_EXPRs that use X.
129 if (x) goto ... else goto ...
131 Will be transformed into:
134 if (a != 0) goto ... else goto ...
136 (Assuming a is an integral type and x is a boolean or x is an
137 integral and a is a boolean.)
139 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
140 For these cases, we propagate A into all, possibly more than one,
141 COND_EXPRs that use X.
143 In addition to eliminating the variable and the statement which assigns
144 a value to the variable, we may be able to later thread the jump without
145 adding insane complexity in the dominator optimizer.
147 Also note these transformations can cascade. We handle this by having
148 a worklist of COND_EXPR statements to examine. As we make a change to
149 a statement, we put it back on the worklist to examine on the next
150 iteration of the main loop.
152 A second class of propagation opportunities arises for ADDR_EXPR
163 ptr = (type1*)&type2var;
166 Will get turned into (if type1 and type2 are the same size
167 and neither have volatile on them):
168 res = VIEW_CONVERT_EXPR<type1>(type2var)
173 ptr2 = ptr + <constant>;
177 ptr2 = &x[constant/elementsize];
182 offset = index * element_size;
183 offset_p = (pointer) offset;
184 ptr2 = ptr + offset_p
186 Will get turned into:
194 Provided that decl has known alignment >= 2, will get turned into
198 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
199 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
202 This will (of course) be extended as other needs arise. */
204 static bool forward_propagate_addr_expr (tree
, tree
, bool);
206 /* Set to true if we delete dead edges during the optimization. */
207 static bool cfg_changed
;
209 static tree
rhs_to_tree (tree type
, gimple stmt
);
211 static bitmap to_purge
;
213 /* Const-and-copy lattice. */
214 static vec
<tree
> lattice
;
216 /* Set the lattice entry for NAME to VAL. */
218 fwprop_set_lattice_val (tree name
, tree val
)
220 if (TREE_CODE (name
) == SSA_NAME
)
222 if (SSA_NAME_VERSION (name
) >= lattice
.length ())
224 lattice
.reserve (num_ssa_names
- lattice
.length ());
225 lattice
.quick_grow_cleared (num_ssa_names
);
227 lattice
[SSA_NAME_VERSION (name
)] = val
;
231 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
233 fwprop_invalidate_lattice (tree name
)
236 && TREE_CODE (name
) == SSA_NAME
237 && SSA_NAME_VERSION (name
) < lattice
.length ())
238 lattice
[SSA_NAME_VERSION (name
)] = NULL_TREE
;
242 /* Get the statement we can propagate from into NAME skipping
243 trivial copies. Returns the statement which defines the
244 propagation source or NULL_TREE if there is no such one.
245 If SINGLE_USE_ONLY is set considers only sources which have
246 a single use chain up to NAME. If SINGLE_USE_P is non-null,
247 it is set to whether the chain to NAME is a single use chain
248 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
251 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
253 bool single_use
= true;
256 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
258 if (!has_single_use (name
))
265 /* If name is defined by a PHI node or is the default def, bail out. */
266 if (!is_gimple_assign (def_stmt
))
269 /* If def_stmt is a simple copy, continue looking. */
270 if (gimple_assign_rhs_code (def_stmt
) == SSA_NAME
)
271 name
= gimple_assign_rhs1 (def_stmt
);
274 if (!single_use_only
&& single_use_p
)
275 *single_use_p
= single_use
;
282 /* Checks if the destination ssa name in DEF_STMT can be used as
283 propagation source. Returns true if so, otherwise false. */
286 can_propagate_from (gimple def_stmt
)
288 gcc_assert (is_gimple_assign (def_stmt
));
290 /* If the rhs has side-effects we cannot propagate from it. */
291 if (gimple_has_volatile_ops (def_stmt
))
294 /* If the rhs is a load we cannot propagate from it. */
295 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_reference
296 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_declaration
)
299 /* Constants can be always propagated. */
300 if (gimple_assign_single_p (def_stmt
)
301 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
304 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
305 if (stmt_references_abnormal_ssa_name (def_stmt
))
308 /* If the definition is a conversion of a pointer to a function type,
309 then we can not apply optimizations as some targets require
310 function pointers to be canonicalized and in this case this
311 optimization could eliminate a necessary canonicalization. */
312 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
314 tree rhs
= gimple_assign_rhs1 (def_stmt
);
315 if (POINTER_TYPE_P (TREE_TYPE (rhs
))
316 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs
))) == FUNCTION_TYPE
)
323 /* Remove a chain of dead statements starting at the definition of
324 NAME. The chain is linked via the first operand of the defining statements.
325 If NAME was replaced in its only use then this function can be used
326 to clean up dead stmts. The function handles already released SSA
328 Returns true if cleanup-cfg has to run. */
331 remove_prop_source_from_use (tree name
)
333 gimple_stmt_iterator gsi
;
335 bool cfg_changed
= false;
340 if (SSA_NAME_IN_FREE_LIST (name
)
341 || SSA_NAME_IS_DEFAULT_DEF (name
)
342 || !has_zero_uses (name
))
345 stmt
= SSA_NAME_DEF_STMT (name
);
346 if (gimple_code (stmt
) == GIMPLE_PHI
347 || gimple_has_side_effects (stmt
))
350 bb
= gimple_bb (stmt
);
351 gsi
= gsi_for_stmt (stmt
);
352 unlink_stmt_vdef (stmt
);
353 if (gsi_remove (&gsi
, true))
354 bitmap_set_bit (to_purge
, bb
->index
);
355 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
358 name
= is_gimple_assign (stmt
) ? gimple_assign_rhs1 (stmt
) : NULL_TREE
;
359 } while (name
&& TREE_CODE (name
) == SSA_NAME
);
364 /* Return the rhs of a gassign *STMT in a form of a single tree,
365 converted to type TYPE.
367 This should disappear, but is needed so we can combine expressions and use
368 the fold() interfaces. Long term, we need to develop folding and combine
369 routines that deal with gimple exclusively . */
372 rhs_to_tree (tree type
, gimple stmt
)
374 location_t loc
= gimple_location (stmt
);
375 enum tree_code code
= gimple_assign_rhs_code (stmt
);
376 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
377 return fold_build3_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
378 gimple_assign_rhs2 (stmt
),
379 gimple_assign_rhs3 (stmt
));
380 else if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
381 return fold_build2_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
382 gimple_assign_rhs2 (stmt
));
383 else if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
384 return build1 (code
, type
, gimple_assign_rhs1 (stmt
));
385 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
386 return gimple_assign_rhs1 (stmt
);
391 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
392 the folded result in a form suitable for COND_EXPR_COND or
393 NULL_TREE, if there is no suitable simplified form. If
394 INVARIANT_ONLY is true only gimple_min_invariant results are
395 considered simplified. */
398 combine_cond_expr_cond (gimple stmt
, enum tree_code code
, tree type
,
399 tree op0
, tree op1
, bool invariant_only
)
403 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
405 fold_defer_overflow_warnings ();
406 t
= fold_binary_loc (gimple_location (stmt
), code
, type
, op0
, op1
);
409 fold_undefer_overflow_warnings (false, NULL
, 0);
413 /* Require that we got a boolean type out if we put one in. */
414 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
416 /* Canonicalize the combined condition for use in a COND_EXPR. */
417 t
= canonicalize_cond_expr_cond (t
);
419 /* Bail out if we required an invariant but didn't get one. */
420 if (!t
|| (invariant_only
&& !is_gimple_min_invariant (t
)))
422 fold_undefer_overflow_warnings (false, NULL
, 0);
426 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt
), stmt
, 0);
431 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
432 of its operand. Return a new comparison tree or NULL_TREE if there
433 were no simplifying combines. */
436 forward_propagate_into_comparison_1 (gimple stmt
,
437 enum tree_code code
, tree type
,
440 tree tmp
= NULL_TREE
;
441 tree rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
442 bool single_use0_p
= false, single_use1_p
= false;
444 /* For comparisons use the first operand, that is likely to
445 simplify comparisons against constants. */
446 if (TREE_CODE (op0
) == SSA_NAME
)
448 gimple def_stmt
= get_prop_source_stmt (op0
, false, &single_use0_p
);
449 if (def_stmt
&& can_propagate_from (def_stmt
))
451 enum tree_code def_code
= gimple_assign_rhs_code (def_stmt
);
452 bool invariant_only_p
= !single_use0_p
;
454 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
456 /* Always combine comparisons or conversions from booleans. */
457 if (TREE_CODE (op1
) == INTEGER_CST
458 && ((CONVERT_EXPR_CODE_P (def_code
)
459 && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0
, 0)))
461 || TREE_CODE_CLASS (def_code
) == tcc_comparison
))
462 invariant_only_p
= false;
464 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
465 rhs0
, op1
, invariant_only_p
);
471 /* If that wasn't successful, try the second operand. */
472 if (TREE_CODE (op1
) == SSA_NAME
)
474 gimple def_stmt
= get_prop_source_stmt (op1
, false, &single_use1_p
);
475 if (def_stmt
&& can_propagate_from (def_stmt
))
477 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
478 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
479 op0
, rhs1
, !single_use1_p
);
485 /* If that wasn't successful either, try both operands. */
486 if (rhs0
!= NULL_TREE
487 && rhs1
!= NULL_TREE
)
488 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
490 !(single_use0_p
&& single_use1_p
));
495 /* Propagate from the ssa name definition statements of the assignment
496 from a comparison at *GSI into the conditional if that simplifies it.
497 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
498 otherwise returns 0. */
501 forward_propagate_into_comparison (gimple_stmt_iterator
*gsi
)
503 gimple stmt
= gsi_stmt (*gsi
);
505 bool cfg_changed
= false;
506 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
507 tree rhs1
= gimple_assign_rhs1 (stmt
);
508 tree rhs2
= gimple_assign_rhs2 (stmt
);
510 /* Combine the comparison with defining statements. */
511 tmp
= forward_propagate_into_comparison_1 (stmt
,
512 gimple_assign_rhs_code (stmt
),
514 if (tmp
&& useless_type_conversion_p (type
, TREE_TYPE (tmp
)))
516 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
518 update_stmt (gsi_stmt (*gsi
));
520 if (TREE_CODE (rhs1
) == SSA_NAME
)
521 cfg_changed
|= remove_prop_source_from_use (rhs1
);
522 if (TREE_CODE (rhs2
) == SSA_NAME
)
523 cfg_changed
|= remove_prop_source_from_use (rhs2
);
524 return cfg_changed
? 2 : 1;
530 /* Propagate from the ssa name definition statements of COND_EXPR
531 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
532 Returns zero if no statement was changed, one if there were
533 changes and two if cfg_cleanup needs to run.
535 This must be kept in sync with forward_propagate_into_cond. */
538 forward_propagate_into_gimple_cond (gcond
*stmt
)
541 enum tree_code code
= gimple_cond_code (stmt
);
542 bool cfg_changed
= false;
543 tree rhs1
= gimple_cond_lhs (stmt
);
544 tree rhs2
= gimple_cond_rhs (stmt
);
546 /* We can do tree combining on SSA_NAME and comparison expressions. */
547 if (TREE_CODE_CLASS (gimple_cond_code (stmt
)) != tcc_comparison
)
550 tmp
= forward_propagate_into_comparison_1 (stmt
, code
,
555 if (dump_file
&& tmp
)
557 fprintf (dump_file
, " Replaced '");
558 print_gimple_expr (dump_file
, stmt
, 0, 0);
559 fprintf (dump_file
, "' with '");
560 print_generic_expr (dump_file
, tmp
, 0);
561 fprintf (dump_file
, "'\n");
564 gimple_cond_set_condition_from_tree (stmt
, unshare_expr (tmp
));
567 if (TREE_CODE (rhs1
) == SSA_NAME
)
568 cfg_changed
|= remove_prop_source_from_use (rhs1
);
569 if (TREE_CODE (rhs2
) == SSA_NAME
)
570 cfg_changed
|= remove_prop_source_from_use (rhs2
);
571 return (cfg_changed
|| is_gimple_min_invariant (tmp
)) ? 2 : 1;
574 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
575 if ((TREE_CODE (TREE_TYPE (rhs1
)) == BOOLEAN_TYPE
576 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
577 && TYPE_PRECISION (TREE_TYPE (rhs1
)) == 1))
579 && integer_zerop (rhs2
))
581 && integer_onep (rhs2
))))
583 basic_block bb
= gimple_bb (stmt
);
584 gimple_cond_set_code (stmt
, NE_EXPR
);
585 gimple_cond_set_rhs (stmt
, build_zero_cst (TREE_TYPE (rhs1
)));
586 EDGE_SUCC (bb
, 0)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
587 EDGE_SUCC (bb
, 1)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
595 /* Propagate from the ssa name definition statements of COND_EXPR
596 in the rhs of statement STMT into the conditional if that simplifies it.
597 Returns true zero if the stmt was changed. */
600 forward_propagate_into_cond (gimple_stmt_iterator
*gsi_p
)
602 gimple stmt
= gsi_stmt (*gsi_p
);
603 tree tmp
= NULL_TREE
;
604 tree cond
= gimple_assign_rhs1 (stmt
);
605 enum tree_code code
= gimple_assign_rhs_code (stmt
);
607 /* We can do tree combining on SSA_NAME and comparison expressions. */
608 if (COMPARISON_CLASS_P (cond
))
609 tmp
= forward_propagate_into_comparison_1 (stmt
, TREE_CODE (cond
),
611 TREE_OPERAND (cond
, 0),
612 TREE_OPERAND (cond
, 1));
613 else if (TREE_CODE (cond
) == SSA_NAME
)
615 enum tree_code def_code
;
617 gimple def_stmt
= get_prop_source_stmt (name
, true, NULL
);
618 if (!def_stmt
|| !can_propagate_from (def_stmt
))
621 def_code
= gimple_assign_rhs_code (def_stmt
);
622 if (TREE_CODE_CLASS (def_code
) == tcc_comparison
)
623 tmp
= fold_build2_loc (gimple_location (def_stmt
),
626 gimple_assign_rhs1 (def_stmt
),
627 gimple_assign_rhs2 (def_stmt
));
631 && is_gimple_condexpr (tmp
))
633 if (dump_file
&& tmp
)
635 fprintf (dump_file
, " Replaced '");
636 print_generic_expr (dump_file
, cond
, 0);
637 fprintf (dump_file
, "' with '");
638 print_generic_expr (dump_file
, tmp
, 0);
639 fprintf (dump_file
, "'\n");
642 if ((code
== VEC_COND_EXPR
) ? integer_all_onesp (tmp
)
643 : integer_onep (tmp
))
644 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs2 (stmt
));
645 else if (integer_zerop (tmp
))
646 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs3 (stmt
));
648 gimple_assign_set_rhs1 (stmt
, unshare_expr (tmp
));
649 stmt
= gsi_stmt (*gsi_p
);
658 /* We've just substituted an ADDR_EXPR into stmt. Update all the
659 relevant data structures to match. */
662 tidy_after_forward_propagate_addr (gimple stmt
)
664 /* We may have turned a trapping insn into a non-trapping insn. */
665 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
666 bitmap_set_bit (to_purge
, gimple_bb (stmt
)->index
);
668 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
669 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
672 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
673 ADDR_EXPR <whatever>.
675 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
676 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
677 node or for recovery of array indexing from pointer arithmetic.
679 Return true if the propagation was successful (the propagation can
680 be not totally successful, yet things may have been changed). */
683 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
,
684 gimple_stmt_iterator
*use_stmt_gsi
,
687 tree lhs
, rhs
, rhs2
, array_ref
;
688 gimple use_stmt
= gsi_stmt (*use_stmt_gsi
);
689 enum tree_code rhs_code
;
692 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
694 lhs
= gimple_assign_lhs (use_stmt
);
695 rhs_code
= gimple_assign_rhs_code (use_stmt
);
696 rhs
= gimple_assign_rhs1 (use_stmt
);
698 /* Do not perform copy-propagation but recurse through copy chains. */
699 if (TREE_CODE (lhs
) == SSA_NAME
700 && rhs_code
== SSA_NAME
)
701 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
703 /* The use statement could be a conversion. Recurse to the uses of the
704 lhs as copyprop does not copy through pointer to integer to pointer
705 conversions and FRE does not catch all cases either.
706 Treat the case of a single-use name and
707 a conversion to def_rhs type separate, though. */
708 if (TREE_CODE (lhs
) == SSA_NAME
709 && CONVERT_EXPR_CODE_P (rhs_code
))
711 /* If there is a point in a conversion chain where the types match
712 so we can remove a conversion re-materialize the address here
715 && useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
717 gimple_assign_set_rhs1 (use_stmt
, unshare_expr (def_rhs
));
718 gimple_assign_set_rhs_code (use_stmt
, TREE_CODE (def_rhs
));
722 /* Else recurse if the conversion preserves the address value. */
723 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
724 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
725 && (TYPE_PRECISION (TREE_TYPE (lhs
))
726 >= TYPE_PRECISION (TREE_TYPE (def_rhs
))))
727 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
732 /* If this isn't a conversion chain from this on we only can propagate
733 into compatible pointer contexts. */
734 if (!types_compatible_p (TREE_TYPE (name
), TREE_TYPE (def_rhs
)))
737 /* Propagate through constant pointer adjustments. */
738 if (TREE_CODE (lhs
) == SSA_NAME
739 && rhs_code
== POINTER_PLUS_EXPR
741 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
)
744 /* As we come here with non-invariant addresses in def_rhs we need
745 to make sure we can build a valid constant offsetted address
746 for further propagation. Simply rely on fold building that
747 and check after the fact. */
748 new_def_rhs
= fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (rhs
)),
750 fold_convert (ptr_type_node
,
751 gimple_assign_rhs2 (use_stmt
)));
752 if (TREE_CODE (new_def_rhs
) == MEM_REF
753 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs
, 0)))
755 new_def_rhs
= build_fold_addr_expr_with_type (new_def_rhs
,
758 /* Recurse. If we could propagate into all uses of lhs do not
759 bother to replace into the current use but just pretend we did. */
760 if (TREE_CODE (new_def_rhs
) == ADDR_EXPR
761 && forward_propagate_addr_expr (lhs
, new_def_rhs
, single_use_p
))
764 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (new_def_rhs
)))
765 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, TREE_CODE (new_def_rhs
),
767 else if (is_gimple_min_invariant (new_def_rhs
))
768 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, NOP_EXPR
, new_def_rhs
);
771 gcc_assert (gsi_stmt (*use_stmt_gsi
) == use_stmt
);
772 update_stmt (use_stmt
);
776 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
777 ADDR_EXPR will not appear on the LHS. */
778 tree
*lhsp
= gimple_assign_lhs_ptr (use_stmt
);
779 while (handled_component_p (*lhsp
))
780 lhsp
= &TREE_OPERAND (*lhsp
, 0);
783 /* Now see if the LHS node is a MEM_REF using NAME. If so,
784 propagate the ADDR_EXPR into the use of NAME and fold the result. */
785 if (TREE_CODE (lhs
) == MEM_REF
786 && TREE_OPERAND (lhs
, 0) == name
)
789 HOST_WIDE_INT def_rhs_offset
;
790 /* If the address is invariant we can always fold it. */
791 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
794 offset_int off
= mem_ref_offset (lhs
);
796 off
+= def_rhs_offset
;
797 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
799 off
+= mem_ref_offset (def_rhs_base
);
800 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
803 new_ptr
= build_fold_addr_expr (def_rhs_base
);
804 TREE_OPERAND (lhs
, 0) = new_ptr
;
805 TREE_OPERAND (lhs
, 1)
806 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs
, 1)), off
);
807 tidy_after_forward_propagate_addr (use_stmt
);
808 /* Continue propagating into the RHS if this was not the only use. */
812 /* If the LHS is a plain dereference and the value type is the same as
813 that of the pointed-to type of the address we can put the
814 dereferenced address on the LHS preserving the original alias-type. */
815 else if (integer_zerop (TREE_OPERAND (lhs
, 1))
816 && ((gimple_assign_lhs (use_stmt
) == lhs
817 && useless_type_conversion_p
818 (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)),
819 TREE_TYPE (gimple_assign_rhs1 (use_stmt
))))
820 || types_compatible_p (TREE_TYPE (lhs
),
821 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
822 /* Don't forward anything into clobber stmts if it would result
823 in the lhs no longer being a MEM_REF. */
824 && (!gimple_clobber_p (use_stmt
)
825 || TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == MEM_REF
))
827 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
828 tree new_offset
, new_base
, saved
, new_lhs
;
829 while (handled_component_p (*def_rhs_basep
))
830 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
831 saved
= *def_rhs_basep
;
832 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
834 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
835 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (lhs
, 1)),
836 TREE_OPERAND (*def_rhs_basep
, 1));
840 new_base
= build_fold_addr_expr (*def_rhs_basep
);
841 new_offset
= TREE_OPERAND (lhs
, 1);
843 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
844 new_base
, new_offset
);
845 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (lhs
);
846 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (lhs
);
847 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (lhs
);
848 new_lhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
850 TREE_THIS_VOLATILE (new_lhs
) = TREE_THIS_VOLATILE (lhs
);
851 TREE_SIDE_EFFECTS (new_lhs
) = TREE_SIDE_EFFECTS (lhs
);
852 *def_rhs_basep
= saved
;
853 tidy_after_forward_propagate_addr (use_stmt
);
854 /* Continue propagating into the RHS if this was not the
860 /* We can have a struct assignment dereferencing our name twice.
861 Note that we didn't propagate into the lhs to not falsely
862 claim we did when propagating into the rhs. */
866 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
867 nodes from the RHS. */
868 tree
*rhsp
= gimple_assign_rhs1_ptr (use_stmt
);
869 if (TREE_CODE (*rhsp
) == ADDR_EXPR
)
870 rhsp
= &TREE_OPERAND (*rhsp
, 0);
871 while (handled_component_p (*rhsp
))
872 rhsp
= &TREE_OPERAND (*rhsp
, 0);
875 /* Now see if the RHS node is a MEM_REF using NAME. If so,
876 propagate the ADDR_EXPR into the use of NAME and fold the result. */
877 if (TREE_CODE (rhs
) == MEM_REF
878 && TREE_OPERAND (rhs
, 0) == name
)
881 HOST_WIDE_INT def_rhs_offset
;
882 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
885 offset_int off
= mem_ref_offset (rhs
);
887 off
+= def_rhs_offset
;
888 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
890 off
+= mem_ref_offset (def_rhs_base
);
891 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
894 new_ptr
= build_fold_addr_expr (def_rhs_base
);
895 TREE_OPERAND (rhs
, 0) = new_ptr
;
896 TREE_OPERAND (rhs
, 1)
897 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs
, 1)), off
);
898 fold_stmt_inplace (use_stmt_gsi
);
899 tidy_after_forward_propagate_addr (use_stmt
);
902 /* If the RHS is a plain dereference and the value type is the same as
903 that of the pointed-to type of the address we can put the
904 dereferenced address on the RHS preserving the original alias-type. */
905 else if (integer_zerop (TREE_OPERAND (rhs
, 1))
906 && ((gimple_assign_rhs1 (use_stmt
) == rhs
907 && useless_type_conversion_p
908 (TREE_TYPE (gimple_assign_lhs (use_stmt
)),
909 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
910 || types_compatible_p (TREE_TYPE (rhs
),
911 TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))))
913 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
914 tree new_offset
, new_base
, saved
, new_rhs
;
915 while (handled_component_p (*def_rhs_basep
))
916 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
917 saved
= *def_rhs_basep
;
918 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
920 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
921 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (rhs
, 1)),
922 TREE_OPERAND (*def_rhs_basep
, 1));
926 new_base
= build_fold_addr_expr (*def_rhs_basep
);
927 new_offset
= TREE_OPERAND (rhs
, 1);
929 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
930 new_base
, new_offset
);
931 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (rhs
);
932 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (rhs
);
933 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (rhs
);
934 new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
936 TREE_THIS_VOLATILE (new_rhs
) = TREE_THIS_VOLATILE (rhs
);
937 TREE_SIDE_EFFECTS (new_rhs
) = TREE_SIDE_EFFECTS (rhs
);
938 *def_rhs_basep
= saved
;
939 fold_stmt_inplace (use_stmt_gsi
);
940 tidy_after_forward_propagate_addr (use_stmt
);
945 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
947 if (gimple_assign_rhs_code (use_stmt
) != POINTER_PLUS_EXPR
948 || gimple_assign_rhs1 (use_stmt
) != name
)
951 /* The remaining cases are all for turning pointer arithmetic into
952 array indexing. They only apply when we have the address of
953 element zero in an array. If that is not the case then there
955 array_ref
= TREE_OPERAND (def_rhs
, 0);
956 if ((TREE_CODE (array_ref
) != ARRAY_REF
957 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
958 || TREE_CODE (TREE_OPERAND (array_ref
, 1)) != INTEGER_CST
)
959 && TREE_CODE (TREE_TYPE (array_ref
)) != ARRAY_TYPE
)
962 rhs2
= gimple_assign_rhs2 (use_stmt
);
963 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
964 if (TREE_CODE (rhs2
) == INTEGER_CST
)
966 tree new_rhs
= build1_loc (gimple_location (use_stmt
),
967 ADDR_EXPR
, TREE_TYPE (def_rhs
),
968 fold_build2 (MEM_REF
,
969 TREE_TYPE (TREE_TYPE (def_rhs
)),
970 unshare_expr (def_rhs
),
971 fold_convert (ptr_type_node
,
973 gimple_assign_set_rhs_from_tree (use_stmt_gsi
, new_rhs
);
974 use_stmt
= gsi_stmt (*use_stmt_gsi
);
975 update_stmt (use_stmt
);
976 tidy_after_forward_propagate_addr (use_stmt
);
983 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
985 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
986 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
987 node or for recovery of array indexing from pointer arithmetic.
989 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
990 the single use in the previous invocation. Pass true when calling
993 Returns true, if all uses have been propagated into. */
996 forward_propagate_addr_expr (tree name
, tree rhs
, bool parent_single_use_p
)
998 imm_use_iterator iter
;
1001 bool single_use_p
= parent_single_use_p
&& has_single_use (name
);
1003 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
1008 /* If the use is not in a simple assignment statement, then
1009 there is nothing we can do. */
1010 if (!is_gimple_assign (use_stmt
))
1012 if (!is_gimple_debug (use_stmt
))
1017 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1018 result
= forward_propagate_addr_expr_1 (name
, rhs
, &gsi
,
1020 /* If the use has moved to a different statement adjust
1021 the update machinery for the old statement too. */
1022 if (use_stmt
!= gsi_stmt (gsi
))
1024 update_stmt (use_stmt
);
1025 use_stmt
= gsi_stmt (gsi
);
1027 update_stmt (use_stmt
);
1030 /* Remove intermediate now unused copy and conversion chains. */
1031 use_rhs
= gimple_assign_rhs1 (use_stmt
);
1033 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
1034 && TREE_CODE (use_rhs
) == SSA_NAME
1035 && has_zero_uses (gimple_assign_lhs (use_stmt
)))
1037 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1038 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt
));
1039 release_defs (use_stmt
);
1040 gsi_remove (&gsi
, true);
1044 return all
&& has_zero_uses (name
);
1048 /* Helper function for simplify_gimple_switch. Remove case labels that
1049 have values outside the range of the new type. */
1052 simplify_gimple_switch_label_vec (gswitch
*stmt
, tree index_type
)
1054 unsigned int branch_num
= gimple_switch_num_labels (stmt
);
1055 auto_vec
<tree
> labels (branch_num
);
1056 unsigned int i
, len
;
1058 /* Collect the existing case labels in a VEC, and preprocess it as if
1059 we are gimplifying a GENERIC SWITCH_EXPR. */
1060 for (i
= 1; i
< branch_num
; i
++)
1061 labels
.quick_push (gimple_switch_label (stmt
, i
));
1062 preprocess_case_label_vec_for_gimple (labels
, index_type
, NULL
);
1064 /* If any labels were removed, replace the existing case labels
1065 in the GIMPLE_SWITCH statement with the correct ones.
1066 Note that the type updates were done in-place on the case labels,
1067 so we only have to replace the case labels in the GIMPLE_SWITCH
1068 if the number of labels changed. */
1069 len
= labels
.length ();
1070 if (len
< branch_num
- 1)
1072 bitmap target_blocks
;
1076 /* Corner case: *all* case labels have been removed as being
1077 out-of-range for INDEX_TYPE. Push one label and let the
1078 CFG cleanups deal with this further. */
1083 label
= CASE_LABEL (gimple_switch_default_label (stmt
));
1084 elt
= build_case_label (build_int_cst (index_type
, 0), NULL
, label
);
1085 labels
.quick_push (elt
);
1089 for (i
= 0; i
< labels
.length (); i
++)
1090 gimple_switch_set_label (stmt
, i
+ 1, labels
[i
]);
1091 for (i
++ ; i
< branch_num
; i
++)
1092 gimple_switch_set_label (stmt
, i
, NULL_TREE
);
1093 gimple_switch_set_num_labels (stmt
, len
+ 1);
1095 /* Cleanup any edges that are now dead. */
1096 target_blocks
= BITMAP_ALLOC (NULL
);
1097 for (i
= 0; i
< gimple_switch_num_labels (stmt
); i
++)
1099 tree elt
= gimple_switch_label (stmt
, i
);
1100 basic_block target
= label_to_block (CASE_LABEL (elt
));
1101 bitmap_set_bit (target_blocks
, target
->index
);
1103 for (ei
= ei_start (gimple_bb (stmt
)->succs
); (e
= ei_safe_edge (ei
)); )
1105 if (! bitmap_bit_p (target_blocks
, e
->dest
->index
))
1109 free_dominance_info (CDI_DOMINATORS
);
1114 BITMAP_FREE (target_blocks
);
1118 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1119 the condition which we may be able to optimize better. */
1122 simplify_gimple_switch (gswitch
*stmt
)
1124 /* The optimization that we really care about is removing unnecessary
1125 casts. That will let us do much better in propagating the inferred
1126 constant at the switch target. */
1127 tree cond
= gimple_switch_index (stmt
);
1128 if (TREE_CODE (cond
) == SSA_NAME
)
1130 gimple def_stmt
= SSA_NAME_DEF_STMT (cond
);
1131 if (gimple_assign_cast_p (def_stmt
))
1133 tree def
= gimple_assign_rhs1 (def_stmt
);
1134 if (TREE_CODE (def
) != SSA_NAME
)
1137 /* If we have an extension or sign-change that preserves the
1138 values we check against then we can copy the source value into
1140 tree ti
= TREE_TYPE (def
);
1141 if (INTEGRAL_TYPE_P (ti
)
1142 && TYPE_PRECISION (ti
) <= TYPE_PRECISION (TREE_TYPE (cond
)))
1144 size_t n
= gimple_switch_num_labels (stmt
);
1145 tree min
= NULL_TREE
, max
= NULL_TREE
;
1148 min
= CASE_LOW (gimple_switch_label (stmt
, 1));
1149 if (CASE_HIGH (gimple_switch_label (stmt
, n
- 1)))
1150 max
= CASE_HIGH (gimple_switch_label (stmt
, n
- 1));
1152 max
= CASE_LOW (gimple_switch_label (stmt
, n
- 1));
1154 if ((!min
|| int_fits_type_p (min
, ti
))
1155 && (!max
|| int_fits_type_p (max
, ti
)))
1157 gimple_switch_set_index (stmt
, def
);
1158 simplify_gimple_switch_label_vec (stmt
, ti
);
1169 /* For pointers p2 and p1 return p2 - p1 if the
1170 difference is known and constant, otherwise return NULL. */
1173 constant_pointer_difference (tree p1
, tree p2
)
1176 #define CPD_ITERATIONS 5
1177 tree exps
[2][CPD_ITERATIONS
];
1178 tree offs
[2][CPD_ITERATIONS
];
1181 for (i
= 0; i
< 2; i
++)
1183 tree p
= i
? p1
: p2
;
1184 tree off
= size_zero_node
;
1186 enum tree_code code
;
1188 /* For each of p1 and p2 we need to iterate at least
1189 twice, to handle ADDR_EXPR directly in p1/p2,
1190 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1191 on definition's stmt RHS. Iterate a few extra times. */
1195 if (!POINTER_TYPE_P (TREE_TYPE (p
)))
1197 if (TREE_CODE (p
) == ADDR_EXPR
)
1199 tree q
= TREE_OPERAND (p
, 0);
1200 HOST_WIDE_INT offset
;
1201 tree base
= get_addr_base_and_unit_offset (q
, &offset
);
1206 off
= size_binop (PLUS_EXPR
, off
, size_int (offset
));
1208 if (TREE_CODE (q
) == MEM_REF
1209 && TREE_CODE (TREE_OPERAND (q
, 0)) == SSA_NAME
)
1211 p
= TREE_OPERAND (q
, 0);
1212 off
= size_binop (PLUS_EXPR
, off
,
1213 wide_int_to_tree (sizetype
,
1214 mem_ref_offset (q
)));
1223 if (TREE_CODE (p
) != SSA_NAME
)
1227 if (j
== CPD_ITERATIONS
)
1229 stmt
= SSA_NAME_DEF_STMT (p
);
1230 if (!is_gimple_assign (stmt
) || gimple_assign_lhs (stmt
) != p
)
1232 code
= gimple_assign_rhs_code (stmt
);
1233 if (code
== POINTER_PLUS_EXPR
)
1235 if (TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)
1237 off
= size_binop (PLUS_EXPR
, off
, gimple_assign_rhs2 (stmt
));
1238 p
= gimple_assign_rhs1 (stmt
);
1240 else if (code
== ADDR_EXPR
|| CONVERT_EXPR_CODE_P (code
))
1241 p
= gimple_assign_rhs1 (stmt
);
1249 for (i
= 0; i
< cnt
[0]; i
++)
1250 for (j
= 0; j
< cnt
[1]; j
++)
1251 if (exps
[0][i
] == exps
[1][j
])
1252 return size_binop (MINUS_EXPR
, offs
[0][i
], offs
[1][j
]);
1257 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1259 memcpy (p, "abcd", 4);
1260 memset (p + 4, ' ', 3);
1262 memcpy (p, "abcd ", 7);
1263 call if the latter can be stored by pieces during expansion. */
1266 simplify_builtin_call (gimple_stmt_iterator
*gsi_p
, tree callee2
)
1268 gimple stmt1
, stmt2
= gsi_stmt (*gsi_p
);
1269 tree vuse
= gimple_vuse (stmt2
);
1272 stmt1
= SSA_NAME_DEF_STMT (vuse
);
1274 switch (DECL_FUNCTION_CODE (callee2
))
1276 case BUILT_IN_MEMSET
:
1277 if (gimple_call_num_args (stmt2
) != 3
1278 || gimple_call_lhs (stmt2
)
1280 || BITS_PER_UNIT
!= 8)
1285 tree ptr1
, src1
, str1
, off1
, len1
, lhs1
;
1286 tree ptr2
= gimple_call_arg (stmt2
, 0);
1287 tree val2
= gimple_call_arg (stmt2
, 1);
1288 tree len2
= gimple_call_arg (stmt2
, 2);
1289 tree diff
, vdef
, new_str_cst
;
1291 unsigned int ptr1_align
;
1292 unsigned HOST_WIDE_INT src_len
;
1294 use_operand_p use_p
;
1296 if (!tree_fits_shwi_p (val2
)
1297 || !tree_fits_uhwi_p (len2
)
1298 || compare_tree_int (len2
, 1024) == 1)
1300 if (is_gimple_call (stmt1
))
1302 /* If first stmt is a call, it needs to be memcpy
1303 or mempcpy, with string literal as second argument and
1305 callee1
= gimple_call_fndecl (stmt1
);
1306 if (callee1
== NULL_TREE
1307 || DECL_BUILT_IN_CLASS (callee1
) != BUILT_IN_NORMAL
1308 || gimple_call_num_args (stmt1
) != 3)
1310 if (DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMCPY
1311 && DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMPCPY
)
1313 ptr1
= gimple_call_arg (stmt1
, 0);
1314 src1
= gimple_call_arg (stmt1
, 1);
1315 len1
= gimple_call_arg (stmt1
, 2);
1316 lhs1
= gimple_call_lhs (stmt1
);
1317 if (!tree_fits_uhwi_p (len1
))
1319 str1
= string_constant (src1
, &off1
);
1320 if (str1
== NULL_TREE
)
1322 if (!tree_fits_uhwi_p (off1
)
1323 || compare_tree_int (off1
, TREE_STRING_LENGTH (str1
) - 1) > 0
1324 || compare_tree_int (len1
, TREE_STRING_LENGTH (str1
)
1325 - tree_to_uhwi (off1
)) > 0
1326 || TREE_CODE (TREE_TYPE (str1
)) != ARRAY_TYPE
1327 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1
)))
1328 != TYPE_MODE (char_type_node
))
1331 else if (gimple_assign_single_p (stmt1
))
1333 /* Otherwise look for length 1 memcpy optimized into
1335 ptr1
= gimple_assign_lhs (stmt1
);
1336 src1
= gimple_assign_rhs1 (stmt1
);
1337 if (TREE_CODE (ptr1
) != MEM_REF
1338 || TYPE_MODE (TREE_TYPE (ptr1
)) != TYPE_MODE (char_type_node
)
1339 || !tree_fits_shwi_p (src1
))
1341 ptr1
= build_fold_addr_expr (ptr1
);
1342 callee1
= NULL_TREE
;
1343 len1
= size_one_node
;
1345 off1
= size_zero_node
;
1351 diff
= constant_pointer_difference (ptr1
, ptr2
);
1352 if (diff
== NULL
&& lhs1
!= NULL
)
1354 diff
= constant_pointer_difference (lhs1
, ptr2
);
1355 if (DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1357 diff
= size_binop (PLUS_EXPR
, diff
,
1358 fold_convert (sizetype
, len1
));
1360 /* If the difference between the second and first destination pointer
1361 is not constant, or is bigger than memcpy length, bail out. */
1363 || !tree_fits_uhwi_p (diff
)
1364 || tree_int_cst_lt (len1
, diff
)
1365 || compare_tree_int (diff
, 1024) == 1)
1368 /* Use maximum of difference plus memset length and memcpy length
1369 as the new memcpy length, if it is too big, bail out. */
1370 src_len
= tree_to_uhwi (diff
);
1371 src_len
+= tree_to_uhwi (len2
);
1372 if (src_len
< tree_to_uhwi (len1
))
1373 src_len
= tree_to_uhwi (len1
);
1377 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1378 with bigger length will return different result. */
1379 if (lhs1
!= NULL_TREE
1380 && DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1381 && (TREE_CODE (lhs1
) != SSA_NAME
1382 || !single_imm_use (lhs1
, &use_p
, &use_stmt
)
1383 || use_stmt
!= stmt2
))
1386 /* If anything reads memory in between memcpy and memset
1387 call, the modified memcpy call might change it. */
1388 vdef
= gimple_vdef (stmt1
);
1390 && (!single_imm_use (vdef
, &use_p
, &use_stmt
)
1391 || use_stmt
!= stmt2
))
1394 ptr1_align
= get_pointer_alignment (ptr1
);
1395 /* Construct the new source string literal. */
1396 src_buf
= XALLOCAVEC (char, src_len
+ 1);
1399 TREE_STRING_POINTER (str1
) + tree_to_uhwi (off1
),
1400 tree_to_uhwi (len1
));
1402 src_buf
[0] = tree_to_shwi (src1
);
1403 memset (src_buf
+ tree_to_uhwi (diff
),
1404 tree_to_shwi (val2
), tree_to_uhwi (len2
));
1405 src_buf
[src_len
] = '\0';
1406 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1407 handle embedded '\0's. */
1408 if (strlen (src_buf
) != src_len
)
1410 rtl_profile_for_bb (gimple_bb (stmt2
));
1411 /* If the new memcpy wouldn't be emitted by storing the literal
1412 by pieces, this optimization might enlarge .rodata too much,
1413 as commonly used string literals couldn't be shared any
1415 if (!can_store_by_pieces (src_len
,
1416 builtin_strncpy_read_str
,
1417 src_buf
, ptr1_align
, false))
1420 new_str_cst
= build_string_literal (src_len
, src_buf
);
1423 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1425 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1426 gimple_call_set_lhs (stmt1
, NULL_TREE
);
1427 gimple_call_set_arg (stmt1
, 1, new_str_cst
);
1428 gimple_call_set_arg (stmt1
, 2,
1429 build_int_cst (TREE_TYPE (len1
), src_len
));
1430 update_stmt (stmt1
);
1431 unlink_stmt_vdef (stmt2
);
1432 gsi_remove (gsi_p
, true);
1433 fwprop_invalidate_lattice (gimple_get_lhs (stmt2
));
1434 release_defs (stmt2
);
1435 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1437 fwprop_invalidate_lattice (lhs1
);
1438 release_ssa_name (lhs1
);
1444 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1445 assignment, remove STMT1 and change memset call into
1447 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt1
);
1449 if (!is_gimple_val (ptr1
))
1450 ptr1
= force_gimple_operand_gsi (gsi_p
, ptr1
, true, NULL_TREE
,
1451 true, GSI_SAME_STMT
);
1452 gimple_call_set_fndecl (stmt2
,
1453 builtin_decl_explicit (BUILT_IN_MEMCPY
));
1454 gimple_call_set_arg (stmt2
, 0, ptr1
);
1455 gimple_call_set_arg (stmt2
, 1, new_str_cst
);
1456 gimple_call_set_arg (stmt2
, 2,
1457 build_int_cst (TREE_TYPE (len2
), src_len
));
1458 unlink_stmt_vdef (stmt1
);
1459 gsi_remove (&gsi
, true);
1460 fwprop_invalidate_lattice (gimple_get_lhs (stmt1
));
1461 release_defs (stmt1
);
1462 update_stmt (stmt2
);
1473 /* Given a ssa_name in NAME see if it was defined by an assignment and
1474 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1475 to the second operand on the rhs. */
1478 defcodefor_name (tree name
, enum tree_code
*code
, tree
*arg1
, tree
*arg2
)
1481 enum tree_code code1
;
1485 enum gimple_rhs_class grhs_class
;
1487 code1
= TREE_CODE (name
);
1490 grhs_class
= get_gimple_rhs_class (code1
);
1492 if (code1
== SSA_NAME
)
1494 def
= SSA_NAME_DEF_STMT (name
);
1496 if (def
&& is_gimple_assign (def
)
1497 && can_propagate_from (def
))
1499 code1
= gimple_assign_rhs_code (def
);
1500 arg11
= gimple_assign_rhs1 (def
);
1501 arg21
= gimple_assign_rhs2 (def
);
1502 arg31
= gimple_assign_rhs2 (def
);
1505 else if (grhs_class
== GIMPLE_TERNARY_RHS
1506 || GIMPLE_BINARY_RHS
1508 || GIMPLE_SINGLE_RHS
)
1509 extract_ops_from_tree_1 (name
, &code1
, &arg11
, &arg21
, &arg31
);
1515 /* Ignore arg3 currently. */
1519 /* Recognize rotation patterns. Return true if a transformation
1520 applied, otherwise return false.
1522 We are looking for X with unsigned type T with bitsize B, OP being
1523 +, | or ^, some type T2 wider than T and
1524 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1525 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1526 (X << Y) OP (X >> (B - Y))
1527 (X << (int) Y) OP (X >> (int) (B - Y))
1528 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1529 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1530 (X << Y) | (X >> ((-Y) & (B - 1)))
1531 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1532 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1533 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1535 and transform these into:
1539 Note, in the patterns with T2 type, the type of OP operands
1540 might be even a signed type, but should have precision B. */
1543 simplify_rotate (gimple_stmt_iterator
*gsi
)
1545 gimple stmt
= gsi_stmt (*gsi
);
1546 tree arg
[2], rtype
, rotcnt
= NULL_TREE
;
1547 tree def_arg1
[2], def_arg2
[2];
1548 enum tree_code def_code
[2];
1551 bool swapped_p
= false;
1554 arg
[0] = gimple_assign_rhs1 (stmt
);
1555 arg
[1] = gimple_assign_rhs2 (stmt
);
1556 rtype
= TREE_TYPE (arg
[0]);
1558 /* Only create rotates in complete modes. Other cases are not
1559 expanded properly. */
1560 if (!INTEGRAL_TYPE_P (rtype
)
1561 || TYPE_PRECISION (rtype
) != GET_MODE_PRECISION (TYPE_MODE (rtype
)))
1564 for (i
= 0; i
< 2; i
++)
1565 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1567 /* Look through narrowing conversions. */
1568 if (CONVERT_EXPR_CODE_P (def_code
[0])
1569 && CONVERT_EXPR_CODE_P (def_code
[1])
1570 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[0]))
1571 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[1]))
1572 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0]))
1573 == TYPE_PRECISION (TREE_TYPE (def_arg1
[1]))
1574 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) > TYPE_PRECISION (rtype
)
1575 && has_single_use (arg
[0])
1576 && has_single_use (arg
[1]))
1578 for (i
= 0; i
< 2; i
++)
1580 arg
[i
] = def_arg1
[i
];
1581 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1585 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1586 for (i
= 0; i
< 2; i
++)
1587 if (def_code
[i
] != LSHIFT_EXPR
&& def_code
[i
] != RSHIFT_EXPR
)
1589 else if (!has_single_use (arg
[i
]))
1591 if (def_code
[0] == def_code
[1])
1594 /* If we've looked through narrowing conversions before, look through
1595 widening conversions from unsigned type with the same precision
1597 if (TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) != TYPE_PRECISION (rtype
))
1598 for (i
= 0; i
< 2; i
++)
1601 enum tree_code code
;
1602 defcodefor_name (def_arg1
[i
], &code
, &tem
, NULL
);
1603 if (!CONVERT_EXPR_CODE_P (code
)
1604 || !INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1605 || TYPE_PRECISION (TREE_TYPE (tem
)) != TYPE_PRECISION (rtype
))
1609 /* Both shifts have to use the same first operand. */
1610 if (TREE_CODE (def_arg1
[0]) != SSA_NAME
|| def_arg1
[0] != def_arg1
[1])
1612 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1
[0])))
1615 /* CNT1 + CNT2 == B case above. */
1616 if (tree_fits_uhwi_p (def_arg2
[0])
1617 && tree_fits_uhwi_p (def_arg2
[1])
1618 && tree_to_uhwi (def_arg2
[0])
1619 + tree_to_uhwi (def_arg2
[1]) == TYPE_PRECISION (rtype
))
1620 rotcnt
= def_arg2
[0];
1621 else if (TREE_CODE (def_arg2
[0]) != SSA_NAME
1622 || TREE_CODE (def_arg2
[1]) != SSA_NAME
)
1626 tree cdef_arg1
[2], cdef_arg2
[2], def_arg2_alt
[2];
1627 enum tree_code cdef_code
[2];
1628 /* Look through conversion of the shift count argument.
1629 The C/C++ FE cast any shift count argument to integer_type_node.
1630 The only problem might be if the shift count type maximum value
1631 is equal or smaller than number of bits in rtype. */
1632 for (i
= 0; i
< 2; i
++)
1634 def_arg2_alt
[i
] = def_arg2
[i
];
1635 defcodefor_name (def_arg2
[i
], &cdef_code
[i
],
1636 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1637 if (CONVERT_EXPR_CODE_P (cdef_code
[i
])
1638 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1
[i
]))
1639 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
1640 > floor_log2 (TYPE_PRECISION (rtype
))
1641 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
1642 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (cdef_arg1
[i
]))))
1644 def_arg2_alt
[i
] = cdef_arg1
[i
];
1645 defcodefor_name (def_arg2_alt
[i
], &cdef_code
[i
],
1646 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1649 for (i
= 0; i
< 2; i
++)
1650 /* Check for one shift count being Y and the other B - Y,
1651 with optional casts. */
1652 if (cdef_code
[i
] == MINUS_EXPR
1653 && tree_fits_shwi_p (cdef_arg1
[i
])
1654 && tree_to_shwi (cdef_arg1
[i
]) == TYPE_PRECISION (rtype
)
1655 && TREE_CODE (cdef_arg2
[i
]) == SSA_NAME
)
1658 enum tree_code code
;
1660 if (cdef_arg2
[i
] == def_arg2
[1 - i
]
1661 || cdef_arg2
[i
] == def_arg2_alt
[1 - i
])
1663 rotcnt
= cdef_arg2
[i
];
1666 defcodefor_name (cdef_arg2
[i
], &code
, &tem
, NULL
);
1667 if (CONVERT_EXPR_CODE_P (code
)
1668 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1669 && TYPE_PRECISION (TREE_TYPE (tem
))
1670 > floor_log2 (TYPE_PRECISION (rtype
))
1671 && TYPE_PRECISION (TREE_TYPE (tem
))
1672 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
1673 && (tem
== def_arg2
[1 - i
]
1674 || tem
== def_arg2_alt
[1 - i
]))
1680 /* The above sequence isn't safe for Y being 0,
1681 because then one of the shifts triggers undefined behavior.
1682 This alternative is safe even for rotation count of 0.
1683 One shift count is Y and the other (-Y) & (B - 1). */
1684 else if (cdef_code
[i
] == BIT_AND_EXPR
1685 && tree_fits_shwi_p (cdef_arg2
[i
])
1686 && tree_to_shwi (cdef_arg2
[i
])
1687 == TYPE_PRECISION (rtype
) - 1
1688 && TREE_CODE (cdef_arg1
[i
]) == SSA_NAME
1689 && gimple_assign_rhs_code (stmt
) == BIT_IOR_EXPR
)
1692 enum tree_code code
;
1694 defcodefor_name (cdef_arg1
[i
], &code
, &tem
, NULL
);
1695 if (CONVERT_EXPR_CODE_P (code
)
1696 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1697 && TYPE_PRECISION (TREE_TYPE (tem
))
1698 > floor_log2 (TYPE_PRECISION (rtype
))
1699 && TYPE_PRECISION (TREE_TYPE (tem
))
1700 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
))))
1701 defcodefor_name (tem
, &code
, &tem
, NULL
);
1703 if (code
== NEGATE_EXPR
)
1705 if (tem
== def_arg2
[1 - i
] || tem
== def_arg2_alt
[1 - i
])
1710 defcodefor_name (tem
, &code
, &tem
, NULL
);
1711 if (CONVERT_EXPR_CODE_P (code
)
1712 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1713 && TYPE_PRECISION (TREE_TYPE (tem
))
1714 > floor_log2 (TYPE_PRECISION (rtype
))
1715 && TYPE_PRECISION (TREE_TYPE (tem
))
1716 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
1717 && (tem
== def_arg2
[1 - i
]
1718 || tem
== def_arg2_alt
[1 - i
]))
1725 if (rotcnt
== NULL_TREE
)
1730 if (!useless_type_conversion_p (TREE_TYPE (def_arg2
[0]),
1731 TREE_TYPE (rotcnt
)))
1733 g
= gimple_build_assign (make_ssa_name (TREE_TYPE (def_arg2
[0])),
1735 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1736 rotcnt
= gimple_assign_lhs (g
);
1738 lhs
= gimple_assign_lhs (stmt
);
1739 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1740 lhs
= make_ssa_name (TREE_TYPE (def_arg1
[0]));
1741 g
= gimple_build_assign (lhs
,
1742 ((def_code
[0] == LSHIFT_EXPR
) ^ swapped_p
)
1743 ? LROTATE_EXPR
: RROTATE_EXPR
, def_arg1
[0], rotcnt
);
1744 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1746 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1747 g
= gimple_build_assign (gimple_assign_lhs (stmt
), NOP_EXPR
, lhs
);
1749 gsi_replace (gsi
, g
, false);
1753 /* Combine an element access with a shuffle. Returns true if there were
1754 any changes made, else it returns false. */
1757 simplify_bitfield_ref (gimple_stmt_iterator
*gsi
)
1759 gimple stmt
= gsi_stmt (*gsi
);
1761 tree op
, op0
, op1
, op2
;
1763 unsigned idx
, n
, size
;
1764 enum tree_code code
;
1766 op
= gimple_assign_rhs1 (stmt
);
1767 gcc_checking_assert (TREE_CODE (op
) == BIT_FIELD_REF
);
1769 op0
= TREE_OPERAND (op
, 0);
1770 if (TREE_CODE (op0
) != SSA_NAME
1771 || TREE_CODE (TREE_TYPE (op0
)) != VECTOR_TYPE
)
1774 def_stmt
= get_prop_source_stmt (op0
, false, NULL
);
1775 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1778 op1
= TREE_OPERAND (op
, 1);
1779 op2
= TREE_OPERAND (op
, 2);
1780 code
= gimple_assign_rhs_code (def_stmt
);
1782 if (code
== CONSTRUCTOR
)
1784 tree tem
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (op
),
1785 gimple_assign_rhs1 (def_stmt
), op1
, op2
);
1786 if (!tem
|| !valid_gimple_rhs_p (tem
))
1788 gimple_assign_set_rhs_from_tree (gsi
, tem
);
1789 update_stmt (gsi_stmt (*gsi
));
1793 elem_type
= TREE_TYPE (TREE_TYPE (op0
));
1794 if (TREE_TYPE (op
) != elem_type
)
1797 size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
1798 n
= TREE_INT_CST_LOW (op1
) / size
;
1801 idx
= TREE_INT_CST_LOW (op2
) / size
;
1803 if (code
== VEC_PERM_EXPR
)
1805 tree p
, m
, index
, tem
;
1807 m
= gimple_assign_rhs3 (def_stmt
);
1808 if (TREE_CODE (m
) != VECTOR_CST
)
1810 nelts
= VECTOR_CST_NELTS (m
);
1811 idx
= TREE_INT_CST_LOW (VECTOR_CST_ELT (m
, idx
));
1815 p
= gimple_assign_rhs1 (def_stmt
);
1819 p
= gimple_assign_rhs2 (def_stmt
);
1822 index
= build_int_cst (TREE_TYPE (TREE_TYPE (m
)), idx
* size
);
1823 tem
= build3 (BIT_FIELD_REF
, TREE_TYPE (op
),
1824 unshare_expr (p
), op1
, index
);
1825 gimple_assign_set_rhs1 (stmt
, tem
);
1827 update_stmt (gsi_stmt (*gsi
));
1834 /* Determine whether applying the 2 permutations (mask1 then mask2)
1835 gives back one of the input. */
1838 is_combined_permutation_identity (tree mask1
, tree mask2
)
1841 unsigned int nelts
, i
, j
;
1842 bool maybe_identity1
= true;
1843 bool maybe_identity2
= true;
1845 gcc_checking_assert (TREE_CODE (mask1
) == VECTOR_CST
1846 && TREE_CODE (mask2
) == VECTOR_CST
);
1847 mask
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (mask1
), mask1
, mask1
, mask2
);
1848 gcc_assert (TREE_CODE (mask
) == VECTOR_CST
);
1850 nelts
= VECTOR_CST_NELTS (mask
);
1851 for (i
= 0; i
< nelts
; i
++)
1853 tree val
= VECTOR_CST_ELT (mask
, i
);
1854 gcc_assert (TREE_CODE (val
) == INTEGER_CST
);
1855 j
= TREE_INT_CST_LOW (val
) & (2 * nelts
- 1);
1857 maybe_identity2
= false;
1858 else if (j
== i
+ nelts
)
1859 maybe_identity1
= false;
1863 return maybe_identity1
? 1 : maybe_identity2
? 2 : 0;
1866 /* Combine a shuffle with its arguments. Returns 1 if there were any
1867 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
1870 simplify_permutation (gimple_stmt_iterator
*gsi
)
1872 gimple stmt
= gsi_stmt (*gsi
);
1874 tree op0
, op1
, op2
, op3
, arg0
, arg1
;
1875 enum tree_code code
;
1876 bool single_use_op0
= false;
1878 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == VEC_PERM_EXPR
);
1880 op0
= gimple_assign_rhs1 (stmt
);
1881 op1
= gimple_assign_rhs2 (stmt
);
1882 op2
= gimple_assign_rhs3 (stmt
);
1884 if (TREE_CODE (op2
) != VECTOR_CST
)
1887 if (TREE_CODE (op0
) == VECTOR_CST
)
1892 else if (TREE_CODE (op0
) == SSA_NAME
)
1894 def_stmt
= get_prop_source_stmt (op0
, false, &single_use_op0
);
1895 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1898 code
= gimple_assign_rhs_code (def_stmt
);
1899 arg0
= gimple_assign_rhs1 (def_stmt
);
1904 /* Two consecutive shuffles. */
1905 if (code
== VEC_PERM_EXPR
)
1912 op3
= gimple_assign_rhs3 (def_stmt
);
1913 if (TREE_CODE (op3
) != VECTOR_CST
)
1915 ident
= is_combined_permutation_identity (op3
, op2
);
1918 orig
= (ident
== 1) ? gimple_assign_rhs1 (def_stmt
)
1919 : gimple_assign_rhs2 (def_stmt
);
1920 gimple_assign_set_rhs1 (stmt
, unshare_expr (orig
));
1921 gimple_assign_set_rhs_code (stmt
, TREE_CODE (orig
));
1922 gimple_set_num_ops (stmt
, 2);
1924 return remove_prop_source_from_use (op0
) ? 2 : 1;
1927 /* Shuffle of a constructor. */
1928 else if (code
== CONSTRUCTOR
|| code
== VECTOR_CST
)
1934 if (TREE_CODE (op0
) == SSA_NAME
&& !single_use_op0
)
1937 if (TREE_CODE (op1
) == VECTOR_CST
)
1939 else if (TREE_CODE (op1
) == SSA_NAME
)
1941 enum tree_code code2
;
1943 gimple def_stmt2
= get_prop_source_stmt (op1
, true, NULL
);
1944 if (!def_stmt2
|| !can_propagate_from (def_stmt2
))
1947 code2
= gimple_assign_rhs_code (def_stmt2
);
1948 if (code2
!= CONSTRUCTOR
&& code2
!= VECTOR_CST
)
1950 arg1
= gimple_assign_rhs1 (def_stmt2
);
1957 /* Already used twice in this statement. */
1958 if (TREE_CODE (op0
) == SSA_NAME
&& num_imm_uses (op0
) > 2)
1962 opt
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (op0
), arg0
, arg1
, op2
);
1964 || (TREE_CODE (opt
) != CONSTRUCTOR
&& TREE_CODE (opt
) != VECTOR_CST
))
1966 gimple_assign_set_rhs_from_tree (gsi
, opt
);
1967 update_stmt (gsi_stmt (*gsi
));
1968 if (TREE_CODE (op0
) == SSA_NAME
)
1969 ret
= remove_prop_source_from_use (op0
);
1970 if (op0
!= op1
&& TREE_CODE (op1
) == SSA_NAME
)
1971 ret
|= remove_prop_source_from_use (op1
);
1978 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
1981 simplify_vector_constructor (gimple_stmt_iterator
*gsi
)
1983 gimple stmt
= gsi_stmt (*gsi
);
1985 tree op
, op2
, orig
, type
, elem_type
;
1986 unsigned elem_size
, nelts
, i
;
1987 enum tree_code code
;
1988 constructor_elt
*elt
;
1992 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
);
1994 op
= gimple_assign_rhs1 (stmt
);
1995 type
= TREE_TYPE (op
);
1996 gcc_checking_assert (TREE_CODE (type
) == VECTOR_TYPE
);
1998 nelts
= TYPE_VECTOR_SUBPARTS (type
);
1999 elem_type
= TREE_TYPE (type
);
2000 elem_size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
2002 sel
= XALLOCAVEC (unsigned char, nelts
);
2005 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op
), i
, elt
)
2012 if (TREE_CODE (elt
->value
) != SSA_NAME
)
2014 def_stmt
= get_prop_source_stmt (elt
->value
, false, NULL
);
2017 code
= gimple_assign_rhs_code (def_stmt
);
2018 if (code
!= BIT_FIELD_REF
)
2020 op1
= gimple_assign_rhs1 (def_stmt
);
2021 ref
= TREE_OPERAND (op1
, 0);
2029 if (TREE_CODE (ref
) != SSA_NAME
)
2031 if (!useless_type_conversion_p (type
, TREE_TYPE (ref
)))
2035 if (TREE_INT_CST_LOW (TREE_OPERAND (op1
, 1)) != elem_size
)
2037 sel
[i
] = TREE_INT_CST_LOW (TREE_OPERAND (op1
, 2)) / elem_size
;
2038 if (sel
[i
] != i
) maybe_ident
= false;
2044 gimple_assign_set_rhs_from_tree (gsi
, orig
);
2047 tree mask_type
, *mask_elts
;
2049 if (!can_vec_perm_p (TYPE_MODE (type
), false, sel
))
2052 = build_vector_type (build_nonstandard_integer_type (elem_size
, 1),
2054 if (GET_MODE_CLASS (TYPE_MODE (mask_type
)) != MODE_VECTOR_INT
2055 || GET_MODE_SIZE (TYPE_MODE (mask_type
))
2056 != GET_MODE_SIZE (TYPE_MODE (type
)))
2058 mask_elts
= XALLOCAVEC (tree
, nelts
);
2059 for (i
= 0; i
< nelts
; i
++)
2060 mask_elts
[i
] = build_int_cst (TREE_TYPE (mask_type
), sel
[i
]);
2061 op2
= build_vector (mask_type
, mask_elts
);
2062 gimple_assign_set_rhs_with_ops (gsi
, VEC_PERM_EXPR
, orig
, orig
, op2
);
2064 update_stmt (gsi_stmt (*gsi
));
2069 /* Primitive "lattice" function for gimple_simplify. */
2072 fwprop_ssa_val (tree name
)
2074 /* First valueize NAME. */
2075 if (TREE_CODE (name
) == SSA_NAME
2076 && SSA_NAME_VERSION (name
) < lattice
.length ())
2078 tree val
= lattice
[SSA_NAME_VERSION (name
)];
2082 /* We continue matching along SSA use-def edges for SSA names
2083 that are not single-use. Currently there are no patterns
2084 that would cause any issues with that. */
2088 /* Main entry point for the forward propagation and statement combine
2093 const pass_data pass_data_forwprop
=
2095 GIMPLE_PASS
, /* type */
2096 "forwprop", /* name */
2097 OPTGROUP_NONE
, /* optinfo_flags */
2098 TV_TREE_FORWPROP
, /* tv_id */
2099 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2100 0, /* properties_provided */
2101 0, /* properties_destroyed */
2102 0, /* todo_flags_start */
2103 TODO_update_ssa
, /* todo_flags_finish */
2106 class pass_forwprop
: public gimple_opt_pass
2109 pass_forwprop (gcc::context
*ctxt
)
2110 : gimple_opt_pass (pass_data_forwprop
, ctxt
)
2113 /* opt_pass methods: */
2114 opt_pass
* clone () { return new pass_forwprop (m_ctxt
); }
2115 virtual bool gate (function
*) { return flag_tree_forwprop
; }
2116 virtual unsigned int execute (function
*);
2118 }; // class pass_forwprop
2121 pass_forwprop::execute (function
*fun
)
2123 unsigned int todoflags
= 0;
2125 cfg_changed
= false;
2127 /* Combine stmts with the stmts defining their operands. Do that
2128 in an order that guarantees visiting SSA defs before SSA uses. */
2129 lattice
.create (num_ssa_names
);
2130 lattice
.quick_grow_cleared (num_ssa_names
);
2131 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
2132 int postorder_num
= inverted_post_order_compute (postorder
);
2133 to_purge
= BITMAP_ALLOC (NULL
);
2134 for (int i
= 0; i
< postorder_num
; ++i
)
2136 gimple_stmt_iterator gsi
;
2137 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, postorder
[i
]);
2139 /* Apply forward propagation to all stmts in the basic-block.
2140 Note we update GSI within the loop as necessary. */
2141 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2143 gimple stmt
= gsi_stmt (gsi
);
2145 enum tree_code code
;
2147 if (!is_gimple_assign (stmt
))
2153 lhs
= gimple_assign_lhs (stmt
);
2154 rhs
= gimple_assign_rhs1 (stmt
);
2155 code
= gimple_assign_rhs_code (stmt
);
2156 if (TREE_CODE (lhs
) != SSA_NAME
2157 || has_zero_uses (lhs
))
2163 /* If this statement sets an SSA_NAME to an address,
2164 try to propagate the address into the uses of the SSA_NAME. */
2165 if (code
== ADDR_EXPR
2166 /* Handle pointer conversions on invariant addresses
2167 as well, as this is valid gimple. */
2168 || (CONVERT_EXPR_CODE_P (code
)
2169 && TREE_CODE (rhs
) == ADDR_EXPR
2170 && POINTER_TYPE_P (TREE_TYPE (lhs
))))
2172 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2175 || decl_address_invariant_p (base
))
2176 && !stmt_references_abnormal_ssa_name (stmt
)
2177 && forward_propagate_addr_expr (lhs
, rhs
, true))
2179 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2180 release_defs (stmt
);
2181 gsi_remove (&gsi
, true);
2186 else if (code
== POINTER_PLUS_EXPR
)
2188 tree off
= gimple_assign_rhs2 (stmt
);
2189 if (TREE_CODE (off
) == INTEGER_CST
2190 && can_propagate_from (stmt
)
2191 && !simple_iv_increment_p (stmt
)
2192 /* ??? Better adjust the interface to that function
2193 instead of building new trees here. */
2194 && forward_propagate_addr_expr
2196 build1_loc (gimple_location (stmt
),
2197 ADDR_EXPR
, TREE_TYPE (rhs
),
2198 fold_build2 (MEM_REF
,
2199 TREE_TYPE (TREE_TYPE (rhs
)),
2201 fold_convert (ptr_type_node
,
2204 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2205 release_defs (stmt
);
2206 gsi_remove (&gsi
, true);
2208 else if (is_gimple_min_invariant (rhs
))
2210 /* Make sure to fold &a[0] + off_1 here. */
2211 fold_stmt_inplace (&gsi
);
2213 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2219 else if (TREE_CODE (TREE_TYPE (lhs
)) == COMPLEX_TYPE
2220 && gimple_assign_load_p (stmt
)
2221 && !gimple_has_volatile_ops (stmt
)
2222 && !stmt_can_throw_internal (stmt
))
2224 /* Rewrite loads used only in real/imagpart extractions to
2225 component-wise loads. */
2226 use_operand_p use_p
;
2227 imm_use_iterator iter
;
2228 bool rewrite
= true;
2229 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
2231 gimple use_stmt
= USE_STMT (use_p
);
2232 if (is_gimple_debug (use_stmt
))
2234 if (!is_gimple_assign (use_stmt
)
2235 || (gimple_assign_rhs_code (use_stmt
) != REALPART_EXPR
2236 && gimple_assign_rhs_code (use_stmt
) != IMAGPART_EXPR
))
2245 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2247 if (is_gimple_debug (use_stmt
))
2249 if (gimple_debug_bind_p (use_stmt
))
2251 gimple_debug_bind_reset_value (use_stmt
);
2252 update_stmt (use_stmt
);
2257 tree new_rhs
= build1 (gimple_assign_rhs_code (use_stmt
),
2258 TREE_TYPE (TREE_TYPE (rhs
)),
2259 unshare_expr (rhs
));
2261 = gimple_build_assign (gimple_assign_lhs (use_stmt
),
2264 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2265 unlink_stmt_vdef (use_stmt
);
2266 gsi_remove (&gsi2
, true);
2268 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
2270 gsi_remove (&gsi
, true);
2275 else if (code
== COMPLEX_EXPR
)
2277 /* Rewrite stores of a single-use complex build expression
2278 to component-wise stores. */
2279 use_operand_p use_p
;
2281 if (single_imm_use (lhs
, &use_p
, &use_stmt
)
2282 && gimple_store_p (use_stmt
)
2283 && !gimple_has_volatile_ops (use_stmt
)
2284 && is_gimple_assign (use_stmt
))
2286 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2287 tree new_lhs
= build1 (REALPART_EXPR
,
2288 TREE_TYPE (TREE_TYPE (use_lhs
)),
2289 unshare_expr (use_lhs
));
2290 gimple new_stmt
= gimple_build_assign (new_lhs
, rhs
);
2291 gimple_set_vuse (new_stmt
, gimple_vuse (use_stmt
));
2292 gimple_set_vdef (new_stmt
, make_ssa_name (gimple_vop (cfun
)));
2293 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt
)) = new_stmt
;
2294 gimple_set_vuse (use_stmt
, gimple_vdef (new_stmt
));
2295 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2296 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
2298 new_lhs
= build1 (IMAGPART_EXPR
,
2299 TREE_TYPE (TREE_TYPE (use_lhs
)),
2300 unshare_expr (use_lhs
));
2301 gimple_assign_set_lhs (use_stmt
, new_lhs
);
2302 gimple_assign_set_rhs1 (use_stmt
, gimple_assign_rhs2 (stmt
));
2303 update_stmt (use_stmt
);
2305 gsi_remove (&gsi
, true);
2314 /* Combine stmts with the stmts defining their operands.
2315 Note we update GSI within the loop as necessary. */
2316 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2318 gimple stmt
= gsi_stmt (gsi
);
2319 gimple orig_stmt
= stmt
;
2320 bool changed
= false;
2322 /* Mark stmt as potentially needing revisiting. */
2323 gimple_set_plf (stmt
, GF_PLF_1
, false);
2325 if (fold_stmt (&gsi
, fwprop_ssa_val
))
2328 stmt
= gsi_stmt (gsi
);
2329 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
2330 bitmap_set_bit (to_purge
, bb
->index
);
2331 /* Cleanup the CFG if we simplified a condition to
2333 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2334 if (gimple_cond_true_p (cond
)
2335 || gimple_cond_false_p (cond
))
2340 switch (gimple_code (stmt
))
2344 tree rhs1
= gimple_assign_rhs1 (stmt
);
2345 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2347 if (code
== COND_EXPR
2348 || code
== VEC_COND_EXPR
)
2350 /* In this case the entire COND_EXPR is in rhs1. */
2351 if (forward_propagate_into_cond (&gsi
))
2354 stmt
= gsi_stmt (gsi
);
2357 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2360 did_something
= forward_propagate_into_comparison (&gsi
);
2361 if (did_something
== 2)
2363 changed
= did_something
!= 0;
2365 else if ((code
== PLUS_EXPR
2366 || code
== BIT_IOR_EXPR
2367 || code
== BIT_XOR_EXPR
)
2368 && simplify_rotate (&gsi
))
2370 else if (code
== VEC_PERM_EXPR
)
2372 int did_something
= simplify_permutation (&gsi
);
2373 if (did_something
== 2)
2375 changed
= did_something
!= 0;
2377 else if (code
== BIT_FIELD_REF
)
2378 changed
= simplify_bitfield_ref (&gsi
);
2379 else if (code
== CONSTRUCTOR
2380 && TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
2381 changed
= simplify_vector_constructor (&gsi
);
2386 changed
= simplify_gimple_switch (as_a
<gswitch
*> (stmt
));
2392 = forward_propagate_into_gimple_cond (as_a
<gcond
*> (stmt
));
2393 if (did_something
== 2)
2395 changed
= did_something
!= 0;
2401 tree callee
= gimple_call_fndecl (stmt
);
2402 if (callee
!= NULL_TREE
2403 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2404 changed
= simplify_builtin_call (&gsi
, callee
);
2413 /* If the stmt changed then re-visit it and the statements
2414 inserted before it. */
2415 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2416 if (gimple_plf (gsi_stmt (gsi
), GF_PLF_1
))
2418 if (gsi_end_p (gsi
))
2419 gsi
= gsi_start_bb (bb
);
2425 /* Stmt no longer needs to be revisited. */
2426 gimple_set_plf (stmt
, GF_PLF_1
, true);
2428 /* Fill up the lattice. */
2429 if (gimple_assign_single_p (stmt
))
2431 tree lhs
= gimple_assign_lhs (stmt
);
2432 tree rhs
= gimple_assign_rhs1 (stmt
);
2433 if (TREE_CODE (lhs
) == SSA_NAME
)
2436 if (TREE_CODE (rhs
) == SSA_NAME
)
2437 val
= fwprop_ssa_val (rhs
);
2438 else if (is_gimple_min_invariant (rhs
))
2440 fwprop_set_lattice_val (lhs
, val
);
2451 cfg_changed
|= gimple_purge_all_dead_eh_edges (to_purge
);
2452 BITMAP_FREE (to_purge
);
2455 todoflags
|= TODO_cleanup_cfg
;
2463 make_pass_forwprop (gcc::context
*ctxt
)
2465 return new pass_forwprop (ctxt
);