1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2017 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 "tree-pass.h"
31 #include "optabs-query.h"
32 #include "gimple-pretty-print.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-fold.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
43 #include "tree-ssa-propagate.h"
44 #include "tree-ssa-dom.h"
46 #include "tree-cfgcleanup.h"
48 #include "optabs-tree.h"
49 #include "tree-vector-builder.h"
51 /* This pass propagates the RHS of assignment statements into use
52 sites of the LHS of the assignment. It's basically a specialized
53 form of tree combination. It is hoped all of this can disappear
54 when we have a generalized tree combiner.
56 One class of common cases we handle is forward propagating a single use
57 variable into a COND_EXPR.
61 if (x) goto ... else goto ...
63 Will be transformed into:
66 if (a COND b) goto ... else goto ...
68 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
70 Or (assuming c1 and c2 are constants):
74 if (x EQ/NEQ c2) goto ... else goto ...
76 Will be transformed into:
79 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
81 Similarly for x = a - c1.
87 if (x) goto ... else goto ...
89 Will be transformed into:
92 if (a == 0) goto ... else goto ...
94 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
95 For these cases, we propagate A into all, possibly more than one,
96 COND_EXPRs that use X.
102 if (x) goto ... else goto ...
104 Will be transformed into:
107 if (a != 0) goto ... else goto ...
109 (Assuming a is an integral type and x is a boolean or x is an
110 integral and a is a boolean.)
112 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
113 For these cases, we propagate A into all, possibly more than one,
114 COND_EXPRs that use X.
116 In addition to eliminating the variable and the statement which assigns
117 a value to the variable, we may be able to later thread the jump without
118 adding insane complexity in the dominator optimizer.
120 Also note these transformations can cascade. We handle this by having
121 a worklist of COND_EXPR statements to examine. As we make a change to
122 a statement, we put it back on the worklist to examine on the next
123 iteration of the main loop.
125 A second class of propagation opportunities arises for ADDR_EXPR
136 ptr = (type1*)&type2var;
139 Will get turned into (if type1 and type2 are the same size
140 and neither have volatile on them):
141 res = VIEW_CONVERT_EXPR<type1>(type2var)
146 ptr2 = ptr + <constant>;
150 ptr2 = &x[constant/elementsize];
155 offset = index * element_size;
156 offset_p = (pointer) offset;
157 ptr2 = ptr + offset_p
159 Will get turned into:
167 Provided that decl has known alignment >= 2, will get turned into
171 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
172 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
175 This will (of course) be extended as other needs arise. */
177 static bool forward_propagate_addr_expr (tree
, tree
, bool);
179 /* Set to true if we delete dead edges during the optimization. */
180 static bool cfg_changed
;
182 static tree
rhs_to_tree (tree type
, gimple
*stmt
);
184 static bitmap to_purge
;
186 /* Const-and-copy lattice. */
187 static vec
<tree
> lattice
;
189 /* Set the lattice entry for NAME to VAL. */
191 fwprop_set_lattice_val (tree name
, tree val
)
193 if (TREE_CODE (name
) == SSA_NAME
)
195 if (SSA_NAME_VERSION (name
) >= lattice
.length ())
197 lattice
.reserve (num_ssa_names
- lattice
.length ());
198 lattice
.quick_grow_cleared (num_ssa_names
);
200 lattice
[SSA_NAME_VERSION (name
)] = val
;
204 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
206 fwprop_invalidate_lattice (tree name
)
209 && TREE_CODE (name
) == SSA_NAME
210 && SSA_NAME_VERSION (name
) < lattice
.length ())
211 lattice
[SSA_NAME_VERSION (name
)] = NULL_TREE
;
215 /* Get the statement we can propagate from into NAME skipping
216 trivial copies. Returns the statement which defines the
217 propagation source or NULL_TREE if there is no such one.
218 If SINGLE_USE_ONLY is set considers only sources which have
219 a single use chain up to NAME. If SINGLE_USE_P is non-null,
220 it is set to whether the chain to NAME is a single use chain
221 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
224 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
226 bool single_use
= true;
229 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
231 if (!has_single_use (name
))
238 /* If name is defined by a PHI node or is the default def, bail out. */
239 if (!is_gimple_assign (def_stmt
))
242 /* If def_stmt is a simple copy, continue looking. */
243 if (gimple_assign_rhs_code (def_stmt
) == SSA_NAME
)
244 name
= gimple_assign_rhs1 (def_stmt
);
247 if (!single_use_only
&& single_use_p
)
248 *single_use_p
= single_use
;
255 /* Checks if the destination ssa name in DEF_STMT can be used as
256 propagation source. Returns true if so, otherwise false. */
259 can_propagate_from (gimple
*def_stmt
)
261 gcc_assert (is_gimple_assign (def_stmt
));
263 /* If the rhs has side-effects we cannot propagate from it. */
264 if (gimple_has_volatile_ops (def_stmt
))
267 /* If the rhs is a load we cannot propagate from it. */
268 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_reference
269 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_declaration
)
272 /* Constants can be always propagated. */
273 if (gimple_assign_single_p (def_stmt
)
274 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
277 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
278 if (stmt_references_abnormal_ssa_name (def_stmt
))
281 /* If the definition is a conversion of a pointer to a function type,
282 then we can not apply optimizations as some targets require
283 function pointers to be canonicalized and in this case this
284 optimization could eliminate a necessary canonicalization. */
285 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
287 tree rhs
= gimple_assign_rhs1 (def_stmt
);
288 if (POINTER_TYPE_P (TREE_TYPE (rhs
))
289 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs
))) == FUNCTION_TYPE
)
296 /* Remove a chain of dead statements starting at the definition of
297 NAME. The chain is linked via the first operand of the defining statements.
298 If NAME was replaced in its only use then this function can be used
299 to clean up dead stmts. The function handles already released SSA
301 Returns true if cleanup-cfg has to run. */
304 remove_prop_source_from_use (tree name
)
306 gimple_stmt_iterator gsi
;
308 bool cfg_changed
= false;
313 if (SSA_NAME_IN_FREE_LIST (name
)
314 || SSA_NAME_IS_DEFAULT_DEF (name
)
315 || !has_zero_uses (name
))
318 stmt
= SSA_NAME_DEF_STMT (name
);
319 if (gimple_code (stmt
) == GIMPLE_PHI
320 || gimple_has_side_effects (stmt
))
323 bb
= gimple_bb (stmt
);
324 gsi
= gsi_for_stmt (stmt
);
325 unlink_stmt_vdef (stmt
);
326 if (gsi_remove (&gsi
, true))
327 bitmap_set_bit (to_purge
, bb
->index
);
328 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
331 name
= is_gimple_assign (stmt
) ? gimple_assign_rhs1 (stmt
) : NULL_TREE
;
332 } while (name
&& TREE_CODE (name
) == SSA_NAME
);
337 /* Return the rhs of a gassign *STMT in a form of a single tree,
338 converted to type TYPE.
340 This should disappear, but is needed so we can combine expressions and use
341 the fold() interfaces. Long term, we need to develop folding and combine
342 routines that deal with gimple exclusively . */
345 rhs_to_tree (tree type
, gimple
*stmt
)
347 location_t loc
= gimple_location (stmt
);
348 enum tree_code code
= gimple_assign_rhs_code (stmt
);
349 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
350 return fold_build3_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
351 gimple_assign_rhs2 (stmt
),
352 gimple_assign_rhs3 (stmt
));
353 else if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
354 return fold_build2_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
355 gimple_assign_rhs2 (stmt
));
356 else if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
357 return build1 (code
, type
, gimple_assign_rhs1 (stmt
));
358 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
359 return gimple_assign_rhs1 (stmt
);
364 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
365 the folded result in a form suitable for COND_EXPR_COND or
366 NULL_TREE, if there is no suitable simplified form. If
367 INVARIANT_ONLY is true only gimple_min_invariant results are
368 considered simplified. */
371 combine_cond_expr_cond (gimple
*stmt
, enum tree_code code
, tree type
,
372 tree op0
, tree op1
, bool invariant_only
)
376 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
378 fold_defer_overflow_warnings ();
379 t
= fold_binary_loc (gimple_location (stmt
), code
, type
, op0
, op1
);
382 fold_undefer_overflow_warnings (false, NULL
, 0);
386 /* Require that we got a boolean type out if we put one in. */
387 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
389 /* Canonicalize the combined condition for use in a COND_EXPR. */
390 t
= canonicalize_cond_expr_cond (t
);
392 /* Bail out if we required an invariant but didn't get one. */
393 if (!t
|| (invariant_only
&& !is_gimple_min_invariant (t
)))
395 fold_undefer_overflow_warnings (false, NULL
, 0);
399 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt
), stmt
, 0);
404 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
405 of its operand. Return a new comparison tree or NULL_TREE if there
406 were no simplifying combines. */
409 forward_propagate_into_comparison_1 (gimple
*stmt
,
410 enum tree_code code
, tree type
,
413 tree tmp
= NULL_TREE
;
414 tree rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
415 bool single_use0_p
= false, single_use1_p
= false;
417 /* For comparisons use the first operand, that is likely to
418 simplify comparisons against constants. */
419 if (TREE_CODE (op0
) == SSA_NAME
)
421 gimple
*def_stmt
= get_prop_source_stmt (op0
, false, &single_use0_p
);
422 if (def_stmt
&& can_propagate_from (def_stmt
))
424 enum tree_code def_code
= gimple_assign_rhs_code (def_stmt
);
425 bool invariant_only_p
= !single_use0_p
;
427 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
429 /* Always combine comparisons or conversions from booleans. */
430 if (TREE_CODE (op1
) == INTEGER_CST
431 && ((CONVERT_EXPR_CODE_P (def_code
)
432 && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0
, 0)))
434 || TREE_CODE_CLASS (def_code
) == tcc_comparison
))
435 invariant_only_p
= false;
437 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
438 rhs0
, op1
, invariant_only_p
);
444 /* If that wasn't successful, try the second operand. */
445 if (TREE_CODE (op1
) == SSA_NAME
)
447 gimple
*def_stmt
= get_prop_source_stmt (op1
, false, &single_use1_p
);
448 if (def_stmt
&& can_propagate_from (def_stmt
))
450 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
451 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
452 op0
, rhs1
, !single_use1_p
);
458 /* If that wasn't successful either, try both operands. */
459 if (rhs0
!= NULL_TREE
460 && rhs1
!= NULL_TREE
)
461 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
463 !(single_use0_p
&& single_use1_p
));
468 /* Propagate from the ssa name definition statements of the assignment
469 from a comparison at *GSI into the conditional if that simplifies it.
470 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
471 otherwise returns 0. */
474 forward_propagate_into_comparison (gimple_stmt_iterator
*gsi
)
476 gimple
*stmt
= gsi_stmt (*gsi
);
478 bool cfg_changed
= false;
479 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
480 tree rhs1
= gimple_assign_rhs1 (stmt
);
481 tree rhs2
= gimple_assign_rhs2 (stmt
);
483 /* Combine the comparison with defining statements. */
484 tmp
= forward_propagate_into_comparison_1 (stmt
,
485 gimple_assign_rhs_code (stmt
),
487 if (tmp
&& useless_type_conversion_p (type
, TREE_TYPE (tmp
)))
489 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
491 update_stmt (gsi_stmt (*gsi
));
493 if (TREE_CODE (rhs1
) == SSA_NAME
)
494 cfg_changed
|= remove_prop_source_from_use (rhs1
);
495 if (TREE_CODE (rhs2
) == SSA_NAME
)
496 cfg_changed
|= remove_prop_source_from_use (rhs2
);
497 return cfg_changed
? 2 : 1;
503 /* Propagate from the ssa name definition statements of COND_EXPR
504 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
505 Returns zero if no statement was changed, one if there were
506 changes and two if cfg_cleanup needs to run.
508 This must be kept in sync with forward_propagate_into_cond. */
511 forward_propagate_into_gimple_cond (gcond
*stmt
)
514 enum tree_code code
= gimple_cond_code (stmt
);
515 bool cfg_changed
= false;
516 tree rhs1
= gimple_cond_lhs (stmt
);
517 tree rhs2
= gimple_cond_rhs (stmt
);
519 /* We can do tree combining on SSA_NAME and comparison expressions. */
520 if (TREE_CODE_CLASS (gimple_cond_code (stmt
)) != tcc_comparison
)
523 tmp
= forward_propagate_into_comparison_1 (stmt
, code
,
528 if (dump_file
&& tmp
)
530 fprintf (dump_file
, " Replaced '");
531 print_gimple_expr (dump_file
, stmt
, 0);
532 fprintf (dump_file
, "' with '");
533 print_generic_expr (dump_file
, tmp
);
534 fprintf (dump_file
, "'\n");
537 gimple_cond_set_condition_from_tree (stmt
, unshare_expr (tmp
));
540 if (TREE_CODE (rhs1
) == SSA_NAME
)
541 cfg_changed
|= remove_prop_source_from_use (rhs1
);
542 if (TREE_CODE (rhs2
) == SSA_NAME
)
543 cfg_changed
|= remove_prop_source_from_use (rhs2
);
544 return (cfg_changed
|| is_gimple_min_invariant (tmp
)) ? 2 : 1;
547 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
548 if ((TREE_CODE (TREE_TYPE (rhs1
)) == BOOLEAN_TYPE
549 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
550 && TYPE_PRECISION (TREE_TYPE (rhs1
)) == 1))
552 && integer_zerop (rhs2
))
554 && integer_onep (rhs2
))))
556 basic_block bb
= gimple_bb (stmt
);
557 gimple_cond_set_code (stmt
, NE_EXPR
);
558 gimple_cond_set_rhs (stmt
, build_zero_cst (TREE_TYPE (rhs1
)));
559 EDGE_SUCC (bb
, 0)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
560 EDGE_SUCC (bb
, 1)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
568 /* Propagate from the ssa name definition statements of COND_EXPR
569 in the rhs of statement STMT into the conditional if that simplifies it.
570 Returns true zero if the stmt was changed. */
573 forward_propagate_into_cond (gimple_stmt_iterator
*gsi_p
)
575 gimple
*stmt
= gsi_stmt (*gsi_p
);
576 tree tmp
= NULL_TREE
;
577 tree cond
= gimple_assign_rhs1 (stmt
);
578 enum tree_code code
= gimple_assign_rhs_code (stmt
);
580 /* We can do tree combining on SSA_NAME and comparison expressions. */
581 if (COMPARISON_CLASS_P (cond
))
582 tmp
= forward_propagate_into_comparison_1 (stmt
, TREE_CODE (cond
),
584 TREE_OPERAND (cond
, 0),
585 TREE_OPERAND (cond
, 1));
586 else if (TREE_CODE (cond
) == SSA_NAME
)
588 enum tree_code def_code
;
590 gimple
*def_stmt
= get_prop_source_stmt (name
, true, NULL
);
591 if (!def_stmt
|| !can_propagate_from (def_stmt
))
594 def_code
= gimple_assign_rhs_code (def_stmt
);
595 if (TREE_CODE_CLASS (def_code
) == tcc_comparison
)
596 tmp
= fold_build2_loc (gimple_location (def_stmt
),
599 gimple_assign_rhs1 (def_stmt
),
600 gimple_assign_rhs2 (def_stmt
));
604 && is_gimple_condexpr (tmp
))
606 if (dump_file
&& tmp
)
608 fprintf (dump_file
, " Replaced '");
609 print_generic_expr (dump_file
, cond
);
610 fprintf (dump_file
, "' with '");
611 print_generic_expr (dump_file
, tmp
);
612 fprintf (dump_file
, "'\n");
615 if ((code
== VEC_COND_EXPR
) ? integer_all_onesp (tmp
)
616 : integer_onep (tmp
))
617 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs2 (stmt
));
618 else if (integer_zerop (tmp
))
619 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs3 (stmt
));
621 gimple_assign_set_rhs1 (stmt
, unshare_expr (tmp
));
622 stmt
= gsi_stmt (*gsi_p
);
631 /* We've just substituted an ADDR_EXPR into stmt. Update all the
632 relevant data structures to match. */
635 tidy_after_forward_propagate_addr (gimple
*stmt
)
637 /* We may have turned a trapping insn into a non-trapping insn. */
638 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
))
639 bitmap_set_bit (to_purge
, gimple_bb (stmt
)->index
);
641 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
642 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
645 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
646 ADDR_EXPR <whatever>.
648 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
649 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
650 node or for recovery of array indexing from pointer arithmetic.
652 Return true if the propagation was successful (the propagation can
653 be not totally successful, yet things may have been changed). */
656 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
,
657 gimple_stmt_iterator
*use_stmt_gsi
,
660 tree lhs
, rhs
, rhs2
, array_ref
;
661 gimple
*use_stmt
= gsi_stmt (*use_stmt_gsi
);
662 enum tree_code rhs_code
;
665 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
667 lhs
= gimple_assign_lhs (use_stmt
);
668 rhs_code
= gimple_assign_rhs_code (use_stmt
);
669 rhs
= gimple_assign_rhs1 (use_stmt
);
671 /* Do not perform copy-propagation but recurse through copy chains. */
672 if (TREE_CODE (lhs
) == SSA_NAME
673 && rhs_code
== SSA_NAME
)
674 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
676 /* The use statement could be a conversion. Recurse to the uses of the
677 lhs as copyprop does not copy through pointer to integer to pointer
678 conversions and FRE does not catch all cases either.
679 Treat the case of a single-use name and
680 a conversion to def_rhs type separate, though. */
681 if (TREE_CODE (lhs
) == SSA_NAME
682 && CONVERT_EXPR_CODE_P (rhs_code
))
684 /* If there is a point in a conversion chain where the types match
685 so we can remove a conversion re-materialize the address here
688 && useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
690 gimple_assign_set_rhs1 (use_stmt
, unshare_expr (def_rhs
));
691 gimple_assign_set_rhs_code (use_stmt
, TREE_CODE (def_rhs
));
695 /* Else recurse if the conversion preserves the address value. */
696 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
697 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
698 && (TYPE_PRECISION (TREE_TYPE (lhs
))
699 >= TYPE_PRECISION (TREE_TYPE (def_rhs
))))
700 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
705 /* If this isn't a conversion chain from this on we only can propagate
706 into compatible pointer contexts. */
707 if (!types_compatible_p (TREE_TYPE (name
), TREE_TYPE (def_rhs
)))
710 /* Propagate through constant pointer adjustments. */
711 if (TREE_CODE (lhs
) == SSA_NAME
712 && rhs_code
== POINTER_PLUS_EXPR
714 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
)
717 /* As we come here with non-invariant addresses in def_rhs we need
718 to make sure we can build a valid constant offsetted address
719 for further propagation. Simply rely on fold building that
720 and check after the fact. */
721 new_def_rhs
= fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (rhs
)),
723 fold_convert (ptr_type_node
,
724 gimple_assign_rhs2 (use_stmt
)));
725 if (TREE_CODE (new_def_rhs
) == MEM_REF
726 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs
, 0)))
728 new_def_rhs
= build_fold_addr_expr_with_type (new_def_rhs
,
731 /* Recurse. If we could propagate into all uses of lhs do not
732 bother to replace into the current use but just pretend we did. */
733 if (TREE_CODE (new_def_rhs
) == ADDR_EXPR
734 && forward_propagate_addr_expr (lhs
, new_def_rhs
, single_use_p
))
737 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (new_def_rhs
)))
738 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, TREE_CODE (new_def_rhs
),
740 else if (is_gimple_min_invariant (new_def_rhs
))
741 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, NOP_EXPR
, new_def_rhs
);
744 gcc_assert (gsi_stmt (*use_stmt_gsi
) == use_stmt
);
745 update_stmt (use_stmt
);
749 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
750 ADDR_EXPR will not appear on the LHS. */
751 tree
*lhsp
= gimple_assign_lhs_ptr (use_stmt
);
752 while (handled_component_p (*lhsp
))
753 lhsp
= &TREE_OPERAND (*lhsp
, 0);
756 /* Now see if the LHS node is a MEM_REF using NAME. If so,
757 propagate the ADDR_EXPR into the use of NAME and fold the result. */
758 if (TREE_CODE (lhs
) == MEM_REF
759 && TREE_OPERAND (lhs
, 0) == name
)
762 poly_int64 def_rhs_offset
;
763 /* If the address is invariant we can always fold it. */
764 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
767 poly_offset_int off
= mem_ref_offset (lhs
);
769 off
+= def_rhs_offset
;
770 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
772 off
+= mem_ref_offset (def_rhs_base
);
773 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
776 new_ptr
= build_fold_addr_expr (def_rhs_base
);
777 TREE_OPERAND (lhs
, 0) = new_ptr
;
778 TREE_OPERAND (lhs
, 1)
779 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs
, 1)), off
);
780 tidy_after_forward_propagate_addr (use_stmt
);
781 /* Continue propagating into the RHS if this was not the only use. */
785 /* If the LHS is a plain dereference and the value type is the same as
786 that of the pointed-to type of the address we can put the
787 dereferenced address on the LHS preserving the original alias-type. */
788 else if (integer_zerop (TREE_OPERAND (lhs
, 1))
789 && ((gimple_assign_lhs (use_stmt
) == lhs
790 && useless_type_conversion_p
791 (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)),
792 TREE_TYPE (gimple_assign_rhs1 (use_stmt
))))
793 || types_compatible_p (TREE_TYPE (lhs
),
794 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
795 /* Don't forward anything into clobber stmts if it would result
796 in the lhs no longer being a MEM_REF. */
797 && (!gimple_clobber_p (use_stmt
)
798 || TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == MEM_REF
))
800 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
801 tree new_offset
, new_base
, saved
, new_lhs
;
802 while (handled_component_p (*def_rhs_basep
))
803 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
804 saved
= *def_rhs_basep
;
805 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
807 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
808 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (lhs
, 1)),
809 TREE_OPERAND (*def_rhs_basep
, 1));
813 new_base
= build_fold_addr_expr (*def_rhs_basep
);
814 new_offset
= TREE_OPERAND (lhs
, 1);
816 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
817 new_base
, new_offset
);
818 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (lhs
);
819 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (lhs
);
820 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (lhs
);
821 new_lhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
823 TREE_THIS_VOLATILE (new_lhs
) = TREE_THIS_VOLATILE (lhs
);
824 TREE_SIDE_EFFECTS (new_lhs
) = TREE_SIDE_EFFECTS (lhs
);
825 *def_rhs_basep
= saved
;
826 tidy_after_forward_propagate_addr (use_stmt
);
827 /* Continue propagating into the RHS if this was not the
833 /* We can have a struct assignment dereferencing our name twice.
834 Note that we didn't propagate into the lhs to not falsely
835 claim we did when propagating into the rhs. */
839 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
840 nodes from the RHS. */
841 tree
*rhsp
= gimple_assign_rhs1_ptr (use_stmt
);
842 if (TREE_CODE (*rhsp
) == ADDR_EXPR
)
843 rhsp
= &TREE_OPERAND (*rhsp
, 0);
844 while (handled_component_p (*rhsp
))
845 rhsp
= &TREE_OPERAND (*rhsp
, 0);
848 /* Now see if the RHS node is a MEM_REF using NAME. If so,
849 propagate the ADDR_EXPR into the use of NAME and fold the result. */
850 if (TREE_CODE (rhs
) == MEM_REF
851 && TREE_OPERAND (rhs
, 0) == name
)
854 poly_int64 def_rhs_offset
;
855 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
858 poly_offset_int off
= mem_ref_offset (rhs
);
860 off
+= def_rhs_offset
;
861 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
863 off
+= mem_ref_offset (def_rhs_base
);
864 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
867 new_ptr
= build_fold_addr_expr (def_rhs_base
);
868 TREE_OPERAND (rhs
, 0) = new_ptr
;
869 TREE_OPERAND (rhs
, 1)
870 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs
, 1)), off
);
871 fold_stmt_inplace (use_stmt_gsi
);
872 tidy_after_forward_propagate_addr (use_stmt
);
875 /* If the RHS is a plain dereference and the value type is the same as
876 that of the pointed-to type of the address we can put the
877 dereferenced address on the RHS preserving the original alias-type. */
878 else if (integer_zerop (TREE_OPERAND (rhs
, 1))
879 && ((gimple_assign_rhs1 (use_stmt
) == rhs
880 && useless_type_conversion_p
881 (TREE_TYPE (gimple_assign_lhs (use_stmt
)),
882 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
883 || types_compatible_p (TREE_TYPE (rhs
),
884 TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))))
886 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
887 tree new_offset
, new_base
, saved
, new_rhs
;
888 while (handled_component_p (*def_rhs_basep
))
889 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
890 saved
= *def_rhs_basep
;
891 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
893 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
894 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (rhs
, 1)),
895 TREE_OPERAND (*def_rhs_basep
, 1));
899 new_base
= build_fold_addr_expr (*def_rhs_basep
);
900 new_offset
= TREE_OPERAND (rhs
, 1);
902 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
903 new_base
, new_offset
);
904 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (rhs
);
905 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (rhs
);
906 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (rhs
);
907 new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
909 TREE_THIS_VOLATILE (new_rhs
) = TREE_THIS_VOLATILE (rhs
);
910 TREE_SIDE_EFFECTS (new_rhs
) = TREE_SIDE_EFFECTS (rhs
);
911 *def_rhs_basep
= saved
;
912 fold_stmt_inplace (use_stmt_gsi
);
913 tidy_after_forward_propagate_addr (use_stmt
);
918 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
920 if (gimple_assign_rhs_code (use_stmt
) != POINTER_PLUS_EXPR
921 || gimple_assign_rhs1 (use_stmt
) != name
)
924 /* The remaining cases are all for turning pointer arithmetic into
925 array indexing. They only apply when we have the address of
926 element zero in an array. If that is not the case then there
928 array_ref
= TREE_OPERAND (def_rhs
, 0);
929 if ((TREE_CODE (array_ref
) != ARRAY_REF
930 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
931 || TREE_CODE (TREE_OPERAND (array_ref
, 1)) != INTEGER_CST
)
932 && TREE_CODE (TREE_TYPE (array_ref
)) != ARRAY_TYPE
)
935 rhs2
= gimple_assign_rhs2 (use_stmt
);
936 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
937 if (TREE_CODE (rhs2
) == INTEGER_CST
)
939 tree new_rhs
= build1_loc (gimple_location (use_stmt
),
940 ADDR_EXPR
, TREE_TYPE (def_rhs
),
941 fold_build2 (MEM_REF
,
942 TREE_TYPE (TREE_TYPE (def_rhs
)),
943 unshare_expr (def_rhs
),
944 fold_convert (ptr_type_node
,
946 gimple_assign_set_rhs_from_tree (use_stmt_gsi
, new_rhs
);
947 use_stmt
= gsi_stmt (*use_stmt_gsi
);
948 update_stmt (use_stmt
);
949 tidy_after_forward_propagate_addr (use_stmt
);
956 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
958 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
959 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
960 node or for recovery of array indexing from pointer arithmetic.
962 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
963 the single use in the previous invocation. Pass true when calling
966 Returns true, if all uses have been propagated into. */
969 forward_propagate_addr_expr (tree name
, tree rhs
, bool parent_single_use_p
)
971 imm_use_iterator iter
;
974 bool single_use_p
= parent_single_use_p
&& has_single_use (name
);
976 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
981 /* If the use is not in a simple assignment statement, then
982 there is nothing we can do. */
983 if (!is_gimple_assign (use_stmt
))
985 if (!is_gimple_debug (use_stmt
))
990 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
991 result
= forward_propagate_addr_expr_1 (name
, rhs
, &gsi
,
993 /* If the use has moved to a different statement adjust
994 the update machinery for the old statement too. */
995 if (use_stmt
!= gsi_stmt (gsi
))
997 update_stmt (use_stmt
);
998 use_stmt
= gsi_stmt (gsi
);
1000 update_stmt (use_stmt
);
1003 /* Remove intermediate now unused copy and conversion chains. */
1004 use_rhs
= gimple_assign_rhs1 (use_stmt
);
1006 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
1007 && TREE_CODE (use_rhs
) == SSA_NAME
1008 && has_zero_uses (gimple_assign_lhs (use_stmt
)))
1010 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1011 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt
));
1012 release_defs (use_stmt
);
1013 gsi_remove (&gsi
, true);
1017 return all
&& has_zero_uses (name
);
1021 /* Helper function for simplify_gimple_switch. Remove case labels that
1022 have values outside the range of the new type. */
1025 simplify_gimple_switch_label_vec (gswitch
*stmt
, tree index_type
)
1027 unsigned int branch_num
= gimple_switch_num_labels (stmt
);
1028 auto_vec
<tree
> labels (branch_num
);
1029 unsigned int i
, len
;
1031 /* Collect the existing case labels in a VEC, and preprocess it as if
1032 we are gimplifying a GENERIC SWITCH_EXPR. */
1033 for (i
= 1; i
< branch_num
; i
++)
1034 labels
.quick_push (gimple_switch_label (stmt
, i
));
1035 preprocess_case_label_vec_for_gimple (labels
, index_type
, NULL
);
1037 /* If any labels were removed, replace the existing case labels
1038 in the GIMPLE_SWITCH statement with the correct ones.
1039 Note that the type updates were done in-place on the case labels,
1040 so we only have to replace the case labels in the GIMPLE_SWITCH
1041 if the number of labels changed. */
1042 len
= labels
.length ();
1043 if (len
< branch_num
- 1)
1045 bitmap target_blocks
;
1049 /* Corner case: *all* case labels have been removed as being
1050 out-of-range for INDEX_TYPE. Push one label and let the
1051 CFG cleanups deal with this further. */
1056 label
= CASE_LABEL (gimple_switch_default_label (stmt
));
1057 elt
= build_case_label (build_int_cst (index_type
, 0), NULL
, label
);
1058 labels
.quick_push (elt
);
1062 for (i
= 0; i
< labels
.length (); i
++)
1063 gimple_switch_set_label (stmt
, i
+ 1, labels
[i
]);
1064 for (i
++ ; i
< branch_num
; i
++)
1065 gimple_switch_set_label (stmt
, i
, NULL_TREE
);
1066 gimple_switch_set_num_labels (stmt
, len
+ 1);
1068 /* Cleanup any edges that are now dead. */
1069 target_blocks
= BITMAP_ALLOC (NULL
);
1070 for (i
= 0; i
< gimple_switch_num_labels (stmt
); i
++)
1072 tree elt
= gimple_switch_label (stmt
, i
);
1073 basic_block target
= label_to_block (CASE_LABEL (elt
));
1074 bitmap_set_bit (target_blocks
, target
->index
);
1076 for (ei
= ei_start (gimple_bb (stmt
)->succs
); (e
= ei_safe_edge (ei
)); )
1078 if (! bitmap_bit_p (target_blocks
, e
->dest
->index
))
1082 free_dominance_info (CDI_DOMINATORS
);
1087 BITMAP_FREE (target_blocks
);
1091 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1092 the condition which we may be able to optimize better. */
1095 simplify_gimple_switch (gswitch
*stmt
)
1097 /* The optimization that we really care about is removing unnecessary
1098 casts. That will let us do much better in propagating the inferred
1099 constant at the switch target. */
1100 tree cond
= gimple_switch_index (stmt
);
1101 if (TREE_CODE (cond
) == SSA_NAME
)
1103 gimple
*def_stmt
= SSA_NAME_DEF_STMT (cond
);
1104 if (gimple_assign_cast_p (def_stmt
))
1106 tree def
= gimple_assign_rhs1 (def_stmt
);
1107 if (TREE_CODE (def
) != SSA_NAME
)
1110 /* If we have an extension or sign-change that preserves the
1111 values we check against then we can copy the source value into
1113 tree ti
= TREE_TYPE (def
);
1114 if (INTEGRAL_TYPE_P (ti
)
1115 && TYPE_PRECISION (ti
) <= TYPE_PRECISION (TREE_TYPE (cond
)))
1117 size_t n
= gimple_switch_num_labels (stmt
);
1118 tree min
= NULL_TREE
, max
= NULL_TREE
;
1121 min
= CASE_LOW (gimple_switch_label (stmt
, 1));
1122 if (CASE_HIGH (gimple_switch_label (stmt
, n
- 1)))
1123 max
= CASE_HIGH (gimple_switch_label (stmt
, n
- 1));
1125 max
= CASE_LOW (gimple_switch_label (stmt
, n
- 1));
1127 if ((!min
|| int_fits_type_p (min
, ti
))
1128 && (!max
|| int_fits_type_p (max
, ti
)))
1130 gimple_switch_set_index (stmt
, def
);
1131 simplify_gimple_switch_label_vec (stmt
, ti
);
1142 /* For pointers p2 and p1 return p2 - p1 if the
1143 difference is known and constant, otherwise return NULL. */
1146 constant_pointer_difference (tree p1
, tree p2
)
1149 #define CPD_ITERATIONS 5
1150 tree exps
[2][CPD_ITERATIONS
];
1151 tree offs
[2][CPD_ITERATIONS
];
1154 for (i
= 0; i
< 2; i
++)
1156 tree p
= i
? p1
: p2
;
1157 tree off
= size_zero_node
;
1159 enum tree_code code
;
1161 /* For each of p1 and p2 we need to iterate at least
1162 twice, to handle ADDR_EXPR directly in p1/p2,
1163 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1164 on definition's stmt RHS. Iterate a few extra times. */
1168 if (!POINTER_TYPE_P (TREE_TYPE (p
)))
1170 if (TREE_CODE (p
) == ADDR_EXPR
)
1172 tree q
= TREE_OPERAND (p
, 0);
1174 tree base
= get_addr_base_and_unit_offset (q
, &offset
);
1178 if (maybe_ne (offset
, 0))
1179 off
= size_binop (PLUS_EXPR
, off
, size_int (offset
));
1181 if (TREE_CODE (q
) == MEM_REF
1182 && TREE_CODE (TREE_OPERAND (q
, 0)) == SSA_NAME
)
1184 p
= TREE_OPERAND (q
, 0);
1185 off
= size_binop (PLUS_EXPR
, off
,
1186 wide_int_to_tree (sizetype
,
1187 mem_ref_offset (q
)));
1196 if (TREE_CODE (p
) != SSA_NAME
)
1200 if (j
== CPD_ITERATIONS
)
1202 stmt
= SSA_NAME_DEF_STMT (p
);
1203 if (!is_gimple_assign (stmt
) || gimple_assign_lhs (stmt
) != p
)
1205 code
= gimple_assign_rhs_code (stmt
);
1206 if (code
== POINTER_PLUS_EXPR
)
1208 if (TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)
1210 off
= size_binop (PLUS_EXPR
, off
, gimple_assign_rhs2 (stmt
));
1211 p
= gimple_assign_rhs1 (stmt
);
1213 else if (code
== ADDR_EXPR
|| CONVERT_EXPR_CODE_P (code
))
1214 p
= gimple_assign_rhs1 (stmt
);
1222 for (i
= 0; i
< cnt
[0]; i
++)
1223 for (j
= 0; j
< cnt
[1]; j
++)
1224 if (exps
[0][i
] == exps
[1][j
])
1225 return size_binop (MINUS_EXPR
, offs
[0][i
], offs
[1][j
]);
1230 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1232 memcpy (p, "abcd", 4);
1233 memset (p + 4, ' ', 3);
1235 memcpy (p, "abcd ", 7);
1236 call if the latter can be stored by pieces during expansion. */
1239 simplify_builtin_call (gimple_stmt_iterator
*gsi_p
, tree callee2
)
1241 gimple
*stmt1
, *stmt2
= gsi_stmt (*gsi_p
);
1242 tree vuse
= gimple_vuse (stmt2
);
1245 stmt1
= SSA_NAME_DEF_STMT (vuse
);
1247 switch (DECL_FUNCTION_CODE (callee2
))
1249 case BUILT_IN_MEMSET
:
1250 if (gimple_call_num_args (stmt2
) != 3
1251 || gimple_call_lhs (stmt2
)
1253 || BITS_PER_UNIT
!= 8)
1258 tree ptr1
, src1
, str1
, off1
, len1
, lhs1
;
1259 tree ptr2
= gimple_call_arg (stmt2
, 0);
1260 tree val2
= gimple_call_arg (stmt2
, 1);
1261 tree len2
= gimple_call_arg (stmt2
, 2);
1262 tree diff
, vdef
, new_str_cst
;
1264 unsigned int ptr1_align
;
1265 unsigned HOST_WIDE_INT src_len
;
1267 use_operand_p use_p
;
1269 if (!tree_fits_shwi_p (val2
)
1270 || !tree_fits_uhwi_p (len2
)
1271 || compare_tree_int (len2
, 1024) == 1)
1273 if (is_gimple_call (stmt1
))
1275 /* If first stmt is a call, it needs to be memcpy
1276 or mempcpy, with string literal as second argument and
1278 callee1
= gimple_call_fndecl (stmt1
);
1279 if (callee1
== NULL_TREE
1280 || DECL_BUILT_IN_CLASS (callee1
) != BUILT_IN_NORMAL
1281 || gimple_call_num_args (stmt1
) != 3)
1283 if (DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMCPY
1284 && DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMPCPY
)
1286 ptr1
= gimple_call_arg (stmt1
, 0);
1287 src1
= gimple_call_arg (stmt1
, 1);
1288 len1
= gimple_call_arg (stmt1
, 2);
1289 lhs1
= gimple_call_lhs (stmt1
);
1290 if (!tree_fits_uhwi_p (len1
))
1292 str1
= string_constant (src1
, &off1
);
1293 if (str1
== NULL_TREE
)
1295 if (!tree_fits_uhwi_p (off1
)
1296 || compare_tree_int (off1
, TREE_STRING_LENGTH (str1
) - 1) > 0
1297 || compare_tree_int (len1
, TREE_STRING_LENGTH (str1
)
1298 - tree_to_uhwi (off1
)) > 0
1299 || TREE_CODE (TREE_TYPE (str1
)) != ARRAY_TYPE
1300 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1
)))
1301 != TYPE_MODE (char_type_node
))
1304 else if (gimple_assign_single_p (stmt1
))
1306 /* Otherwise look for length 1 memcpy optimized into
1308 ptr1
= gimple_assign_lhs (stmt1
);
1309 src1
= gimple_assign_rhs1 (stmt1
);
1310 if (TREE_CODE (ptr1
) != MEM_REF
1311 || TYPE_MODE (TREE_TYPE (ptr1
)) != TYPE_MODE (char_type_node
)
1312 || !tree_fits_shwi_p (src1
))
1314 ptr1
= build_fold_addr_expr (ptr1
);
1315 callee1
= NULL_TREE
;
1316 len1
= size_one_node
;
1318 off1
= size_zero_node
;
1324 diff
= constant_pointer_difference (ptr1
, ptr2
);
1325 if (diff
== NULL
&& lhs1
!= NULL
)
1327 diff
= constant_pointer_difference (lhs1
, ptr2
);
1328 if (DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1330 diff
= size_binop (PLUS_EXPR
, diff
,
1331 fold_convert (sizetype
, len1
));
1333 /* If the difference between the second and first destination pointer
1334 is not constant, or is bigger than memcpy length, bail out. */
1336 || !tree_fits_uhwi_p (diff
)
1337 || tree_int_cst_lt (len1
, diff
)
1338 || compare_tree_int (diff
, 1024) == 1)
1341 /* Use maximum of difference plus memset length and memcpy length
1342 as the new memcpy length, if it is too big, bail out. */
1343 src_len
= tree_to_uhwi (diff
);
1344 src_len
+= tree_to_uhwi (len2
);
1345 if (src_len
< tree_to_uhwi (len1
))
1346 src_len
= tree_to_uhwi (len1
);
1350 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1351 with bigger length will return different result. */
1352 if (lhs1
!= NULL_TREE
1353 && DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1354 && (TREE_CODE (lhs1
) != SSA_NAME
1355 || !single_imm_use (lhs1
, &use_p
, &use_stmt
)
1356 || use_stmt
!= stmt2
))
1359 /* If anything reads memory in between memcpy and memset
1360 call, the modified memcpy call might change it. */
1361 vdef
= gimple_vdef (stmt1
);
1363 && (!single_imm_use (vdef
, &use_p
, &use_stmt
)
1364 || use_stmt
!= stmt2
))
1367 ptr1_align
= get_pointer_alignment (ptr1
);
1368 /* Construct the new source string literal. */
1369 src_buf
= XALLOCAVEC (char, src_len
+ 1);
1372 TREE_STRING_POINTER (str1
) + tree_to_uhwi (off1
),
1373 tree_to_uhwi (len1
));
1375 src_buf
[0] = tree_to_shwi (src1
);
1376 memset (src_buf
+ tree_to_uhwi (diff
),
1377 tree_to_shwi (val2
), tree_to_uhwi (len2
));
1378 src_buf
[src_len
] = '\0';
1379 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1380 handle embedded '\0's. */
1381 if (strlen (src_buf
) != src_len
)
1383 rtl_profile_for_bb (gimple_bb (stmt2
));
1384 /* If the new memcpy wouldn't be emitted by storing the literal
1385 by pieces, this optimization might enlarge .rodata too much,
1386 as commonly used string literals couldn't be shared any
1388 if (!can_store_by_pieces (src_len
,
1389 builtin_strncpy_read_str
,
1390 src_buf
, ptr1_align
, false))
1393 new_str_cst
= build_string_literal (src_len
, src_buf
);
1396 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1398 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1399 gimple_call_set_lhs (stmt1
, NULL_TREE
);
1400 gimple_call_set_arg (stmt1
, 1, new_str_cst
);
1401 gimple_call_set_arg (stmt1
, 2,
1402 build_int_cst (TREE_TYPE (len1
), src_len
));
1403 update_stmt (stmt1
);
1404 unlink_stmt_vdef (stmt2
);
1405 gsi_remove (gsi_p
, true);
1406 fwprop_invalidate_lattice (gimple_get_lhs (stmt2
));
1407 release_defs (stmt2
);
1408 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1410 fwprop_invalidate_lattice (lhs1
);
1411 release_ssa_name (lhs1
);
1417 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1418 assignment, remove STMT1 and change memset call into
1420 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt1
);
1422 if (!is_gimple_val (ptr1
))
1423 ptr1
= force_gimple_operand_gsi (gsi_p
, ptr1
, true, NULL_TREE
,
1424 true, GSI_SAME_STMT
);
1425 gimple_call_set_fndecl (stmt2
,
1426 builtin_decl_explicit (BUILT_IN_MEMCPY
));
1427 gimple_call_set_arg (stmt2
, 0, ptr1
);
1428 gimple_call_set_arg (stmt2
, 1, new_str_cst
);
1429 gimple_call_set_arg (stmt2
, 2,
1430 build_int_cst (TREE_TYPE (len2
), src_len
));
1431 unlink_stmt_vdef (stmt1
);
1432 gsi_remove (&gsi
, true);
1433 fwprop_invalidate_lattice (gimple_get_lhs (stmt1
));
1434 release_defs (stmt1
);
1435 update_stmt (stmt2
);
1446 /* Given a ssa_name in NAME see if it was defined by an assignment and
1447 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1448 to the second operand on the rhs. */
1451 defcodefor_name (tree name
, enum tree_code
*code
, tree
*arg1
, tree
*arg2
)
1454 enum tree_code code1
;
1458 enum gimple_rhs_class grhs_class
;
1460 code1
= TREE_CODE (name
);
1464 grhs_class
= get_gimple_rhs_class (code1
);
1466 if (code1
== SSA_NAME
)
1468 def
= SSA_NAME_DEF_STMT (name
);
1470 if (def
&& is_gimple_assign (def
)
1471 && can_propagate_from (def
))
1473 code1
= gimple_assign_rhs_code (def
);
1474 arg11
= gimple_assign_rhs1 (def
);
1475 arg21
= gimple_assign_rhs2 (def
);
1476 arg31
= gimple_assign_rhs3 (def
);
1479 else if (grhs_class
!= GIMPLE_SINGLE_RHS
)
1491 /* Recognize rotation patterns. Return true if a transformation
1492 applied, otherwise return false.
1494 We are looking for X with unsigned type T with bitsize B, OP being
1495 +, | or ^, some type T2 wider than T. For:
1496 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1497 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1499 transform these into:
1503 (X << Y) OP (X >> (B - Y))
1504 (X << (int) Y) OP (X >> (int) (B - Y))
1505 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1506 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1507 (X << Y) | (X >> ((-Y) & (B - 1)))
1508 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1509 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1510 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1512 transform these into:
1516 (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1)))
1517 (X << (int) (Y & (B - 1))) | (X >> (int) ((-Y) & (B - 1)))
1518 ((T) ((T2) X << (Y & (B - 1)))) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1519 ((T) ((T2) X << (int) (Y & (B - 1)))) \
1520 | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1522 transform these into:
1525 Note, in the patterns with T2 type, the type of OP operands
1526 might be even a signed type, but should have precision B.
1527 Expressions with & (B - 1) should be recognized only if B is
1531 simplify_rotate (gimple_stmt_iterator
*gsi
)
1533 gimple
*stmt
= gsi_stmt (*gsi
);
1534 tree arg
[2], rtype
, rotcnt
= NULL_TREE
;
1535 tree def_arg1
[2], def_arg2
[2];
1536 enum tree_code def_code
[2];
1539 bool swapped_p
= false;
1542 arg
[0] = gimple_assign_rhs1 (stmt
);
1543 arg
[1] = gimple_assign_rhs2 (stmt
);
1544 rtype
= TREE_TYPE (arg
[0]);
1546 /* Only create rotates in complete modes. Other cases are not
1547 expanded properly. */
1548 if (!INTEGRAL_TYPE_P (rtype
)
1549 || !type_has_mode_precision_p (rtype
))
1552 for (i
= 0; i
< 2; i
++)
1553 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1555 /* Look through narrowing conversions. */
1556 if (CONVERT_EXPR_CODE_P (def_code
[0])
1557 && CONVERT_EXPR_CODE_P (def_code
[1])
1558 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[0]))
1559 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[1]))
1560 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0]))
1561 == TYPE_PRECISION (TREE_TYPE (def_arg1
[1]))
1562 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) > TYPE_PRECISION (rtype
)
1563 && has_single_use (arg
[0])
1564 && has_single_use (arg
[1]))
1566 for (i
= 0; i
< 2; i
++)
1568 arg
[i
] = def_arg1
[i
];
1569 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
1573 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1574 for (i
= 0; i
< 2; i
++)
1575 if (def_code
[i
] != LSHIFT_EXPR
&& def_code
[i
] != RSHIFT_EXPR
)
1577 else if (!has_single_use (arg
[i
]))
1579 if (def_code
[0] == def_code
[1])
1582 /* If we've looked through narrowing conversions before, look through
1583 widening conversions from unsigned type with the same precision
1585 if (TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) != TYPE_PRECISION (rtype
))
1586 for (i
= 0; i
< 2; i
++)
1589 enum tree_code code
;
1590 defcodefor_name (def_arg1
[i
], &code
, &tem
, NULL
);
1591 if (!CONVERT_EXPR_CODE_P (code
)
1592 || !INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1593 || TYPE_PRECISION (TREE_TYPE (tem
)) != TYPE_PRECISION (rtype
))
1597 /* Both shifts have to use the same first operand. */
1598 if (!operand_equal_for_phi_arg_p (def_arg1
[0], def_arg1
[1])
1599 || !types_compatible_p (TREE_TYPE (def_arg1
[0]),
1600 TREE_TYPE (def_arg1
[1])))
1602 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1
[0])))
1605 /* CNT1 + CNT2 == B case above. */
1606 if (tree_fits_uhwi_p (def_arg2
[0])
1607 && tree_fits_uhwi_p (def_arg2
[1])
1608 && tree_to_uhwi (def_arg2
[0])
1609 + tree_to_uhwi (def_arg2
[1]) == TYPE_PRECISION (rtype
))
1610 rotcnt
= def_arg2
[0];
1611 else if (TREE_CODE (def_arg2
[0]) != SSA_NAME
1612 || TREE_CODE (def_arg2
[1]) != SSA_NAME
)
1616 tree cdef_arg1
[2], cdef_arg2
[2], def_arg2_alt
[2];
1617 enum tree_code cdef_code
[2];
1618 /* Look through conversion of the shift count argument.
1619 The C/C++ FE cast any shift count argument to integer_type_node.
1620 The only problem might be if the shift count type maximum value
1621 is equal or smaller than number of bits in rtype. */
1622 for (i
= 0; i
< 2; i
++)
1624 def_arg2_alt
[i
] = def_arg2
[i
];
1625 defcodefor_name (def_arg2
[i
], &cdef_code
[i
],
1626 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1627 if (CONVERT_EXPR_CODE_P (cdef_code
[i
])
1628 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1
[i
]))
1629 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
1630 > floor_log2 (TYPE_PRECISION (rtype
))
1631 && type_has_mode_precision_p (TREE_TYPE (cdef_arg1
[i
])))
1633 def_arg2_alt
[i
] = cdef_arg1
[i
];
1634 defcodefor_name (def_arg2_alt
[i
], &cdef_code
[i
],
1635 &cdef_arg1
[i
], &cdef_arg2
[i
]);
1638 for (i
= 0; i
< 2; i
++)
1639 /* Check for one shift count being Y and the other B - Y,
1640 with optional casts. */
1641 if (cdef_code
[i
] == MINUS_EXPR
1642 && tree_fits_shwi_p (cdef_arg1
[i
])
1643 && tree_to_shwi (cdef_arg1
[i
]) == TYPE_PRECISION (rtype
)
1644 && TREE_CODE (cdef_arg2
[i
]) == SSA_NAME
)
1647 enum tree_code code
;
1649 if (cdef_arg2
[i
] == def_arg2
[1 - i
]
1650 || cdef_arg2
[i
] == def_arg2_alt
[1 - i
])
1652 rotcnt
= cdef_arg2
[i
];
1655 defcodefor_name (cdef_arg2
[i
], &code
, &tem
, NULL
);
1656 if (CONVERT_EXPR_CODE_P (code
)
1657 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1658 && TYPE_PRECISION (TREE_TYPE (tem
))
1659 > floor_log2 (TYPE_PRECISION (rtype
))
1660 && type_has_mode_precision_p (TREE_TYPE (tem
))
1661 && (tem
== def_arg2
[1 - i
]
1662 || tem
== def_arg2_alt
[1 - i
]))
1668 /* The above sequence isn't safe for Y being 0,
1669 because then one of the shifts triggers undefined behavior.
1670 This alternative is safe even for rotation count of 0.
1671 One shift count is Y and the other (-Y) & (B - 1).
1672 Or one shift count is Y & (B - 1) and the other (-Y) & (B - 1). */
1673 else if (cdef_code
[i
] == BIT_AND_EXPR
1674 && pow2p_hwi (TYPE_PRECISION (rtype
))
1675 && tree_fits_shwi_p (cdef_arg2
[i
])
1676 && tree_to_shwi (cdef_arg2
[i
])
1677 == TYPE_PRECISION (rtype
) - 1
1678 && TREE_CODE (cdef_arg1
[i
]) == SSA_NAME
1679 && gimple_assign_rhs_code (stmt
) == BIT_IOR_EXPR
)
1682 enum tree_code code
;
1684 defcodefor_name (cdef_arg1
[i
], &code
, &tem
, NULL
);
1685 if (CONVERT_EXPR_CODE_P (code
)
1686 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
1687 && TYPE_PRECISION (TREE_TYPE (tem
))
1688 > floor_log2 (TYPE_PRECISION (rtype
))
1689 && type_has_mode_precision_p (TREE_TYPE (tem
)))
1690 defcodefor_name (tem
, &code
, &tem
, NULL
);
1692 if (code
== NEGATE_EXPR
)
1694 if (tem
== def_arg2
[1 - i
] || tem
== def_arg2_alt
[1 - i
])
1700 defcodefor_name (tem
, &code
, &tem2
, NULL
);
1701 if (CONVERT_EXPR_CODE_P (code
)
1702 && INTEGRAL_TYPE_P (TREE_TYPE (tem2
))
1703 && TYPE_PRECISION (TREE_TYPE (tem2
))
1704 > floor_log2 (TYPE_PRECISION (rtype
))
1705 && type_has_mode_precision_p (TREE_TYPE (tem2
)))
1707 if (tem2
== def_arg2
[1 - i
]
1708 || tem2
== def_arg2_alt
[1 - i
])
1717 if (cdef_code
[1 - i
] == BIT_AND_EXPR
1718 && tree_fits_shwi_p (cdef_arg2
[1 - i
])
1719 && tree_to_shwi (cdef_arg2
[1 - i
])
1720 == TYPE_PRECISION (rtype
) - 1
1721 && TREE_CODE (cdef_arg1
[1 - i
]) == SSA_NAME
)
1723 if (tem
== cdef_arg1
[1 - i
]
1724 || tem2
== cdef_arg1
[1 - i
])
1726 rotcnt
= def_arg2
[1 - i
];
1730 defcodefor_name (cdef_arg1
[1 - i
], &code
, &tem3
, NULL
);
1731 if (CONVERT_EXPR_CODE_P (code
)
1732 && INTEGRAL_TYPE_P (TREE_TYPE (tem3
))
1733 && TYPE_PRECISION (TREE_TYPE (tem3
))
1734 > floor_log2 (TYPE_PRECISION (rtype
))
1735 && type_has_mode_precision_p (TREE_TYPE (tem3
)))
1737 if (tem
== tem3
|| tem2
== tem3
)
1739 rotcnt
= def_arg2
[1 - i
];
1746 if (rotcnt
== NULL_TREE
)
1751 if (!useless_type_conversion_p (TREE_TYPE (def_arg2
[0]),
1752 TREE_TYPE (rotcnt
)))
1754 g
= gimple_build_assign (make_ssa_name (TREE_TYPE (def_arg2
[0])),
1756 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1757 rotcnt
= gimple_assign_lhs (g
);
1759 lhs
= gimple_assign_lhs (stmt
);
1760 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1761 lhs
= make_ssa_name (TREE_TYPE (def_arg1
[0]));
1762 g
= gimple_build_assign (lhs
,
1763 ((def_code
[0] == LSHIFT_EXPR
) ^ swapped_p
)
1764 ? LROTATE_EXPR
: RROTATE_EXPR
, def_arg1
[0], rotcnt
);
1765 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
1767 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
1768 g
= gimple_build_assign (gimple_assign_lhs (stmt
), NOP_EXPR
, lhs
);
1770 gsi_replace (gsi
, g
, false);
1774 /* Combine an element access with a shuffle. Returns true if there were
1775 any changes made, else it returns false. */
1778 simplify_bitfield_ref (gimple_stmt_iterator
*gsi
)
1780 gimple
*stmt
= gsi_stmt (*gsi
);
1782 tree op
, op0
, op1
, op2
;
1785 enum tree_code code
;
1787 op
= gimple_assign_rhs1 (stmt
);
1788 gcc_checking_assert (TREE_CODE (op
) == BIT_FIELD_REF
);
1790 op0
= TREE_OPERAND (op
, 0);
1791 if (TREE_CODE (op0
) != SSA_NAME
1792 || TREE_CODE (TREE_TYPE (op0
)) != VECTOR_TYPE
)
1795 def_stmt
= get_prop_source_stmt (op0
, false, NULL
);
1796 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1799 op1
= TREE_OPERAND (op
, 1);
1800 op2
= TREE_OPERAND (op
, 2);
1801 code
= gimple_assign_rhs_code (def_stmt
);
1803 if (code
== CONSTRUCTOR
)
1805 tree tem
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (op
),
1806 gimple_assign_rhs1 (def_stmt
), op1
, op2
);
1807 if (!tem
|| !valid_gimple_rhs_p (tem
))
1809 gimple_assign_set_rhs_from_tree (gsi
, tem
);
1810 update_stmt (gsi_stmt (*gsi
));
1814 elem_type
= TREE_TYPE (TREE_TYPE (op0
));
1815 if (TREE_TYPE (op
) != elem_type
)
1818 size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
1819 if (maybe_ne (bit_field_size (op
), size
))
1822 if (code
== VEC_PERM_EXPR
1823 && constant_multiple_p (bit_field_offset (op
), size
, &idx
))
1827 m
= gimple_assign_rhs3 (def_stmt
);
1828 if (TREE_CODE (m
) != VECTOR_CST
)
1830 nelts
= VECTOR_CST_NELTS (m
);
1831 idx
= TREE_INT_CST_LOW (VECTOR_CST_ELT (m
, idx
));
1835 p
= gimple_assign_rhs1 (def_stmt
);
1839 p
= gimple_assign_rhs2 (def_stmt
);
1842 tem
= build3 (BIT_FIELD_REF
, TREE_TYPE (op
),
1843 unshare_expr (p
), op1
, bitsize_int (idx
* size
));
1844 gimple_assign_set_rhs1 (stmt
, tem
);
1846 update_stmt (gsi_stmt (*gsi
));
1853 /* Determine whether applying the 2 permutations (mask1 then mask2)
1854 gives back one of the input. */
1857 is_combined_permutation_identity (tree mask1
, tree mask2
)
1860 unsigned int nelts
, i
, j
;
1861 bool maybe_identity1
= true;
1862 bool maybe_identity2
= true;
1864 gcc_checking_assert (TREE_CODE (mask1
) == VECTOR_CST
1865 && TREE_CODE (mask2
) == VECTOR_CST
);
1866 mask
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (mask1
), mask1
, mask1
, mask2
);
1867 gcc_assert (TREE_CODE (mask
) == VECTOR_CST
);
1869 nelts
= VECTOR_CST_NELTS (mask
);
1870 for (i
= 0; i
< nelts
; i
++)
1872 tree val
= VECTOR_CST_ELT (mask
, i
);
1873 gcc_assert (TREE_CODE (val
) == INTEGER_CST
);
1874 j
= TREE_INT_CST_LOW (val
) & (2 * nelts
- 1);
1876 maybe_identity2
= false;
1877 else if (j
== i
+ nelts
)
1878 maybe_identity1
= false;
1882 return maybe_identity1
? 1 : maybe_identity2
? 2 : 0;
1885 /* Combine a shuffle with its arguments. Returns 1 if there were any
1886 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
1889 simplify_permutation (gimple_stmt_iterator
*gsi
)
1891 gimple
*stmt
= gsi_stmt (*gsi
);
1893 tree op0
, op1
, op2
, op3
, arg0
, arg1
;
1894 enum tree_code code
;
1895 bool single_use_op0
= false;
1897 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == VEC_PERM_EXPR
);
1899 op0
= gimple_assign_rhs1 (stmt
);
1900 op1
= gimple_assign_rhs2 (stmt
);
1901 op2
= gimple_assign_rhs3 (stmt
);
1903 if (TREE_CODE (op2
) != VECTOR_CST
)
1906 if (TREE_CODE (op0
) == VECTOR_CST
)
1911 else if (TREE_CODE (op0
) == SSA_NAME
)
1913 def_stmt
= get_prop_source_stmt (op0
, false, &single_use_op0
);
1914 if (!def_stmt
|| !can_propagate_from (def_stmt
))
1917 code
= gimple_assign_rhs_code (def_stmt
);
1918 arg0
= gimple_assign_rhs1 (def_stmt
);
1923 /* Two consecutive shuffles. */
1924 if (code
== VEC_PERM_EXPR
)
1931 op3
= gimple_assign_rhs3 (def_stmt
);
1932 if (TREE_CODE (op3
) != VECTOR_CST
)
1934 ident
= is_combined_permutation_identity (op3
, op2
);
1937 orig
= (ident
== 1) ? gimple_assign_rhs1 (def_stmt
)
1938 : gimple_assign_rhs2 (def_stmt
);
1939 gimple_assign_set_rhs1 (stmt
, unshare_expr (orig
));
1940 gimple_assign_set_rhs_code (stmt
, TREE_CODE (orig
));
1941 gimple_set_num_ops (stmt
, 2);
1943 return remove_prop_source_from_use (op0
) ? 2 : 1;
1946 /* Shuffle of a constructor. */
1947 else if (code
== CONSTRUCTOR
|| code
== VECTOR_CST
)
1953 if (TREE_CODE (op0
) == SSA_NAME
&& !single_use_op0
)
1956 if (TREE_CODE (op1
) == VECTOR_CST
)
1958 else if (TREE_CODE (op1
) == SSA_NAME
)
1960 enum tree_code code2
;
1962 gimple
*def_stmt2
= get_prop_source_stmt (op1
, true, NULL
);
1963 if (!def_stmt2
|| !can_propagate_from (def_stmt2
))
1966 code2
= gimple_assign_rhs_code (def_stmt2
);
1967 if (code2
!= CONSTRUCTOR
&& code2
!= VECTOR_CST
)
1969 arg1
= gimple_assign_rhs1 (def_stmt2
);
1976 /* Already used twice in this statement. */
1977 if (TREE_CODE (op0
) == SSA_NAME
&& num_imm_uses (op0
) > 2)
1981 opt
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (op0
), arg0
, arg1
, op2
);
1983 || (TREE_CODE (opt
) != CONSTRUCTOR
&& TREE_CODE (opt
) != VECTOR_CST
))
1985 gimple_assign_set_rhs_from_tree (gsi
, opt
);
1986 update_stmt (gsi_stmt (*gsi
));
1987 if (TREE_CODE (op0
) == SSA_NAME
)
1988 ret
= remove_prop_source_from_use (op0
);
1989 if (op0
!= op1
&& TREE_CODE (op1
) == SSA_NAME
)
1990 ret
|= remove_prop_source_from_use (op1
);
1997 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
2000 simplify_vector_constructor (gimple_stmt_iterator
*gsi
)
2002 gimple
*stmt
= gsi_stmt (*gsi
);
2004 tree op
, op2
, orig
, type
, elem_type
;
2005 unsigned elem_size
, nelts
, i
;
2006 enum tree_code code
, conv_code
;
2007 constructor_elt
*elt
;
2010 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
);
2012 op
= gimple_assign_rhs1 (stmt
);
2013 type
= TREE_TYPE (op
);
2014 gcc_checking_assert (TREE_CODE (type
) == VECTOR_TYPE
);
2016 nelts
= TYPE_VECTOR_SUBPARTS (type
);
2017 elem_type
= TREE_TYPE (type
);
2018 elem_size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
2020 auto_vec_perm_indices
sel (nelts
);
2022 conv_code
= ERROR_MARK
;
2024 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op
), i
, elt
)
2031 if (TREE_CODE (elt
->value
) != SSA_NAME
)
2033 def_stmt
= get_prop_source_stmt (elt
->value
, false, NULL
);
2036 code
= gimple_assign_rhs_code (def_stmt
);
2037 if (code
== FLOAT_EXPR
2038 || code
== FIX_TRUNC_EXPR
)
2040 op1
= gimple_assign_rhs1 (def_stmt
);
2041 if (conv_code
== ERROR_MARK
)
2043 if (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (elt
->value
)))
2044 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op1
))))
2048 else if (conv_code
!= code
)
2050 if (TREE_CODE (op1
) != SSA_NAME
)
2052 def_stmt
= SSA_NAME_DEF_STMT (op1
);
2053 if (! is_gimple_assign (def_stmt
))
2055 code
= gimple_assign_rhs_code (def_stmt
);
2057 if (code
!= BIT_FIELD_REF
)
2059 op1
= gimple_assign_rhs1 (def_stmt
);
2060 ref
= TREE_OPERAND (op1
, 0);
2068 if (TREE_CODE (ref
) != SSA_NAME
)
2070 if (! VECTOR_TYPE_P (TREE_TYPE (ref
))
2071 || ! useless_type_conversion_p (TREE_TYPE (op1
),
2072 TREE_TYPE (TREE_TYPE (ref
))))
2077 if (maybe_ne (bit_field_size (op1
), elem_size
)
2078 || !constant_multiple_p (bit_field_offset (op1
), elem_size
, &elt
))
2081 maybe_ident
= false;
2082 sel
.quick_push (elt
);
2087 if (! VECTOR_TYPE_P (TREE_TYPE (orig
))
2088 || (TYPE_VECTOR_SUBPARTS (type
)
2089 != TYPE_VECTOR_SUBPARTS (TREE_TYPE (orig
))))
2093 if (conv_code
!= ERROR_MARK
2094 && (! supportable_convert_operation (conv_code
, type
, TREE_TYPE (orig
),
2096 || conv_code
== CALL_EXPR
))
2101 if (conv_code
== ERROR_MARK
)
2102 gimple_assign_set_rhs_from_tree (gsi
, orig
);
2104 gimple_assign_set_rhs_with_ops (gsi
, conv_code
, orig
,
2105 NULL_TREE
, NULL_TREE
);
2111 if (!can_vec_perm_p (TYPE_MODE (type
), false, &sel
))
2114 = build_vector_type (build_nonstandard_integer_type (elem_size
, 1),
2116 if (GET_MODE_CLASS (TYPE_MODE (mask_type
)) != MODE_VECTOR_INT
2117 || GET_MODE_SIZE (TYPE_MODE (mask_type
))
2118 != GET_MODE_SIZE (TYPE_MODE (type
)))
2120 tree_vector_builder
mask_elts (mask_type
, nelts
, 1);
2121 for (i
= 0; i
< nelts
; i
++)
2122 mask_elts
.quick_push (build_int_cst (TREE_TYPE (mask_type
), sel
[i
]));
2123 op2
= mask_elts
.build ();
2124 if (conv_code
== ERROR_MARK
)
2125 gimple_assign_set_rhs_with_ops (gsi
, VEC_PERM_EXPR
, orig
, orig
, op2
);
2129 = gimple_build_assign (make_ssa_name (TREE_TYPE (orig
)),
2130 VEC_PERM_EXPR
, orig
, orig
, op2
);
2131 orig
= gimple_assign_lhs (perm
);
2132 gsi_insert_before (gsi
, perm
, GSI_SAME_STMT
);
2133 gimple_assign_set_rhs_with_ops (gsi
, conv_code
, orig
,
2134 NULL_TREE
, NULL_TREE
);
2137 update_stmt (gsi_stmt (*gsi
));
2142 /* Primitive "lattice" function for gimple_simplify. */
2145 fwprop_ssa_val (tree name
)
2147 /* First valueize NAME. */
2148 if (TREE_CODE (name
) == SSA_NAME
2149 && SSA_NAME_VERSION (name
) < lattice
.length ())
2151 tree val
= lattice
[SSA_NAME_VERSION (name
)];
2155 /* We continue matching along SSA use-def edges for SSA names
2156 that are not single-use. Currently there are no patterns
2157 that would cause any issues with that. */
2161 /* Main entry point for the forward propagation and statement combine
2166 const pass_data pass_data_forwprop
=
2168 GIMPLE_PASS
, /* type */
2169 "forwprop", /* name */
2170 OPTGROUP_NONE
, /* optinfo_flags */
2171 TV_TREE_FORWPROP
, /* tv_id */
2172 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2173 0, /* properties_provided */
2174 0, /* properties_destroyed */
2175 0, /* todo_flags_start */
2176 TODO_update_ssa
, /* todo_flags_finish */
2179 class pass_forwprop
: public gimple_opt_pass
2182 pass_forwprop (gcc::context
*ctxt
)
2183 : gimple_opt_pass (pass_data_forwprop
, ctxt
)
2186 /* opt_pass methods: */
2187 opt_pass
* clone () { return new pass_forwprop (m_ctxt
); }
2188 virtual bool gate (function
*) { return flag_tree_forwprop
; }
2189 virtual unsigned int execute (function
*);
2191 }; // class pass_forwprop
2194 pass_forwprop::execute (function
*fun
)
2196 unsigned int todoflags
= 0;
2198 cfg_changed
= false;
2200 /* Combine stmts with the stmts defining their operands. Do that
2201 in an order that guarantees visiting SSA defs before SSA uses. */
2202 lattice
.create (num_ssa_names
);
2203 lattice
.quick_grow_cleared (num_ssa_names
);
2204 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
2205 int postorder_num
= pre_and_rev_post_order_compute_fn (cfun
, NULL
,
2207 auto_vec
<gimple
*, 4> to_fixup
;
2208 to_purge
= BITMAP_ALLOC (NULL
);
2209 for (int i
= 0; i
< postorder_num
; ++i
)
2211 gimple_stmt_iterator gsi
;
2212 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, postorder
[i
]);
2214 /* Propagate into PHIs and record degenerate ones in the lattice. */
2215 for (gphi_iterator si
= gsi_start_phis (bb
); !gsi_end_p (si
);
2218 gphi
*phi
= si
.phi ();
2219 tree res
= gimple_phi_result (phi
);
2220 if (virtual_operand_p (res
))
2223 use_operand_p use_p
;
2225 tree first
= NULL_TREE
;
2226 bool all_same
= true;
2227 FOR_EACH_PHI_ARG (use_p
, phi
, it
, SSA_OP_USE
)
2229 tree use
= USE_FROM_PTR (use_p
);
2230 tree tem
= fwprop_ssa_val (use
);
2233 else if (! operand_equal_p (first
, tem
, 0))
2236 && may_propagate_copy (use
, tem
))
2237 propagate_value (use_p
, tem
);
2240 fwprop_set_lattice_val (res
, first
);
2243 /* Apply forward propagation to all stmts in the basic-block.
2244 Note we update GSI within the loop as necessary. */
2245 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2247 gimple
*stmt
= gsi_stmt (gsi
);
2249 enum tree_code code
;
2251 if (!is_gimple_assign (stmt
))
2257 lhs
= gimple_assign_lhs (stmt
);
2258 rhs
= gimple_assign_rhs1 (stmt
);
2259 code
= gimple_assign_rhs_code (stmt
);
2260 if (TREE_CODE (lhs
) != SSA_NAME
2261 || has_zero_uses (lhs
))
2267 /* If this statement sets an SSA_NAME to an address,
2268 try to propagate the address into the uses of the SSA_NAME. */
2269 if (code
== ADDR_EXPR
2270 /* Handle pointer conversions on invariant addresses
2271 as well, as this is valid gimple. */
2272 || (CONVERT_EXPR_CODE_P (code
)
2273 && TREE_CODE (rhs
) == ADDR_EXPR
2274 && POINTER_TYPE_P (TREE_TYPE (lhs
))))
2276 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
2279 || decl_address_invariant_p (base
))
2280 && !stmt_references_abnormal_ssa_name (stmt
)
2281 && forward_propagate_addr_expr (lhs
, rhs
, true))
2283 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2284 release_defs (stmt
);
2285 gsi_remove (&gsi
, true);
2290 else if (code
== POINTER_PLUS_EXPR
)
2292 tree off
= gimple_assign_rhs2 (stmt
);
2293 if (TREE_CODE (off
) == INTEGER_CST
2294 && can_propagate_from (stmt
)
2295 && !simple_iv_increment_p (stmt
)
2296 /* ??? Better adjust the interface to that function
2297 instead of building new trees here. */
2298 && forward_propagate_addr_expr
2300 build1_loc (gimple_location (stmt
),
2301 ADDR_EXPR
, TREE_TYPE (rhs
),
2302 fold_build2 (MEM_REF
,
2303 TREE_TYPE (TREE_TYPE (rhs
)),
2305 fold_convert (ptr_type_node
,
2308 fwprop_invalidate_lattice (gimple_get_lhs (stmt
));
2309 release_defs (stmt
);
2310 gsi_remove (&gsi
, true);
2312 else if (is_gimple_min_invariant (rhs
))
2314 /* Make sure to fold &a[0] + off_1 here. */
2315 fold_stmt_inplace (&gsi
);
2317 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2323 else if (TREE_CODE (TREE_TYPE (lhs
)) == COMPLEX_TYPE
2324 && gimple_assign_load_p (stmt
)
2325 && !gimple_has_volatile_ops (stmt
)
2326 && (TREE_CODE (gimple_assign_rhs1 (stmt
))
2328 && !stmt_can_throw_internal (stmt
))
2330 /* Rewrite loads used only in real/imagpart extractions to
2331 component-wise loads. */
2332 use_operand_p use_p
;
2333 imm_use_iterator iter
;
2334 bool rewrite
= true;
2335 FOR_EACH_IMM_USE_FAST (use_p
, iter
, lhs
)
2337 gimple
*use_stmt
= USE_STMT (use_p
);
2338 if (is_gimple_debug (use_stmt
))
2340 if (!is_gimple_assign (use_stmt
)
2341 || (gimple_assign_rhs_code (use_stmt
) != REALPART_EXPR
2342 && gimple_assign_rhs_code (use_stmt
) != IMAGPART_EXPR
))
2351 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2353 if (is_gimple_debug (use_stmt
))
2355 if (gimple_debug_bind_p (use_stmt
))
2357 gimple_debug_bind_reset_value (use_stmt
);
2358 update_stmt (use_stmt
);
2363 tree new_rhs
= build1 (gimple_assign_rhs_code (use_stmt
),
2364 TREE_TYPE (TREE_TYPE (rhs
)),
2365 unshare_expr (rhs
));
2367 = gimple_build_assign (gimple_assign_lhs (use_stmt
),
2370 location_t loc
= gimple_location (use_stmt
);
2371 gimple_set_location (new_stmt
, loc
);
2372 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2373 unlink_stmt_vdef (use_stmt
);
2374 gsi_remove (&gsi2
, true);
2376 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
2379 release_defs (stmt
);
2380 gsi_remove (&gsi
, true);
2385 else if (code
== COMPLEX_EXPR
)
2387 /* Rewrite stores of a single-use complex build expression
2388 to component-wise stores. */
2389 use_operand_p use_p
;
2391 if (single_imm_use (lhs
, &use_p
, &use_stmt
)
2392 && gimple_store_p (use_stmt
)
2393 && !gimple_has_volatile_ops (use_stmt
)
2394 && is_gimple_assign (use_stmt
)
2395 && (TREE_CODE (gimple_assign_lhs (use_stmt
))
2398 tree use_lhs
= gimple_assign_lhs (use_stmt
);
2399 tree new_lhs
= build1 (REALPART_EXPR
,
2400 TREE_TYPE (TREE_TYPE (use_lhs
)),
2401 unshare_expr (use_lhs
));
2402 gimple
*new_stmt
= gimple_build_assign (new_lhs
, rhs
);
2403 location_t loc
= gimple_location (use_stmt
);
2404 gimple_set_location (new_stmt
, loc
);
2405 gimple_set_vuse (new_stmt
, gimple_vuse (use_stmt
));
2406 gimple_set_vdef (new_stmt
, make_ssa_name (gimple_vop (cfun
)));
2407 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt
)) = new_stmt
;
2408 gimple_set_vuse (use_stmt
, gimple_vdef (new_stmt
));
2409 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
2410 gsi_insert_before (&gsi2
, new_stmt
, GSI_SAME_STMT
);
2412 new_lhs
= build1 (IMAGPART_EXPR
,
2413 TREE_TYPE (TREE_TYPE (use_lhs
)),
2414 unshare_expr (use_lhs
));
2415 gimple_assign_set_lhs (use_stmt
, new_lhs
);
2416 gimple_assign_set_rhs1 (use_stmt
, gimple_assign_rhs2 (stmt
));
2417 update_stmt (use_stmt
);
2419 release_defs (stmt
);
2420 gsi_remove (&gsi
, true);
2429 /* Combine stmts with the stmts defining their operands.
2430 Note we update GSI within the loop as necessary. */
2431 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
2433 gimple
*stmt
= gsi_stmt (gsi
);
2434 gimple
*orig_stmt
= stmt
;
2435 bool changed
= false;
2436 bool was_noreturn
= (is_gimple_call (stmt
)
2437 && gimple_call_noreturn_p (stmt
));
2439 /* Mark stmt as potentially needing revisiting. */
2440 gimple_set_plf (stmt
, GF_PLF_1
, false);
2442 if (fold_stmt (&gsi
, fwprop_ssa_val
))
2445 stmt
= gsi_stmt (gsi
);
2446 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
))
2447 bitmap_set_bit (to_purge
, bb
->index
);
2449 && is_gimple_call (stmt
) && gimple_call_noreturn_p (stmt
))
2450 to_fixup
.safe_push (stmt
);
2451 /* Cleanup the CFG if we simplified a condition to
2453 if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
2454 if (gimple_cond_true_p (cond
)
2455 || gimple_cond_false_p (cond
))
2460 switch (gimple_code (stmt
))
2464 tree rhs1
= gimple_assign_rhs1 (stmt
);
2465 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2467 if (code
== COND_EXPR
2468 || code
== VEC_COND_EXPR
)
2470 /* In this case the entire COND_EXPR is in rhs1. */
2471 if (forward_propagate_into_cond (&gsi
))
2474 stmt
= gsi_stmt (gsi
);
2477 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
2480 did_something
= forward_propagate_into_comparison (&gsi
);
2481 if (did_something
== 2)
2483 changed
= did_something
!= 0;
2485 else if ((code
== PLUS_EXPR
2486 || code
== BIT_IOR_EXPR
2487 || code
== BIT_XOR_EXPR
)
2488 && simplify_rotate (&gsi
))
2490 else if (code
== VEC_PERM_EXPR
)
2492 int did_something
= simplify_permutation (&gsi
);
2493 if (did_something
== 2)
2495 changed
= did_something
!= 0;
2497 else if (code
== BIT_FIELD_REF
)
2498 changed
= simplify_bitfield_ref (&gsi
);
2499 else if (code
== CONSTRUCTOR
2500 && TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
2501 changed
= simplify_vector_constructor (&gsi
);
2506 changed
= simplify_gimple_switch (as_a
<gswitch
*> (stmt
));
2512 = forward_propagate_into_gimple_cond (as_a
<gcond
*> (stmt
));
2513 if (did_something
== 2)
2515 changed
= did_something
!= 0;
2521 tree callee
= gimple_call_fndecl (stmt
);
2522 if (callee
!= NULL_TREE
2523 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
2524 changed
= simplify_builtin_call (&gsi
, callee
);
2533 /* If the stmt changed then re-visit it and the statements
2534 inserted before it. */
2535 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2536 if (gimple_plf (gsi_stmt (gsi
), GF_PLF_1
))
2538 if (gsi_end_p (gsi
))
2539 gsi
= gsi_start_bb (bb
);
2545 /* Stmt no longer needs to be revisited. */
2546 gimple_set_plf (stmt
, GF_PLF_1
, true);
2548 /* Fill up the lattice. */
2549 if (gimple_assign_single_p (stmt
))
2551 tree lhs
= gimple_assign_lhs (stmt
);
2552 tree rhs
= gimple_assign_rhs1 (stmt
);
2553 if (TREE_CODE (lhs
) == SSA_NAME
)
2556 if (TREE_CODE (rhs
) == SSA_NAME
)
2557 val
= fwprop_ssa_val (rhs
);
2558 else if (is_gimple_min_invariant (rhs
))
2560 fwprop_set_lattice_val (lhs
, val
);
2571 /* Fixup stmts that became noreturn calls. This may require splitting
2572 blocks and thus isn't possible during the walk. Do this
2573 in reverse order so we don't inadvertedly remove a stmt we want to
2574 fixup by visiting a dominating now noreturn call first. */
2575 while (!to_fixup
.is_empty ())
2577 gimple
*stmt
= to_fixup
.pop ();
2578 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2580 fprintf (dump_file
, "Fixing up noreturn call ");
2581 print_gimple_stmt (dump_file
, stmt
, 0);
2582 fprintf (dump_file
, "\n");
2584 cfg_changed
|= fixup_noreturn_call (stmt
);
2587 cfg_changed
|= gimple_purge_all_dead_eh_edges (to_purge
);
2588 BITMAP_FREE (to_purge
);
2591 todoflags
|= TODO_cleanup_cfg
;
2599 make_pass_forwprop (gcc::context
*ctxt
)
2601 return new pass_forwprop (ctxt
);