1/* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "rtl.h"
25#include "tree.h"
26#include "gimple.h"
27#include "cfghooks.h"
28#include "tree-pass.h"
29#include "ssa.h"
30#include "expmed.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"
36#include "tree-eh.h"
37#include "gimplify.h"
38#include "gimple-iterator.h"
39#include "gimplify-me.h"
40#include "tree-cfg.h"
41#include "expr.h"
42#include "tree-dfa.h"
43#include "tree-ssa-propagate.h"
44#include "tree-ssa-dom.h"
45#include "builtins.h"
46#include "tree-cfgcleanup.h"
47#include "cfganal.h"
48#include "optabs-tree.h"
49#include "tree-vector-builder.h"
50
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.
55
56 One class of common cases we handle is forward propagating a single use
57 variable into a COND_EXPR.
58
59 bb0:
60 x = a COND b;
61 if (x) goto ... else goto ...
62
63 Will be transformed into:
64
65 bb0:
66 if (a COND b) goto ... else goto ...
67
68 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
69
70 Or (assuming c1 and c2 are constants):
71
72 bb0:
73 x = a + c1;
74 if (x EQ/NEQ c2) goto ... else goto ...
75
76 Will be transformed into:
77
78 bb0:
79 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
80
81 Similarly for x = a - c1.
82
83 Or
84
85 bb0:
86 x = !a
87 if (x) goto ... else goto ...
88
89 Will be transformed into:
90
91 bb0:
92 if (a == 0) goto ... else goto ...
93
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.
97
98 Or
99
100 bb0:
101 x = (typecast) a
102 if (x) goto ... else goto ...
103
104 Will be transformed into:
105
106 bb0:
107 if (a != 0) goto ... else goto ...
108
109 (Assuming a is an integral type and x is a boolean or x is an
110 integral and a is a boolean.)
111
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.
115
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.
119
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.
124
125 A second class of propagation opportunities arises for ADDR_EXPR
126 nodes.
127
128 ptr = &x->y->z;
129 res = *ptr;
130
131 Will get turned into
132
133 res = x->y->z;
134
135 Or
136 ptr = (type1*)&type2var;
137 res = *ptr
138
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)
142
143 Or
144
145 ptr = &x[0];
146 ptr2 = ptr + <constant>;
147
148 Will get turned into
149
150 ptr2 = &x[constant/elementsize];
151
152 Or
153
154 ptr = &x[0];
155 offset = index * element_size;
156 offset_p = (pointer) offset;
157 ptr2 = ptr + offset_p
158
159 Will get turned into:
160
161 ptr2 = &x[index];
162
163 Or
164 ssa = (int) decl
165 res = ssa & 1
166
167 Provided that decl has known alignment >= 2, will get turned into
168
169 res = 0
170
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
173 {NOT_EXPR,NEG_EXPR}.
174
175 This will (of course) be extended as other needs arise. */
176
177static bool forward_propagate_addr_expr (tree, tree, bool);
178
179/* Set to true if we delete dead edges during the optimization. */
180static bool cfg_changed;
181
182static tree rhs_to_tree (tree type, gimple *stmt);
183
184static bitmap to_purge;
185
186/* Const-and-copy lattice. */
187static vec<tree> lattice;
188
189/* Set the lattice entry for NAME to VAL. */
190static void
191fwprop_set_lattice_val (tree name, tree val)
192{
193 if (TREE_CODE (name) == SSA_NAME)
194 {
195 if (SSA_NAME_VERSION (name) >= lattice.length ())
196 {
197 lattice.reserve (num_ssa_names - lattice.length ());
198 lattice.quick_grow_cleared (num_ssa_names);
199 }
200 lattice[SSA_NAME_VERSION (name)] = val;
201 }
202}
203
204/* Invalidate the lattice entry for NAME, done when releasing SSA names. */
205static void
206fwprop_invalidate_lattice (tree name)
207{
208 if (name
209 && TREE_CODE (name) == SSA_NAME
210 && SSA_NAME_VERSION (name) < lattice.length ())
211 lattice[SSA_NAME_VERSION (name)] = NULL_TREE;
212}
213
214
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. */
222
223static gimple *
224get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
225{
226 bool single_use = true;
227
228 do {
229 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
230
231 if (!has_single_use (name))
232 {
233 single_use = false;
234 if (single_use_only)
235 return NULL;
236 }
237
238 /* If name is defined by a PHI node or is the default def, bail out. */
239 if (!is_gimple_assign (def_stmt))
240 return NULL;
241
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);
245 else
246 {
247 if (!single_use_only && single_use_p)
248 *single_use_p = single_use;
249
250 return def_stmt;
251 }
252 } while (1);
253}
254
255/* Checks if the destination ssa name in DEF_STMT can be used as
256 propagation source. Returns true if so, otherwise false. */
257
258static bool
259can_propagate_from (gimple *def_stmt)
260{
261 gcc_assert (is_gimple_assign (def_stmt));
262
263 /* If the rhs has side-effects we cannot propagate from it. */
264 if (gimple_has_volatile_ops (def_stmt))
265 return false;
266
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)
270 return false;
271
272 /* Constants can be always propagated. */
273 if (gimple_assign_single_p (def_stmt)
274 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
275 return true;
276
277 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
278 if (stmt_references_abnormal_ssa_name (def_stmt))
279 return false;
280
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)))
286 {
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)
290 return false;
291 }
292
293 return true;
294}
295
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
300 names gracefully.
301 Returns true if cleanup-cfg has to run. */
302
303static bool
304remove_prop_source_from_use (tree name)
305{
306 gimple_stmt_iterator gsi;
307 gimple *stmt;
308 bool cfg_changed = false;
309
310 do {
311 basic_block bb;
312
313 if (SSA_NAME_IN_FREE_LIST (name)
314 || SSA_NAME_IS_DEFAULT_DEF (name)
315 || !has_zero_uses (name))
316 return cfg_changed;
317
318 stmt = SSA_NAME_DEF_STMT (name);
319 if (gimple_code (stmt) == GIMPLE_PHI
320 || gimple_has_side_effects (stmt))
321 return cfg_changed;
322
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));
329 release_defs (stmt);
330
331 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
332 } while (name && TREE_CODE (name) == SSA_NAME);
333
334 return cfg_changed;
335}
336
337/* Return the rhs of a gassign *STMT in a form of a single tree,
338 converted to type TYPE.
339
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 . */
343
344static tree
345rhs_to_tree (tree type, gimple *stmt)
346{
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);
360 else
361 gcc_unreachable ();
362}
363
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. */
369
370static tree
371combine_cond_expr_cond (gimple *stmt, enum tree_code code, tree type,
372 tree op0, tree op1, bool invariant_only)
373{
374 tree t;
375
376 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
377
378 fold_defer_overflow_warnings ();
379 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
380 if (!t)
381 {
382 fold_undefer_overflow_warnings (false, NULL, 0);
383 return NULL_TREE;
384 }
385
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));
388
389 /* Canonicalize the combined condition for use in a COND_EXPR. */
390 t = canonicalize_cond_expr_cond (t);
391
392 /* Bail out if we required an invariant but didn't get one. */
393 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
394 {
395 fold_undefer_overflow_warnings (false, NULL, 0);
396 return NULL_TREE;
397 }
398
399 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
400
401 return t;
402}
403
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. */
407
408static tree
409forward_propagate_into_comparison_1 (gimple *stmt,
410 enum tree_code code, tree type,
411 tree op0, tree op1)
412{
413 tree tmp = NULL_TREE;
414 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
415 bool single_use0_p = false, single_use1_p = false;
416
417 /* For comparisons use the first operand, that is likely to
418 simplify comparisons against constants. */
419 if (TREE_CODE (op0) == SSA_NAME)
420 {
421 gimple *def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
422 if (def_stmt && can_propagate_from (def_stmt))
423 {
424 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
425 bool invariant_only_p = !single_use0_p;
426
427 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
428
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)))
433 == BOOLEAN_TYPE)
434 || TREE_CODE_CLASS (def_code) == tcc_comparison))
435 invariant_only_p = false;
436
437 tmp = combine_cond_expr_cond (stmt, code, type,
438 rhs0, op1, invariant_only_p);
439 if (tmp)
440 return tmp;
441 }
442 }
443
444 /* If that wasn't successful, try the second operand. */
445 if (TREE_CODE (op1) == SSA_NAME)
446 {
447 gimple *def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
448 if (def_stmt && can_propagate_from (def_stmt))
449 {
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);
453 if (tmp)
454 return tmp;
455 }
456 }
457
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,
462 rhs0, rhs1,
463 !(single_use0_p && single_use1_p));
464
465 return tmp;
466}
467
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. */
472
473static int
474forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
475{
476 gimple *stmt = gsi_stmt (*gsi);
477 tree tmp;
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);
482
483 /* Combine the comparison with defining statements. */
484 tmp = forward_propagate_into_comparison_1 (stmt,
485 gimple_assign_rhs_code (stmt),
486 type, rhs1, rhs2);
487 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
488 {
489 gimple_assign_set_rhs_from_tree (gsi, tmp);
490 fold_stmt (gsi);
491 update_stmt (gsi_stmt (*gsi));
492
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;
498 }
499
500 return 0;
501}
502
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.
507
508 This must be kept in sync with forward_propagate_into_cond. */
509
510static int
511forward_propagate_into_gimple_cond (gcond *stmt)
512{
513 tree tmp;
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);
518
519 /* We can do tree combining on SSA_NAME and comparison expressions. */
520 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
521 return 0;
522
523 tmp = forward_propagate_into_comparison_1 (stmt, code,
524 boolean_type_node,
525 rhs1, rhs2);
526 if (tmp)
527 {
528 if (dump_file && tmp)
529 {
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");
535 }
536
537 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
538 update_stmt (stmt);
539
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;
545 }
546
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))
551 && ((code == EQ_EXPR
552 && integer_zerop (rhs2))
553 || (code == NE_EXPR
554 && integer_onep (rhs2))))
555 {
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);
561 return 1;
562 }
563
564 return 0;
565}
566
567
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. */
571
572static bool
573forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
574{
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);
579
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),
583 TREE_TYPE (cond),
584 TREE_OPERAND (cond, 0),
585 TREE_OPERAND (cond, 1));
586 else if (TREE_CODE (cond) == SSA_NAME)
587 {
588 enum tree_code def_code;
589 tree name = cond;
590 gimple *def_stmt = get_prop_source_stmt (name, true, NULL);
591 if (!def_stmt || !can_propagate_from (def_stmt))
592 return 0;
593
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),
597 def_code,
598 TREE_TYPE (cond),
599 gimple_assign_rhs1 (def_stmt),
600 gimple_assign_rhs2 (def_stmt));
601 }
602
603 if (tmp
604 && is_gimple_condexpr (tmp))
605 {
606 if (dump_file && tmp)
607 {
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");
613 }
614
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));
620 else
621 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
622 stmt = gsi_stmt (*gsi_p);
623 update_stmt (stmt);
624
625 return true;
626 }
627
628 return 0;
629}
630
631/* We've just substituted an ADDR_EXPR into stmt. Update all the
632 relevant data structures to match. */
633
634static void
635tidy_after_forward_propagate_addr (gimple *stmt)
636{
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);
640
641 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
642 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
643}
644
645/* NAME is a SSA_NAME representing DEF_RHS which is of the form
646 ADDR_EXPR <whatever>.
647
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.
651
652 Return true if the propagation was successful (the propagation can
653 be not totally successful, yet things may have been changed). */
654
655static bool
656forward_propagate_addr_expr_1 (tree name, tree def_rhs,
657 gimple_stmt_iterator *use_stmt_gsi,
658 bool single_use_p)
659{
660 tree lhs, rhs, rhs2, array_ref;
661 gimple *use_stmt = gsi_stmt (*use_stmt_gsi);
662 enum tree_code rhs_code;
663 bool res = true;
664
665 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
666
667 lhs = gimple_assign_lhs (use_stmt);
668 rhs_code = gimple_assign_rhs_code (use_stmt);
669 rhs = gimple_assign_rhs1 (use_stmt);
670
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);
675
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))
683 {
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
686 and stop. */
687 if (single_use_p
688 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
689 {
690 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
691 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
692 return true;
693 }
694
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);
701
702 return false;
703 }
704
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)))
708 return false;
709
710 /* Propagate through constant pointer adjustments. */
711 if (TREE_CODE (lhs) == SSA_NAME
712 && rhs_code == POINTER_PLUS_EXPR
713 && rhs == name
714 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
715 {
716 tree new_def_rhs;
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)),
722 def_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)))
727 return false;
728 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
729 TREE_TYPE (rhs));
730
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))
735 return true;
736
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),
739 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);
742 else
743 return false;
744 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
745 update_stmt (use_stmt);
746 return true;
747 }
748
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);
754 lhs = *lhsp;
755
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)
760 {
761 tree def_rhs_base;
762 HOST_WIDE_INT 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),
765 &def_rhs_offset)))
766 {
767 offset_int off = mem_ref_offset (lhs);
768 tree new_ptr;
769 off += def_rhs_offset;
770 if (TREE_CODE (def_rhs_base) == MEM_REF)
771 {
772 off += mem_ref_offset (def_rhs_base);
773 new_ptr = TREE_OPERAND (def_rhs_base, 0);
774 }
775 else
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. */
782 if (single_use_p)
783 return true;
784 }
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))
799 {
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)
806 {
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));
810 }
811 else
812 {
813 new_base = build_fold_addr_expr (*def_rhs_basep);
814 new_offset = TREE_OPERAND (lhs, 1);
815 }
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));
822 *lhsp = new_lhs;
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
828 only use. */
829 if (single_use_p)
830 return true;
831 }
832 else
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. */
836 res = false;
837 }
838
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);
846 rhs = *rhsp;
847
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)
852 {
853 tree def_rhs_base;
854 HOST_WIDE_INT def_rhs_offset;
855 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
856 &def_rhs_offset)))
857 {
858 offset_int off = mem_ref_offset (rhs);
859 tree new_ptr;
860 off += def_rhs_offset;
861 if (TREE_CODE (def_rhs_base) == MEM_REF)
862 {
863 off += mem_ref_offset (def_rhs_base);
864 new_ptr = TREE_OPERAND (def_rhs_base, 0);
865 }
866 else
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);
873 return res;
874 }
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)))))
885 {
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)
892 {
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));
896 }
897 else
898 {
899 new_base = build_fold_addr_expr (*def_rhs_basep);
900 new_offset = TREE_OPERAND (rhs, 1);
901 }
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));
908 *rhsp = new_rhs;
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);
914 return res;
915 }
916 }
917
918 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
919 is nothing to do. */
920 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
921 || gimple_assign_rhs1 (use_stmt) != name)
922 return false;
923
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
927 is nothing to do. */
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)
933 return false;
934
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)
938 {
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,
945 rhs2)));
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);
950 return true;
951 }
952
953 return false;
954}
955
956/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
957
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.
961
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
964 this as toplevel.
965
966 Returns true, if all uses have been propagated into. */
967
968static bool
969forward_propagate_addr_expr (tree name, tree rhs, bool parent_single_use_p)
970{
971 imm_use_iterator iter;
972 gimple *use_stmt;
973 bool all = true;
974 bool single_use_p = parent_single_use_p && has_single_use (name);
975
976 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
977 {
978 bool result;
979 tree use_rhs;
980
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))
984 {
985 if (!is_gimple_debug (use_stmt))
986 all = false;
987 continue;
988 }
989
990 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
991 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
992 single_use_p);
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))
996 {
997 update_stmt (use_stmt);
998 use_stmt = gsi_stmt (gsi);
999 }
1000 update_stmt (use_stmt);
1001 all &= result;
1002
1003 /* Remove intermediate now unused copy and conversion chains. */
1004 use_rhs = gimple_assign_rhs1 (use_stmt);
1005 if (result
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)))
1009 {
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);
1014 }
1015 }
1016
1017 return all && has_zero_uses (name);
1018}
1019
1020
1021/* Helper function for simplify_gimple_switch. Remove case labels that
1022 have values outside the range of the new type. */
1023
1024static void
1025simplify_gimple_switch_label_vec (gswitch *stmt, tree index_type)
1026{
1027 unsigned int branch_num = gimple_switch_num_labels (stmt);
1028 auto_vec<tree> labels (branch_num);
1029 unsigned int i, len;
1030
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);
1036
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)
1044 {
1045 bitmap target_blocks;
1046 edge_iterator ei;
1047 edge e;
1048
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. */
1052 if (len == 0)
1053 {
1054 tree label, elt;
1055
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);
1059 len = 1;
1060 }
1061
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);
1067
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++)
1071 {
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);
1075 }
1076 for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
1077 {
1078 if (! bitmap_bit_p (target_blocks, e->dest->index))
1079 {
1080 remove_edge (e);
1081 cfg_changed = true;
1082 free_dominance_info (CDI_DOMINATORS);
1083 }
1084 else
1085 ei_next (&ei);
1086 }
1087 BITMAP_FREE (target_blocks);
1088 }
1089}
1090
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. */
1093
1094static bool
1095simplify_gimple_switch (gswitch *stmt)
1096{
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)
1102 {
1103 gimple *def_stmt = SSA_NAME_DEF_STMT (cond);
1104 if (gimple_assign_cast_p (def_stmt))
1105 {
1106 tree def = gimple_assign_rhs1 (def_stmt);
1107 if (TREE_CODE (def) != SSA_NAME)
1108 return false;
1109
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
1112 the switch. */
1113 tree ti = TREE_TYPE (def);
1114 if (INTEGRAL_TYPE_P (ti)
1115 && TYPE_PRECISION (ti) <= TYPE_PRECISION (TREE_TYPE (cond)))
1116 {
1117 size_t n = gimple_switch_num_labels (stmt);
1118 tree min = NULL_TREE, max = NULL_TREE;
1119 if (n > 1)
1120 {
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));
1124 else
1125 max = CASE_LOW (gimple_switch_label (stmt, n - 1));
1126 }
1127 if ((!min || int_fits_type_p (min, ti))
1128 && (!max || int_fits_type_p (max, ti)))
1129 {
1130 gimple_switch_set_index (stmt, def);
1131 simplify_gimple_switch_label_vec (stmt, ti);
1132 update_stmt (stmt);
1133 return true;
1134 }
1135 }
1136 }
1137 }
1138
1139 return false;
1140}
1141
1142/* For pointers p2 and p1 return p2 - p1 if the
1143 difference is known and constant, otherwise return NULL. */
1144
1145static tree
1146constant_pointer_difference (tree p1, tree p2)
1147{
1148 int i, j;
1149#define CPD_ITERATIONS 5
1150 tree exps[2][CPD_ITERATIONS];
1151 tree offs[2][CPD_ITERATIONS];
1152 int cnt[2];
1153
1154 for (i = 0; i < 2; i++)
1155 {
1156 tree p = i ? p1 : p2;
1157 tree off = size_zero_node;
1158 gimple *stmt;
1159 enum tree_code code;
1160
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. */
1165 j = 0;
1166 do
1167 {
1168 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1169 break;
1170 if (TREE_CODE (p) == ADDR_EXPR)
1171 {
1172 tree q = TREE_OPERAND (p, 0);
1173 HOST_WIDE_INT offset;
1174 tree base = get_addr_base_and_unit_offset (q, &offset);
1175 if (base)
1176 {
1177 q = base;
1178 if (offset)
1179 off = size_binop (PLUS_EXPR, off, size_int (offset));
1180 }
1181 if (TREE_CODE (q) == MEM_REF
1182 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1183 {
1184 p = TREE_OPERAND (q, 0);
1185 off = size_binop (PLUS_EXPR, off,
1186 wide_int_to_tree (sizetype,
1187 mem_ref_offset (q)));
1188 }
1189 else
1190 {
1191 exps[i][j] = q;
1192 offs[i][j++] = off;
1193 break;
1194 }
1195 }
1196 if (TREE_CODE (p) != SSA_NAME)
1197 break;
1198 exps[i][j] = p;
1199 offs[i][j++] = off;
1200 if (j == CPD_ITERATIONS)
1201 break;
1202 stmt = SSA_NAME_DEF_STMT (p);
1203 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1204 break;
1205 code = gimple_assign_rhs_code (stmt);
1206 if (code == POINTER_PLUS_EXPR)
1207 {
1208 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1209 break;
1210 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1211 p = gimple_assign_rhs1 (stmt);
1212 }
1213 else if (code == ADDR_EXPR || CONVERT_EXPR_CODE_P (code))
1214 p = gimple_assign_rhs1 (stmt);
1215 else
1216 break;
1217 }
1218 while (1);
1219 cnt[i] = j;
1220 }
1221
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]);
1226
1227 return NULL_TREE;
1228}
1229
1230/* *GSI_P is a GIMPLE_CALL to a builtin function.
1231 Optimize
1232 memcpy (p, "abcd", 4);
1233 memset (p + 4, ' ', 3);
1234 into
1235 memcpy (p, "abcd ", 7);
1236 call if the latter can be stored by pieces during expansion. */
1237
1238static bool
1239simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1240{
1241 gimple *stmt1, *stmt2 = gsi_stmt (*gsi_p);
1242 tree vuse = gimple_vuse (stmt2);
1243 if (vuse == NULL)
1244 return false;
1245 stmt1 = SSA_NAME_DEF_STMT (vuse);
1246
1247 switch (DECL_FUNCTION_CODE (callee2))
1248 {
1249 case BUILT_IN_MEMSET:
1250 if (gimple_call_num_args (stmt2) != 3
1251 || gimple_call_lhs (stmt2)
1252 || CHAR_BIT != 8
1253 || BITS_PER_UNIT != 8)
1254 break;
1255 else
1256 {
1257 tree callee1;
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;
1263 gimple *use_stmt;
1264 unsigned int ptr1_align;
1265 unsigned HOST_WIDE_INT src_len;
1266 char *src_buf;
1267 use_operand_p use_p;
1268
1269 if (!tree_fits_shwi_p (val2)
1270 || !tree_fits_uhwi_p (len2)
1271 || compare_tree_int (len2, 1024) == 1)
1272 break;
1273 if (is_gimple_call (stmt1))
1274 {
1275 /* If first stmt is a call, it needs to be memcpy
1276 or mempcpy, with string literal as second argument and
1277 constant length. */
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)
1282 break;
1283 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1284 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1285 break;
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))
1291 break;
1292 str1 = string_constant (src1, &off1);
1293 if (str1 == NULL_TREE)
1294 break;
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))
1302 break;
1303 }
1304 else if (gimple_assign_single_p (stmt1))
1305 {
1306 /* Otherwise look for length 1 memcpy optimized into
1307 assignment. */
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))
1313 break;
1314 ptr1 = build_fold_addr_expr (ptr1);
1315 callee1 = NULL_TREE;
1316 len1 = size_one_node;
1317 lhs1 = NULL_TREE;
1318 off1 = size_zero_node;
1319 str1 = NULL_TREE;
1320 }
1321 else
1322 break;
1323
1324 diff = constant_pointer_difference (ptr1, ptr2);
1325 if (diff == NULL && lhs1 != NULL)
1326 {
1327 diff = constant_pointer_difference (lhs1, ptr2);
1328 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1329 && diff != NULL)
1330 diff = size_binop (PLUS_EXPR, diff,
1331 fold_convert (sizetype, len1));
1332 }
1333 /* If the difference between the second and first destination pointer
1334 is not constant, or is bigger than memcpy length, bail out. */
1335 if (diff == NULL
1336 || !tree_fits_uhwi_p (diff)
1337 || tree_int_cst_lt (len1, diff)
1338 || compare_tree_int (diff, 1024) == 1)
1339 break;
1340
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);
1347 if (src_len > 1024)
1348 break;
1349
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))
1357 break;
1358
1359 /* If anything reads memory in between memcpy and memset
1360 call, the modified memcpy call might change it. */
1361 vdef = gimple_vdef (stmt1);
1362 if (vdef != NULL
1363 && (!single_imm_use (vdef, &use_p, &use_stmt)
1364 || use_stmt != stmt2))
1365 break;
1366
1367 ptr1_align = get_pointer_alignment (ptr1);
1368 /* Construct the new source string literal. */
1369 src_buf = XALLOCAVEC (char, src_len + 1);
1370 if (callee1)
1371 memcpy (src_buf,
1372 TREE_STRING_POINTER (str1) + tree_to_uhwi (off1),
1373 tree_to_uhwi (len1));
1374 else
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)
1382 break;
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
1387 longer. */
1388 if (!can_store_by_pieces (src_len,
1389 builtin_strncpy_read_str,
1390 src_buf, ptr1_align, false))
1391 break;
1392
1393 new_str_cst = build_string_literal (src_len, src_buf);
1394 if (callee1)
1395 {
1396 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1397 memset call. */
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)
1409 {
1410 fwprop_invalidate_lattice (lhs1);
1411 release_ssa_name (lhs1);
1412 }
1413 return true;
1414 }
1415 else
1416 {
1417 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1418 assignment, remove STMT1 and change memset call into
1419 memcpy call. */
1420 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1421
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);
1436 return false;
1437 }
1438 }
1439 break;
1440 default:
1441 break;
1442 }
1443 return false;
1444}
1445
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. */
1449
1450static inline void
1451defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
1452{
1453 gimple *def;
1454 enum tree_code code1;
1455 tree arg11;
1456 tree arg21;
1457 tree arg31;
1458 enum gimple_rhs_class grhs_class;
1459
1460 code1 = TREE_CODE (name);
1461 arg11 = name;
1462 arg21 = NULL_TREE;
1463 arg31 = NULL_TREE;
1464 grhs_class = get_gimple_rhs_class (code1);
1465
1466 if (code1 == SSA_NAME)
1467 {
1468 def = SSA_NAME_DEF_STMT (name);
1469
1470 if (def && is_gimple_assign (def)
1471 && can_propagate_from (def))
1472 {
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);
1477 }
1478 }
1479 else if (grhs_class != GIMPLE_SINGLE_RHS)
1480 code1 = ERROR_MARK;
1481
1482 *code = code1;
1483 *arg1 = arg11;
1484 if (arg2)
1485 *arg2 = arg21;
1486 if (arg31)
1487 *code = ERROR_MARK;
1488}
1489
1490
1491/* Recognize rotation patterns. Return true if a transformation
1492 applied, otherwise return false.
1493
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
1498
1499 transform these into:
1500 X r<< CNT1
1501
1502 Or for:
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))))
1511
1512 transform these into:
1513 X r<< Y
1514
1515 Or for:
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))))
1521
1522 transform these into:
1523 X r<< (Y & (B - 1))
1524
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
1528 a power of 2. */
1529
1530static bool
1531simplify_rotate (gimple_stmt_iterator *gsi)
1532{
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];
1537 tree lhs;
1538 int i;
1539 bool swapped_p = false;
1540 gimple *g;
1541
1542 arg[0] = gimple_assign_rhs1 (stmt);
1543 arg[1] = gimple_assign_rhs2 (stmt);
1544 rtype = TREE_TYPE (arg[0]);
1545
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))
1550 return false;
1551
1552 for (i = 0; i < 2; i++)
1553 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1554
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]))
1565 {
1566 for (i = 0; i < 2; i++)
1567 {
1568 arg[i] = def_arg1[i];
1569 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1570 }
1571 }
1572
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)
1576 return false;
1577 else if (!has_single_use (arg[i]))
1578 return false;
1579 if (def_code[0] == def_code[1])
1580 return false;
1581
1582 /* If we've looked through narrowing conversions before, look through
1583 widening conversions from unsigned type with the same precision
1584 as rtype here. */
1585 if (TYPE_PRECISION (TREE_TYPE (def_arg1[0])) != TYPE_PRECISION (rtype))
1586 for (i = 0; i < 2; i++)
1587 {
1588 tree tem;
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))
1594 return false;
1595 def_arg1[i] = tem;
1596 }
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])))
1601 return false;
1602 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[0])))
1603 return false;
1604
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)
1613 return false;
1614 else
1615 {
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++)
1623 {
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])))
1632 {
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]);
1636 }
1637 }
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)
1645 {
1646 tree tem;
1647 enum tree_code code;
1648
1649 if (cdef_arg2[i] == def_arg2[1 - i]
1650 || cdef_arg2[i] == def_arg2_alt[1 - i])
1651 {
1652 rotcnt = cdef_arg2[i];
1653 break;
1654 }
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]))
1663 {
1664 rotcnt = tem;
1665 break;
1666 }
1667 }
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)
1680 {
1681 tree tem;
1682 enum tree_code code;
1683
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);
1691
1692 if (code == NEGATE_EXPR)
1693 {
1694 if (tem == def_arg2[1 - i] || tem == def_arg2_alt[1 - i])
1695 {
1696 rotcnt = tem;
1697 break;
1698 }
1699 tree tem2;
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)))
1706 {
1707 if (tem2 == def_arg2[1 - i]
1708 || tem2 == def_arg2_alt[1 - i])
1709 {
1710 rotcnt = tem2;
1711 break;
1712 }
1713 }
1714 else
1715 tem2 = NULL_TREE;
1716
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)
1722 {
1723 if (tem == cdef_arg1[1 - i]
1724 || tem2 == cdef_arg1[1 - i])
1725 {
1726 rotcnt = def_arg2[1 - i];
1727 break;
1728 }
1729 tree tem3;
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)))
1736 {
1737 if (tem == tem3 || tem2 == tem3)
1738 {
1739 rotcnt = def_arg2[1 - i];
1740 break;
1741 }
1742 }
1743 }
1744 }
1745 }
1746 if (rotcnt == NULL_TREE)
1747 return false;
1748 swapped_p = i != 1;
1749 }
1750
1751 if (!useless_type_conversion_p (TREE_TYPE (def_arg2[0]),
1752 TREE_TYPE (rotcnt)))
1753 {
1754 g = gimple_build_assign (make_ssa_name (TREE_TYPE (def_arg2[0])),
1755 NOP_EXPR, rotcnt);
1756 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1757 rotcnt = gimple_assign_lhs (g);
1758 }
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])))
1766 {
1767 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1768 g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, lhs);
1769 }
1770 gsi_replace (gsi, g, false);
1771 return true;
1772}
1773
1774/* Combine an element access with a shuffle. Returns true if there were
1775 any changes made, else it returns false. */
1776
1777static bool
1778simplify_bitfield_ref (gimple_stmt_iterator *gsi)
1779{
1780 gimple *stmt = gsi_stmt (*gsi);
1781 gimple *def_stmt;
1782 tree op, op0, op1, op2;
1783 tree elem_type;
1784 unsigned idx, n, size;
1785 enum tree_code code;
1786
1787 op = gimple_assign_rhs1 (stmt);
1788 gcc_checking_assert (TREE_CODE (op) == BIT_FIELD_REF);
1789
1790 op0 = TREE_OPERAND (op, 0);
1791 if (TREE_CODE (op0) != SSA_NAME
1792 || TREE_CODE (TREE_TYPE (op0)) != VECTOR_TYPE)
1793 return false;
1794
1795 def_stmt = get_prop_source_stmt (op0, false, NULL);
1796 if (!def_stmt || !can_propagate_from (def_stmt))
1797 return false;
1798
1799 op1 = TREE_OPERAND (op, 1);
1800 op2 = TREE_OPERAND (op, 2);
1801 code = gimple_assign_rhs_code (def_stmt);
1802
1803 if (code == CONSTRUCTOR)
1804 {
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))
1808 return false;
1809 gimple_assign_set_rhs_from_tree (gsi, tem);
1810 update_stmt (gsi_stmt (*gsi));
1811 return true;
1812 }
1813
1814 elem_type = TREE_TYPE (TREE_TYPE (op0));
1815 if (TREE_TYPE (op) != elem_type)
1816 return false;
1817
1818 size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
1819 n = TREE_INT_CST_LOW (op1) / size;
1820 if (n != 1)
1821 return false;
1822 idx = TREE_INT_CST_LOW (op2) / size;
1823
1824 if (code == VEC_PERM_EXPR)
1825 {
1826 tree p, m, tem;
1827 unsigned nelts;
1828 m = gimple_assign_rhs3 (def_stmt);
1829 if (TREE_CODE (m) != VECTOR_CST)
1830 return false;
1831 nelts = VECTOR_CST_NELTS (m);
1832 idx = TREE_INT_CST_LOW (VECTOR_CST_ELT (m, idx));
1833 idx %= 2 * nelts;
1834 if (idx < nelts)
1835 {
1836 p = gimple_assign_rhs1 (def_stmt);
1837 }
1838 else
1839 {
1840 p = gimple_assign_rhs2 (def_stmt);
1841 idx -= nelts;
1842 }
1843 tem = build3 (BIT_FIELD_REF, TREE_TYPE (op),
1844 unshare_expr (p), op1, bitsize_int (idx * size));
1845 gimple_assign_set_rhs1 (stmt, tem);
1846 fold_stmt (gsi);
1847 update_stmt (gsi_stmt (*gsi));
1848 return true;
1849 }
1850
1851 return false;
1852}
1853
1854/* Determine whether applying the 2 permutations (mask1 then mask2)
1855 gives back one of the input. */
1856
1857static int
1858is_combined_permutation_identity (tree mask1, tree mask2)
1859{
1860 tree mask;
1861 unsigned int nelts, i, j;
1862 bool maybe_identity1 = true;
1863 bool maybe_identity2 = true;
1864
1865 gcc_checking_assert (TREE_CODE (mask1) == VECTOR_CST
1866 && TREE_CODE (mask2) == VECTOR_CST);
1867 mask = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (mask1), mask1, mask1, mask2);
1868 gcc_assert (TREE_CODE (mask) == VECTOR_CST);
1869
1870 nelts = VECTOR_CST_NELTS (mask);
1871 for (i = 0; i < nelts; i++)
1872 {
1873 tree val = VECTOR_CST_ELT (mask, i);
1874 gcc_assert (TREE_CODE (val) == INTEGER_CST);
1875 j = TREE_INT_CST_LOW (val) & (2 * nelts - 1);
1876 if (j == i)
1877 maybe_identity2 = false;
1878 else if (j == i + nelts)
1879 maybe_identity1 = false;
1880 else
1881 return 0;
1882 }
1883 return maybe_identity1 ? 1 : maybe_identity2 ? 2 : 0;
1884}
1885
1886/* Combine a shuffle with its arguments. Returns 1 if there were any
1887 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
1888
1889static int
1890simplify_permutation (gimple_stmt_iterator *gsi)
1891{
1892 gimple *stmt = gsi_stmt (*gsi);
1893 gimple *def_stmt;
1894 tree op0, op1, op2, op3, arg0, arg1;
1895 enum tree_code code;
1896 bool single_use_op0 = false;
1897
1898 gcc_checking_assert (gimple_assign_rhs_code (stmt) == VEC_PERM_EXPR);
1899
1900 op0 = gimple_assign_rhs1 (stmt);
1901 op1 = gimple_assign_rhs2 (stmt);
1902 op2 = gimple_assign_rhs3 (stmt);
1903
1904 if (TREE_CODE (op2) != VECTOR_CST)
1905 return 0;
1906
1907 if (TREE_CODE (op0) == VECTOR_CST)
1908 {
1909 code = VECTOR_CST;
1910 arg0 = op0;
1911 }
1912 else if (TREE_CODE (op0) == SSA_NAME)
1913 {
1914 def_stmt = get_prop_source_stmt (op0, false, &single_use_op0);
1915 if (!def_stmt || !can_propagate_from (def_stmt))
1916 return 0;
1917
1918 code = gimple_assign_rhs_code (def_stmt);
1919 arg0 = gimple_assign_rhs1 (def_stmt);
1920 }
1921 else
1922 return 0;
1923
1924 /* Two consecutive shuffles. */
1925 if (code == VEC_PERM_EXPR)
1926 {
1927 tree orig;
1928 int ident;
1929
1930 if (op0 != op1)
1931 return 0;
1932 op3 = gimple_assign_rhs3 (def_stmt);
1933 if (TREE_CODE (op3) != VECTOR_CST)
1934 return 0;
1935 ident = is_combined_permutation_identity (op3, op2);
1936 if (!ident)
1937 return 0;
1938 orig = (ident == 1) ? gimple_assign_rhs1 (def_stmt)
1939 : gimple_assign_rhs2 (def_stmt);
1940 gimple_assign_set_rhs1 (stmt, unshare_expr (orig));
1941 gimple_assign_set_rhs_code (stmt, TREE_CODE (orig));
1942 gimple_set_num_ops (stmt, 2);
1943 update_stmt (stmt);
1944 return remove_prop_source_from_use (op0) ? 2 : 1;
1945 }
1946
1947 /* Shuffle of a constructor. */
1948 else if (code == CONSTRUCTOR || code == VECTOR_CST)
1949 {
1950 tree opt;
1951 bool ret = false;
1952 if (op0 != op1)
1953 {
1954 if (TREE_CODE (op0) == SSA_NAME && !single_use_op0)
1955 return 0;
1956
1957 if (TREE_CODE (op1) == VECTOR_CST)
1958 arg1 = op1;
1959 else if (TREE_CODE (op1) == SSA_NAME)
1960 {
1961 enum tree_code code2;
1962
1963 gimple *def_stmt2 = get_prop_source_stmt (op1, true, NULL);
1964 if (!def_stmt2 || !can_propagate_from (def_stmt2))
1965 return 0;
1966
1967 code2 = gimple_assign_rhs_code (def_stmt2);
1968 if (code2 != CONSTRUCTOR && code2 != VECTOR_CST)
1969 return 0;
1970 arg1 = gimple_assign_rhs1 (def_stmt2);
1971 }
1972 else
1973 return 0;
1974 }
1975 else
1976 {
1977 /* Already used twice in this statement. */
1978 if (TREE_CODE (op0) == SSA_NAME && num_imm_uses (op0) > 2)
1979 return 0;
1980 arg1 = arg0;
1981 }
1982 opt = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (op0), arg0, arg1, op2);
1983 if (!opt
1984 || (TREE_CODE (opt) != CONSTRUCTOR && TREE_CODE (opt) != VECTOR_CST))
1985 return 0;
1986 gimple_assign_set_rhs_from_tree (gsi, opt);
1987 update_stmt (gsi_stmt (*gsi));
1988 if (TREE_CODE (op0) == SSA_NAME)
1989 ret = remove_prop_source_from_use (op0);
1990 if (op0 != op1 && TREE_CODE (op1) == SSA_NAME)
1991 ret |= remove_prop_source_from_use (op1);
1992 return ret ? 2 : 1;
1993 }
1994
1995 return 0;
1996}
1997
1998/* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
1999
2000static bool
2001simplify_vector_constructor (gimple_stmt_iterator *gsi)
2002{
2003 gimple *stmt = gsi_stmt (*gsi);
2004 gimple *def_stmt;
2005 tree op, op2, orig, type, elem_type;
2006 unsigned elem_size, nelts, i;
2007 enum tree_code code, conv_code;
2008 constructor_elt *elt;
2009 bool maybe_ident;
2010
2011 gcc_checking_assert (gimple_assign_rhs_code (stmt) == CONSTRUCTOR);
2012
2013 op = gimple_assign_rhs1 (stmt);
2014 type = TREE_TYPE (op);
2015 gcc_checking_assert (TREE_CODE (type) == VECTOR_TYPE);
2016
2017 nelts = TYPE_VECTOR_SUBPARTS (type);
2018 elem_type = TREE_TYPE (type);
2019 elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2020
2021 auto_vec_perm_indices sel (nelts);
2022 orig = NULL;
2023 conv_code = ERROR_MARK;
2024 maybe_ident = true;
2025 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op), i, elt)
2026 {
2027 tree ref, op1;
2028
2029 if (i >= nelts)
2030 return false;
2031
2032 if (TREE_CODE (elt->value) != SSA_NAME)
2033 return false;
2034 def_stmt = get_prop_source_stmt (elt->value, false, NULL);
2035 if (!def_stmt)
2036 return false;
2037 code = gimple_assign_rhs_code (def_stmt);
2038 if (code == FLOAT_EXPR
2039 || code == FIX_TRUNC_EXPR)
2040 {
2041 op1 = gimple_assign_rhs1 (def_stmt);
2042 if (conv_code == ERROR_MARK)
2043 {
2044 if (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (elt->value)))
2045 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op1))))
2046 return false;
2047 conv_code = code;
2048 }
2049 else if (conv_code != code)
2050 return false;
2051 if (TREE_CODE (op1) != SSA_NAME)
2052 return false;
2053 def_stmt = SSA_NAME_DEF_STMT (op1);
2054 if (! is_gimple_assign (def_stmt))
2055 return false;
2056 code = gimple_assign_rhs_code (def_stmt);
2057 }
2058 if (code != BIT_FIELD_REF)
2059 return false;
2060 op1 = gimple_assign_rhs1 (def_stmt);
2061 ref = TREE_OPERAND (op1, 0);
2062 if (orig)
2063 {
2064 if (ref != orig)
2065 return false;
2066 }
2067 else
2068 {
2069 if (TREE_CODE (ref) != SSA_NAME)
2070 return false;
2071 if (! VECTOR_TYPE_P (TREE_TYPE (ref))
2072 || ! useless_type_conversion_p (TREE_TYPE (op1),
2073 TREE_TYPE (TREE_TYPE (ref))))
2074 return false;
2075 orig = ref;
2076 }
2077 if (TREE_INT_CST_LOW (TREE_OPERAND (op1, 1)) != elem_size)
2078 return false;
2079 unsigned int elt = TREE_INT_CST_LOW (TREE_OPERAND (op1, 2)) / elem_size;
2080 if (elt != i)
2081 maybe_ident = false;
2082 sel.quick_push (elt);
2083 }
2084 if (i < nelts)
2085 return false;
2086
2087 if (! VECTOR_TYPE_P (TREE_TYPE (orig))
2088 || (TYPE_VECTOR_SUBPARTS (type)
2089 != TYPE_VECTOR_SUBPARTS (TREE_TYPE (orig))))
2090 return false;
2091
2092 tree tem;
2093 if (conv_code != ERROR_MARK
2094 && (! supportable_convert_operation (conv_code, type, TREE_TYPE (orig),
2095 &tem, &conv_code)
2096 || conv_code == CALL_EXPR))
2097 return false;
2098
2099 if (maybe_ident)
2100 {
2101 if (conv_code == ERROR_MARK)
2102 gimple_assign_set_rhs_from_tree (gsi, orig);
2103 else
2104 gimple_assign_set_rhs_with_ops (gsi, conv_code, orig,
2105 NULL_TREE, NULL_TREE);
2106 }
2107 else
2108 {
2109 tree mask_type;
2110
2111 if (!can_vec_perm_p (TYPE_MODE (type), false, &sel))
2112 return false;
2113 mask_type
2114 = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
2115 nelts);
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)))
2119 return false;
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);
2126 else
2127 {
2128 gimple *perm
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);
2135 }
2136 }
2137 update_stmt (gsi_stmt (*gsi));
2138 return true;
2139}
2140
2141
2142/* Primitive "lattice" function for gimple_simplify. */
2143
2144static tree
2145fwprop_ssa_val (tree name)
2146{
2147 /* First valueize NAME. */
2148 if (TREE_CODE (name) == SSA_NAME
2149 && SSA_NAME_VERSION (name) < lattice.length ())
2150 {
2151 tree val = lattice[SSA_NAME_VERSION (name)];
2152 if (val)
2153 name = val;
2154 }
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. */
2158 return name;
2159}
2160
2161/* Main entry point for the forward propagation and statement combine
2162 optimizer. */
2163
2164namespace {
2165
2166const pass_data pass_data_forwprop =
2167{
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 */
2177};
2178
2179class pass_forwprop : public gimple_opt_pass
2180{
2181public:
2182 pass_forwprop (gcc::context *ctxt)
2183 : gimple_opt_pass (pass_data_forwprop, ctxt)
2184 {}
2185
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 *);
2190
2191}; // class pass_forwprop
2192
2193unsigned int
2194pass_forwprop::execute (function *fun)
2195{
2196 unsigned int todoflags = 0;
2197
2198 cfg_changed = false;
2199
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,
2206 postorder, false);
2207 auto_vec<gimple *, 4> to_fixup;
2208 to_purge = BITMAP_ALLOC (NULL);
2209 for (int i = 0; i < postorder_num; ++i)
2210 {
2211 gimple_stmt_iterator gsi;
2212 basic_block bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
2213
2214 /* Propagate into PHIs and record degenerate ones in the lattice. */
2215 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
2216 gsi_next (&si))
2217 {
2218 gphi *phi = si.phi ();
2219 tree res = gimple_phi_result (phi);
2220 if (virtual_operand_p (res))
2221 continue;
2222
2223 use_operand_p use_p;
2224 ssa_op_iter it;
2225 tree first = NULL_TREE;
2226 bool all_same = true;
2227 FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
2228 {
2229 tree use = USE_FROM_PTR (use_p);
2230 tree tem = fwprop_ssa_val (use);
2231 if (! first)
2232 first = tem;
2233 else if (! operand_equal_p (first, tem, 0))
2234 all_same = false;
2235 if (tem != use
2236 && may_propagate_copy (use, tem))
2237 propagate_value (use_p, tem);
2238 }
2239 if (all_same)
2240 fwprop_set_lattice_val (res, first);
2241 }
2242
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); )
2246 {
2247 gimple *stmt = gsi_stmt (gsi);
2248 tree lhs, rhs;
2249 enum tree_code code;
2250
2251 if (!is_gimple_assign (stmt))
2252 {
2253 gsi_next (&gsi);
2254 continue;
2255 }
2256
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))
2262 {
2263 gsi_next (&gsi);
2264 continue;
2265 }
2266
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))))
2275 {
2276 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2277 if ((!base
2278 || !DECL_P (base)
2279 || decl_address_invariant_p (base))
2280 && !stmt_references_abnormal_ssa_name (stmt)
2281 && forward_propagate_addr_expr (lhs, rhs, true))
2282 {
2283 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2284 release_defs (stmt);
2285 gsi_remove (&gsi, true);
2286 }
2287 else
2288 gsi_next (&gsi);
2289 }
2290 else if (code == POINTER_PLUS_EXPR)
2291 {
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
2299 (lhs,
2300 build1_loc (gimple_location (stmt),
2301 ADDR_EXPR, TREE_TYPE (rhs),
2302 fold_build2 (MEM_REF,
2303 TREE_TYPE (TREE_TYPE (rhs)),
2304 rhs,
2305 fold_convert (ptr_type_node,
2306 off))), true))
2307 {
2308 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2309 release_defs (stmt);
2310 gsi_remove (&gsi, true);
2311 }
2312 else if (is_gimple_min_invariant (rhs))
2313 {
2314 /* Make sure to fold &a[0] + off_1 here. */
2315 fold_stmt_inplace (&gsi);
2316 update_stmt (stmt);
2317 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2318 gsi_next (&gsi);
2319 }
2320 else
2321 gsi_next (&gsi);
2322 }
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))
2327 != TARGET_MEM_REF)
2328 && !stmt_can_throw_internal (stmt))
2329 {
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)
2336 {
2337 gimple *use_stmt = USE_STMT (use_p);
2338 if (is_gimple_debug (use_stmt))
2339 continue;
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))
2343 {
2344 rewrite = false;
2345 break;
2346 }
2347 }
2348 if (rewrite)
2349 {
2350 gimple *use_stmt;
2351 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2352 {
2353 if (is_gimple_debug (use_stmt))
2354 {
2355 if (gimple_debug_bind_p (use_stmt))
2356 {
2357 gimple_debug_bind_reset_value (use_stmt);
2358 update_stmt (use_stmt);
2359 }
2360 continue;
2361 }
2362
2363 tree new_rhs = build1 (gimple_assign_rhs_code (use_stmt),
2364 TREE_TYPE (TREE_TYPE (rhs)),
2365 unshare_expr (rhs));
2366 gimple *new_stmt
2367 = gimple_build_assign (gimple_assign_lhs (use_stmt),
2368 new_rhs);
2369
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);
2375
2376 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
2377 }
2378
2379 release_defs (stmt);
2380 gsi_remove (&gsi, true);
2381 }
2382 else
2383 gsi_next (&gsi);
2384 }
2385 else if (code == COMPLEX_EXPR)
2386 {
2387 /* Rewrite stores of a single-use complex build expression
2388 to component-wise stores. */
2389 use_operand_p use_p;
2390 gimple *use_stmt;
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))
2396 != TARGET_MEM_REF))
2397 {
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);
2411
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);
2418
2419 release_defs (stmt);
2420 gsi_remove (&gsi, true);
2421 }
2422 else
2423 gsi_next (&gsi);
2424 }
2425 else
2426 gsi_next (&gsi);
2427 }
2428
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);)
2432 {
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));
2438
2439 /* Mark stmt as potentially needing revisiting. */
2440 gimple_set_plf (stmt, GF_PLF_1, false);
2441
2442 if (fold_stmt (&gsi, fwprop_ssa_val))
2443 {
2444 changed = true;
2445 stmt = gsi_stmt (gsi);
2446 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
2447 bitmap_set_bit (to_purge, bb->index);
2448 if (!was_noreturn
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
2452 true or false. */
2453 if (gcond *cond = dyn_cast <gcond *> (stmt))
2454 if (gimple_cond_true_p (cond)
2455 || gimple_cond_false_p (cond))
2456 cfg_changed = true;
2457 update_stmt (stmt);
2458 }
2459
2460 switch (gimple_code (stmt))
2461 {
2462 case GIMPLE_ASSIGN:
2463 {
2464 tree rhs1 = gimple_assign_rhs1 (stmt);
2465 enum tree_code code = gimple_assign_rhs_code (stmt);
2466
2467 if (code == COND_EXPR
2468 || code == VEC_COND_EXPR)
2469 {
2470 /* In this case the entire COND_EXPR is in rhs1. */
2471 if (forward_propagate_into_cond (&gsi))
2472 {
2473 changed = true;
2474 stmt = gsi_stmt (gsi);
2475 }
2476 }
2477 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2478 {
2479 int did_something;
2480 did_something = forward_propagate_into_comparison (&gsi);
2481 if (did_something == 2)
2482 cfg_changed = true;
2483 changed = did_something != 0;
2484 }
2485 else if ((code == PLUS_EXPR
2486 || code == BIT_IOR_EXPR
2487 || code == BIT_XOR_EXPR)
2488 && simplify_rotate (&gsi))
2489 changed = true;
2490 else if (code == VEC_PERM_EXPR)
2491 {
2492 int did_something = simplify_permutation (&gsi);
2493 if (did_something == 2)
2494 cfg_changed = true;
2495 changed = did_something != 0;
2496 }
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);
2502 break;
2503 }
2504
2505 case GIMPLE_SWITCH:
2506 changed = simplify_gimple_switch (as_a <gswitch *> (stmt));
2507 break;
2508
2509 case GIMPLE_COND:
2510 {
2511 int did_something
2512 = forward_propagate_into_gimple_cond (as_a <gcond *> (stmt));
2513 if (did_something == 2)
2514 cfg_changed = true;
2515 changed = did_something != 0;
2516 break;
2517 }
2518
2519 case GIMPLE_CALL:
2520 {
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);
2525 break;
2526 }
2527
2528 default:;
2529 }
2530
2531 if (changed)
2532 {
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))
2537 break;
2538 if (gsi_end_p (gsi))
2539 gsi = gsi_start_bb (bb);
2540 else
2541 gsi_next (&gsi);
2542 }
2543 else
2544 {
2545 /* Stmt no longer needs to be revisited. */
2546 gimple_set_plf (stmt, GF_PLF_1, true);
2547
2548 /* Fill up the lattice. */
2549 if (gimple_assign_single_p (stmt))
2550 {
2551 tree lhs = gimple_assign_lhs (stmt);
2552 tree rhs = gimple_assign_rhs1 (stmt);
2553 if (TREE_CODE (lhs) == SSA_NAME)
2554 {
2555 tree val = lhs;
2556 if (TREE_CODE (rhs) == SSA_NAME)
2557 val = fwprop_ssa_val (rhs);
2558 else if (is_gimple_min_invariant (rhs))
2559 val = rhs;
2560 fwprop_set_lattice_val (lhs, val);
2561 }
2562 }
2563
2564 gsi_next (&gsi);
2565 }
2566 }
2567 }
2568 free (postorder);
2569 lattice.release ();
2570
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 ())
2576 {
2577 gimple *stmt = to_fixup.pop ();
2578 if (dump_file && dump_flags & TDF_DETAILS)
2579 {
2580 fprintf (dump_file, "Fixing up noreturn call ");
2581 print_gimple_stmt (dump_file, stmt, 0);
2582 fprintf (dump_file, "\n");
2583 }
2584 cfg_changed |= fixup_noreturn_call (stmt);
2585 }
2586
2587 cfg_changed |= gimple_purge_all_dead_eh_edges (to_purge);
2588 BITMAP_FREE (to_purge);
2589
2590 if (cfg_changed)
2591 todoflags |= TODO_cleanup_cfg;
2592
2593 return todoflags;
2594}
2595
2596} // anon namespace
2597
2598gimple_opt_pass *
2599make_pass_forwprop (gcc::context *ctxt)
2600{
2601 return new pass_forwprop (ctxt);
2602}
2603