* gcc.dg/store-motion-fgcse-sm.c (dg-final): Cleanup
[official-gcc.git] / gcc / tree-ssa-forwprop.c
blob43f4f2a05e0633ce5613db86b3a67777faf5f31b
1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2014 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)
9 any later version.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "stor-layout.h"
26 #include "tm_p.h"
27 #include "predict.h"
28 #include "vec.h"
29 #include "hashtab.h"
30 #include "hash-set.h"
31 #include "machmode.h"
32 #include "hard-reg-set.h"
33 #include "input.h"
34 #include "function.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "basic-block.h"
38 #include "gimple-pretty-print.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
42 #include "tree-eh.h"
43 #include "gimple-expr.h"
44 #include "is-a.h"
45 #include "gimple.h"
46 #include "gimplify.h"
47 #include "gimple-iterator.h"
48 #include "gimplify-me.h"
49 #include "gimple-ssa.h"
50 #include "tree-cfg.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
55 #include "expr.h"
56 #include "tree-dfa.h"
57 #include "tree-pass.h"
58 #include "langhooks.h"
59 #include "flags.h"
60 #include "diagnostic.h"
61 #include "expr.h"
62 #include "cfgloop.h"
63 #include "insn-codes.h"
64 #include "optabs.h"
65 #include "tree-ssa-propagate.h"
66 #include "tree-ssa-dom.h"
67 #include "builtins.h"
68 #include "tree-cfgcleanup.h"
69 #include "tree-into-ssa.h"
70 #include "cfganal.h"
72 /* This pass propagates the RHS of assignment statements into use
73 sites of the LHS of the assignment. It's basically a specialized
74 form of tree combination. It is hoped all of this can disappear
75 when we have a generalized tree combiner.
77 One class of common cases we handle is forward propagating a single use
78 variable into a COND_EXPR.
80 bb0:
81 x = a COND b;
82 if (x) goto ... else goto ...
84 Will be transformed into:
86 bb0:
87 if (a COND b) goto ... else goto ...
89 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
91 Or (assuming c1 and c2 are constants):
93 bb0:
94 x = a + c1;
95 if (x EQ/NEQ c2) goto ... else goto ...
97 Will be transformed into:
99 bb0:
100 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
102 Similarly for x = a - c1.
106 bb0:
107 x = !a
108 if (x) goto ... else goto ...
110 Will be transformed into:
112 bb0:
113 if (a == 0) goto ... else goto ...
115 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
116 For these cases, we propagate A into all, possibly more than one,
117 COND_EXPRs that use X.
121 bb0:
122 x = (typecast) a
123 if (x) goto ... else goto ...
125 Will be transformed into:
127 bb0:
128 if (a != 0) goto ... else goto ...
130 (Assuming a is an integral type and x is a boolean or x is an
131 integral and a is a boolean.)
133 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
134 For these cases, we propagate A into all, possibly more than one,
135 COND_EXPRs that use X.
137 In addition to eliminating the variable and the statement which assigns
138 a value to the variable, we may be able to later thread the jump without
139 adding insane complexity in the dominator optimizer.
141 Also note these transformations can cascade. We handle this by having
142 a worklist of COND_EXPR statements to examine. As we make a change to
143 a statement, we put it back on the worklist to examine on the next
144 iteration of the main loop.
146 A second class of propagation opportunities arises for ADDR_EXPR
147 nodes.
149 ptr = &x->y->z;
150 res = *ptr;
152 Will get turned into
154 res = x->y->z;
157 ptr = (type1*)&type2var;
158 res = *ptr
160 Will get turned into (if type1 and type2 are the same size
161 and neither have volatile on them):
162 res = VIEW_CONVERT_EXPR<type1>(type2var)
166 ptr = &x[0];
167 ptr2 = ptr + <constant>;
169 Will get turned into
171 ptr2 = &x[constant/elementsize];
175 ptr = &x[0];
176 offset = index * element_size;
177 offset_p = (pointer) offset;
178 ptr2 = ptr + offset_p
180 Will get turned into:
182 ptr2 = &x[index];
185 ssa = (int) decl
186 res = ssa & 1
188 Provided that decl has known alignment >= 2, will get turned into
190 res = 0
192 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
193 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
194 {NOT_EXPR,NEG_EXPR}.
196 This will (of course) be extended as other needs arise. */
198 static bool forward_propagate_addr_expr (tree, tree, bool);
200 /* Set to true if we delete dead edges during the optimization. */
201 static bool cfg_changed;
203 static tree rhs_to_tree (tree type, gimple stmt);
205 static bitmap to_purge;
207 /* Const-and-copy lattice. */
208 static vec<tree> lattice;
210 /* Set the lattice entry for NAME to VAL. */
211 static void
212 fwprop_set_lattice_val (tree name, tree val)
214 if (TREE_CODE (name) == SSA_NAME)
216 if (SSA_NAME_VERSION (name) >= lattice.length ())
218 lattice.reserve (num_ssa_names - lattice.length ());
219 lattice.quick_grow_cleared (num_ssa_names);
221 lattice[SSA_NAME_VERSION (name)] = val;
225 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
226 static void
227 fwprop_invalidate_lattice (tree name)
229 if (name
230 && TREE_CODE (name) == SSA_NAME
231 && SSA_NAME_VERSION (name) < lattice.length ())
232 lattice[SSA_NAME_VERSION (name)] = NULL_TREE;
236 /* Get the statement we can propagate from into NAME skipping
237 trivial copies. Returns the statement which defines the
238 propagation source or NULL_TREE if there is no such one.
239 If SINGLE_USE_ONLY is set considers only sources which have
240 a single use chain up to NAME. If SINGLE_USE_P is non-null,
241 it is set to whether the chain to NAME is a single use chain
242 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
244 static gimple
245 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
247 bool single_use = true;
249 do {
250 gimple def_stmt = SSA_NAME_DEF_STMT (name);
252 if (!has_single_use (name))
254 single_use = false;
255 if (single_use_only)
256 return NULL;
259 /* If name is defined by a PHI node or is the default def, bail out. */
260 if (!is_gimple_assign (def_stmt))
261 return NULL;
263 /* If def_stmt is a simple copy, continue looking. */
264 if (gimple_assign_rhs_code (def_stmt) == SSA_NAME)
265 name = gimple_assign_rhs1 (def_stmt);
266 else
268 if (!single_use_only && single_use_p)
269 *single_use_p = single_use;
271 return def_stmt;
273 } while (1);
276 /* Checks if the destination ssa name in DEF_STMT can be used as
277 propagation source. Returns true if so, otherwise false. */
279 static bool
280 can_propagate_from (gimple def_stmt)
282 gcc_assert (is_gimple_assign (def_stmt));
284 /* If the rhs has side-effects we cannot propagate from it. */
285 if (gimple_has_volatile_ops (def_stmt))
286 return false;
288 /* If the rhs is a load we cannot propagate from it. */
289 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
290 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
291 return false;
293 /* Constants can be always propagated. */
294 if (gimple_assign_single_p (def_stmt)
295 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
296 return true;
298 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
299 if (stmt_references_abnormal_ssa_name (def_stmt))
300 return false;
302 /* If the definition is a conversion of a pointer to a function type,
303 then we can not apply optimizations as some targets require
304 function pointers to be canonicalized and in this case this
305 optimization could eliminate a necessary canonicalization. */
306 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
308 tree rhs = gimple_assign_rhs1 (def_stmt);
309 if (POINTER_TYPE_P (TREE_TYPE (rhs))
310 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
311 return false;
314 return true;
317 /* Remove a chain of dead statements starting at the definition of
318 NAME. The chain is linked via the first operand of the defining statements.
319 If NAME was replaced in its only use then this function can be used
320 to clean up dead stmts. The function handles already released SSA
321 names gracefully.
322 Returns true if cleanup-cfg has to run. */
324 static bool
325 remove_prop_source_from_use (tree name)
327 gimple_stmt_iterator gsi;
328 gimple stmt;
329 bool cfg_changed = false;
331 do {
332 basic_block bb;
334 if (SSA_NAME_IN_FREE_LIST (name)
335 || SSA_NAME_IS_DEFAULT_DEF (name)
336 || !has_zero_uses (name))
337 return cfg_changed;
339 stmt = SSA_NAME_DEF_STMT (name);
340 if (gimple_code (stmt) == GIMPLE_PHI
341 || gimple_has_side_effects (stmt))
342 return cfg_changed;
344 bb = gimple_bb (stmt);
345 gsi = gsi_for_stmt (stmt);
346 unlink_stmt_vdef (stmt);
347 if (gsi_remove (&gsi, true))
348 bitmap_set_bit (to_purge, bb->index);
349 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
350 release_defs (stmt);
352 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
353 } while (name && TREE_CODE (name) == SSA_NAME);
355 return cfg_changed;
358 /* Return the rhs of a gassign *STMT in a form of a single tree,
359 converted to type TYPE.
361 This should disappear, but is needed so we can combine expressions and use
362 the fold() interfaces. Long term, we need to develop folding and combine
363 routines that deal with gimple exclusively . */
365 static tree
366 rhs_to_tree (tree type, gimple stmt)
368 location_t loc = gimple_location (stmt);
369 enum tree_code code = gimple_assign_rhs_code (stmt);
370 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
371 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
372 gimple_assign_rhs2 (stmt),
373 gimple_assign_rhs3 (stmt));
374 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
375 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
376 gimple_assign_rhs2 (stmt));
377 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
378 return build1 (code, type, gimple_assign_rhs1 (stmt));
379 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
380 return gimple_assign_rhs1 (stmt);
381 else
382 gcc_unreachable ();
385 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
386 the folded result in a form suitable for COND_EXPR_COND or
387 NULL_TREE, if there is no suitable simplified form. If
388 INVARIANT_ONLY is true only gimple_min_invariant results are
389 considered simplified. */
391 static tree
392 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
393 tree op0, tree op1, bool invariant_only)
395 tree t;
397 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
399 fold_defer_overflow_warnings ();
400 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
401 if (!t)
403 fold_undefer_overflow_warnings (false, NULL, 0);
404 return NULL_TREE;
407 /* Require that we got a boolean type out if we put one in. */
408 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
410 /* Canonicalize the combined condition for use in a COND_EXPR. */
411 t = canonicalize_cond_expr_cond (t);
413 /* Bail out if we required an invariant but didn't get one. */
414 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
416 fold_undefer_overflow_warnings (false, NULL, 0);
417 return NULL_TREE;
420 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
422 return t;
425 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
426 of its operand. Return a new comparison tree or NULL_TREE if there
427 were no simplifying combines. */
429 static tree
430 forward_propagate_into_comparison_1 (gimple stmt,
431 enum tree_code code, tree type,
432 tree op0, tree op1)
434 tree tmp = NULL_TREE;
435 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
436 bool single_use0_p = false, single_use1_p = false;
438 /* For comparisons use the first operand, that is likely to
439 simplify comparisons against constants. */
440 if (TREE_CODE (op0) == SSA_NAME)
442 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
443 if (def_stmt && can_propagate_from (def_stmt))
445 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
446 bool invariant_only_p = !single_use0_p;
448 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
450 /* Always combine comparisons or conversions from booleans. */
451 if (TREE_CODE (op1) == INTEGER_CST
452 && ((CONVERT_EXPR_CODE_P (def_code)
453 && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0, 0)))
454 == BOOLEAN_TYPE)
455 || TREE_CODE_CLASS (def_code) == tcc_comparison))
456 invariant_only_p = false;
458 tmp = combine_cond_expr_cond (stmt, code, type,
459 rhs0, op1, invariant_only_p);
460 if (tmp)
461 return tmp;
465 /* If that wasn't successful, try the second operand. */
466 if (TREE_CODE (op1) == SSA_NAME)
468 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
469 if (def_stmt && can_propagate_from (def_stmt))
471 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
472 tmp = combine_cond_expr_cond (stmt, code, type,
473 op0, rhs1, !single_use1_p);
474 if (tmp)
475 return tmp;
479 /* If that wasn't successful either, try both operands. */
480 if (rhs0 != NULL_TREE
481 && rhs1 != NULL_TREE)
482 tmp = combine_cond_expr_cond (stmt, code, type,
483 rhs0, rhs1,
484 !(single_use0_p && single_use1_p));
486 return tmp;
489 /* Propagate from the ssa name definition statements of the assignment
490 from a comparison at *GSI into the conditional if that simplifies it.
491 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
492 otherwise returns 0. */
494 static int
495 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
497 gimple stmt = gsi_stmt (*gsi);
498 tree tmp;
499 bool cfg_changed = false;
500 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
501 tree rhs1 = gimple_assign_rhs1 (stmt);
502 tree rhs2 = gimple_assign_rhs2 (stmt);
504 /* Combine the comparison with defining statements. */
505 tmp = forward_propagate_into_comparison_1 (stmt,
506 gimple_assign_rhs_code (stmt),
507 type, rhs1, rhs2);
508 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
510 gimple_assign_set_rhs_from_tree (gsi, tmp);
511 fold_stmt (gsi);
512 update_stmt (gsi_stmt (*gsi));
514 if (TREE_CODE (rhs1) == SSA_NAME)
515 cfg_changed |= remove_prop_source_from_use (rhs1);
516 if (TREE_CODE (rhs2) == SSA_NAME)
517 cfg_changed |= remove_prop_source_from_use (rhs2);
518 return cfg_changed ? 2 : 1;
521 return 0;
524 /* Propagate from the ssa name definition statements of COND_EXPR
525 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
526 Returns zero if no statement was changed, one if there were
527 changes and two if cfg_cleanup needs to run.
529 This must be kept in sync with forward_propagate_into_cond. */
531 static int
532 forward_propagate_into_gimple_cond (gcond *stmt)
534 tree tmp;
535 enum tree_code code = gimple_cond_code (stmt);
536 bool cfg_changed = false;
537 tree rhs1 = gimple_cond_lhs (stmt);
538 tree rhs2 = gimple_cond_rhs (stmt);
540 /* We can do tree combining on SSA_NAME and comparison expressions. */
541 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
542 return 0;
544 tmp = forward_propagate_into_comparison_1 (stmt, code,
545 boolean_type_node,
546 rhs1, rhs2);
547 if (tmp)
549 if (dump_file && tmp)
551 fprintf (dump_file, " Replaced '");
552 print_gimple_expr (dump_file, stmt, 0, 0);
553 fprintf (dump_file, "' with '");
554 print_generic_expr (dump_file, tmp, 0);
555 fprintf (dump_file, "'\n");
558 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
559 update_stmt (stmt);
561 if (TREE_CODE (rhs1) == SSA_NAME)
562 cfg_changed |= remove_prop_source_from_use (rhs1);
563 if (TREE_CODE (rhs2) == SSA_NAME)
564 cfg_changed |= remove_prop_source_from_use (rhs2);
565 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
568 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
569 if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
570 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
571 && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
572 && ((code == EQ_EXPR
573 && integer_zerop (rhs2))
574 || (code == NE_EXPR
575 && integer_onep (rhs2))))
577 basic_block bb = gimple_bb (stmt);
578 gimple_cond_set_code (stmt, NE_EXPR);
579 gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
580 EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
581 EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
582 return 1;
585 return 0;
589 /* Propagate from the ssa name definition statements of COND_EXPR
590 in the rhs of statement STMT into the conditional if that simplifies it.
591 Returns true zero if the stmt was changed. */
593 static bool
594 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
596 gimple stmt = gsi_stmt (*gsi_p);
597 tree tmp = NULL_TREE;
598 tree cond = gimple_assign_rhs1 (stmt);
599 enum tree_code code = gimple_assign_rhs_code (stmt);
601 /* We can do tree combining on SSA_NAME and comparison expressions. */
602 if (COMPARISON_CLASS_P (cond))
603 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
604 TREE_TYPE (cond),
605 TREE_OPERAND (cond, 0),
606 TREE_OPERAND (cond, 1));
607 else if (TREE_CODE (cond) == SSA_NAME)
609 enum tree_code def_code;
610 tree name = cond;
611 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
612 if (!def_stmt || !can_propagate_from (def_stmt))
613 return 0;
615 def_code = gimple_assign_rhs_code (def_stmt);
616 if (TREE_CODE_CLASS (def_code) == tcc_comparison)
617 tmp = fold_build2_loc (gimple_location (def_stmt),
618 def_code,
619 TREE_TYPE (cond),
620 gimple_assign_rhs1 (def_stmt),
621 gimple_assign_rhs2 (def_stmt));
624 if (tmp
625 && is_gimple_condexpr (tmp))
627 if (dump_file && tmp)
629 fprintf (dump_file, " Replaced '");
630 print_generic_expr (dump_file, cond, 0);
631 fprintf (dump_file, "' with '");
632 print_generic_expr (dump_file, tmp, 0);
633 fprintf (dump_file, "'\n");
636 if ((code == VEC_COND_EXPR) ? integer_all_onesp (tmp)
637 : integer_onep (tmp))
638 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
639 else if (integer_zerop (tmp))
640 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
641 else
642 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
643 stmt = gsi_stmt (*gsi_p);
644 update_stmt (stmt);
646 return true;
649 return 0;
652 /* We've just substituted an ADDR_EXPR into stmt. Update all the
653 relevant data structures to match. */
655 static void
656 tidy_after_forward_propagate_addr (gimple stmt)
658 /* We may have turned a trapping insn into a non-trapping insn. */
659 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
660 bitmap_set_bit (to_purge, gimple_bb (stmt)->index);
662 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
663 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
666 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
667 ADDR_EXPR <whatever>.
669 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
670 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
671 node or for recovery of array indexing from pointer arithmetic.
673 Return true if the propagation was successful (the propagation can
674 be not totally successful, yet things may have been changed). */
676 static bool
677 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
678 gimple_stmt_iterator *use_stmt_gsi,
679 bool single_use_p)
681 tree lhs, rhs, rhs2, array_ref;
682 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
683 enum tree_code rhs_code;
684 bool res = true;
686 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
688 lhs = gimple_assign_lhs (use_stmt);
689 rhs_code = gimple_assign_rhs_code (use_stmt);
690 rhs = gimple_assign_rhs1 (use_stmt);
692 /* Do not perform copy-propagation but recurse through copy chains. */
693 if (TREE_CODE (lhs) == SSA_NAME
694 && rhs_code == SSA_NAME)
695 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
697 /* The use statement could be a conversion. Recurse to the uses of the
698 lhs as copyprop does not copy through pointer to integer to pointer
699 conversions and FRE does not catch all cases either.
700 Treat the case of a single-use name and
701 a conversion to def_rhs type separate, though. */
702 if (TREE_CODE (lhs) == SSA_NAME
703 && CONVERT_EXPR_CODE_P (rhs_code))
705 /* If there is a point in a conversion chain where the types match
706 so we can remove a conversion re-materialize the address here
707 and stop. */
708 if (single_use_p
709 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
711 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
712 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
713 return true;
716 /* Else recurse if the conversion preserves the address value. */
717 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
718 || POINTER_TYPE_P (TREE_TYPE (lhs)))
719 && (TYPE_PRECISION (TREE_TYPE (lhs))
720 >= TYPE_PRECISION (TREE_TYPE (def_rhs))))
721 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
723 return false;
726 /* If this isn't a conversion chain from this on we only can propagate
727 into compatible pointer contexts. */
728 if (!types_compatible_p (TREE_TYPE (name), TREE_TYPE (def_rhs)))
729 return false;
731 /* Propagate through constant pointer adjustments. */
732 if (TREE_CODE (lhs) == SSA_NAME
733 && rhs_code == POINTER_PLUS_EXPR
734 && rhs == name
735 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
737 tree new_def_rhs;
738 /* As we come here with non-invariant addresses in def_rhs we need
739 to make sure we can build a valid constant offsetted address
740 for further propagation. Simply rely on fold building that
741 and check after the fact. */
742 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
743 def_rhs,
744 fold_convert (ptr_type_node,
745 gimple_assign_rhs2 (use_stmt)));
746 if (TREE_CODE (new_def_rhs) == MEM_REF
747 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
748 return false;
749 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
750 TREE_TYPE (rhs));
752 /* Recurse. If we could propagate into all uses of lhs do not
753 bother to replace into the current use but just pretend we did. */
754 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
755 && forward_propagate_addr_expr (lhs, new_def_rhs, single_use_p))
756 return true;
758 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
759 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
760 new_def_rhs);
761 else if (is_gimple_min_invariant (new_def_rhs))
762 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR, new_def_rhs);
763 else
764 return false;
765 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
766 update_stmt (use_stmt);
767 return true;
770 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
771 ADDR_EXPR will not appear on the LHS. */
772 tree *lhsp = gimple_assign_lhs_ptr (use_stmt);
773 while (handled_component_p (*lhsp))
774 lhsp = &TREE_OPERAND (*lhsp, 0);
775 lhs = *lhsp;
777 /* Now see if the LHS node is a MEM_REF using NAME. If so,
778 propagate the ADDR_EXPR into the use of NAME and fold the result. */
779 if (TREE_CODE (lhs) == MEM_REF
780 && TREE_OPERAND (lhs, 0) == name)
782 tree def_rhs_base;
783 HOST_WIDE_INT def_rhs_offset;
784 /* If the address is invariant we can always fold it. */
785 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
786 &def_rhs_offset)))
788 offset_int off = mem_ref_offset (lhs);
789 tree new_ptr;
790 off += def_rhs_offset;
791 if (TREE_CODE (def_rhs_base) == MEM_REF)
793 off += mem_ref_offset (def_rhs_base);
794 new_ptr = TREE_OPERAND (def_rhs_base, 0);
796 else
797 new_ptr = build_fold_addr_expr (def_rhs_base);
798 TREE_OPERAND (lhs, 0) = new_ptr;
799 TREE_OPERAND (lhs, 1)
800 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
801 tidy_after_forward_propagate_addr (use_stmt);
802 /* Continue propagating into the RHS if this was not the only use. */
803 if (single_use_p)
804 return true;
806 /* If the LHS is a plain dereference and the value type is the same as
807 that of the pointed-to type of the address we can put the
808 dereferenced address on the LHS preserving the original alias-type. */
809 else if (integer_zerop (TREE_OPERAND (lhs, 1))
810 && ((gimple_assign_lhs (use_stmt) == lhs
811 && useless_type_conversion_p
812 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
813 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
814 || types_compatible_p (TREE_TYPE (lhs),
815 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
816 /* Don't forward anything into clobber stmts if it would result
817 in the lhs no longer being a MEM_REF. */
818 && (!gimple_clobber_p (use_stmt)
819 || TREE_CODE (TREE_OPERAND (def_rhs, 0)) == MEM_REF))
821 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
822 tree new_offset, new_base, saved, new_lhs;
823 while (handled_component_p (*def_rhs_basep))
824 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
825 saved = *def_rhs_basep;
826 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
828 new_base = TREE_OPERAND (*def_rhs_basep, 0);
829 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)),
830 TREE_OPERAND (*def_rhs_basep, 1));
832 else
834 new_base = build_fold_addr_expr (*def_rhs_basep);
835 new_offset = TREE_OPERAND (lhs, 1);
837 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
838 new_base, new_offset);
839 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
840 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
841 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
842 new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
843 *lhsp = new_lhs;
844 TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
845 TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
846 *def_rhs_basep = saved;
847 tidy_after_forward_propagate_addr (use_stmt);
848 /* Continue propagating into the RHS if this was not the
849 only use. */
850 if (single_use_p)
851 return true;
853 else
854 /* We can have a struct assignment dereferencing our name twice.
855 Note that we didn't propagate into the lhs to not falsely
856 claim we did when propagating into the rhs. */
857 res = false;
860 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
861 nodes from the RHS. */
862 tree *rhsp = gimple_assign_rhs1_ptr (use_stmt);
863 if (TREE_CODE (*rhsp) == ADDR_EXPR)
864 rhsp = &TREE_OPERAND (*rhsp, 0);
865 while (handled_component_p (*rhsp))
866 rhsp = &TREE_OPERAND (*rhsp, 0);
867 rhs = *rhsp;
869 /* Now see if the RHS node is a MEM_REF using NAME. If so,
870 propagate the ADDR_EXPR into the use of NAME and fold the result. */
871 if (TREE_CODE (rhs) == MEM_REF
872 && TREE_OPERAND (rhs, 0) == name)
874 tree def_rhs_base;
875 HOST_WIDE_INT def_rhs_offset;
876 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
877 &def_rhs_offset)))
879 offset_int off = mem_ref_offset (rhs);
880 tree new_ptr;
881 off += def_rhs_offset;
882 if (TREE_CODE (def_rhs_base) == MEM_REF)
884 off += mem_ref_offset (def_rhs_base);
885 new_ptr = TREE_OPERAND (def_rhs_base, 0);
887 else
888 new_ptr = build_fold_addr_expr (def_rhs_base);
889 TREE_OPERAND (rhs, 0) = new_ptr;
890 TREE_OPERAND (rhs, 1)
891 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
892 fold_stmt_inplace (use_stmt_gsi);
893 tidy_after_forward_propagate_addr (use_stmt);
894 return res;
896 /* If the RHS is a plain dereference and the value type is the same as
897 that of the pointed-to type of the address we can put the
898 dereferenced address on the RHS preserving the original alias-type. */
899 else if (integer_zerop (TREE_OPERAND (rhs, 1))
900 && ((gimple_assign_rhs1 (use_stmt) == rhs
901 && useless_type_conversion_p
902 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
903 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
904 || types_compatible_p (TREE_TYPE (rhs),
905 TREE_TYPE (TREE_OPERAND (def_rhs, 0)))))
907 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
908 tree new_offset, new_base, saved, new_rhs;
909 while (handled_component_p (*def_rhs_basep))
910 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
911 saved = *def_rhs_basep;
912 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
914 new_base = TREE_OPERAND (*def_rhs_basep, 0);
915 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)),
916 TREE_OPERAND (*def_rhs_basep, 1));
918 else
920 new_base = build_fold_addr_expr (*def_rhs_basep);
921 new_offset = TREE_OPERAND (rhs, 1);
923 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
924 new_base, new_offset);
925 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
926 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
927 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
928 new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
929 *rhsp = new_rhs;
930 TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
931 TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
932 *def_rhs_basep = saved;
933 fold_stmt_inplace (use_stmt_gsi);
934 tidy_after_forward_propagate_addr (use_stmt);
935 return res;
939 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
940 is nothing to do. */
941 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
942 || gimple_assign_rhs1 (use_stmt) != name)
943 return false;
945 /* The remaining cases are all for turning pointer arithmetic into
946 array indexing. They only apply when we have the address of
947 element zero in an array. If that is not the case then there
948 is nothing to do. */
949 array_ref = TREE_OPERAND (def_rhs, 0);
950 if ((TREE_CODE (array_ref) != ARRAY_REF
951 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
952 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
953 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
954 return false;
956 rhs2 = gimple_assign_rhs2 (use_stmt);
957 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
958 if (TREE_CODE (rhs2) == INTEGER_CST)
960 tree new_rhs = build1_loc (gimple_location (use_stmt),
961 ADDR_EXPR, TREE_TYPE (def_rhs),
962 fold_build2 (MEM_REF,
963 TREE_TYPE (TREE_TYPE (def_rhs)),
964 unshare_expr (def_rhs),
965 fold_convert (ptr_type_node,
966 rhs2)));
967 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
968 use_stmt = gsi_stmt (*use_stmt_gsi);
969 update_stmt (use_stmt);
970 tidy_after_forward_propagate_addr (use_stmt);
971 return true;
974 return false;
977 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
979 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
980 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
981 node or for recovery of array indexing from pointer arithmetic.
983 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
984 the single use in the previous invocation. Pass true when calling
985 this as toplevel.
987 Returns true, if all uses have been propagated into. */
989 static bool
990 forward_propagate_addr_expr (tree name, tree rhs, bool parent_single_use_p)
992 imm_use_iterator iter;
993 gimple use_stmt;
994 bool all = true;
995 bool single_use_p = parent_single_use_p && has_single_use (name);
997 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
999 bool result;
1000 tree use_rhs;
1002 /* If the use is not in a simple assignment statement, then
1003 there is nothing we can do. */
1004 if (!is_gimple_assign (use_stmt))
1006 if (!is_gimple_debug (use_stmt))
1007 all = false;
1008 continue;
1011 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1012 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1013 single_use_p);
1014 /* If the use has moved to a different statement adjust
1015 the update machinery for the old statement too. */
1016 if (use_stmt != gsi_stmt (gsi))
1018 update_stmt (use_stmt);
1019 use_stmt = gsi_stmt (gsi);
1021 update_stmt (use_stmt);
1022 all &= result;
1024 /* Remove intermediate now unused copy and conversion chains. */
1025 use_rhs = gimple_assign_rhs1 (use_stmt);
1026 if (result
1027 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1028 && TREE_CODE (use_rhs) == SSA_NAME
1029 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1031 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1032 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt));
1033 release_defs (use_stmt);
1034 gsi_remove (&gsi, true);
1038 return all && has_zero_uses (name);
1042 /* Helper function for simplify_gimple_switch. Remove case labels that
1043 have values outside the range of the new type. */
1045 static void
1046 simplify_gimple_switch_label_vec (gswitch *stmt, tree index_type)
1048 unsigned int branch_num = gimple_switch_num_labels (stmt);
1049 auto_vec<tree> labels (branch_num);
1050 unsigned int i, len;
1052 /* Collect the existing case labels in a VEC, and preprocess it as if
1053 we are gimplifying a GENERIC SWITCH_EXPR. */
1054 for (i = 1; i < branch_num; i++)
1055 labels.quick_push (gimple_switch_label (stmt, i));
1056 preprocess_case_label_vec_for_gimple (labels, index_type, NULL);
1058 /* If any labels were removed, replace the existing case labels
1059 in the GIMPLE_SWITCH statement with the correct ones.
1060 Note that the type updates were done in-place on the case labels,
1061 so we only have to replace the case labels in the GIMPLE_SWITCH
1062 if the number of labels changed. */
1063 len = labels.length ();
1064 if (len < branch_num - 1)
1066 bitmap target_blocks;
1067 edge_iterator ei;
1068 edge e;
1070 /* Corner case: *all* case labels have been removed as being
1071 out-of-range for INDEX_TYPE. Push one label and let the
1072 CFG cleanups deal with this further. */
1073 if (len == 0)
1075 tree label, elt;
1077 label = CASE_LABEL (gimple_switch_default_label (stmt));
1078 elt = build_case_label (build_int_cst (index_type, 0), NULL, label);
1079 labels.quick_push (elt);
1080 len = 1;
1083 for (i = 0; i < labels.length (); i++)
1084 gimple_switch_set_label (stmt, i + 1, labels[i]);
1085 for (i++ ; i < branch_num; i++)
1086 gimple_switch_set_label (stmt, i, NULL_TREE);
1087 gimple_switch_set_num_labels (stmt, len + 1);
1089 /* Cleanup any edges that are now dead. */
1090 target_blocks = BITMAP_ALLOC (NULL);
1091 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
1093 tree elt = gimple_switch_label (stmt, i);
1094 basic_block target = label_to_block (CASE_LABEL (elt));
1095 bitmap_set_bit (target_blocks, target->index);
1097 for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
1099 if (! bitmap_bit_p (target_blocks, e->dest->index))
1101 remove_edge (e);
1102 cfg_changed = true;
1103 free_dominance_info (CDI_DOMINATORS);
1105 else
1106 ei_next (&ei);
1108 BITMAP_FREE (target_blocks);
1112 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1113 the condition which we may be able to optimize better. */
1115 static bool
1116 simplify_gimple_switch (gswitch *stmt)
1118 /* The optimization that we really care about is removing unnecessary
1119 casts. That will let us do much better in propagating the inferred
1120 constant at the switch target. */
1121 tree cond = gimple_switch_index (stmt);
1122 if (TREE_CODE (cond) == SSA_NAME)
1124 gimple def_stmt = SSA_NAME_DEF_STMT (cond);
1125 if (gimple_assign_cast_p (def_stmt))
1127 tree def = gimple_assign_rhs1 (def_stmt);
1128 if (TREE_CODE (def) != SSA_NAME)
1129 return false;
1131 /* If we have an extension or sign-change that preserves the
1132 values we check against then we can copy the source value into
1133 the switch. */
1134 tree ti = TREE_TYPE (def);
1135 if (INTEGRAL_TYPE_P (ti)
1136 && TYPE_PRECISION (ti) <= TYPE_PRECISION (TREE_TYPE (cond)))
1138 size_t n = gimple_switch_num_labels (stmt);
1139 tree min = NULL_TREE, max = NULL_TREE;
1140 if (n > 1)
1142 min = CASE_LOW (gimple_switch_label (stmt, 1));
1143 if (CASE_HIGH (gimple_switch_label (stmt, n - 1)))
1144 max = CASE_HIGH (gimple_switch_label (stmt, n - 1));
1145 else
1146 max = CASE_LOW (gimple_switch_label (stmt, n - 1));
1148 if ((!min || int_fits_type_p (min, ti))
1149 && (!max || int_fits_type_p (max, ti)))
1151 gimple_switch_set_index (stmt, def);
1152 simplify_gimple_switch_label_vec (stmt, ti);
1153 update_stmt (stmt);
1154 return true;
1160 return false;
1163 /* For pointers p2 and p1 return p2 - p1 if the
1164 difference is known and constant, otherwise return NULL. */
1166 static tree
1167 constant_pointer_difference (tree p1, tree p2)
1169 int i, j;
1170 #define CPD_ITERATIONS 5
1171 tree exps[2][CPD_ITERATIONS];
1172 tree offs[2][CPD_ITERATIONS];
1173 int cnt[2];
1175 for (i = 0; i < 2; i++)
1177 tree p = i ? p1 : p2;
1178 tree off = size_zero_node;
1179 gimple stmt;
1180 enum tree_code code;
1182 /* For each of p1 and p2 we need to iterate at least
1183 twice, to handle ADDR_EXPR directly in p1/p2,
1184 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1185 on definition's stmt RHS. Iterate a few extra times. */
1186 j = 0;
1189 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1190 break;
1191 if (TREE_CODE (p) == ADDR_EXPR)
1193 tree q = TREE_OPERAND (p, 0);
1194 HOST_WIDE_INT offset;
1195 tree base = get_addr_base_and_unit_offset (q, &offset);
1196 if (base)
1198 q = base;
1199 if (offset)
1200 off = size_binop (PLUS_EXPR, off, size_int (offset));
1202 if (TREE_CODE (q) == MEM_REF
1203 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1205 p = TREE_OPERAND (q, 0);
1206 off = size_binop (PLUS_EXPR, off,
1207 wide_int_to_tree (sizetype,
1208 mem_ref_offset (q)));
1210 else
1212 exps[i][j] = q;
1213 offs[i][j++] = off;
1214 break;
1217 if (TREE_CODE (p) != SSA_NAME)
1218 break;
1219 exps[i][j] = p;
1220 offs[i][j++] = off;
1221 if (j == CPD_ITERATIONS)
1222 break;
1223 stmt = SSA_NAME_DEF_STMT (p);
1224 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1225 break;
1226 code = gimple_assign_rhs_code (stmt);
1227 if (code == POINTER_PLUS_EXPR)
1229 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1230 break;
1231 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1232 p = gimple_assign_rhs1 (stmt);
1234 else if (code == ADDR_EXPR || CONVERT_EXPR_CODE_P (code))
1235 p = gimple_assign_rhs1 (stmt);
1236 else
1237 break;
1239 while (1);
1240 cnt[i] = j;
1243 for (i = 0; i < cnt[0]; i++)
1244 for (j = 0; j < cnt[1]; j++)
1245 if (exps[0][i] == exps[1][j])
1246 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1248 return NULL_TREE;
1251 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1252 Optimize
1253 memcpy (p, "abcd", 4);
1254 memset (p + 4, ' ', 3);
1255 into
1256 memcpy (p, "abcd ", 7);
1257 call if the latter can be stored by pieces during expansion. */
1259 static bool
1260 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1262 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1263 tree vuse = gimple_vuse (stmt2);
1264 if (vuse == NULL)
1265 return false;
1266 stmt1 = SSA_NAME_DEF_STMT (vuse);
1268 switch (DECL_FUNCTION_CODE (callee2))
1270 case BUILT_IN_MEMSET:
1271 if (gimple_call_num_args (stmt2) != 3
1272 || gimple_call_lhs (stmt2)
1273 || CHAR_BIT != 8
1274 || BITS_PER_UNIT != 8)
1275 break;
1276 else
1278 tree callee1;
1279 tree ptr1, src1, str1, off1, len1, lhs1;
1280 tree ptr2 = gimple_call_arg (stmt2, 0);
1281 tree val2 = gimple_call_arg (stmt2, 1);
1282 tree len2 = gimple_call_arg (stmt2, 2);
1283 tree diff, vdef, new_str_cst;
1284 gimple use_stmt;
1285 unsigned int ptr1_align;
1286 unsigned HOST_WIDE_INT src_len;
1287 char *src_buf;
1288 use_operand_p use_p;
1290 if (!tree_fits_shwi_p (val2)
1291 || !tree_fits_uhwi_p (len2))
1292 break;
1293 if (is_gimple_call (stmt1))
1295 /* If first stmt is a call, it needs to be memcpy
1296 or mempcpy, with string literal as second argument and
1297 constant length. */
1298 callee1 = gimple_call_fndecl (stmt1);
1299 if (callee1 == NULL_TREE
1300 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1301 || gimple_call_num_args (stmt1) != 3)
1302 break;
1303 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1304 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1305 break;
1306 ptr1 = gimple_call_arg (stmt1, 0);
1307 src1 = gimple_call_arg (stmt1, 1);
1308 len1 = gimple_call_arg (stmt1, 2);
1309 lhs1 = gimple_call_lhs (stmt1);
1310 if (!tree_fits_uhwi_p (len1))
1311 break;
1312 str1 = string_constant (src1, &off1);
1313 if (str1 == NULL_TREE)
1314 break;
1315 if (!tree_fits_uhwi_p (off1)
1316 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1317 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1318 - tree_to_uhwi (off1)) > 0
1319 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1320 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1321 != TYPE_MODE (char_type_node))
1322 break;
1324 else if (gimple_assign_single_p (stmt1))
1326 /* Otherwise look for length 1 memcpy optimized into
1327 assignment. */
1328 ptr1 = gimple_assign_lhs (stmt1);
1329 src1 = gimple_assign_rhs1 (stmt1);
1330 if (TREE_CODE (ptr1) != MEM_REF
1331 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1332 || !tree_fits_shwi_p (src1))
1333 break;
1334 ptr1 = build_fold_addr_expr (ptr1);
1335 callee1 = NULL_TREE;
1336 len1 = size_one_node;
1337 lhs1 = NULL_TREE;
1338 off1 = size_zero_node;
1339 str1 = NULL_TREE;
1341 else
1342 break;
1344 diff = constant_pointer_difference (ptr1, ptr2);
1345 if (diff == NULL && lhs1 != NULL)
1347 diff = constant_pointer_difference (lhs1, ptr2);
1348 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1349 && diff != NULL)
1350 diff = size_binop (PLUS_EXPR, diff,
1351 fold_convert (sizetype, len1));
1353 /* If the difference between the second and first destination pointer
1354 is not constant, or is bigger than memcpy length, bail out. */
1355 if (diff == NULL
1356 || !tree_fits_uhwi_p (diff)
1357 || tree_int_cst_lt (len1, diff))
1358 break;
1360 /* Use maximum of difference plus memset length and memcpy length
1361 as the new memcpy length, if it is too big, bail out. */
1362 src_len = tree_to_uhwi (diff);
1363 src_len += tree_to_uhwi (len2);
1364 if (src_len < tree_to_uhwi (len1))
1365 src_len = tree_to_uhwi (len1);
1366 if (src_len > 1024)
1367 break;
1369 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1370 with bigger length will return different result. */
1371 if (lhs1 != NULL_TREE
1372 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1373 && (TREE_CODE (lhs1) != SSA_NAME
1374 || !single_imm_use (lhs1, &use_p, &use_stmt)
1375 || use_stmt != stmt2))
1376 break;
1378 /* If anything reads memory in between memcpy and memset
1379 call, the modified memcpy call might change it. */
1380 vdef = gimple_vdef (stmt1);
1381 if (vdef != NULL
1382 && (!single_imm_use (vdef, &use_p, &use_stmt)
1383 || use_stmt != stmt2))
1384 break;
1386 ptr1_align = get_pointer_alignment (ptr1);
1387 /* Construct the new source string literal. */
1388 src_buf = XALLOCAVEC (char, src_len + 1);
1389 if (callee1)
1390 memcpy (src_buf,
1391 TREE_STRING_POINTER (str1) + tree_to_uhwi (off1),
1392 tree_to_uhwi (len1));
1393 else
1394 src_buf[0] = tree_to_shwi (src1);
1395 memset (src_buf + tree_to_uhwi (diff),
1396 tree_to_shwi (val2), tree_to_uhwi (len2));
1397 src_buf[src_len] = '\0';
1398 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1399 handle embedded '\0's. */
1400 if (strlen (src_buf) != src_len)
1401 break;
1402 rtl_profile_for_bb (gimple_bb (stmt2));
1403 /* If the new memcpy wouldn't be emitted by storing the literal
1404 by pieces, this optimization might enlarge .rodata too much,
1405 as commonly used string literals couldn't be shared any
1406 longer. */
1407 if (!can_store_by_pieces (src_len,
1408 builtin_strncpy_read_str,
1409 src_buf, ptr1_align, false))
1410 break;
1412 new_str_cst = build_string_literal (src_len, src_buf);
1413 if (callee1)
1415 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1416 memset call. */
1417 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1418 gimple_call_set_lhs (stmt1, NULL_TREE);
1419 gimple_call_set_arg (stmt1, 1, new_str_cst);
1420 gimple_call_set_arg (stmt1, 2,
1421 build_int_cst (TREE_TYPE (len1), src_len));
1422 update_stmt (stmt1);
1423 unlink_stmt_vdef (stmt2);
1424 gsi_remove (gsi_p, true);
1425 fwprop_invalidate_lattice (gimple_get_lhs (stmt2));
1426 release_defs (stmt2);
1427 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1429 fwprop_invalidate_lattice (lhs1);
1430 release_ssa_name (lhs1);
1432 return true;
1434 else
1436 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1437 assignment, remove STMT1 and change memset call into
1438 memcpy call. */
1439 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1441 if (!is_gimple_val (ptr1))
1442 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1443 true, GSI_SAME_STMT);
1444 gimple_call_set_fndecl (stmt2,
1445 builtin_decl_explicit (BUILT_IN_MEMCPY));
1446 gimple_call_set_arg (stmt2, 0, ptr1);
1447 gimple_call_set_arg (stmt2, 1, new_str_cst);
1448 gimple_call_set_arg (stmt2, 2,
1449 build_int_cst (TREE_TYPE (len2), src_len));
1450 unlink_stmt_vdef (stmt1);
1451 gsi_remove (&gsi, true);
1452 fwprop_invalidate_lattice (gimple_get_lhs (stmt1));
1453 release_defs (stmt1);
1454 update_stmt (stmt2);
1455 return false;
1458 break;
1459 default:
1460 break;
1462 return false;
1465 /* Given a ssa_name in NAME see if it was defined by an assignment and
1466 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1467 to the second operand on the rhs. */
1469 static inline void
1470 defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
1472 gimple def;
1473 enum tree_code code1;
1474 tree arg11;
1475 tree arg21;
1476 tree arg31;
1477 enum gimple_rhs_class grhs_class;
1479 code1 = TREE_CODE (name);
1480 arg11 = name;
1481 arg21 = NULL_TREE;
1482 grhs_class = get_gimple_rhs_class (code1);
1484 if (code1 == SSA_NAME)
1486 def = SSA_NAME_DEF_STMT (name);
1488 if (def && is_gimple_assign (def)
1489 && can_propagate_from (def))
1491 code1 = gimple_assign_rhs_code (def);
1492 arg11 = gimple_assign_rhs1 (def);
1493 arg21 = gimple_assign_rhs2 (def);
1494 arg31 = gimple_assign_rhs2 (def);
1497 else if (grhs_class == GIMPLE_TERNARY_RHS
1498 || GIMPLE_BINARY_RHS
1499 || GIMPLE_UNARY_RHS
1500 || GIMPLE_SINGLE_RHS)
1501 extract_ops_from_tree_1 (name, &code1, &arg11, &arg21, &arg31);
1503 *code = code1;
1504 *arg1 = arg11;
1505 if (arg2)
1506 *arg2 = arg21;
1507 /* Ignore arg3 currently. */
1511 /* Recognize rotation patterns. Return true if a transformation
1512 applied, otherwise return false.
1514 We are looking for X with unsigned type T with bitsize B, OP being
1515 +, | or ^, some type T2 wider than T and
1516 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1517 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1518 (X << Y) OP (X >> (B - Y))
1519 (X << (int) Y) OP (X >> (int) (B - Y))
1520 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1521 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1522 (X << Y) | (X >> ((-Y) & (B - 1)))
1523 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1524 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1525 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1527 and transform these into:
1528 X r<< CNT1
1529 X r<< Y
1531 Note, in the patterns with T2 type, the type of OP operands
1532 might be even a signed type, but should have precision B. */
1534 static bool
1535 simplify_rotate (gimple_stmt_iterator *gsi)
1537 gimple stmt = gsi_stmt (*gsi);
1538 tree arg[2], rtype, rotcnt = NULL_TREE;
1539 tree def_arg1[2], def_arg2[2];
1540 enum tree_code def_code[2];
1541 tree lhs;
1542 int i;
1543 bool swapped_p = false;
1544 gimple g;
1546 arg[0] = gimple_assign_rhs1 (stmt);
1547 arg[1] = gimple_assign_rhs2 (stmt);
1548 rtype = TREE_TYPE (arg[0]);
1550 /* Only create rotates in complete modes. Other cases are not
1551 expanded properly. */
1552 if (!INTEGRAL_TYPE_P (rtype)
1553 || TYPE_PRECISION (rtype) != GET_MODE_PRECISION (TYPE_MODE (rtype)))
1554 return false;
1556 for (i = 0; i < 2; i++)
1557 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1559 /* Look through narrowing conversions. */
1560 if (CONVERT_EXPR_CODE_P (def_code[0])
1561 && CONVERT_EXPR_CODE_P (def_code[1])
1562 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[0]))
1563 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[1]))
1564 && TYPE_PRECISION (TREE_TYPE (def_arg1[0]))
1565 == TYPE_PRECISION (TREE_TYPE (def_arg1[1]))
1566 && TYPE_PRECISION (TREE_TYPE (def_arg1[0])) > TYPE_PRECISION (rtype)
1567 && has_single_use (arg[0])
1568 && has_single_use (arg[1]))
1570 for (i = 0; i < 2; i++)
1572 arg[i] = def_arg1[i];
1573 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1577 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1578 for (i = 0; i < 2; i++)
1579 if (def_code[i] != LSHIFT_EXPR && def_code[i] != RSHIFT_EXPR)
1580 return false;
1581 else if (!has_single_use (arg[i]))
1582 return false;
1583 if (def_code[0] == def_code[1])
1584 return false;
1586 /* If we've looked through narrowing conversions before, look through
1587 widening conversions from unsigned type with the same precision
1588 as rtype here. */
1589 if (TYPE_PRECISION (TREE_TYPE (def_arg1[0])) != TYPE_PRECISION (rtype))
1590 for (i = 0; i < 2; i++)
1592 tree tem;
1593 enum tree_code code;
1594 defcodefor_name (def_arg1[i], &code, &tem, NULL);
1595 if (!CONVERT_EXPR_CODE_P (code)
1596 || !INTEGRAL_TYPE_P (TREE_TYPE (tem))
1597 || TYPE_PRECISION (TREE_TYPE (tem)) != TYPE_PRECISION (rtype))
1598 return false;
1599 def_arg1[i] = tem;
1601 /* Both shifts have to use the same first operand. */
1602 if (TREE_CODE (def_arg1[0]) != SSA_NAME || def_arg1[0] != def_arg1[1])
1603 return false;
1604 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[0])))
1605 return false;
1607 /* CNT1 + CNT2 == B case above. */
1608 if (tree_fits_uhwi_p (def_arg2[0])
1609 && tree_fits_uhwi_p (def_arg2[1])
1610 && tree_to_uhwi (def_arg2[0])
1611 + tree_to_uhwi (def_arg2[1]) == TYPE_PRECISION (rtype))
1612 rotcnt = def_arg2[0];
1613 else if (TREE_CODE (def_arg2[0]) != SSA_NAME
1614 || TREE_CODE (def_arg2[1]) != SSA_NAME)
1615 return false;
1616 else
1618 tree cdef_arg1[2], cdef_arg2[2], def_arg2_alt[2];
1619 enum tree_code cdef_code[2];
1620 /* Look through conversion of the shift count argument.
1621 The C/C++ FE cast any shift count argument to integer_type_node.
1622 The only problem might be if the shift count type maximum value
1623 is equal or smaller than number of bits in rtype. */
1624 for (i = 0; i < 2; i++)
1626 def_arg2_alt[i] = def_arg2[i];
1627 defcodefor_name (def_arg2[i], &cdef_code[i],
1628 &cdef_arg1[i], &cdef_arg2[i]);
1629 if (CONVERT_EXPR_CODE_P (cdef_code[i])
1630 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1[i]))
1631 && TYPE_PRECISION (TREE_TYPE (cdef_arg1[i]))
1632 > floor_log2 (TYPE_PRECISION (rtype))
1633 && TYPE_PRECISION (TREE_TYPE (cdef_arg1[i]))
1634 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (cdef_arg1[i]))))
1636 def_arg2_alt[i] = cdef_arg1[i];
1637 defcodefor_name (def_arg2_alt[i], &cdef_code[i],
1638 &cdef_arg1[i], &cdef_arg2[i]);
1641 for (i = 0; i < 2; i++)
1642 /* Check for one shift count being Y and the other B - Y,
1643 with optional casts. */
1644 if (cdef_code[i] == MINUS_EXPR
1645 && tree_fits_shwi_p (cdef_arg1[i])
1646 && tree_to_shwi (cdef_arg1[i]) == TYPE_PRECISION (rtype)
1647 && TREE_CODE (cdef_arg2[i]) == SSA_NAME)
1649 tree tem;
1650 enum tree_code code;
1652 if (cdef_arg2[i] == def_arg2[1 - i]
1653 || cdef_arg2[i] == def_arg2_alt[1 - i])
1655 rotcnt = cdef_arg2[i];
1656 break;
1658 defcodefor_name (cdef_arg2[i], &code, &tem, NULL);
1659 if (CONVERT_EXPR_CODE_P (code)
1660 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1661 && TYPE_PRECISION (TREE_TYPE (tem))
1662 > floor_log2 (TYPE_PRECISION (rtype))
1663 && TYPE_PRECISION (TREE_TYPE (tem))
1664 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem)))
1665 && (tem == def_arg2[1 - i]
1666 || tem == def_arg2_alt[1 - i]))
1668 rotcnt = tem;
1669 break;
1672 /* The above sequence isn't safe for Y being 0,
1673 because then one of the shifts triggers undefined behavior.
1674 This alternative is safe even for rotation count of 0.
1675 One shift count is Y and the other (-Y) & (B - 1). */
1676 else if (cdef_code[i] == BIT_AND_EXPR
1677 && tree_fits_shwi_p (cdef_arg2[i])
1678 && tree_to_shwi (cdef_arg2[i])
1679 == TYPE_PRECISION (rtype) - 1
1680 && TREE_CODE (cdef_arg1[i]) == SSA_NAME
1681 && gimple_assign_rhs_code (stmt) == BIT_IOR_EXPR)
1683 tree tem;
1684 enum tree_code code;
1686 defcodefor_name (cdef_arg1[i], &code, &tem, NULL);
1687 if (CONVERT_EXPR_CODE_P (code)
1688 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1689 && TYPE_PRECISION (TREE_TYPE (tem))
1690 > floor_log2 (TYPE_PRECISION (rtype))
1691 && TYPE_PRECISION (TREE_TYPE (tem))
1692 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem))))
1693 defcodefor_name (tem, &code, &tem, NULL);
1695 if (code == NEGATE_EXPR)
1697 if (tem == def_arg2[1 - i] || tem == def_arg2_alt[1 - i])
1699 rotcnt = tem;
1700 break;
1702 defcodefor_name (tem, &code, &tem, NULL);
1703 if (CONVERT_EXPR_CODE_P (code)
1704 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1705 && TYPE_PRECISION (TREE_TYPE (tem))
1706 > floor_log2 (TYPE_PRECISION (rtype))
1707 && TYPE_PRECISION (TREE_TYPE (tem))
1708 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem)))
1709 && (tem == def_arg2[1 - i]
1710 || tem == def_arg2_alt[1 - i]))
1712 rotcnt = tem;
1713 break;
1717 if (rotcnt == NULL_TREE)
1718 return false;
1719 swapped_p = i != 1;
1722 if (!useless_type_conversion_p (TREE_TYPE (def_arg2[0]),
1723 TREE_TYPE (rotcnt)))
1725 g = gimple_build_assign_with_ops (NOP_EXPR,
1726 make_ssa_name (TREE_TYPE (def_arg2[0]),
1727 NULL), rotcnt);
1728 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1729 rotcnt = gimple_assign_lhs (g);
1731 lhs = gimple_assign_lhs (stmt);
1732 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
1733 lhs = make_ssa_name (TREE_TYPE (def_arg1[0]), NULL);
1734 g = gimple_build_assign_with_ops (((def_code[0] == LSHIFT_EXPR) ^ swapped_p)
1735 ? LROTATE_EXPR : RROTATE_EXPR,
1736 lhs, def_arg1[0], rotcnt);
1737 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
1739 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1740 g = gimple_build_assign_with_ops (NOP_EXPR, gimple_assign_lhs (stmt),
1741 lhs);
1743 gsi_replace (gsi, g, false);
1744 return true;
1747 /* Combine an element access with a shuffle. Returns true if there were
1748 any changes made, else it returns false. */
1750 static bool
1751 simplify_bitfield_ref (gimple_stmt_iterator *gsi)
1753 gimple stmt = gsi_stmt (*gsi);
1754 gimple def_stmt;
1755 tree op, op0, op1, op2;
1756 tree elem_type;
1757 unsigned idx, n, size;
1758 enum tree_code code;
1760 op = gimple_assign_rhs1 (stmt);
1761 gcc_checking_assert (TREE_CODE (op) == BIT_FIELD_REF);
1763 op0 = TREE_OPERAND (op, 0);
1764 if (TREE_CODE (op0) != SSA_NAME
1765 || TREE_CODE (TREE_TYPE (op0)) != VECTOR_TYPE)
1766 return false;
1768 def_stmt = get_prop_source_stmt (op0, false, NULL);
1769 if (!def_stmt || !can_propagate_from (def_stmt))
1770 return false;
1772 op1 = TREE_OPERAND (op, 1);
1773 op2 = TREE_OPERAND (op, 2);
1774 code = gimple_assign_rhs_code (def_stmt);
1776 if (code == CONSTRUCTOR)
1778 tree tem = fold_ternary (BIT_FIELD_REF, TREE_TYPE (op),
1779 gimple_assign_rhs1 (def_stmt), op1, op2);
1780 if (!tem || !valid_gimple_rhs_p (tem))
1781 return false;
1782 gimple_assign_set_rhs_from_tree (gsi, tem);
1783 update_stmt (gsi_stmt (*gsi));
1784 return true;
1787 elem_type = TREE_TYPE (TREE_TYPE (op0));
1788 if (TREE_TYPE (op) != elem_type)
1789 return false;
1791 size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
1792 n = TREE_INT_CST_LOW (op1) / size;
1793 if (n != 1)
1794 return false;
1795 idx = TREE_INT_CST_LOW (op2) / size;
1797 if (code == VEC_PERM_EXPR)
1799 tree p, m, index, tem;
1800 unsigned nelts;
1801 m = gimple_assign_rhs3 (def_stmt);
1802 if (TREE_CODE (m) != VECTOR_CST)
1803 return false;
1804 nelts = VECTOR_CST_NELTS (m);
1805 idx = TREE_INT_CST_LOW (VECTOR_CST_ELT (m, idx));
1806 idx %= 2 * nelts;
1807 if (idx < nelts)
1809 p = gimple_assign_rhs1 (def_stmt);
1811 else
1813 p = gimple_assign_rhs2 (def_stmt);
1814 idx -= nelts;
1816 index = build_int_cst (TREE_TYPE (TREE_TYPE (m)), idx * size);
1817 tem = build3 (BIT_FIELD_REF, TREE_TYPE (op),
1818 unshare_expr (p), op1, index);
1819 gimple_assign_set_rhs1 (stmt, tem);
1820 fold_stmt (gsi);
1821 update_stmt (gsi_stmt (*gsi));
1822 return true;
1825 return false;
1828 /* Determine whether applying the 2 permutations (mask1 then mask2)
1829 gives back one of the input. */
1831 static int
1832 is_combined_permutation_identity (tree mask1, tree mask2)
1834 tree mask;
1835 unsigned int nelts, i, j;
1836 bool maybe_identity1 = true;
1837 bool maybe_identity2 = true;
1839 gcc_checking_assert (TREE_CODE (mask1) == VECTOR_CST
1840 && TREE_CODE (mask2) == VECTOR_CST);
1841 mask = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (mask1), mask1, mask1, mask2);
1842 gcc_assert (TREE_CODE (mask) == VECTOR_CST);
1844 nelts = VECTOR_CST_NELTS (mask);
1845 for (i = 0; i < nelts; i++)
1847 tree val = VECTOR_CST_ELT (mask, i);
1848 gcc_assert (TREE_CODE (val) == INTEGER_CST);
1849 j = TREE_INT_CST_LOW (val) & (2 * nelts - 1);
1850 if (j == i)
1851 maybe_identity2 = false;
1852 else if (j == i + nelts)
1853 maybe_identity1 = false;
1854 else
1855 return 0;
1857 return maybe_identity1 ? 1 : maybe_identity2 ? 2 : 0;
1860 /* Combine a shuffle with its arguments. Returns 1 if there were any
1861 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
1863 static int
1864 simplify_permutation (gimple_stmt_iterator *gsi)
1866 gimple stmt = gsi_stmt (*gsi);
1867 gimple def_stmt;
1868 tree op0, op1, op2, op3, arg0, arg1;
1869 enum tree_code code;
1870 bool single_use_op0 = false;
1872 gcc_checking_assert (gimple_assign_rhs_code (stmt) == VEC_PERM_EXPR);
1874 op0 = gimple_assign_rhs1 (stmt);
1875 op1 = gimple_assign_rhs2 (stmt);
1876 op2 = gimple_assign_rhs3 (stmt);
1878 if (TREE_CODE (op2) != VECTOR_CST)
1879 return 0;
1881 if (TREE_CODE (op0) == VECTOR_CST)
1883 code = VECTOR_CST;
1884 arg0 = op0;
1886 else if (TREE_CODE (op0) == SSA_NAME)
1888 def_stmt = get_prop_source_stmt (op0, false, &single_use_op0);
1889 if (!def_stmt || !can_propagate_from (def_stmt))
1890 return 0;
1892 code = gimple_assign_rhs_code (def_stmt);
1893 arg0 = gimple_assign_rhs1 (def_stmt);
1895 else
1896 return 0;
1898 /* Two consecutive shuffles. */
1899 if (code == VEC_PERM_EXPR)
1901 tree orig;
1902 int ident;
1904 if (op0 != op1)
1905 return 0;
1906 op3 = gimple_assign_rhs3 (def_stmt);
1907 if (TREE_CODE (op3) != VECTOR_CST)
1908 return 0;
1909 ident = is_combined_permutation_identity (op3, op2);
1910 if (!ident)
1911 return 0;
1912 orig = (ident == 1) ? gimple_assign_rhs1 (def_stmt)
1913 : gimple_assign_rhs2 (def_stmt);
1914 gimple_assign_set_rhs1 (stmt, unshare_expr (orig));
1915 gimple_assign_set_rhs_code (stmt, TREE_CODE (orig));
1916 gimple_set_num_ops (stmt, 2);
1917 update_stmt (stmt);
1918 return remove_prop_source_from_use (op0) ? 2 : 1;
1921 /* Shuffle of a constructor. */
1922 else if (code == CONSTRUCTOR || code == VECTOR_CST)
1924 tree opt;
1925 bool ret = false;
1926 if (op0 != op1)
1928 if (TREE_CODE (op0) == SSA_NAME && !single_use_op0)
1929 return 0;
1931 if (TREE_CODE (op1) == VECTOR_CST)
1932 arg1 = op1;
1933 else if (TREE_CODE (op1) == SSA_NAME)
1935 enum tree_code code2;
1937 gimple def_stmt2 = get_prop_source_stmt (op1, true, NULL);
1938 if (!def_stmt2 || !can_propagate_from (def_stmt2))
1939 return 0;
1941 code2 = gimple_assign_rhs_code (def_stmt2);
1942 if (code2 != CONSTRUCTOR && code2 != VECTOR_CST)
1943 return 0;
1944 arg1 = gimple_assign_rhs1 (def_stmt2);
1946 else
1947 return 0;
1949 else
1951 /* Already used twice in this statement. */
1952 if (TREE_CODE (op0) == SSA_NAME && num_imm_uses (op0) > 2)
1953 return 0;
1954 arg1 = arg0;
1956 opt = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (op0), arg0, arg1, op2);
1957 if (!opt
1958 || (TREE_CODE (opt) != CONSTRUCTOR && TREE_CODE (opt) != VECTOR_CST))
1959 return 0;
1960 gimple_assign_set_rhs_from_tree (gsi, opt);
1961 update_stmt (gsi_stmt (*gsi));
1962 if (TREE_CODE (op0) == SSA_NAME)
1963 ret = remove_prop_source_from_use (op0);
1964 if (op0 != op1 && TREE_CODE (op1) == SSA_NAME)
1965 ret |= remove_prop_source_from_use (op1);
1966 return ret ? 2 : 1;
1969 return 0;
1972 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
1974 static bool
1975 simplify_vector_constructor (gimple_stmt_iterator *gsi)
1977 gimple stmt = gsi_stmt (*gsi);
1978 gimple def_stmt;
1979 tree op, op2, orig, type, elem_type;
1980 unsigned elem_size, nelts, i;
1981 enum tree_code code;
1982 constructor_elt *elt;
1983 unsigned char *sel;
1984 bool maybe_ident;
1986 gcc_checking_assert (gimple_assign_rhs_code (stmt) == CONSTRUCTOR);
1988 op = gimple_assign_rhs1 (stmt);
1989 type = TREE_TYPE (op);
1990 gcc_checking_assert (TREE_CODE (type) == VECTOR_TYPE);
1992 nelts = TYPE_VECTOR_SUBPARTS (type);
1993 elem_type = TREE_TYPE (type);
1994 elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
1996 sel = XALLOCAVEC (unsigned char, nelts);
1997 orig = NULL;
1998 maybe_ident = true;
1999 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op), i, elt)
2001 tree ref, op1;
2003 if (i >= nelts)
2004 return false;
2006 if (TREE_CODE (elt->value) != SSA_NAME)
2007 return false;
2008 def_stmt = get_prop_source_stmt (elt->value, false, NULL);
2009 if (!def_stmt)
2010 return false;
2011 code = gimple_assign_rhs_code (def_stmt);
2012 if (code != BIT_FIELD_REF)
2013 return false;
2014 op1 = gimple_assign_rhs1 (def_stmt);
2015 ref = TREE_OPERAND (op1, 0);
2016 if (orig)
2018 if (ref != orig)
2019 return false;
2021 else
2023 if (TREE_CODE (ref) != SSA_NAME)
2024 return false;
2025 if (!useless_type_conversion_p (type, TREE_TYPE (ref)))
2026 return false;
2027 orig = ref;
2029 if (TREE_INT_CST_LOW (TREE_OPERAND (op1, 1)) != elem_size)
2030 return false;
2031 sel[i] = TREE_INT_CST_LOW (TREE_OPERAND (op1, 2)) / elem_size;
2032 if (sel[i] != i) maybe_ident = false;
2034 if (i < nelts)
2035 return false;
2037 if (maybe_ident)
2038 gimple_assign_set_rhs_from_tree (gsi, orig);
2039 else
2041 tree mask_type, *mask_elts;
2043 if (!can_vec_perm_p (TYPE_MODE (type), false, sel))
2044 return false;
2045 mask_type
2046 = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
2047 nelts);
2048 if (GET_MODE_CLASS (TYPE_MODE (mask_type)) != MODE_VECTOR_INT
2049 || GET_MODE_SIZE (TYPE_MODE (mask_type))
2050 != GET_MODE_SIZE (TYPE_MODE (type)))
2051 return false;
2052 mask_elts = XALLOCAVEC (tree, nelts);
2053 for (i = 0; i < nelts; i++)
2054 mask_elts[i] = build_int_cst (TREE_TYPE (mask_type), sel[i]);
2055 op2 = build_vector (mask_type, mask_elts);
2056 gimple_assign_set_rhs_with_ops (gsi, VEC_PERM_EXPR, orig, orig, op2);
2058 update_stmt (gsi_stmt (*gsi));
2059 return true;
2063 /* Primitive "lattice" function for gimple_simplify. */
2065 static tree
2066 fwprop_ssa_val (tree name)
2068 /* First valueize NAME. */
2069 if (TREE_CODE (name) == SSA_NAME
2070 && SSA_NAME_VERSION (name) < lattice.length ())
2072 tree val = lattice[SSA_NAME_VERSION (name)];
2073 if (val)
2074 name = val;
2076 /* We continue matching along SSA use-def edges for SSA names
2077 that are not single-use. Currently there are no patterns
2078 that would cause any issues with that. */
2079 return name;
2082 /* Main entry point for the forward propagation and statement combine
2083 optimizer. */
2085 namespace {
2087 const pass_data pass_data_forwprop =
2089 GIMPLE_PASS, /* type */
2090 "forwprop", /* name */
2091 OPTGROUP_NONE, /* optinfo_flags */
2092 TV_TREE_FORWPROP, /* tv_id */
2093 ( PROP_cfg | PROP_ssa ), /* properties_required */
2094 0, /* properties_provided */
2095 0, /* properties_destroyed */
2096 0, /* todo_flags_start */
2097 TODO_update_ssa, /* todo_flags_finish */
2100 class pass_forwprop : public gimple_opt_pass
2102 public:
2103 pass_forwprop (gcc::context *ctxt)
2104 : gimple_opt_pass (pass_data_forwprop, ctxt)
2107 /* opt_pass methods: */
2108 opt_pass * clone () { return new pass_forwprop (m_ctxt); }
2109 virtual bool gate (function *) { return flag_tree_forwprop; }
2110 virtual unsigned int execute (function *);
2112 }; // class pass_forwprop
2114 unsigned int
2115 pass_forwprop::execute (function *fun)
2117 unsigned int todoflags = 0;
2119 cfg_changed = false;
2121 /* Combine stmts with the stmts defining their operands. Do that
2122 in an order that guarantees visiting SSA defs before SSA uses. */
2123 lattice.create (num_ssa_names);
2124 lattice.quick_grow_cleared (num_ssa_names);
2125 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (fun));
2126 int postorder_num = inverted_post_order_compute (postorder);
2127 to_purge = BITMAP_ALLOC (NULL);
2128 for (int i = 0; i < postorder_num; ++i)
2130 gimple_stmt_iterator gsi;
2131 basic_block bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
2133 /* Apply forward propagation to all stmts in the basic-block.
2134 Note we update GSI within the loop as necessary. */
2135 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2137 gimple stmt = gsi_stmt (gsi);
2138 tree lhs, rhs;
2139 enum tree_code code;
2141 if (!is_gimple_assign (stmt))
2143 gsi_next (&gsi);
2144 continue;
2147 lhs = gimple_assign_lhs (stmt);
2148 rhs = gimple_assign_rhs1 (stmt);
2149 code = gimple_assign_rhs_code (stmt);
2150 if (TREE_CODE (lhs) != SSA_NAME
2151 || has_zero_uses (lhs))
2153 gsi_next (&gsi);
2154 continue;
2157 /* If this statement sets an SSA_NAME to an address,
2158 try to propagate the address into the uses of the SSA_NAME. */
2159 if (code == ADDR_EXPR
2160 /* Handle pointer conversions on invariant addresses
2161 as well, as this is valid gimple. */
2162 || (CONVERT_EXPR_CODE_P (code)
2163 && TREE_CODE (rhs) == ADDR_EXPR
2164 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2166 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2167 if ((!base
2168 || !DECL_P (base)
2169 || decl_address_invariant_p (base))
2170 && !stmt_references_abnormal_ssa_name (stmt)
2171 && forward_propagate_addr_expr (lhs, rhs, true))
2173 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2174 release_defs (stmt);
2175 gsi_remove (&gsi, true);
2177 else
2178 gsi_next (&gsi);
2180 else if (code == POINTER_PLUS_EXPR)
2182 tree off = gimple_assign_rhs2 (stmt);
2183 if (TREE_CODE (off) == INTEGER_CST
2184 && can_propagate_from (stmt)
2185 && !simple_iv_increment_p (stmt)
2186 /* ??? Better adjust the interface to that function
2187 instead of building new trees here. */
2188 && forward_propagate_addr_expr
2189 (lhs,
2190 build1_loc (gimple_location (stmt),
2191 ADDR_EXPR, TREE_TYPE (rhs),
2192 fold_build2 (MEM_REF,
2193 TREE_TYPE (TREE_TYPE (rhs)),
2194 rhs,
2195 fold_convert (ptr_type_node,
2196 off))), true))
2198 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2199 release_defs (stmt);
2200 gsi_remove (&gsi, true);
2202 else if (is_gimple_min_invariant (rhs))
2204 /* Make sure to fold &a[0] + off_1 here. */
2205 fold_stmt_inplace (&gsi);
2206 update_stmt (stmt);
2207 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2208 gsi_next (&gsi);
2210 else
2211 gsi_next (&gsi);
2213 else
2214 gsi_next (&gsi);
2217 /* Combine stmts with the stmts defining their operands.
2218 Note we update GSI within the loop as necessary. */
2219 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2221 gimple stmt = gsi_stmt (gsi);
2222 gimple orig_stmt = stmt;
2223 bool changed = false;
2225 /* Mark stmt as potentially needing revisiting. */
2226 gimple_set_plf (stmt, GF_PLF_1, false);
2228 if (fold_stmt (&gsi, fwprop_ssa_val))
2230 changed = true;
2231 stmt = gsi_stmt (gsi);
2232 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
2233 bitmap_set_bit (to_purge, bb->index);
2234 /* Cleanup the CFG if we simplified a condition to
2235 true or false. */
2236 if (gcond *cond = dyn_cast <gcond *> (stmt))
2237 if (gimple_cond_true_p (cond)
2238 || gimple_cond_false_p (cond))
2239 cfg_changed = true;
2240 update_stmt (stmt);
2243 switch (gimple_code (stmt))
2245 case GIMPLE_ASSIGN:
2247 tree rhs1 = gimple_assign_rhs1 (stmt);
2248 enum tree_code code = gimple_assign_rhs_code (stmt);
2250 if (code == COND_EXPR
2251 || code == VEC_COND_EXPR)
2253 /* In this case the entire COND_EXPR is in rhs1. */
2254 if (forward_propagate_into_cond (&gsi))
2256 changed = true;
2257 stmt = gsi_stmt (gsi);
2260 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2262 int did_something;
2263 did_something = forward_propagate_into_comparison (&gsi);
2264 if (did_something == 2)
2265 cfg_changed = true;
2266 changed = did_something != 0;
2268 else if ((code == PLUS_EXPR
2269 || code == BIT_IOR_EXPR
2270 || code == BIT_XOR_EXPR)
2271 && simplify_rotate (&gsi))
2272 changed = true;
2273 else if (code == VEC_PERM_EXPR)
2275 int did_something = simplify_permutation (&gsi);
2276 if (did_something == 2)
2277 cfg_changed = true;
2278 changed = did_something != 0;
2280 else if (code == BIT_FIELD_REF)
2281 changed = simplify_bitfield_ref (&gsi);
2282 else if (code == CONSTRUCTOR
2283 && TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
2284 changed = simplify_vector_constructor (&gsi);
2285 break;
2288 case GIMPLE_SWITCH:
2289 changed = simplify_gimple_switch (as_a <gswitch *> (stmt));
2290 break;
2292 case GIMPLE_COND:
2294 int did_something
2295 = forward_propagate_into_gimple_cond (as_a <gcond *> (stmt));
2296 if (did_something == 2)
2297 cfg_changed = true;
2298 changed = did_something != 0;
2299 break;
2302 case GIMPLE_CALL:
2304 tree callee = gimple_call_fndecl (stmt);
2305 if (callee != NULL_TREE
2306 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2307 changed = simplify_builtin_call (&gsi, callee);
2308 break;
2311 default:;
2314 if (changed)
2316 /* If the stmt changed then re-visit it and the statements
2317 inserted before it. */
2318 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
2319 if (gimple_plf (gsi_stmt (gsi), GF_PLF_1))
2320 break;
2321 if (gsi_end_p (gsi))
2322 gsi = gsi_start_bb (bb);
2323 else
2324 gsi_next (&gsi);
2326 else
2328 /* Stmt no longer needs to be revisited. */
2329 gimple_set_plf (stmt, GF_PLF_1, true);
2331 /* Fill up the lattice. */
2332 if (gimple_assign_single_p (stmt))
2334 tree lhs = gimple_assign_lhs (stmt);
2335 tree rhs = gimple_assign_rhs1 (stmt);
2336 if (TREE_CODE (lhs) == SSA_NAME)
2338 tree val = lhs;
2339 if (TREE_CODE (rhs) == SSA_NAME)
2340 val = fwprop_ssa_val (rhs);
2341 else if (is_gimple_min_invariant (rhs))
2342 val = rhs;
2343 fwprop_set_lattice_val (lhs, val);
2347 gsi_next (&gsi);
2351 free (postorder);
2352 lattice.release ();
2354 cfg_changed |= gimple_purge_all_dead_eh_edges (to_purge);
2355 BITMAP_FREE (to_purge);
2357 if (cfg_changed)
2358 todoflags |= TODO_cleanup_cfg;
2360 return todoflags;
2363 } // anon namespace
2365 gimple_opt_pass *
2366 make_pass_forwprop (gcc::context *ctxt)
2368 return new pass_forwprop (ctxt);