1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2022 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
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 #include "vec-perm-indices.h"
51 #include "internal-fn.h"
52 #include "cgraph.h"
53 #include "tree-ssa.h"
54 #include "gimple-range.h"
55
56 /* This pass propagates the RHS of assignment statements into use
57 sites of the LHS of the assignment. It's basically a specialized
58 form of tree combination. It is hoped all of this can disappear
59 when we have a generalized tree combiner.
60
61 One class of common cases we handle is forward propagating a single use
62 variable into a COND_EXPR.
63
64 bb0:
65 x = a COND b;
66 if (x) goto ... else goto ...
67
68 Will be transformed into:
69
70 bb0:
71 if (a COND b) goto ... else goto ...
72
73 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
74
75 Or (assuming c1 and c2 are constants):
76
77 bb0:
78 x = a + c1;
79 if (x EQ/NEQ c2) goto ... else goto ...
80
81 Will be transformed into:
82
83 bb0:
84 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
85
86 Similarly for x = a - c1.
87
88 Or
89
90 bb0:
91 x = !a
92 if (x) goto ... else goto ...
93
94 Will be transformed into:
95
96 bb0:
97 if (a == 0) goto ... else goto ...
98
99 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
100 For these cases, we propagate A into all, possibly more than one,
101 COND_EXPRs that use X.
102
103 Or
104
105 bb0:
106 x = (typecast) a
107 if (x) goto ... else goto ...
108
109 Will be transformed into:
110
111 bb0:
112 if (a != 0) goto ... else goto ...
113
114 (Assuming a is an integral type and x is a boolean or x is an
115 integral and a is a boolean.)
116
117 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
118 For these cases, we propagate A into all, possibly more than one,
119 COND_EXPRs that use X.
120
121 In addition to eliminating the variable and the statement which assigns
122 a value to the variable, we may be able to later thread the jump without
123 adding insane complexity in the dominator optimizer.
124
125 Also note these transformations can cascade. We handle this by having
126 a worklist of COND_EXPR statements to examine. As we make a change to
127 a statement, we put it back on the worklist to examine on the next
128 iteration of the main loop.
129
130 A second class of propagation opportunities arises for ADDR_EXPR
131 nodes.
132
133 ptr = &x->y->z;
134 res = *ptr;
135
136 Will get turned into
137
138 res = x->y->z;
139
140 Or
141 ptr = (type1*)&type2var;
142 res = *ptr
143
144 Will get turned into (if type1 and type2 are the same size
145 and neither have volatile on them):
146 res = VIEW_CONVERT_EXPR<type1>(type2var)
147
148 Or
149
150 ptr = &x[0];
151 ptr2 = ptr + <constant>;
152
153 Will get turned into
154
155 ptr2 = &x[constant/elementsize];
156
157 Or
158
159 ptr = &x[0];
160 offset = index * element_size;
161 offset_p = (pointer) offset;
162 ptr2 = ptr + offset_p
163
164 Will get turned into:
165
166 ptr2 = &x[index];
167
168 Or
169 ssa = (int) decl
170 res = ssa & 1
171
172 Provided that decl has known alignment >= 2, will get turned into
173
174 res = 0
175
176 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
177 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
178 {NOT_EXPR,NEG_EXPR}.
179
180 This will (of course) be extended as other needs arise. */
181
182 static bool forward_propagate_addr_expr (tree, tree, bool);
183
184 /* Set to true if we delete dead edges during the optimization. */
185 static bool cfg_changed;
186
187 static tree rhs_to_tree (tree type, gimple *stmt);
188
189 static bitmap to_purge;
190
191 /* Const-and-copy lattice. */
192 static vec<tree> lattice;
193
194 /* Set the lattice entry for NAME to VAL. */
195 static void
fwprop_set_lattice_val(tree name,tree val)196 fwprop_set_lattice_val (tree name, tree val)
197 {
198 if (TREE_CODE (name) == SSA_NAME)
199 {
200 if (SSA_NAME_VERSION (name) >= lattice.length ())
201 {
202 lattice.reserve (num_ssa_names - lattice.length ());
203 lattice.quick_grow_cleared (num_ssa_names);
204 }
205 lattice[SSA_NAME_VERSION (name)] = val;
206 }
207 }
208
209 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
210 static void
fwprop_invalidate_lattice(tree name)211 fwprop_invalidate_lattice (tree name)
212 {
213 if (name
214 && TREE_CODE (name) == SSA_NAME
215 && SSA_NAME_VERSION (name) < lattice.length ())
216 lattice[SSA_NAME_VERSION (name)] = NULL_TREE;
217 }
218
219
220 /* Get the statement we can propagate from into NAME skipping
221 trivial copies. Returns the statement which defines the
222 propagation source or NULL_TREE if there is no such one.
223 If SINGLE_USE_ONLY is set considers only sources which have
224 a single use chain up to NAME. If SINGLE_USE_P is non-null,
225 it is set to whether the chain to NAME is a single use chain
226 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
227
228 static gimple *
get_prop_source_stmt(tree name,bool single_use_only,bool * single_use_p)229 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
230 {
231 bool single_use = true;
232
233 do {
234 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
235
236 if (!has_single_use (name))
237 {
238 single_use = false;
239 if (single_use_only)
240 return NULL;
241 }
242
243 /* If name is defined by a PHI node or is the default def, bail out. */
244 if (!is_gimple_assign (def_stmt))
245 return NULL;
246
247 /* If def_stmt is a simple copy, continue looking. */
248 if (gimple_assign_rhs_code (def_stmt) == SSA_NAME)
249 name = gimple_assign_rhs1 (def_stmt);
250 else
251 {
252 if (!single_use_only && single_use_p)
253 *single_use_p = single_use;
254
255 return def_stmt;
256 }
257 } while (1);
258 }
259
260 /* Checks if the destination ssa name in DEF_STMT can be used as
261 propagation source. Returns true if so, otherwise false. */
262
263 static bool
can_propagate_from(gimple * def_stmt)264 can_propagate_from (gimple *def_stmt)
265 {
266 gcc_assert (is_gimple_assign (def_stmt));
267
268 /* If the rhs has side-effects we cannot propagate from it. */
269 if (gimple_has_volatile_ops (def_stmt))
270 return false;
271
272 /* If the rhs is a load we cannot propagate from it. */
273 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
274 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
275 return false;
276
277 /* Constants can be always propagated. */
278 if (gimple_assign_single_p (def_stmt)
279 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
280 return true;
281
282 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
283 if (stmt_references_abnormal_ssa_name (def_stmt))
284 return false;
285
286 /* If the definition is a conversion of a pointer to a function type,
287 then we cannot apply optimizations as some targets require
288 function pointers to be canonicalized and in this case this
289 optimization could eliminate a necessary canonicalization. */
290 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
291 {
292 tree rhs = gimple_assign_rhs1 (def_stmt);
293 if (POINTER_TYPE_P (TREE_TYPE (rhs))
294 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
295 return false;
296 }
297
298 return true;
299 }
300
301 /* Remove a chain of dead statements starting at the definition of
302 NAME. The chain is linked via the first operand of the defining statements.
303 If NAME was replaced in its only use then this function can be used
304 to clean up dead stmts. The function handles already released SSA
305 names gracefully.
306 Returns true if cleanup-cfg has to run. */
307
308 static bool
remove_prop_source_from_use(tree name)309 remove_prop_source_from_use (tree name)
310 {
311 gimple_stmt_iterator gsi;
312 gimple *stmt;
313 bool cfg_changed = false;
314
315 do {
316 basic_block bb;
317
318 if (SSA_NAME_IN_FREE_LIST (name)
319 || SSA_NAME_IS_DEFAULT_DEF (name)
320 || !has_zero_uses (name))
321 return cfg_changed;
322
323 stmt = SSA_NAME_DEF_STMT (name);
324 if (gimple_code (stmt) == GIMPLE_PHI
325 || gimple_has_side_effects (stmt))
326 return cfg_changed;
327
328 bb = gimple_bb (stmt);
329 gsi = gsi_for_stmt (stmt);
330 unlink_stmt_vdef (stmt);
331 if (gsi_remove (&gsi, true))
332 bitmap_set_bit (to_purge, bb->index);
333 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
334 release_defs (stmt);
335
336 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
337 } while (name && TREE_CODE (name) == SSA_NAME);
338
339 return cfg_changed;
340 }
341
342 /* Return the rhs of a gassign *STMT in a form of a single tree,
343 converted to type TYPE.
344
345 This should disappear, but is needed so we can combine expressions and use
346 the fold() interfaces. Long term, we need to develop folding and combine
347 routines that deal with gimple exclusively . */
348
349 static tree
rhs_to_tree(tree type,gimple * stmt)350 rhs_to_tree (tree type, gimple *stmt)
351 {
352 location_t loc = gimple_location (stmt);
353 enum tree_code code = gimple_assign_rhs_code (stmt);
354 switch (get_gimple_rhs_class (code))
355 {
356 case GIMPLE_TERNARY_RHS:
357 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
358 gimple_assign_rhs2 (stmt),
359 gimple_assign_rhs3 (stmt));
360 case GIMPLE_BINARY_RHS:
361 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
362 gimple_assign_rhs2 (stmt));
363 case GIMPLE_UNARY_RHS:
364 return build1 (code, type, gimple_assign_rhs1 (stmt));
365 case GIMPLE_SINGLE_RHS:
366 return gimple_assign_rhs1 (stmt);
367 default:
368 gcc_unreachable ();
369 }
370 }
371
372 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
373 the folded result in a form suitable for COND_EXPR_COND or
374 NULL_TREE, if there is no suitable simplified form. If
375 INVARIANT_ONLY is true only gimple_min_invariant results are
376 considered simplified. */
377
378 static tree
combine_cond_expr_cond(gimple * stmt,enum tree_code code,tree type,tree op0,tree op1,bool invariant_only)379 combine_cond_expr_cond (gimple *stmt, enum tree_code code, tree type,
380 tree op0, tree op1, bool invariant_only)
381 {
382 tree t;
383
384 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
385
386 fold_defer_overflow_warnings ();
387 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
388 if (!t)
389 {
390 fold_undefer_overflow_warnings (false, NULL, 0);
391 return NULL_TREE;
392 }
393
394 /* Require that we got a boolean type out if we put one in. */
395 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
396
397 /* Canonicalize the combined condition for use in a COND_EXPR. */
398 t = canonicalize_cond_expr_cond (t);
399
400 /* Bail out if we required an invariant but didn't get one. */
401 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
402 {
403 fold_undefer_overflow_warnings (false, NULL, 0);
404 return NULL_TREE;
405 }
406
407 bool nowarn = warning_suppressed_p (stmt, OPT_Wstrict_overflow);
408 fold_undefer_overflow_warnings (!nowarn, stmt, 0);
409
410 return t;
411 }
412
413 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
414 of its operand. Return a new comparison tree or NULL_TREE if there
415 were no simplifying combines. */
416
417 static tree
forward_propagate_into_comparison_1(gimple * stmt,enum tree_code code,tree type,tree op0,tree op1)418 forward_propagate_into_comparison_1 (gimple *stmt,
419 enum tree_code code, tree type,
420 tree op0, tree op1)
421 {
422 tree tmp = NULL_TREE;
423 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
424 bool single_use0_p = false, single_use1_p = false;
425
426 /* For comparisons use the first operand, that is likely to
427 simplify comparisons against constants. */
428 if (TREE_CODE (op0) == SSA_NAME)
429 {
430 gimple *def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
431 if (def_stmt && can_propagate_from (def_stmt))
432 {
433 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
434 bool invariant_only_p = !single_use0_p;
435
436 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
437
438 /* Always combine comparisons or conversions from booleans. */
439 if (TREE_CODE (op1) == INTEGER_CST
440 && ((CONVERT_EXPR_CODE_P (def_code)
441 && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs0, 0)))
442 == BOOLEAN_TYPE)
443 || TREE_CODE_CLASS (def_code) == tcc_comparison))
444 invariant_only_p = false;
445
446 tmp = combine_cond_expr_cond (stmt, code, type,
447 rhs0, op1, invariant_only_p);
448 if (tmp)
449 return tmp;
450 }
451 }
452
453 /* If that wasn't successful, try the second operand. */
454 if (TREE_CODE (op1) == SSA_NAME)
455 {
456 gimple *def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
457 if (def_stmt && can_propagate_from (def_stmt))
458 {
459 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
460 tmp = combine_cond_expr_cond (stmt, code, type,
461 op0, rhs1, !single_use1_p);
462 if (tmp)
463 return tmp;
464 }
465 }
466
467 /* If that wasn't successful either, try both operands. */
468 if (rhs0 != NULL_TREE
469 && rhs1 != NULL_TREE)
470 tmp = combine_cond_expr_cond (stmt, code, type,
471 rhs0, rhs1,
472 !(single_use0_p && single_use1_p));
473
474 return tmp;
475 }
476
477 /* Propagate from the ssa name definition statements of the assignment
478 from a comparison at *GSI into the conditional if that simplifies it.
479 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
480 otherwise returns 0. */
481
482 static int
forward_propagate_into_comparison(gimple_stmt_iterator * gsi)483 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
484 {
485 gimple *stmt = gsi_stmt (*gsi);
486 tree tmp;
487 bool cfg_changed = false;
488 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
489 tree rhs1 = gimple_assign_rhs1 (stmt);
490 tree rhs2 = gimple_assign_rhs2 (stmt);
491
492 /* Combine the comparison with defining statements. */
493 tmp = forward_propagate_into_comparison_1 (stmt,
494 gimple_assign_rhs_code (stmt),
495 type, rhs1, rhs2);
496 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
497 {
498 gimple_assign_set_rhs_from_tree (gsi, tmp);
499 fold_stmt (gsi);
500 update_stmt (gsi_stmt (*gsi));
501
502 if (TREE_CODE (rhs1) == SSA_NAME)
503 cfg_changed |= remove_prop_source_from_use (rhs1);
504 if (TREE_CODE (rhs2) == SSA_NAME)
505 cfg_changed |= remove_prop_source_from_use (rhs2);
506 return cfg_changed ? 2 : 1;
507 }
508
509 return 0;
510 }
511
512 /* Propagate from the ssa name definition statements of COND_EXPR
513 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
514 Returns zero if no statement was changed, one if there were
515 changes and two if cfg_cleanup needs to run.
516
517 This must be kept in sync with forward_propagate_into_cond. */
518
519 static int
forward_propagate_into_gimple_cond(gcond * stmt)520 forward_propagate_into_gimple_cond (gcond *stmt)
521 {
522 tree tmp;
523 enum tree_code code = gimple_cond_code (stmt);
524 bool cfg_changed = false;
525 tree rhs1 = gimple_cond_lhs (stmt);
526 tree rhs2 = gimple_cond_rhs (stmt);
527
528 /* We can do tree combining on SSA_NAME and comparison expressions. */
529 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
530 return 0;
531
532 tmp = forward_propagate_into_comparison_1 (stmt, code,
533 boolean_type_node,
534 rhs1, rhs2);
535 if (tmp
536 && is_gimple_condexpr_for_cond (tmp))
537 {
538 if (dump_file)
539 {
540 fprintf (dump_file, " Replaced '");
541 print_gimple_expr (dump_file, stmt, 0);
542 fprintf (dump_file, "' with '");
543 print_generic_expr (dump_file, tmp);
544 fprintf (dump_file, "'\n");
545 }
546
547 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
548 update_stmt (stmt);
549
550 if (TREE_CODE (rhs1) == SSA_NAME)
551 cfg_changed |= remove_prop_source_from_use (rhs1);
552 if (TREE_CODE (rhs2) == SSA_NAME)
553 cfg_changed |= remove_prop_source_from_use (rhs2);
554 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
555 }
556
557 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
558 if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
559 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
560 && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
561 && ((code == EQ_EXPR
562 && integer_zerop (rhs2))
563 || (code == NE_EXPR
564 && integer_onep (rhs2))))
565 {
566 basic_block bb = gimple_bb (stmt);
567 gimple_cond_set_code (stmt, NE_EXPR);
568 gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
569 EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
570 EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
571 return 1;
572 }
573
574 return 0;
575 }
576
577
578 /* Propagate from the ssa name definition statements of COND_EXPR
579 in the rhs of statement STMT into the conditional if that simplifies it.
580 Returns true zero if the stmt was changed. */
581
582 static bool
forward_propagate_into_cond(gimple_stmt_iterator * gsi_p)583 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
584 {
585 gimple *stmt = gsi_stmt (*gsi_p);
586 tree tmp = NULL_TREE;
587 tree cond = gimple_assign_rhs1 (stmt);
588 enum tree_code code = gimple_assign_rhs_code (stmt);
589
590 /* We can do tree combining on SSA_NAME and comparison expressions. */
591 if (COMPARISON_CLASS_P (cond))
592 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
593 TREE_TYPE (cond),
594 TREE_OPERAND (cond, 0),
595 TREE_OPERAND (cond, 1));
596 else if (TREE_CODE (cond) == SSA_NAME)
597 {
598 enum tree_code def_code;
599 tree name = cond;
600 gimple *def_stmt = get_prop_source_stmt (name, true, NULL);
601 if (!def_stmt || !can_propagate_from (def_stmt))
602 return 0;
603
604 def_code = gimple_assign_rhs_code (def_stmt);
605 if (TREE_CODE_CLASS (def_code) == tcc_comparison)
606 tmp = fold_build2_loc (gimple_location (def_stmt),
607 def_code,
608 TREE_TYPE (cond),
609 gimple_assign_rhs1 (def_stmt),
610 gimple_assign_rhs2 (def_stmt));
611 }
612
613 if (tmp
614 && is_gimple_condexpr (tmp))
615 {
616 if (dump_file)
617 {
618 fprintf (dump_file, " Replaced '");
619 print_generic_expr (dump_file, cond);
620 fprintf (dump_file, "' with '");
621 print_generic_expr (dump_file, tmp);
622 fprintf (dump_file, "'\n");
623 }
624
625 if ((code == VEC_COND_EXPR) ? integer_all_onesp (tmp)
626 : integer_onep (tmp))
627 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
628 else if (integer_zerop (tmp))
629 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
630 else
631 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
632 stmt = gsi_stmt (*gsi_p);
633 update_stmt (stmt);
634
635 return true;
636 }
637
638 return 0;
639 }
640
641 /* We've just substituted an ADDR_EXPR into stmt. Update all the
642 relevant data structures to match. */
643
644 static void
tidy_after_forward_propagate_addr(gimple * stmt)645 tidy_after_forward_propagate_addr (gimple *stmt)
646 {
647 /* We may have turned a trapping insn into a non-trapping insn. */
648 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
649 bitmap_set_bit (to_purge, gimple_bb (stmt)->index);
650
651 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
652 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
653 }
654
655 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
656 ADDR_EXPR <whatever>.
657
658 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
659 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
660 node or for recovery of array indexing from pointer arithmetic.
661
662 Return true if the propagation was successful (the propagation can
663 be not totally successful, yet things may have been changed). */
664
665 static bool
forward_propagate_addr_expr_1(tree name,tree def_rhs,gimple_stmt_iterator * use_stmt_gsi,bool single_use_p)666 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
667 gimple_stmt_iterator *use_stmt_gsi,
668 bool single_use_p)
669 {
670 tree lhs, rhs, rhs2, array_ref;
671 gimple *use_stmt = gsi_stmt (*use_stmt_gsi);
672 enum tree_code rhs_code;
673 bool res = true;
674
675 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
676
677 lhs = gimple_assign_lhs (use_stmt);
678 rhs_code = gimple_assign_rhs_code (use_stmt);
679 rhs = gimple_assign_rhs1 (use_stmt);
680
681 /* Do not perform copy-propagation but recurse through copy chains. */
682 if (TREE_CODE (lhs) == SSA_NAME
683 && rhs_code == SSA_NAME)
684 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
685
686 /* The use statement could be a conversion. Recurse to the uses of the
687 lhs as copyprop does not copy through pointer to integer to pointer
688 conversions and FRE does not catch all cases either.
689 Treat the case of a single-use name and
690 a conversion to def_rhs type separate, though. */
691 if (TREE_CODE (lhs) == SSA_NAME
692 && CONVERT_EXPR_CODE_P (rhs_code))
693 {
694 /* If there is a point in a conversion chain where the types match
695 so we can remove a conversion re-materialize the address here
696 and stop. */
697 if (single_use_p
698 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
699 {
700 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
701 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
702 return true;
703 }
704
705 /* Else recurse if the conversion preserves the address value. */
706 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
707 || POINTER_TYPE_P (TREE_TYPE (lhs)))
708 && (TYPE_PRECISION (TREE_TYPE (lhs))
709 >= TYPE_PRECISION (TREE_TYPE (def_rhs))))
710 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
711
712 return false;
713 }
714
715 /* If this isn't a conversion chain from this on we only can propagate
716 into compatible pointer contexts. */
717 if (!types_compatible_p (TREE_TYPE (name), TREE_TYPE (def_rhs)))
718 return false;
719
720 /* Propagate through constant pointer adjustments. */
721 if (TREE_CODE (lhs) == SSA_NAME
722 && rhs_code == POINTER_PLUS_EXPR
723 && rhs == name
724 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
725 {
726 tree new_def_rhs;
727 /* As we come here with non-invariant addresses in def_rhs we need
728 to make sure we can build a valid constant offsetted address
729 for further propagation. Simply rely on fold building that
730 and check after the fact. */
731 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
732 def_rhs,
733 fold_convert (ptr_type_node,
734 gimple_assign_rhs2 (use_stmt)));
735 if (TREE_CODE (new_def_rhs) == MEM_REF
736 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
737 return false;
738 new_def_rhs = build1 (ADDR_EXPR, TREE_TYPE (rhs), new_def_rhs);
739
740 /* Recurse. If we could propagate into all uses of lhs do not
741 bother to replace into the current use but just pretend we did. */
742 if (forward_propagate_addr_expr (lhs, new_def_rhs, single_use_p))
743 return true;
744
745 if (useless_type_conversion_p (TREE_TYPE (lhs),
746 TREE_TYPE (new_def_rhs)))
747 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
748 new_def_rhs);
749 else if (is_gimple_min_invariant (new_def_rhs))
750 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR, new_def_rhs);
751 else
752 return false;
753 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
754 update_stmt (use_stmt);
755 return true;
756 }
757
758 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
759 ADDR_EXPR will not appear on the LHS. */
760 tree *lhsp = gimple_assign_lhs_ptr (use_stmt);
761 while (handled_component_p (*lhsp))
762 lhsp = &TREE_OPERAND (*lhsp, 0);
763 lhs = *lhsp;
764
765 /* Now see if the LHS node is a MEM_REF using NAME. If so,
766 propagate the ADDR_EXPR into the use of NAME and fold the result. */
767 if (TREE_CODE (lhs) == MEM_REF
768 && TREE_OPERAND (lhs, 0) == name)
769 {
770 tree def_rhs_base;
771 poly_int64 def_rhs_offset;
772 /* If the address is invariant we can always fold it. */
773 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
774 &def_rhs_offset)))
775 {
776 poly_offset_int off = mem_ref_offset (lhs);
777 tree new_ptr;
778 off += def_rhs_offset;
779 if (TREE_CODE (def_rhs_base) == MEM_REF)
780 {
781 off += mem_ref_offset (def_rhs_base);
782 new_ptr = TREE_OPERAND (def_rhs_base, 0);
783 }
784 else
785 new_ptr = build_fold_addr_expr (def_rhs_base);
786 TREE_OPERAND (lhs, 0) = new_ptr;
787 TREE_OPERAND (lhs, 1)
788 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
789 tidy_after_forward_propagate_addr (use_stmt);
790 /* Continue propagating into the RHS if this was not the only use. */
791 if (single_use_p)
792 return true;
793 }
794 /* If the LHS is a plain dereference and the value type is the same as
795 that of the pointed-to type of the address we can put the
796 dereferenced address on the LHS preserving the original alias-type. */
797 else if (integer_zerop (TREE_OPERAND (lhs, 1))
798 && ((gimple_assign_lhs (use_stmt) == lhs
799 && useless_type_conversion_p
800 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
801 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
802 || types_compatible_p (TREE_TYPE (lhs),
803 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
804 /* Don't forward anything into clobber stmts if it would result
805 in the lhs no longer being a MEM_REF. */
806 && (!gimple_clobber_p (use_stmt)
807 || TREE_CODE (TREE_OPERAND (def_rhs, 0)) == MEM_REF))
808 {
809 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
810 tree new_offset, new_base, saved, new_lhs;
811 while (handled_component_p (*def_rhs_basep))
812 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
813 saved = *def_rhs_basep;
814 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
815 {
816 new_base = TREE_OPERAND (*def_rhs_basep, 0);
817 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)),
818 TREE_OPERAND (*def_rhs_basep, 1));
819 }
820 else
821 {
822 new_base = build_fold_addr_expr (*def_rhs_basep);
823 new_offset = TREE_OPERAND (lhs, 1);
824 }
825 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
826 new_base, new_offset);
827 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
828 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
829 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
830 new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
831 *lhsp = new_lhs;
832 TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
833 TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
834 *def_rhs_basep = saved;
835 tidy_after_forward_propagate_addr (use_stmt);
836 /* Continue propagating into the RHS if this was not the
837 only use. */
838 if (single_use_p)
839 return true;
840 }
841 else
842 /* We can have a struct assignment dereferencing our name twice.
843 Note that we didn't propagate into the lhs to not falsely
844 claim we did when propagating into the rhs. */
845 res = false;
846 }
847
848 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
849 nodes from the RHS. */
850 tree *rhsp = gimple_assign_rhs1_ptr (use_stmt);
851 if (TREE_CODE (*rhsp) == ADDR_EXPR)
852 rhsp = &TREE_OPERAND (*rhsp, 0);
853 while (handled_component_p (*rhsp))
854 rhsp = &TREE_OPERAND (*rhsp, 0);
855 rhs = *rhsp;
856
857 /* Now see if the RHS node is a MEM_REF using NAME. If so,
858 propagate the ADDR_EXPR into the use of NAME and fold the result. */
859 if (TREE_CODE (rhs) == MEM_REF
860 && TREE_OPERAND (rhs, 0) == name)
861 {
862 tree def_rhs_base;
863 poly_int64 def_rhs_offset;
864 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
865 &def_rhs_offset)))
866 {
867 poly_offset_int off = mem_ref_offset (rhs);
868 tree new_ptr;
869 off += def_rhs_offset;
870 if (TREE_CODE (def_rhs_base) == MEM_REF)
871 {
872 off += mem_ref_offset (def_rhs_base);
873 new_ptr = TREE_OPERAND (def_rhs_base, 0);
874 }
875 else
876 new_ptr = build_fold_addr_expr (def_rhs_base);
877 TREE_OPERAND (rhs, 0) = new_ptr;
878 TREE_OPERAND (rhs, 1)
879 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
880 fold_stmt_inplace (use_stmt_gsi);
881 tidy_after_forward_propagate_addr (use_stmt);
882 return res;
883 }
884 /* If the RHS is a plain dereference and the value type is the same as
885 that of the pointed-to type of the address we can put the
886 dereferenced address on the RHS preserving the original alias-type. */
887 else if (integer_zerop (TREE_OPERAND (rhs, 1))
888 && ((gimple_assign_rhs1 (use_stmt) == rhs
889 && useless_type_conversion_p
890 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
891 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
892 || types_compatible_p (TREE_TYPE (rhs),
893 TREE_TYPE (TREE_OPERAND (def_rhs, 0)))))
894 {
895 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
896 tree new_offset, new_base, saved, new_rhs;
897 while (handled_component_p (*def_rhs_basep))
898 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
899 saved = *def_rhs_basep;
900 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
901 {
902 new_base = TREE_OPERAND (*def_rhs_basep, 0);
903 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)),
904 TREE_OPERAND (*def_rhs_basep, 1));
905 }
906 else
907 {
908 new_base = build_fold_addr_expr (*def_rhs_basep);
909 new_offset = TREE_OPERAND (rhs, 1);
910 }
911 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
912 new_base, new_offset);
913 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
914 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
915 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
916 new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
917 *rhsp = new_rhs;
918 TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
919 TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
920 *def_rhs_basep = saved;
921 fold_stmt_inplace (use_stmt_gsi);
922 tidy_after_forward_propagate_addr (use_stmt);
923 return res;
924 }
925 }
926
927 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
928 is nothing to do. */
929 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
930 || gimple_assign_rhs1 (use_stmt) != name)
931 return false;
932
933 /* The remaining cases are all for turning pointer arithmetic into
934 array indexing. They only apply when we have the address of
935 element zero in an array. If that is not the case then there
936 is nothing to do. */
937 array_ref = TREE_OPERAND (def_rhs, 0);
938 if ((TREE_CODE (array_ref) != ARRAY_REF
939 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
940 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
941 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
942 return false;
943
944 rhs2 = gimple_assign_rhs2 (use_stmt);
945 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
946 if (TREE_CODE (rhs2) == INTEGER_CST)
947 {
948 tree new_rhs = build1_loc (gimple_location (use_stmt),
949 ADDR_EXPR, TREE_TYPE (def_rhs),
950 fold_build2 (MEM_REF,
951 TREE_TYPE (TREE_TYPE (def_rhs)),
952 unshare_expr (def_rhs),
953 fold_convert (ptr_type_node,
954 rhs2)));
955 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
956 use_stmt = gsi_stmt (*use_stmt_gsi);
957 update_stmt (use_stmt);
958 tidy_after_forward_propagate_addr (use_stmt);
959 return true;
960 }
961
962 return false;
963 }
964
965 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
966
967 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
968 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
969 node or for recovery of array indexing from pointer arithmetic.
970
971 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
972 the single use in the previous invocation. Pass true when calling
973 this as toplevel.
974
975 Returns true, if all uses have been propagated into. */
976
977 static bool
forward_propagate_addr_expr(tree name,tree rhs,bool parent_single_use_p)978 forward_propagate_addr_expr (tree name, tree rhs, bool parent_single_use_p)
979 {
980 imm_use_iterator iter;
981 gimple *use_stmt;
982 bool all = true;
983 bool single_use_p = parent_single_use_p && has_single_use (name);
984
985 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
986 {
987 bool result;
988 tree use_rhs;
989
990 /* If the use is not in a simple assignment statement, then
991 there is nothing we can do. */
992 if (!is_gimple_assign (use_stmt))
993 {
994 if (!is_gimple_debug (use_stmt))
995 all = false;
996 continue;
997 }
998
999 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1000 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1001 single_use_p);
1002 /* If the use has moved to a different statement adjust
1003 the update machinery for the old statement too. */
1004 if (use_stmt != gsi_stmt (gsi))
1005 {
1006 update_stmt (use_stmt);
1007 use_stmt = gsi_stmt (gsi);
1008 }
1009 update_stmt (use_stmt);
1010 all &= result;
1011
1012 /* Remove intermediate now unused copy and conversion chains. */
1013 use_rhs = gimple_assign_rhs1 (use_stmt);
1014 if (result
1015 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1016 && TREE_CODE (use_rhs) == SSA_NAME
1017 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1018 {
1019 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1020 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt));
1021 release_defs (use_stmt);
1022 gsi_remove (&gsi, true);
1023 }
1024 }
1025
1026 return all && has_zero_uses (name);
1027 }
1028
1029
1030 /* Helper function for simplify_gimple_switch. Remove case labels that
1031 have values outside the range of the new type. */
1032
1033 static void
simplify_gimple_switch_label_vec(gswitch * stmt,tree index_type)1034 simplify_gimple_switch_label_vec (gswitch *stmt, tree index_type)
1035 {
1036 unsigned int branch_num = gimple_switch_num_labels (stmt);
1037 auto_vec<tree> labels (branch_num);
1038 unsigned int i, len;
1039
1040 /* Collect the existing case labels in a VEC, and preprocess it as if
1041 we are gimplifying a GENERIC SWITCH_EXPR. */
1042 for (i = 1; i < branch_num; i++)
1043 labels.quick_push (gimple_switch_label (stmt, i));
1044 preprocess_case_label_vec_for_gimple (labels, index_type, NULL);
1045
1046 /* If any labels were removed, replace the existing case labels
1047 in the GIMPLE_SWITCH statement with the correct ones.
1048 Note that the type updates were done in-place on the case labels,
1049 so we only have to replace the case labels in the GIMPLE_SWITCH
1050 if the number of labels changed. */
1051 len = labels.length ();
1052 if (len < branch_num - 1)
1053 {
1054 bitmap target_blocks;
1055 edge_iterator ei;
1056 edge e;
1057
1058 /* Corner case: *all* case labels have been removed as being
1059 out-of-range for INDEX_TYPE. Push one label and let the
1060 CFG cleanups deal with this further. */
1061 if (len == 0)
1062 {
1063 tree label, elt;
1064
1065 label = CASE_LABEL (gimple_switch_default_label (stmt));
1066 elt = build_case_label (build_int_cst (index_type, 0), NULL, label);
1067 labels.quick_push (elt);
1068 len = 1;
1069 }
1070
1071 for (i = 0; i < labels.length (); i++)
1072 gimple_switch_set_label (stmt, i + 1, labels[i]);
1073 for (i++ ; i < branch_num; i++)
1074 gimple_switch_set_label (stmt, i, NULL_TREE);
1075 gimple_switch_set_num_labels (stmt, len + 1);
1076
1077 /* Cleanup any edges that are now dead. */
1078 target_blocks = BITMAP_ALLOC (NULL);
1079 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
1080 {
1081 tree elt = gimple_switch_label (stmt, i);
1082 basic_block target = label_to_block (cfun, CASE_LABEL (elt));
1083 bitmap_set_bit (target_blocks, target->index);
1084 }
1085 for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
1086 {
1087 if (! bitmap_bit_p (target_blocks, e->dest->index))
1088 {
1089 remove_edge (e);
1090 cfg_changed = true;
1091 free_dominance_info (CDI_DOMINATORS);
1092 }
1093 else
1094 ei_next (&ei);
1095 }
1096 BITMAP_FREE (target_blocks);
1097 }
1098 }
1099
1100 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1101 the condition which we may be able to optimize better. */
1102
1103 static bool
simplify_gimple_switch(gswitch * stmt)1104 simplify_gimple_switch (gswitch *stmt)
1105 {
1106 /* The optimization that we really care about is removing unnecessary
1107 casts. That will let us do much better in propagating the inferred
1108 constant at the switch target. */
1109 tree cond = gimple_switch_index (stmt);
1110 if (TREE_CODE (cond) == SSA_NAME)
1111 {
1112 gimple *def_stmt = SSA_NAME_DEF_STMT (cond);
1113 if (gimple_assign_cast_p (def_stmt))
1114 {
1115 tree def = gimple_assign_rhs1 (def_stmt);
1116 if (TREE_CODE (def) != SSA_NAME)
1117 return false;
1118
1119 /* If we have an extension or sign-change that preserves the
1120 values we check against then we can copy the source value into
1121 the switch. */
1122 tree ti = TREE_TYPE (def);
1123 if (INTEGRAL_TYPE_P (ti)
1124 && TYPE_PRECISION (ti) <= TYPE_PRECISION (TREE_TYPE (cond)))
1125 {
1126 size_t n = gimple_switch_num_labels (stmt);
1127 tree min = NULL_TREE, max = NULL_TREE;
1128 if (n > 1)
1129 {
1130 min = CASE_LOW (gimple_switch_label (stmt, 1));
1131 if (CASE_HIGH (gimple_switch_label (stmt, n - 1)))
1132 max = CASE_HIGH (gimple_switch_label (stmt, n - 1));
1133 else
1134 max = CASE_LOW (gimple_switch_label (stmt, n - 1));
1135 }
1136 if ((!min || int_fits_type_p (min, ti))
1137 && (!max || int_fits_type_p (max, ti)))
1138 {
1139 gimple_switch_set_index (stmt, def);
1140 simplify_gimple_switch_label_vec (stmt, ti);
1141 update_stmt (stmt);
1142 return true;
1143 }
1144 }
1145 }
1146 }
1147
1148 return false;
1149 }
1150
1151 /* For pointers p2 and p1 return p2 - p1 if the
1152 difference is known and constant, otherwise return NULL. */
1153
1154 static tree
constant_pointer_difference(tree p1,tree p2)1155 constant_pointer_difference (tree p1, tree p2)
1156 {
1157 int i, j;
1158 #define CPD_ITERATIONS 5
1159 tree exps[2][CPD_ITERATIONS];
1160 tree offs[2][CPD_ITERATIONS];
1161 int cnt[2];
1162
1163 for (i = 0; i < 2; i++)
1164 {
1165 tree p = i ? p1 : p2;
1166 tree off = size_zero_node;
1167 gimple *stmt;
1168 enum tree_code code;
1169
1170 /* For each of p1 and p2 we need to iterate at least
1171 twice, to handle ADDR_EXPR directly in p1/p2,
1172 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1173 on definition's stmt RHS. Iterate a few extra times. */
1174 j = 0;
1175 do
1176 {
1177 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1178 break;
1179 if (TREE_CODE (p) == ADDR_EXPR)
1180 {
1181 tree q = TREE_OPERAND (p, 0);
1182 poly_int64 offset;
1183 tree base = get_addr_base_and_unit_offset (q, &offset);
1184 if (base)
1185 {
1186 q = base;
1187 if (maybe_ne (offset, 0))
1188 off = size_binop (PLUS_EXPR, off, size_int (offset));
1189 }
1190 if (TREE_CODE (q) == MEM_REF
1191 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1192 {
1193 p = TREE_OPERAND (q, 0);
1194 off = size_binop (PLUS_EXPR, off,
1195 wide_int_to_tree (sizetype,
1196 mem_ref_offset (q)));
1197 }
1198 else
1199 {
1200 exps[i][j] = q;
1201 offs[i][j++] = off;
1202 break;
1203 }
1204 }
1205 if (TREE_CODE (p) != SSA_NAME)
1206 break;
1207 exps[i][j] = p;
1208 offs[i][j++] = off;
1209 if (j == CPD_ITERATIONS)
1210 break;
1211 stmt = SSA_NAME_DEF_STMT (p);
1212 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1213 break;
1214 code = gimple_assign_rhs_code (stmt);
1215 if (code == POINTER_PLUS_EXPR)
1216 {
1217 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1218 break;
1219 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1220 p = gimple_assign_rhs1 (stmt);
1221 }
1222 else if (code == ADDR_EXPR || CONVERT_EXPR_CODE_P (code))
1223 p = gimple_assign_rhs1 (stmt);
1224 else
1225 break;
1226 }
1227 while (1);
1228 cnt[i] = j;
1229 }
1230
1231 for (i = 0; i < cnt[0]; i++)
1232 for (j = 0; j < cnt[1]; j++)
1233 if (exps[0][i] == exps[1][j])
1234 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1235
1236 return NULL_TREE;
1237 }
1238
1239 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1240 Optimize
1241 memcpy (p, "abcd", 4);
1242 memset (p + 4, ' ', 3);
1243 into
1244 memcpy (p, "abcd ", 7);
1245 call if the latter can be stored by pieces during expansion.
1246
1247 Also canonicalize __atomic_fetch_op (p, x, y) op x
1248 to __atomic_op_fetch (p, x, y) or
1249 __atomic_op_fetch (p, x, y) iop x
1250 to __atomic_fetch_op (p, x, y) when possible (also __sync). */
1251
1252 static bool
simplify_builtin_call(gimple_stmt_iterator * gsi_p,tree callee2)1253 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1254 {
1255 gimple *stmt1, *stmt2 = gsi_stmt (*gsi_p);
1256 enum built_in_function other_atomic = END_BUILTINS;
1257 enum tree_code atomic_op = ERROR_MARK;
1258 tree vuse = gimple_vuse (stmt2);
1259 if (vuse == NULL)
1260 return false;
1261 stmt1 = SSA_NAME_DEF_STMT (vuse);
1262
1263 switch (DECL_FUNCTION_CODE (callee2))
1264 {
1265 case BUILT_IN_MEMSET:
1266 if (gimple_call_num_args (stmt2) != 3
1267 || gimple_call_lhs (stmt2)
1268 || CHAR_BIT != 8
1269 || BITS_PER_UNIT != 8)
1270 break;
1271 else
1272 {
1273 tree callee1;
1274 tree ptr1, src1, str1, off1, len1, lhs1;
1275 tree ptr2 = gimple_call_arg (stmt2, 0);
1276 tree val2 = gimple_call_arg (stmt2, 1);
1277 tree len2 = gimple_call_arg (stmt2, 2);
1278 tree diff, vdef, new_str_cst;
1279 gimple *use_stmt;
1280 unsigned int ptr1_align;
1281 unsigned HOST_WIDE_INT src_len;
1282 char *src_buf;
1283 use_operand_p use_p;
1284
1285 if (!tree_fits_shwi_p (val2)
1286 || !tree_fits_uhwi_p (len2)
1287 || compare_tree_int (len2, 1024) == 1)
1288 break;
1289 if (is_gimple_call (stmt1))
1290 {
1291 /* If first stmt is a call, it needs to be memcpy
1292 or mempcpy, with string literal as second argument and
1293 constant length. */
1294 callee1 = gimple_call_fndecl (stmt1);
1295 if (callee1 == NULL_TREE
1296 || !fndecl_built_in_p (callee1, BUILT_IN_NORMAL)
1297 || gimple_call_num_args (stmt1) != 3)
1298 break;
1299 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1300 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1301 break;
1302 ptr1 = gimple_call_arg (stmt1, 0);
1303 src1 = gimple_call_arg (stmt1, 1);
1304 len1 = gimple_call_arg (stmt1, 2);
1305 lhs1 = gimple_call_lhs (stmt1);
1306 if (!tree_fits_uhwi_p (len1))
1307 break;
1308 str1 = string_constant (src1, &off1, NULL, NULL);
1309 if (str1 == NULL_TREE)
1310 break;
1311 if (!tree_fits_uhwi_p (off1)
1312 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1313 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1314 - tree_to_uhwi (off1)) > 0
1315 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1316 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1317 != TYPE_MODE (char_type_node))
1318 break;
1319 }
1320 else if (gimple_assign_single_p (stmt1))
1321 {
1322 /* Otherwise look for length 1 memcpy optimized into
1323 assignment. */
1324 ptr1 = gimple_assign_lhs (stmt1);
1325 src1 = gimple_assign_rhs1 (stmt1);
1326 if (TREE_CODE (ptr1) != MEM_REF
1327 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1328 || !tree_fits_shwi_p (src1))
1329 break;
1330 ptr1 = build_fold_addr_expr (ptr1);
1331 STRIP_USELESS_TYPE_CONVERSION (ptr1);
1332 callee1 = NULL_TREE;
1333 len1 = size_one_node;
1334 lhs1 = NULL_TREE;
1335 off1 = size_zero_node;
1336 str1 = NULL_TREE;
1337 }
1338 else
1339 break;
1340
1341 diff = constant_pointer_difference (ptr1, ptr2);
1342 if (diff == NULL && lhs1 != NULL)
1343 {
1344 diff = constant_pointer_difference (lhs1, ptr2);
1345 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1346 && diff != NULL)
1347 diff = size_binop (PLUS_EXPR, diff,
1348 fold_convert (sizetype, len1));
1349 }
1350 /* If the difference between the second and first destination pointer
1351 is not constant, or is bigger than memcpy length, bail out. */
1352 if (diff == NULL
1353 || !tree_fits_uhwi_p (diff)
1354 || tree_int_cst_lt (len1, diff)
1355 || compare_tree_int (diff, 1024) == 1)
1356 break;
1357
1358 /* Use maximum of difference plus memset length and memcpy length
1359 as the new memcpy length, if it is too big, bail out. */
1360 src_len = tree_to_uhwi (diff);
1361 src_len += tree_to_uhwi (len2);
1362 if (src_len < tree_to_uhwi (len1))
1363 src_len = tree_to_uhwi (len1);
1364 if (src_len > 1024)
1365 break;
1366
1367 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1368 with bigger length will return different result. */
1369 if (lhs1 != NULL_TREE
1370 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1371 && (TREE_CODE (lhs1) != SSA_NAME
1372 || !single_imm_use (lhs1, &use_p, &use_stmt)
1373 || use_stmt != stmt2))
1374 break;
1375
1376 /* If anything reads memory in between memcpy and memset
1377 call, the modified memcpy call might change it. */
1378 vdef = gimple_vdef (stmt1);
1379 if (vdef != NULL
1380 && (!single_imm_use (vdef, &use_p, &use_stmt)
1381 || use_stmt != stmt2))
1382 break;
1383
1384 ptr1_align = get_pointer_alignment (ptr1);
1385 /* Construct the new source string literal. */
1386 src_buf = XALLOCAVEC (char, src_len + 1);
1387 if (callee1)
1388 memcpy (src_buf,
1389 TREE_STRING_POINTER (str1) + tree_to_uhwi (off1),
1390 tree_to_uhwi (len1));
1391 else
1392 src_buf[0] = tree_to_shwi (src1);
1393 memset (src_buf + tree_to_uhwi (diff),
1394 tree_to_shwi (val2), tree_to_uhwi (len2));
1395 src_buf[src_len] = '\0';
1396 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1397 handle embedded '\0's. */
1398 if (strlen (src_buf) != src_len)
1399 break;
1400 rtl_profile_for_bb (gimple_bb (stmt2));
1401 /* If the new memcpy wouldn't be emitted by storing the literal
1402 by pieces, this optimization might enlarge .rodata too much,
1403 as commonly used string literals couldn't be shared any
1404 longer. */
1405 if (!can_store_by_pieces (src_len,
1406 builtin_strncpy_read_str,
1407 src_buf, ptr1_align, false))
1408 break;
1409
1410 new_str_cst = build_string_literal (src_len, src_buf);
1411 if (callee1)
1412 {
1413 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1414 memset call. */
1415 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1416 gimple_call_set_lhs (stmt1, NULL_TREE);
1417 gimple_call_set_arg (stmt1, 1, new_str_cst);
1418 gimple_call_set_arg (stmt1, 2,
1419 build_int_cst (TREE_TYPE (len1), src_len));
1420 update_stmt (stmt1);
1421 unlink_stmt_vdef (stmt2);
1422 gsi_replace (gsi_p, gimple_build_nop (), false);
1423 fwprop_invalidate_lattice (gimple_get_lhs (stmt2));
1424 release_defs (stmt2);
1425 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1426 {
1427 fwprop_invalidate_lattice (lhs1);
1428 release_ssa_name (lhs1);
1429 }
1430 return true;
1431 }
1432 else
1433 {
1434 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1435 assignment, remove STMT1 and change memset call into
1436 memcpy call. */
1437 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1438
1439 if (!is_gimple_val (ptr1))
1440 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1441 true, GSI_SAME_STMT);
1442 tree fndecl = builtin_decl_explicit (BUILT_IN_MEMCPY);
1443 gimple_call_set_fndecl (stmt2, fndecl);
1444 gimple_call_set_fntype (as_a <gcall *> (stmt2),
1445 TREE_TYPE (fndecl));
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;
1456 }
1457 }
1458 break;
1459
1460 #define CASE_ATOMIC(NAME, OTHER, OP) \
1461 case BUILT_IN_##NAME##_1: \
1462 case BUILT_IN_##NAME##_2: \
1463 case BUILT_IN_##NAME##_4: \
1464 case BUILT_IN_##NAME##_8: \
1465 case BUILT_IN_##NAME##_16: \
1466 atomic_op = OP; \
1467 other_atomic \
1468 = (enum built_in_function) (BUILT_IN_##OTHER##_1 \
1469 + (DECL_FUNCTION_CODE (callee2) \
1470 - BUILT_IN_##NAME##_1)); \
1471 goto handle_atomic_fetch_op;
1472
1473 CASE_ATOMIC (ATOMIC_FETCH_ADD, ATOMIC_ADD_FETCH, PLUS_EXPR)
1474 CASE_ATOMIC (ATOMIC_FETCH_SUB, ATOMIC_SUB_FETCH, MINUS_EXPR)
1475 CASE_ATOMIC (ATOMIC_FETCH_AND, ATOMIC_AND_FETCH, BIT_AND_EXPR)
1476 CASE_ATOMIC (ATOMIC_FETCH_XOR, ATOMIC_XOR_FETCH, BIT_XOR_EXPR)
1477 CASE_ATOMIC (ATOMIC_FETCH_OR, ATOMIC_OR_FETCH, BIT_IOR_EXPR)
1478
1479 CASE_ATOMIC (SYNC_FETCH_AND_ADD, SYNC_ADD_AND_FETCH, PLUS_EXPR)
1480 CASE_ATOMIC (SYNC_FETCH_AND_SUB, SYNC_SUB_AND_FETCH, MINUS_EXPR)
1481 CASE_ATOMIC (SYNC_FETCH_AND_AND, SYNC_AND_AND_FETCH, BIT_AND_EXPR)
1482 CASE_ATOMIC (SYNC_FETCH_AND_XOR, SYNC_XOR_AND_FETCH, BIT_XOR_EXPR)
1483 CASE_ATOMIC (SYNC_FETCH_AND_OR, SYNC_OR_AND_FETCH, BIT_IOR_EXPR)
1484
1485 CASE_ATOMIC (ATOMIC_ADD_FETCH, ATOMIC_FETCH_ADD, MINUS_EXPR)
1486 CASE_ATOMIC (ATOMIC_SUB_FETCH, ATOMIC_FETCH_SUB, PLUS_EXPR)
1487 CASE_ATOMIC (ATOMIC_XOR_FETCH, ATOMIC_FETCH_XOR, BIT_XOR_EXPR)
1488
1489 CASE_ATOMIC (SYNC_ADD_AND_FETCH, SYNC_FETCH_AND_ADD, MINUS_EXPR)
1490 CASE_ATOMIC (SYNC_SUB_AND_FETCH, SYNC_FETCH_AND_SUB, PLUS_EXPR)
1491 CASE_ATOMIC (SYNC_XOR_AND_FETCH, SYNC_FETCH_AND_XOR, BIT_XOR_EXPR)
1492
1493 #undef CASE_ATOMIC
1494
1495 handle_atomic_fetch_op:
1496 if (gimple_call_num_args (stmt2) >= 2 && gimple_call_lhs (stmt2))
1497 {
1498 tree lhs2 = gimple_call_lhs (stmt2), lhsc = lhs2;
1499 tree arg = gimple_call_arg (stmt2, 1);
1500 gimple *use_stmt, *cast_stmt = NULL;
1501 use_operand_p use_p;
1502 tree ndecl = builtin_decl_explicit (other_atomic);
1503
1504 if (ndecl == NULL_TREE || !single_imm_use (lhs2, &use_p, &use_stmt))
1505 break;
1506
1507 if (gimple_assign_cast_p (use_stmt))
1508 {
1509 cast_stmt = use_stmt;
1510 lhsc = gimple_assign_lhs (cast_stmt);
1511 if (lhsc == NULL_TREE
1512 || !INTEGRAL_TYPE_P (TREE_TYPE (lhsc))
1513 || (TYPE_PRECISION (TREE_TYPE (lhsc))
1514 != TYPE_PRECISION (TREE_TYPE (lhs2)))
1515 || !single_imm_use (lhsc, &use_p, &use_stmt))
1516 {
1517 use_stmt = cast_stmt;
1518 cast_stmt = NULL;
1519 lhsc = lhs2;
1520 }
1521 }
1522
1523 bool ok = false;
1524 tree oarg = NULL_TREE;
1525 enum tree_code ccode = ERROR_MARK;
1526 tree crhs1 = NULL_TREE, crhs2 = NULL_TREE;
1527 if (is_gimple_assign (use_stmt)
1528 && gimple_assign_rhs_code (use_stmt) == atomic_op)
1529 {
1530 if (gimple_assign_rhs1 (use_stmt) == lhsc)
1531 oarg = gimple_assign_rhs2 (use_stmt);
1532 else if (atomic_op != MINUS_EXPR)
1533 oarg = gimple_assign_rhs1 (use_stmt);
1534 }
1535 else if (atomic_op == MINUS_EXPR
1536 && is_gimple_assign (use_stmt)
1537 && gimple_assign_rhs_code (use_stmt) == PLUS_EXPR
1538 && TREE_CODE (arg) == INTEGER_CST
1539 && (TREE_CODE (gimple_assign_rhs2 (use_stmt))
1540 == INTEGER_CST))
1541 {
1542 tree a = fold_convert (TREE_TYPE (lhs2), arg);
1543 tree o = fold_convert (TREE_TYPE (lhs2),
1544 gimple_assign_rhs2 (use_stmt));
1545 if (wi::to_wide (a) == wi::neg (wi::to_wide (o)))
1546 ok = true;
1547 }
1548 else if (atomic_op == BIT_AND_EXPR || atomic_op == BIT_IOR_EXPR)
1549 ;
1550 else if (gimple_code (use_stmt) == GIMPLE_COND)
1551 {
1552 ccode = gimple_cond_code (use_stmt);
1553 crhs1 = gimple_cond_lhs (use_stmt);
1554 crhs2 = gimple_cond_rhs (use_stmt);
1555 }
1556 else if (is_gimple_assign (use_stmt))
1557 {
1558 if (gimple_assign_rhs_class (use_stmt) == GIMPLE_BINARY_RHS)
1559 {
1560 ccode = gimple_assign_rhs_code (use_stmt);
1561 crhs1 = gimple_assign_rhs1 (use_stmt);
1562 crhs2 = gimple_assign_rhs2 (use_stmt);
1563 }
1564 else if (gimple_assign_rhs_code (use_stmt) == COND_EXPR)
1565 {
1566 tree cond = gimple_assign_rhs1 (use_stmt);
1567 if (COMPARISON_CLASS_P (cond))
1568 {
1569 ccode = TREE_CODE (cond);
1570 crhs1 = TREE_OPERAND (cond, 0);
1571 crhs2 = TREE_OPERAND (cond, 1);
1572 }
1573 }
1574 }
1575 if (ccode == EQ_EXPR || ccode == NE_EXPR)
1576 {
1577 /* Deal with x - y == 0 or x ^ y == 0
1578 being optimized into x == y and x + cst == 0
1579 into x == -cst. */
1580 tree o = NULL_TREE;
1581 if (crhs1 == lhsc)
1582 o = crhs2;
1583 else if (crhs2 == lhsc)
1584 o = crhs1;
1585 if (o && atomic_op != PLUS_EXPR)
1586 oarg = o;
1587 else if (o
1588 && TREE_CODE (o) == INTEGER_CST
1589 && TREE_CODE (arg) == INTEGER_CST)
1590 {
1591 tree a = fold_convert (TREE_TYPE (lhs2), arg);
1592 o = fold_convert (TREE_TYPE (lhs2), o);
1593 if (wi::to_wide (a) == wi::neg (wi::to_wide (o)))
1594 ok = true;
1595 }
1596 }
1597 if (oarg && !ok)
1598 {
1599 if (operand_equal_p (arg, oarg, 0))
1600 ok = true;
1601 else if (TREE_CODE (arg) == SSA_NAME
1602 && TREE_CODE (oarg) == SSA_NAME)
1603 {
1604 tree oarg2 = oarg;
1605 if (gimple_assign_cast_p (SSA_NAME_DEF_STMT (oarg)))
1606 {
1607 gimple *g = SSA_NAME_DEF_STMT (oarg);
1608 oarg2 = gimple_assign_rhs1 (g);
1609 if (TREE_CODE (oarg2) != SSA_NAME
1610 || !INTEGRAL_TYPE_P (TREE_TYPE (oarg2))
1611 || (TYPE_PRECISION (TREE_TYPE (oarg2))
1612 != TYPE_PRECISION (TREE_TYPE (oarg))))
1613 oarg2 = oarg;
1614 }
1615 if (gimple_assign_cast_p (SSA_NAME_DEF_STMT (arg)))
1616 {
1617 gimple *g = SSA_NAME_DEF_STMT (arg);
1618 tree rhs1 = gimple_assign_rhs1 (g);
1619 /* Handle e.g.
1620 x.0_1 = (long unsigned int) x_4(D);
1621 _2 = __atomic_fetch_add_8 (&vlong, x.0_1, 0);
1622 _3 = (long int) _2;
1623 _7 = x_4(D) + _3; */
1624 if (rhs1 == oarg || rhs1 == oarg2)
1625 ok = true;
1626 /* Handle e.g.
1627 x.18_1 = (short unsigned int) x_5(D);
1628 _2 = (int) x.18_1;
1629 _3 = __atomic_fetch_xor_2 (&vshort, _2, 0);
1630 _4 = (short int) _3;
1631 _8 = x_5(D) ^ _4;
1632 This happens only for char/short. */
1633 else if (TREE_CODE (rhs1) == SSA_NAME
1634 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1635 && (TYPE_PRECISION (TREE_TYPE (rhs1))
1636 == TYPE_PRECISION (TREE_TYPE (lhs2))))
1637 {
1638 g = SSA_NAME_DEF_STMT (rhs1);
1639 if (gimple_assign_cast_p (g)
1640 && (gimple_assign_rhs1 (g) == oarg
1641 || gimple_assign_rhs1 (g) == oarg2))
1642 ok = true;
1643 }
1644 }
1645 if (!ok && arg == oarg2)
1646 /* Handle e.g.
1647 _1 = __sync_fetch_and_add_4 (&v, x_5(D));
1648 _2 = (int) _1;
1649 x.0_3 = (int) x_5(D);
1650 _7 = _2 + x.0_3; */
1651 ok = true;
1652 }
1653 }
1654
1655 if (ok)
1656 {
1657 tree new_lhs = make_ssa_name (TREE_TYPE (lhs2));
1658 gimple_call_set_lhs (stmt2, new_lhs);
1659 gimple_call_set_fndecl (stmt2, ndecl);
1660 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1661 if (ccode == ERROR_MARK)
1662 gimple_assign_set_rhs_with_ops (&gsi, cast_stmt
1663 ? NOP_EXPR : SSA_NAME,
1664 new_lhs);
1665 else
1666 {
1667 crhs1 = new_lhs;
1668 crhs2 = build_zero_cst (TREE_TYPE (lhs2));
1669 if (gimple_code (use_stmt) == GIMPLE_COND)
1670 {
1671 gcond *cond_stmt = as_a <gcond *> (use_stmt);
1672 gimple_cond_set_lhs (cond_stmt, crhs1);
1673 gimple_cond_set_rhs (cond_stmt, crhs2);
1674 }
1675 else if (gimple_assign_rhs_class (use_stmt)
1676 == GIMPLE_BINARY_RHS)
1677 {
1678 gimple_assign_set_rhs1 (use_stmt, crhs1);
1679 gimple_assign_set_rhs2 (use_stmt, crhs2);
1680 }
1681 else
1682 {
1683 gcc_checking_assert (gimple_assign_rhs_code (use_stmt)
1684 == COND_EXPR);
1685 tree cond = build2 (ccode, boolean_type_node,
1686 crhs1, crhs2);
1687 gimple_assign_set_rhs1 (use_stmt, cond);
1688 }
1689 }
1690 update_stmt (use_stmt);
1691 if (atomic_op != BIT_AND_EXPR
1692 && atomic_op != BIT_IOR_EXPR
1693 && !stmt_ends_bb_p (stmt2))
1694 {
1695 /* For the benefit of debug stmts, emit stmt(s) to set
1696 lhs2 to the value it had from the new builtin.
1697 E.g. if it was previously:
1698 lhs2 = __atomic_fetch_add_8 (ptr, arg, 0);
1699 emit:
1700 new_lhs = __atomic_add_fetch_8 (ptr, arg, 0);
1701 lhs2 = new_lhs - arg;
1702 We also keep cast_stmt if any in the IL for
1703 the same reasons.
1704 These stmts will be DCEd later and proper debug info
1705 will be emitted.
1706 This is only possible for reversible operations
1707 (+/-/^) and without -fnon-call-exceptions. */
1708 gsi = gsi_for_stmt (stmt2);
1709 tree type = TREE_TYPE (lhs2);
1710 if (TREE_CODE (arg) == INTEGER_CST)
1711 arg = fold_convert (type, arg);
1712 else if (!useless_type_conversion_p (type, TREE_TYPE (arg)))
1713 {
1714 tree narg = make_ssa_name (type);
1715 gimple *g = gimple_build_assign (narg, NOP_EXPR, arg);
1716 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
1717 arg = narg;
1718 }
1719 enum tree_code rcode;
1720 switch (atomic_op)
1721 {
1722 case PLUS_EXPR: rcode = MINUS_EXPR; break;
1723 case MINUS_EXPR: rcode = PLUS_EXPR; break;
1724 case BIT_XOR_EXPR: rcode = atomic_op; break;
1725 default: gcc_unreachable ();
1726 }
1727 gimple *g = gimple_build_assign (lhs2, rcode, new_lhs, arg);
1728 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
1729 update_stmt (stmt2);
1730 }
1731 else
1732 {
1733 /* For e.g.
1734 lhs2 = __atomic_fetch_or_8 (ptr, arg, 0);
1735 after we change it to
1736 new_lhs = __atomic_or_fetch_8 (ptr, arg, 0);
1737 there is no way to find out the lhs2 value (i.e.
1738 what the atomic memory contained before the operation),
1739 values of some bits are lost. We have checked earlier
1740 that we don't have any non-debug users except for what
1741 we are already changing, so we need to reset the
1742 debug stmts and remove the cast_stmt if any. */
1743 imm_use_iterator iter;
1744 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs2)
1745 if (use_stmt != cast_stmt)
1746 {
1747 gcc_assert (is_gimple_debug (use_stmt));
1748 gimple_debug_bind_reset_value (use_stmt);
1749 update_stmt (use_stmt);
1750 }
1751 if (cast_stmt)
1752 {
1753 gsi = gsi_for_stmt (cast_stmt);
1754 gsi_remove (&gsi, true);
1755 }
1756 update_stmt (stmt2);
1757 release_ssa_name (lhs2);
1758 }
1759 }
1760 }
1761 break;
1762
1763 default:
1764 break;
1765 }
1766 return false;
1767 }
1768
1769 /* Given a ssa_name in NAME see if it was defined by an assignment and
1770 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1771 to the second operand on the rhs. */
1772
1773 static inline void
defcodefor_name(tree name,enum tree_code * code,tree * arg1,tree * arg2)1774 defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
1775 {
1776 gimple *def;
1777 enum tree_code code1;
1778 tree arg11;
1779 tree arg21;
1780 tree arg31;
1781 enum gimple_rhs_class grhs_class;
1782
1783 code1 = TREE_CODE (name);
1784 arg11 = name;
1785 arg21 = NULL_TREE;
1786 arg31 = NULL_TREE;
1787 grhs_class = get_gimple_rhs_class (code1);
1788
1789 if (code1 == SSA_NAME)
1790 {
1791 def = SSA_NAME_DEF_STMT (name);
1792
1793 if (def && is_gimple_assign (def)
1794 && can_propagate_from (def))
1795 {
1796 code1 = gimple_assign_rhs_code (def);
1797 arg11 = gimple_assign_rhs1 (def);
1798 arg21 = gimple_assign_rhs2 (def);
1799 arg31 = gimple_assign_rhs3 (def);
1800 }
1801 }
1802 else if (grhs_class != GIMPLE_SINGLE_RHS)
1803 code1 = ERROR_MARK;
1804
1805 *code = code1;
1806 *arg1 = arg11;
1807 if (arg2)
1808 *arg2 = arg21;
1809 if (arg31)
1810 *code = ERROR_MARK;
1811 }
1812
1813
1814 /* Recognize rotation patterns. Return true if a transformation
1815 applied, otherwise return false.
1816
1817 We are looking for X with unsigned type T with bitsize B, OP being
1818 +, | or ^, some type T2 wider than T. For:
1819 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1820 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1821
1822 transform these into:
1823 X r<< CNT1
1824
1825 Or for:
1826 (X << Y) OP (X >> (B - Y))
1827 (X << (int) Y) OP (X >> (int) (B - Y))
1828 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1829 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1830 (X << Y) | (X >> ((-Y) & (B - 1)))
1831 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1832 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1833 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1834
1835 transform these into (last 2 only if ranger can prove Y < B
1836 or Y = N * B):
1837 X r<< Y
1838 or
1839 X r<< (& & (B - 1))
1840 The latter for the forms with T2 wider than T if ranger can't prove Y < B.
1841
1842 Or for:
1843 (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1)))
1844 (X << (int) (Y & (B - 1))) | (X >> (int) ((-Y) & (B - 1)))
1845 ((T) ((T2) X << (Y & (B - 1)))) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1846 ((T) ((T2) X << (int) (Y & (B - 1)))) \
1847 | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1848
1849 transform these into:
1850 X r<< (Y & (B - 1))
1851
1852 Note, in the patterns with T2 type, the type of OP operands
1853 might be even a signed type, but should have precision B.
1854 Expressions with & (B - 1) should be recognized only if B is
1855 a power of 2. */
1856
1857 static bool
simplify_rotate(gimple_stmt_iterator * gsi)1858 simplify_rotate (gimple_stmt_iterator *gsi)
1859 {
1860 gimple *stmt = gsi_stmt (*gsi);
1861 tree arg[2], rtype, rotcnt = NULL_TREE;
1862 tree def_arg1[2], def_arg2[2];
1863 enum tree_code def_code[2];
1864 tree lhs;
1865 int i;
1866 bool swapped_p = false;
1867 gimple *g;
1868 gimple *def_arg_stmt[2] = { NULL, NULL };
1869 int wider_prec = 0;
1870 bool add_masking = false;
1871
1872 arg[0] = gimple_assign_rhs1 (stmt);
1873 arg[1] = gimple_assign_rhs2 (stmt);
1874 rtype = TREE_TYPE (arg[0]);
1875
1876 /* Only create rotates in complete modes. Other cases are not
1877 expanded properly. */
1878 if (!INTEGRAL_TYPE_P (rtype)
1879 || !type_has_mode_precision_p (rtype))
1880 return false;
1881
1882 for (i = 0; i < 2; i++)
1883 {
1884 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1885 if (TREE_CODE (arg[i]) == SSA_NAME)
1886 def_arg_stmt[i] = SSA_NAME_DEF_STMT (arg[i]);
1887 }
1888
1889 /* Look through narrowing (or same precision) conversions. */
1890 if (CONVERT_EXPR_CODE_P (def_code[0])
1891 && CONVERT_EXPR_CODE_P (def_code[1])
1892 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[0]))
1893 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[1]))
1894 && TYPE_PRECISION (TREE_TYPE (def_arg1[0]))
1895 == TYPE_PRECISION (TREE_TYPE (def_arg1[1]))
1896 && TYPE_PRECISION (TREE_TYPE (def_arg1[0])) >= TYPE_PRECISION (rtype)
1897 && has_single_use (arg[0])
1898 && has_single_use (arg[1]))
1899 {
1900 wider_prec = TYPE_PRECISION (TREE_TYPE (def_arg1[0]));
1901 for (i = 0; i < 2; i++)
1902 {
1903 arg[i] = def_arg1[i];
1904 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1905 if (TREE_CODE (arg[i]) == SSA_NAME)
1906 def_arg_stmt[i] = SSA_NAME_DEF_STMT (arg[i]);
1907 }
1908 }
1909 else
1910 {
1911 /* Handle signed rotate; the RSHIFT_EXPR has to be done
1912 in unsigned type but LSHIFT_EXPR could be signed. */
1913 i = (def_code[0] == LSHIFT_EXPR || def_code[0] == RSHIFT_EXPR);
1914 if (CONVERT_EXPR_CODE_P (def_code[i])
1915 && (def_code[1 - i] == LSHIFT_EXPR || def_code[1 - i] == RSHIFT_EXPR)
1916 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[i]))
1917 && TYPE_PRECISION (rtype) == TYPE_PRECISION (TREE_TYPE (def_arg1[i]))
1918 && has_single_use (arg[i]))
1919 {
1920 arg[i] = def_arg1[i];
1921 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1922 if (TREE_CODE (arg[i]) == SSA_NAME)
1923 def_arg_stmt[i] = SSA_NAME_DEF_STMT (arg[i]);
1924 }
1925 }
1926
1927 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1928 for (i = 0; i < 2; i++)
1929 if (def_code[i] != LSHIFT_EXPR && def_code[i] != RSHIFT_EXPR)
1930 return false;
1931 else if (!has_single_use (arg[i]))
1932 return false;
1933 if (def_code[0] == def_code[1])
1934 return false;
1935
1936 /* If we've looked through narrowing conversions before, look through
1937 widening conversions from unsigned type with the same precision
1938 as rtype here. */
1939 if (TYPE_PRECISION (TREE_TYPE (def_arg1[0])) != TYPE_PRECISION (rtype))
1940 for (i = 0; i < 2; i++)
1941 {
1942 tree tem;
1943 enum tree_code code;
1944 defcodefor_name (def_arg1[i], &code, &tem, NULL);
1945 if (!CONVERT_EXPR_CODE_P (code)
1946 || !INTEGRAL_TYPE_P (TREE_TYPE (tem))
1947 || TYPE_PRECISION (TREE_TYPE (tem)) != TYPE_PRECISION (rtype))
1948 return false;
1949 def_arg1[i] = tem;
1950 }
1951 /* Both shifts have to use the same first operand. */
1952 if (!operand_equal_for_phi_arg_p (def_arg1[0], def_arg1[1])
1953 || !types_compatible_p (TREE_TYPE (def_arg1[0]),
1954 TREE_TYPE (def_arg1[1])))
1955 {
1956 if ((TYPE_PRECISION (TREE_TYPE (def_arg1[0]))
1957 != TYPE_PRECISION (TREE_TYPE (def_arg1[1])))
1958 || (TYPE_UNSIGNED (TREE_TYPE (def_arg1[0]))
1959 == TYPE_UNSIGNED (TREE_TYPE (def_arg1[1]))))
1960 return false;
1961
1962 /* Handle signed rotate; the RSHIFT_EXPR has to be done
1963 in unsigned type but LSHIFT_EXPR could be signed. */
1964 i = def_code[0] != RSHIFT_EXPR;
1965 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[i])))
1966 return false;
1967
1968 tree tem;
1969 enum tree_code code;
1970 defcodefor_name (def_arg1[i], &code, &tem, NULL);
1971 if (!CONVERT_EXPR_CODE_P (code)
1972 || !INTEGRAL_TYPE_P (TREE_TYPE (tem))
1973 || TYPE_PRECISION (TREE_TYPE (tem)) != TYPE_PRECISION (rtype))
1974 return false;
1975 def_arg1[i] = tem;
1976 if (!operand_equal_for_phi_arg_p (def_arg1[0], def_arg1[1])
1977 || !types_compatible_p (TREE_TYPE (def_arg1[0]),
1978 TREE_TYPE (def_arg1[1])))
1979 return false;
1980 }
1981 else if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[0])))
1982 return false;
1983
1984 /* CNT1 + CNT2 == B case above. */
1985 if (tree_fits_uhwi_p (def_arg2[0])
1986 && tree_fits_uhwi_p (def_arg2[1])
1987 && tree_to_uhwi (def_arg2[0])
1988 + tree_to_uhwi (def_arg2[1]) == TYPE_PRECISION (rtype))
1989 rotcnt = def_arg2[0];
1990 else if (TREE_CODE (def_arg2[0]) != SSA_NAME
1991 || TREE_CODE (def_arg2[1]) != SSA_NAME)
1992 return false;
1993 else
1994 {
1995 tree cdef_arg1[2], cdef_arg2[2], def_arg2_alt[2];
1996 enum tree_code cdef_code[2];
1997 gimple *def_arg_alt_stmt[2] = { NULL, NULL };
1998 int check_range = 0;
1999 gimple *check_range_stmt = NULL;
2000 /* Look through conversion of the shift count argument.
2001 The C/C++ FE cast any shift count argument to integer_type_node.
2002 The only problem might be if the shift count type maximum value
2003 is equal or smaller than number of bits in rtype. */
2004 for (i = 0; i < 2; i++)
2005 {
2006 def_arg2_alt[i] = def_arg2[i];
2007 defcodefor_name (def_arg2[i], &cdef_code[i],
2008 &cdef_arg1[i], &cdef_arg2[i]);
2009 if (CONVERT_EXPR_CODE_P (cdef_code[i])
2010 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1[i]))
2011 && TYPE_PRECISION (TREE_TYPE (cdef_arg1[i]))
2012 > floor_log2 (TYPE_PRECISION (rtype))
2013 && type_has_mode_precision_p (TREE_TYPE (cdef_arg1[i])))
2014 {
2015 def_arg2_alt[i] = cdef_arg1[i];
2016 if (TREE_CODE (def_arg2[i]) == SSA_NAME)
2017 def_arg_alt_stmt[i] = SSA_NAME_DEF_STMT (def_arg2[i]);
2018 defcodefor_name (def_arg2_alt[i], &cdef_code[i],
2019 &cdef_arg1[i], &cdef_arg2[i]);
2020 }
2021 else
2022 def_arg_alt_stmt[i] = def_arg_stmt[i];
2023 }
2024 for (i = 0; i < 2; i++)
2025 /* Check for one shift count being Y and the other B - Y,
2026 with optional casts. */
2027 if (cdef_code[i] == MINUS_EXPR
2028 && tree_fits_shwi_p (cdef_arg1[i])
2029 && tree_to_shwi (cdef_arg1[i]) == TYPE_PRECISION (rtype)
2030 && TREE_CODE (cdef_arg2[i]) == SSA_NAME)
2031 {
2032 tree tem;
2033 enum tree_code code;
2034
2035 if (cdef_arg2[i] == def_arg2[1 - i]
2036 || cdef_arg2[i] == def_arg2_alt[1 - i])
2037 {
2038 rotcnt = cdef_arg2[i];
2039 check_range = -1;
2040 if (cdef_arg2[i] == def_arg2[1 - i])
2041 check_range_stmt = def_arg_stmt[1 - i];
2042 else
2043 check_range_stmt = def_arg_alt_stmt[1 - i];
2044 break;
2045 }
2046 defcodefor_name (cdef_arg2[i], &code, &tem, NULL);
2047 if (CONVERT_EXPR_CODE_P (code)
2048 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
2049 && TYPE_PRECISION (TREE_TYPE (tem))
2050 > floor_log2 (TYPE_PRECISION (rtype))
2051 && type_has_mode_precision_p (TREE_TYPE (tem))
2052 && (tem == def_arg2[1 - i]
2053 || tem == def_arg2_alt[1 - i]))
2054 {
2055 rotcnt = tem;
2056 check_range = -1;
2057 if (tem == def_arg2[1 - i])
2058 check_range_stmt = def_arg_stmt[1 - i];
2059 else
2060 check_range_stmt = def_arg_alt_stmt[1 - i];
2061 break;
2062 }
2063 }
2064 /* The above sequence isn't safe for Y being 0,
2065 because then one of the shifts triggers undefined behavior.
2066 This alternative is safe even for rotation count of 0.
2067 One shift count is Y and the other (-Y) & (B - 1).
2068 Or one shift count is Y & (B - 1) and the other (-Y) & (B - 1). */
2069 else if (cdef_code[i] == BIT_AND_EXPR
2070 && pow2p_hwi (TYPE_PRECISION (rtype))
2071 && tree_fits_shwi_p (cdef_arg2[i])
2072 && tree_to_shwi (cdef_arg2[i])
2073 == TYPE_PRECISION (rtype) - 1
2074 && TREE_CODE (cdef_arg1[i]) == SSA_NAME
2075 && gimple_assign_rhs_code (stmt) == BIT_IOR_EXPR)
2076 {
2077 tree tem;
2078 enum tree_code code;
2079
2080 defcodefor_name (cdef_arg1[i], &code, &tem, NULL);
2081 if (CONVERT_EXPR_CODE_P (code)
2082 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
2083 && TYPE_PRECISION (TREE_TYPE (tem))
2084 > floor_log2 (TYPE_PRECISION (rtype))
2085 && type_has_mode_precision_p (TREE_TYPE (tem)))
2086 defcodefor_name (tem, &code, &tem, NULL);
2087
2088 if (code == NEGATE_EXPR)
2089 {
2090 if (tem == def_arg2[1 - i] || tem == def_arg2_alt[1 - i])
2091 {
2092 rotcnt = tem;
2093 check_range = 1;
2094 if (tem == def_arg2[1 - i])
2095 check_range_stmt = def_arg_stmt[1 - i];
2096 else
2097 check_range_stmt = def_arg_alt_stmt[1 - i];
2098 break;
2099 }
2100 tree tem2;
2101 defcodefor_name (tem, &code, &tem2, NULL);
2102 if (CONVERT_EXPR_CODE_P (code)
2103 && INTEGRAL_TYPE_P (TREE_TYPE (tem2))
2104 && TYPE_PRECISION (TREE_TYPE (tem2))
2105 > floor_log2 (TYPE_PRECISION (rtype))
2106 && type_has_mode_precision_p (TREE_TYPE (tem2)))
2107 {
2108 if (tem2 == def_arg2[1 - i]
2109 || tem2 == def_arg2_alt[1 - i])
2110 {
2111 rotcnt = tem2;
2112 check_range = 1;
2113 if (tem2 == def_arg2[1 - i])
2114 check_range_stmt = def_arg_stmt[1 - i];
2115 else
2116 check_range_stmt = def_arg_alt_stmt[1 - i];
2117 break;
2118 }
2119 }
2120 else
2121 tem2 = NULL_TREE;
2122
2123 if (cdef_code[1 - i] == BIT_AND_EXPR
2124 && tree_fits_shwi_p (cdef_arg2[1 - i])
2125 && tree_to_shwi (cdef_arg2[1 - i])
2126 == TYPE_PRECISION (rtype) - 1
2127 && TREE_CODE (cdef_arg1[1 - i]) == SSA_NAME)
2128 {
2129 if (tem == cdef_arg1[1 - i]
2130 || tem2 == cdef_arg1[1 - i])
2131 {
2132 rotcnt = def_arg2[1 - i];
2133 break;
2134 }
2135 tree tem3;
2136 defcodefor_name (cdef_arg1[1 - i], &code, &tem3, NULL);
2137 if (CONVERT_EXPR_CODE_P (code)
2138 && INTEGRAL_TYPE_P (TREE_TYPE (tem3))
2139 && TYPE_PRECISION (TREE_TYPE (tem3))
2140 > floor_log2 (TYPE_PRECISION (rtype))
2141 && type_has_mode_precision_p (TREE_TYPE (tem3)))
2142 {
2143 if (tem == tem3 || tem2 == tem3)
2144 {
2145 rotcnt = def_arg2[1 - i];
2146 break;
2147 }
2148 }
2149 }
2150 }
2151 }
2152 if (check_range && wider_prec > TYPE_PRECISION (rtype))
2153 {
2154 if (TREE_CODE (rotcnt) != SSA_NAME)
2155 return false;
2156 int_range_max r;
2157 range_query *q = get_range_query (cfun);
2158 if (q == get_global_range_query ())
2159 q = enable_ranger (cfun);
2160 if (!q->range_of_expr (r, rotcnt, check_range_stmt))
2161 {
2162 if (check_range > 0)
2163 return false;
2164 r.set_varying (TREE_TYPE (rotcnt));
2165 }
2166 int prec = TYPE_PRECISION (TREE_TYPE (rotcnt));
2167 signop sign = TYPE_SIGN (TREE_TYPE (rotcnt));
2168 wide_int min = wide_int::from (TYPE_PRECISION (rtype), prec, sign);
2169 wide_int max = wide_int::from (wider_prec - 1, prec, sign);
2170 if (check_range < 0)
2171 max = min;
2172 int_range<1> r2 (TREE_TYPE (rotcnt), min, max);
2173 r.intersect (r2);
2174 if (!r.undefined_p ())
2175 {
2176 if (check_range > 0)
2177 {
2178 int_range_max r3;
2179 for (int i = TYPE_PRECISION (rtype) + 1; i < wider_prec;
2180 i += TYPE_PRECISION (rtype))
2181 {
2182 int j = i + TYPE_PRECISION (rtype) - 2;
2183 min = wide_int::from (i, prec, sign);
2184 max = wide_int::from (MIN (j, wider_prec - 1),
2185 prec, sign);
2186 int_range<1> r4 (TREE_TYPE (rotcnt), min, max);
2187 r3.union_ (r4);
2188 }
2189 r.intersect (r3);
2190 if (!r.undefined_p ())
2191 return false;
2192 }
2193 add_masking = true;
2194 }
2195 }
2196 if (rotcnt == NULL_TREE)
2197 return false;
2198 swapped_p = i != 1;
2199 }
2200
2201 if (!useless_type_conversion_p (TREE_TYPE (def_arg2[0]),
2202 TREE_TYPE (rotcnt)))
2203 {
2204 g = gimple_build_assign (make_ssa_name (TREE_TYPE (def_arg2[0])),
2205 NOP_EXPR, rotcnt);
2206 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2207 rotcnt = gimple_assign_lhs (g);
2208 }
2209 if (add_masking)
2210 {
2211 g = gimple_build_assign (make_ssa_name (TREE_TYPE (rotcnt)),
2212 BIT_AND_EXPR, rotcnt,
2213 build_int_cst (TREE_TYPE (rotcnt),
2214 TYPE_PRECISION (rtype) - 1));
2215 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2216 rotcnt = gimple_assign_lhs (g);
2217 }
2218 lhs = gimple_assign_lhs (stmt);
2219 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
2220 lhs = make_ssa_name (TREE_TYPE (def_arg1[0]));
2221 g = gimple_build_assign (lhs,
2222 ((def_code[0] == LSHIFT_EXPR) ^ swapped_p)
2223 ? LROTATE_EXPR : RROTATE_EXPR, def_arg1[0], rotcnt);
2224 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
2225 {
2226 gsi_insert_before (gsi, g, GSI_SAME_STMT);
2227 g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, lhs);
2228 }
2229 gsi_replace (gsi, g, false);
2230 return true;
2231 }
2232
2233
2234 /* Check whether an array contains a valid ctz table. */
2235 static bool
check_ctz_array(tree ctor,unsigned HOST_WIDE_INT mulc,HOST_WIDE_INT & zero_val,unsigned shift,unsigned bits)2236 check_ctz_array (tree ctor, unsigned HOST_WIDE_INT mulc,
2237 HOST_WIDE_INT &zero_val, unsigned shift, unsigned bits)
2238 {
2239 tree elt, idx;
2240 unsigned HOST_WIDE_INT i, mask;
2241 unsigned matched = 0;
2242
2243 mask = ((HOST_WIDE_INT_1U << (bits - shift)) - 1) << shift;
2244
2245 zero_val = 0;
2246
2247 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), i, idx, elt)
2248 {
2249 if (TREE_CODE (idx) != INTEGER_CST || TREE_CODE (elt) != INTEGER_CST)
2250 return false;
2251 if (i > bits * 2)
2252 return false;
2253
2254 unsigned HOST_WIDE_INT index = tree_to_shwi (idx);
2255 HOST_WIDE_INT val = tree_to_shwi (elt);
2256
2257 if (index == 0)
2258 {
2259 zero_val = val;
2260 matched++;
2261 }
2262
2263 if (val >= 0 && val < bits && (((mulc << val) & mask) >> shift) == index)
2264 matched++;
2265
2266 if (matched > bits)
2267 return true;
2268 }
2269
2270 return false;
2271 }
2272
2273 /* Check whether a string contains a valid ctz table. */
2274 static bool
check_ctz_string(tree string,unsigned HOST_WIDE_INT mulc,HOST_WIDE_INT & zero_val,unsigned shift,unsigned bits)2275 check_ctz_string (tree string, unsigned HOST_WIDE_INT mulc,
2276 HOST_WIDE_INT &zero_val, unsigned shift, unsigned bits)
2277 {
2278 unsigned HOST_WIDE_INT len = TREE_STRING_LENGTH (string);
2279 unsigned HOST_WIDE_INT mask;
2280 unsigned matched = 0;
2281 const unsigned char *p = (const unsigned char *) TREE_STRING_POINTER (string);
2282
2283 if (len < bits || len > bits * 2)
2284 return false;
2285
2286 mask = ((HOST_WIDE_INT_1U << (bits - shift)) - 1) << shift;
2287
2288 zero_val = p[0];
2289
2290 for (unsigned i = 0; i < len; i++)
2291 if (p[i] < bits && (((mulc << p[i]) & mask) >> shift) == i)
2292 matched++;
2293
2294 return matched == bits;
2295 }
2296
2297 /* Recognize count trailing zeroes idiom.
2298 The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
2299 constant which when multiplied by a power of 2 creates a unique value
2300 in the top 5 or 6 bits. This is then indexed into a table which maps it
2301 to the number of trailing zeroes. Array[0] is returned so the caller can
2302 emit an appropriate sequence depending on whether ctz (0) is defined on
2303 the target. */
2304 static bool
optimize_count_trailing_zeroes(tree array_ref,tree x,tree mulc,tree tshift,HOST_WIDE_INT & zero_val)2305 optimize_count_trailing_zeroes (tree array_ref, tree x, tree mulc,
2306 tree tshift, HOST_WIDE_INT &zero_val)
2307 {
2308 tree type = TREE_TYPE (array_ref);
2309 tree array = TREE_OPERAND (array_ref, 0);
2310
2311 gcc_assert (TREE_CODE (mulc) == INTEGER_CST);
2312 gcc_assert (TREE_CODE (tshift) == INTEGER_CST);
2313
2314 tree input_type = TREE_TYPE (x);
2315 unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type));
2316
2317 /* Check the array element type is not wider than 32 bits and the input is
2318 an unsigned 32-bit or 64-bit type. */
2319 if (TYPE_PRECISION (type) > 32 || !TYPE_UNSIGNED (input_type))
2320 return false;
2321 if (input_bits != 32 && input_bits != 64)
2322 return false;
2323
2324 if (!direct_internal_fn_supported_p (IFN_CTZ, input_type, OPTIMIZE_FOR_BOTH))
2325 return false;
2326
2327 /* Check the lower bound of the array is zero. */
2328 tree low = array_ref_low_bound (array_ref);
2329 if (!low || !integer_zerop (low))
2330 return false;
2331
2332 unsigned shiftval = tree_to_shwi (tshift);
2333
2334 /* Check the shift extracts the top 5..7 bits. */
2335 if (shiftval < input_bits - 7 || shiftval > input_bits - 5)
2336 return false;
2337
2338 tree ctor = ctor_for_folding (array);
2339 if (!ctor)
2340 return false;
2341
2342 unsigned HOST_WIDE_INT val = tree_to_uhwi (mulc);
2343
2344 if (TREE_CODE (ctor) == CONSTRUCTOR)
2345 return check_ctz_array (ctor, val, zero_val, shiftval, input_bits);
2346
2347 if (TREE_CODE (ctor) == STRING_CST
2348 && TYPE_PRECISION (type) == CHAR_TYPE_SIZE)
2349 return check_ctz_string (ctor, val, zero_val, shiftval, input_bits);
2350
2351 return false;
2352 }
2353
2354 /* Match.pd function to match the ctz expression. */
2355 extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree));
2356
2357 static bool
simplify_count_trailing_zeroes(gimple_stmt_iterator * gsi)2358 simplify_count_trailing_zeroes (gimple_stmt_iterator *gsi)
2359 {
2360 gimple *stmt = gsi_stmt (*gsi);
2361 tree array_ref = gimple_assign_rhs1 (stmt);
2362 tree res_ops[3];
2363 HOST_WIDE_INT zero_val;
2364
2365 gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF);
2366
2367 if (!gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL))
2368 return false;
2369
2370 if (optimize_count_trailing_zeroes (array_ref, res_ops[0],
2371 res_ops[1], res_ops[2], zero_val))
2372 {
2373 tree type = TREE_TYPE (res_ops[0]);
2374 HOST_WIDE_INT ctz_val = 0;
2375 HOST_WIDE_INT type_size = tree_to_shwi (TYPE_SIZE (type));
2376 bool zero_ok
2377 = CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (type), ctz_val) == 2;
2378
2379 /* If the input value can't be zero, don't special case ctz (0). */
2380 if (tree_expr_nonzero_p (res_ops[0]))
2381 {
2382 zero_ok = true;
2383 zero_val = 0;
2384 ctz_val = 0;
2385 }
2386
2387 /* Skip if there is no value defined at zero, or if we can't easily
2388 return the correct value for zero. */
2389 if (!zero_ok)
2390 return false;
2391 if (zero_val != ctz_val && !(zero_val == 0 && ctz_val == type_size))
2392 return false;
2393
2394 gimple_seq seq = NULL;
2395 gimple *g;
2396 gcall *call = gimple_build_call_internal (IFN_CTZ, 1, res_ops[0]);
2397 gimple_set_location (call, gimple_location (stmt));
2398 gimple_set_lhs (call, make_ssa_name (integer_type_node));
2399 gimple_seq_add_stmt (&seq, call);
2400
2401 tree prev_lhs = gimple_call_lhs (call);
2402
2403 /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0. */
2404 if (zero_val == 0 && ctz_val == type_size)
2405 {
2406 g = gimple_build_assign (make_ssa_name (integer_type_node),
2407 BIT_AND_EXPR, prev_lhs,
2408 build_int_cst (integer_type_node,
2409 type_size - 1));
2410 gimple_set_location (g, gimple_location (stmt));
2411 gimple_seq_add_stmt (&seq, g);
2412 prev_lhs = gimple_assign_lhs (g);
2413 }
2414
2415 g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs);
2416 gimple_seq_add_stmt (&seq, g);
2417 gsi_replace_with_seq (gsi, seq, true);
2418 return true;
2419 }
2420
2421 return false;
2422 }
2423
2424
2425 /* Combine an element access with a shuffle. Returns true if there were
2426 any changes made, else it returns false. */
2427
2428 static bool
simplify_bitfield_ref(gimple_stmt_iterator * gsi)2429 simplify_bitfield_ref (gimple_stmt_iterator *gsi)
2430 {
2431 gimple *stmt = gsi_stmt (*gsi);
2432 gimple *def_stmt;
2433 tree op, op0, op1;
2434 tree elem_type;
2435 unsigned idx, size;
2436 enum tree_code code;
2437
2438 op = gimple_assign_rhs1 (stmt);
2439 gcc_checking_assert (TREE_CODE (op) == BIT_FIELD_REF);
2440
2441 op0 = TREE_OPERAND (op, 0);
2442 if (TREE_CODE (op0) != SSA_NAME
2443 || TREE_CODE (TREE_TYPE (op0)) != VECTOR_TYPE)
2444 return false;
2445
2446 def_stmt = get_prop_source_stmt (op0, false, NULL);
2447 if (!def_stmt || !can_propagate_from (def_stmt))
2448 return false;
2449
2450 op1 = TREE_OPERAND (op, 1);
2451 code = gimple_assign_rhs_code (def_stmt);
2452 elem_type = TREE_TYPE (TREE_TYPE (op0));
2453 if (TREE_TYPE (op) != elem_type)
2454 return false;
2455
2456 size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2457 if (maybe_ne (bit_field_size (op), size))
2458 return false;
2459
2460 if (code == VEC_PERM_EXPR
2461 && constant_multiple_p (bit_field_offset (op), size, &idx))
2462 {
2463 tree p, m, tem;
2464 unsigned HOST_WIDE_INT nelts;
2465 m = gimple_assign_rhs3 (def_stmt);
2466 if (TREE_CODE (m) != VECTOR_CST
2467 || !VECTOR_CST_NELTS (m).is_constant (&nelts))
2468 return false;
2469 idx = TREE_INT_CST_LOW (VECTOR_CST_ELT (m, idx));
2470 idx %= 2 * nelts;
2471 if (idx < nelts)
2472 {
2473 p = gimple_assign_rhs1 (def_stmt);
2474 }
2475 else
2476 {
2477 p = gimple_assign_rhs2 (def_stmt);
2478 idx -= nelts;
2479 }
2480 tem = build3 (BIT_FIELD_REF, TREE_TYPE (op),
2481 unshare_expr (p), op1, bitsize_int (idx * size));
2482 gimple_assign_set_rhs1 (stmt, tem);
2483 fold_stmt (gsi);
2484 update_stmt (gsi_stmt (*gsi));
2485 return true;
2486 }
2487
2488 return false;
2489 }
2490
2491 /* Determine whether applying the 2 permutations (mask1 then mask2)
2492 gives back one of the input. */
2493
2494 static int
is_combined_permutation_identity(tree mask1,tree mask2)2495 is_combined_permutation_identity (tree mask1, tree mask2)
2496 {
2497 tree mask;
2498 unsigned HOST_WIDE_INT nelts, i, j;
2499 bool maybe_identity1 = true;
2500 bool maybe_identity2 = true;
2501
2502 gcc_checking_assert (TREE_CODE (mask1) == VECTOR_CST
2503 && TREE_CODE (mask2) == VECTOR_CST);
2504 mask = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (mask1), mask1, mask1, mask2);
2505 if (mask == NULL_TREE || TREE_CODE (mask) != VECTOR_CST)
2506 return 0;
2507
2508 if (!VECTOR_CST_NELTS (mask).is_constant (&nelts))
2509 return 0;
2510 for (i = 0; i < nelts; i++)
2511 {
2512 tree val = VECTOR_CST_ELT (mask, i);
2513 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2514 j = TREE_INT_CST_LOW (val) & (2 * nelts - 1);
2515 if (j == i)
2516 maybe_identity2 = false;
2517 else if (j == i + nelts)
2518 maybe_identity1 = false;
2519 else
2520 return 0;
2521 }
2522 return maybe_identity1 ? 1 : maybe_identity2 ? 2 : 0;
2523 }
2524
2525 /* Combine a shuffle with its arguments. Returns 1 if there were any
2526 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
2527
2528 static int
simplify_permutation(gimple_stmt_iterator * gsi)2529 simplify_permutation (gimple_stmt_iterator *gsi)
2530 {
2531 gimple *stmt = gsi_stmt (*gsi);
2532 gimple *def_stmt = NULL;
2533 tree op0, op1, op2, op3, arg0, arg1;
2534 enum tree_code code, code2 = ERROR_MARK;
2535 bool single_use_op0 = false;
2536
2537 gcc_checking_assert (gimple_assign_rhs_code (stmt) == VEC_PERM_EXPR);
2538
2539 op0 = gimple_assign_rhs1 (stmt);
2540 op1 = gimple_assign_rhs2 (stmt);
2541 op2 = gimple_assign_rhs3 (stmt);
2542
2543 if (TREE_CODE (op2) != VECTOR_CST)
2544 return 0;
2545
2546 if (TREE_CODE (op0) == VECTOR_CST)
2547 {
2548 code = VECTOR_CST;
2549 arg0 = op0;
2550 }
2551 else if (TREE_CODE (op0) == SSA_NAME)
2552 {
2553 def_stmt = get_prop_source_stmt (op0, false, &single_use_op0);
2554 if (!def_stmt)
2555 return 0;
2556 code = gimple_assign_rhs_code (def_stmt);
2557 if (code == VIEW_CONVERT_EXPR)
2558 {
2559 tree rhs = gimple_assign_rhs1 (def_stmt);
2560 tree name = TREE_OPERAND (rhs, 0);
2561 if (TREE_CODE (name) != SSA_NAME)
2562 return 0;
2563 if (!has_single_use (name))
2564 single_use_op0 = false;
2565 /* Here we update the def_stmt through this VIEW_CONVERT_EXPR,
2566 but still keep the code to indicate it comes from
2567 VIEW_CONVERT_EXPR. */
2568 def_stmt = SSA_NAME_DEF_STMT (name);
2569 if (!def_stmt || !is_gimple_assign (def_stmt))
2570 return 0;
2571 if (gimple_assign_rhs_code (def_stmt) != CONSTRUCTOR)
2572 return 0;
2573 }
2574 if (!can_propagate_from (def_stmt))
2575 return 0;
2576 arg0 = gimple_assign_rhs1 (def_stmt);
2577 }
2578 else
2579 return 0;
2580
2581 /* Two consecutive shuffles. */
2582 if (code == VEC_PERM_EXPR)
2583 {
2584 tree orig;
2585 int ident;
2586
2587 if (op0 != op1)
2588 return 0;
2589 op3 = gimple_assign_rhs3 (def_stmt);
2590 if (TREE_CODE (op3) != VECTOR_CST)
2591 return 0;
2592 ident = is_combined_permutation_identity (op3, op2);
2593 if (!ident)
2594 return 0;
2595 orig = (ident == 1) ? gimple_assign_rhs1 (def_stmt)
2596 : gimple_assign_rhs2 (def_stmt);
2597 gimple_assign_set_rhs1 (stmt, unshare_expr (orig));
2598 gimple_assign_set_rhs_code (stmt, TREE_CODE (orig));
2599 gimple_set_num_ops (stmt, 2);
2600 update_stmt (stmt);
2601 return remove_prop_source_from_use (op0) ? 2 : 1;
2602 }
2603 else if (code == CONSTRUCTOR
2604 || code == VECTOR_CST
2605 || code == VIEW_CONVERT_EXPR)
2606 {
2607 if (op0 != op1)
2608 {
2609 if (TREE_CODE (op0) == SSA_NAME && !single_use_op0)
2610 return 0;
2611
2612 if (TREE_CODE (op1) == VECTOR_CST)
2613 arg1 = op1;
2614 else if (TREE_CODE (op1) == SSA_NAME)
2615 {
2616 gimple *def_stmt2 = get_prop_source_stmt (op1, true, NULL);
2617 if (!def_stmt2)
2618 return 0;
2619 code2 = gimple_assign_rhs_code (def_stmt2);
2620 if (code2 == VIEW_CONVERT_EXPR)
2621 {
2622 tree rhs = gimple_assign_rhs1 (def_stmt2);
2623 tree name = TREE_OPERAND (rhs, 0);
2624 if (TREE_CODE (name) != SSA_NAME)
2625 return 0;
2626 if (!has_single_use (name))
2627 return 0;
2628 def_stmt2 = SSA_NAME_DEF_STMT (name);
2629 if (!def_stmt2 || !is_gimple_assign (def_stmt2))
2630 return 0;
2631 if (gimple_assign_rhs_code (def_stmt2) != CONSTRUCTOR)
2632 return 0;
2633 }
2634 else if (code2 != CONSTRUCTOR && code2 != VECTOR_CST)
2635 return 0;
2636 if (!can_propagate_from (def_stmt2))
2637 return 0;
2638 arg1 = gimple_assign_rhs1 (def_stmt2);
2639 }
2640 else
2641 return 0;
2642 }
2643 else
2644 {
2645 /* Already used twice in this statement. */
2646 if (TREE_CODE (op0) == SSA_NAME && num_imm_uses (op0) > 2)
2647 return 0;
2648 arg1 = arg0;
2649 }
2650
2651 /* If there are any VIEW_CONVERT_EXPRs found when finding permutation
2652 operands source, check whether it's valid to transform and prepare
2653 the required new operands. */
2654 if (code == VIEW_CONVERT_EXPR || code2 == VIEW_CONVERT_EXPR)
2655 {
2656 /* Figure out the target vector type to which operands should be
2657 converted. If both are CONSTRUCTOR, the types should be the
2658 same, otherwise, use the one of CONSTRUCTOR. */
2659 tree tgt_type = NULL_TREE;
2660 if (code == VIEW_CONVERT_EXPR)
2661 {
2662 gcc_assert (gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR);
2663 code = CONSTRUCTOR;
2664 tgt_type = TREE_TYPE (arg0);
2665 }
2666 if (code2 == VIEW_CONVERT_EXPR)
2667 {
2668 tree arg1_type = TREE_TYPE (arg1);
2669 if (tgt_type == NULL_TREE)
2670 tgt_type = arg1_type;
2671 else if (tgt_type != arg1_type)
2672 return 0;
2673 }
2674
2675 if (!VECTOR_TYPE_P (tgt_type))
2676 return 0;
2677 tree op2_type = TREE_TYPE (op2);
2678
2679 /* Figure out the shrunk factor. */
2680 poly_uint64 tgt_units = TYPE_VECTOR_SUBPARTS (tgt_type);
2681 poly_uint64 op2_units = TYPE_VECTOR_SUBPARTS (op2_type);
2682 if (maybe_gt (tgt_units, op2_units))
2683 return 0;
2684 unsigned int factor;
2685 if (!constant_multiple_p (op2_units, tgt_units, &factor))
2686 return 0;
2687
2688 /* Build the new permutation control vector as target vector. */
2689 vec_perm_builder builder;
2690 if (!tree_to_vec_perm_builder (&builder, op2))
2691 return 0;
2692 vec_perm_indices indices (builder, 2, op2_units);
2693 vec_perm_indices new_indices;
2694 if (new_indices.new_shrunk_vector (indices, factor))
2695 {
2696 tree mask_type = tgt_type;
2697 if (!VECTOR_INTEGER_TYPE_P (mask_type))
2698 {
2699 tree elem_type = TREE_TYPE (mask_type);
2700 unsigned elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2701 tree int_type = build_nonstandard_integer_type (elem_size, 0);
2702 mask_type = build_vector_type (int_type, tgt_units);
2703 }
2704 op2 = vec_perm_indices_to_tree (mask_type, new_indices);
2705 }
2706 else
2707 return 0;
2708
2709 /* Convert the VECTOR_CST to the appropriate vector type. */
2710 if (tgt_type != TREE_TYPE (arg0))
2711 arg0 = fold_build1 (VIEW_CONVERT_EXPR, tgt_type, arg0);
2712 else if (tgt_type != TREE_TYPE (arg1))
2713 arg1 = fold_build1 (VIEW_CONVERT_EXPR, tgt_type, arg1);
2714 }
2715
2716 /* VIEW_CONVERT_EXPR should be updated to CONSTRUCTOR before. */
2717 gcc_assert (code == CONSTRUCTOR || code == VECTOR_CST);
2718
2719 /* Shuffle of a constructor. */
2720 bool ret = false;
2721 tree res_type = TREE_TYPE (arg0);
2722 tree opt = fold_ternary (VEC_PERM_EXPR, res_type, arg0, arg1, op2);
2723 if (!opt
2724 || (TREE_CODE (opt) != CONSTRUCTOR && TREE_CODE (opt) != VECTOR_CST))
2725 return 0;
2726 /* Found VIEW_CONVERT_EXPR before, need one explicit conversion. */
2727 if (res_type != TREE_TYPE (op0))
2728 {
2729 tree name = make_ssa_name (TREE_TYPE (opt));
2730 gimple *ass_stmt = gimple_build_assign (name, opt);
2731 gsi_insert_before (gsi, ass_stmt, GSI_SAME_STMT);
2732 opt = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (op0), name);
2733 }
2734 gimple_assign_set_rhs_from_tree (gsi, opt);
2735 update_stmt (gsi_stmt (*gsi));
2736 if (TREE_CODE (op0) == SSA_NAME)
2737 ret = remove_prop_source_from_use (op0);
2738 if (op0 != op1 && TREE_CODE (op1) == SSA_NAME)
2739 ret |= remove_prop_source_from_use (op1);
2740 return ret ? 2 : 1;
2741 }
2742
2743 return 0;
2744 }
2745
2746 /* Get the BIT_FIELD_REF definition of VAL, if any, looking through
2747 conversions with code CONV_CODE or update it if still ERROR_MARK.
2748 Return NULL_TREE if no such matching def was found. */
2749
2750 static tree
get_bit_field_ref_def(tree val,enum tree_code & conv_code)2751 get_bit_field_ref_def (tree val, enum tree_code &conv_code)
2752 {
2753 if (TREE_CODE (val) != SSA_NAME)
2754 return NULL_TREE ;
2755 gimple *def_stmt = get_prop_source_stmt (val, false, NULL);
2756 if (!def_stmt)
2757 return NULL_TREE;
2758 enum tree_code code = gimple_assign_rhs_code (def_stmt);
2759 if (code == FLOAT_EXPR
2760 || code == FIX_TRUNC_EXPR
2761 || CONVERT_EXPR_CODE_P (code))
2762 {
2763 tree op1 = gimple_assign_rhs1 (def_stmt);
2764 if (conv_code == ERROR_MARK)
2765 conv_code = code;
2766 else if (conv_code != code)
2767 return NULL_TREE;
2768 if (TREE_CODE (op1) != SSA_NAME)
2769 return NULL_TREE;
2770 def_stmt = SSA_NAME_DEF_STMT (op1);
2771 if (! is_gimple_assign (def_stmt))
2772 return NULL_TREE;
2773 code = gimple_assign_rhs_code (def_stmt);
2774 }
2775 if (code != BIT_FIELD_REF)
2776 return NULL_TREE;
2777 return gimple_assign_rhs1 (def_stmt);
2778 }
2779
2780 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
2781
2782 static bool
simplify_vector_constructor(gimple_stmt_iterator * gsi)2783 simplify_vector_constructor (gimple_stmt_iterator *gsi)
2784 {
2785 gimple *stmt = gsi_stmt (*gsi);
2786 tree op, orig[2], type, elem_type;
2787 unsigned elem_size, i;
2788 unsigned HOST_WIDE_INT nelts;
2789 unsigned HOST_WIDE_INT refnelts;
2790 enum tree_code conv_code;
2791 constructor_elt *elt;
2792
2793 op = gimple_assign_rhs1 (stmt);
2794 type = TREE_TYPE (op);
2795 gcc_checking_assert (TREE_CODE (op) == CONSTRUCTOR
2796 && TREE_CODE (type) == VECTOR_TYPE);
2797
2798 if (!TYPE_VECTOR_SUBPARTS (type).is_constant (&nelts))
2799 return false;
2800 elem_type = TREE_TYPE (type);
2801 elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2802
2803 orig[0] = NULL;
2804 orig[1] = NULL;
2805 conv_code = ERROR_MARK;
2806 bool maybe_ident = true;
2807 bool maybe_blend[2] = { true, true };
2808 tree one_constant = NULL_TREE;
2809 tree one_nonconstant = NULL_TREE;
2810 auto_vec<tree> constants;
2811 constants.safe_grow_cleared (nelts, true);
2812 auto_vec<std::pair<unsigned, unsigned>, 64> elts;
2813 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op), i, elt)
2814 {
2815 tree ref, op1;
2816 unsigned int elem;
2817
2818 if (i >= nelts)
2819 return false;
2820
2821 /* Look for elements extracted and possibly converted from
2822 another vector. */
2823 op1 = get_bit_field_ref_def (elt->value, conv_code);
2824 if (op1
2825 && TREE_CODE ((ref = TREE_OPERAND (op1, 0))) == SSA_NAME
2826 && VECTOR_TYPE_P (TREE_TYPE (ref))
2827 && useless_type_conversion_p (TREE_TYPE (op1),
2828 TREE_TYPE (TREE_TYPE (ref)))
2829 && constant_multiple_p (bit_field_offset (op1),
2830 bit_field_size (op1), &elem)
2831 && TYPE_VECTOR_SUBPARTS (TREE_TYPE (ref)).is_constant (&refnelts))
2832 {
2833 unsigned int j;
2834 for (j = 0; j < 2; ++j)
2835 {
2836 if (!orig[j])
2837 {
2838 if (j == 0
2839 || useless_type_conversion_p (TREE_TYPE (orig[0]),
2840 TREE_TYPE (ref)))
2841 break;
2842 }
2843 else if (ref == orig[j])
2844 break;
2845 }
2846 /* Found a suitable vector element. */
2847 if (j < 2)
2848 {
2849 orig[j] = ref;
2850 if (elem != i || j != 0)
2851 maybe_ident = false;
2852 if (elem != i)
2853 maybe_blend[j] = false;
2854 elts.safe_push (std::make_pair (j, elem));
2855 continue;
2856 }
2857 /* Else fallthru. */
2858 }
2859 /* Handle elements not extracted from a vector.
2860 1. constants by permuting with constant vector
2861 2. a unique non-constant element by permuting with a splat vector */
2862 if (orig[1]
2863 && orig[1] != error_mark_node)
2864 return false;
2865 orig[1] = error_mark_node;
2866 if (CONSTANT_CLASS_P (elt->value))
2867 {
2868 if (one_nonconstant)
2869 return false;
2870 if (!one_constant)
2871 one_constant = elt->value;
2872 constants[i] = elt->value;
2873 }
2874 else
2875 {
2876 if (one_constant)
2877 return false;
2878 if (!one_nonconstant)
2879 one_nonconstant = elt->value;
2880 else if (!operand_equal_p (one_nonconstant, elt->value, 0))
2881 return false;
2882 }
2883 elts.safe_push (std::make_pair (1, i));
2884 maybe_ident = false;
2885 }
2886 if (i < nelts)
2887 return false;
2888
2889 if (! orig[0]
2890 || ! VECTOR_TYPE_P (TREE_TYPE (orig[0])))
2891 return false;
2892 refnelts = TYPE_VECTOR_SUBPARTS (TREE_TYPE (orig[0])).to_constant ();
2893 /* We currently do not handle larger destination vectors. */
2894 if (refnelts < nelts)
2895 return false;
2896
2897 if (maybe_ident)
2898 {
2899 tree conv_src_type
2900 = (nelts != refnelts
2901 ? (conv_code != ERROR_MARK
2902 ? build_vector_type (TREE_TYPE (TREE_TYPE (orig[0])), nelts)
2903 : type)
2904 : TREE_TYPE (orig[0]));
2905 if (conv_code != ERROR_MARK
2906 && !supportable_convert_operation (conv_code, type, conv_src_type,
2907 &conv_code))
2908 {
2909 /* Only few targets implement direct conversion patterns so try
2910 some simple special cases via VEC_[UN]PACK[_FLOAT]_LO_EXPR. */
2911 optab optab;
2912 tree halfvectype, dblvectype;
2913 enum tree_code unpack_op;
2914
2915 if (!BYTES_BIG_ENDIAN)
2916 unpack_op = (FLOAT_TYPE_P (TREE_TYPE (type))
2917 ? VEC_UNPACK_FLOAT_LO_EXPR
2918 : VEC_UNPACK_LO_EXPR);
2919 else
2920 unpack_op = (FLOAT_TYPE_P (TREE_TYPE (type))
2921 ? VEC_UNPACK_FLOAT_HI_EXPR
2922 : VEC_UNPACK_HI_EXPR);
2923
2924 /* Conversions between DFP and FP have no special tree code
2925 but we cannot handle those since all relevant vector conversion
2926 optabs only have a single mode. */
2927 if (CONVERT_EXPR_CODE_P (conv_code)
2928 && FLOAT_TYPE_P (TREE_TYPE (type))
2929 && (DECIMAL_FLOAT_TYPE_P (TREE_TYPE (type))
2930 != DECIMAL_FLOAT_TYPE_P (TREE_TYPE (conv_src_type))))
2931 return false;
2932
2933 if (CONVERT_EXPR_CODE_P (conv_code)
2934 && (2 * TYPE_PRECISION (TREE_TYPE (TREE_TYPE (orig[0])))
2935 == TYPE_PRECISION (TREE_TYPE (type)))
2936 && mode_for_vector (as_a <scalar_mode>
2937 (TYPE_MODE (TREE_TYPE (TREE_TYPE (orig[0])))),
2938 nelts * 2).exists ()
2939 && (dblvectype
2940 = build_vector_type (TREE_TYPE (TREE_TYPE (orig[0])),
2941 nelts * 2))
2942 /* Only use it for vector modes or for vector booleans
2943 represented as scalar bitmasks. See PR95528. */
2944 && (VECTOR_MODE_P (TYPE_MODE (dblvectype))
2945 || VECTOR_BOOLEAN_TYPE_P (dblvectype))
2946 && (optab = optab_for_tree_code (unpack_op,
2947 dblvectype,
2948 optab_default))
2949 && (optab_handler (optab, TYPE_MODE (dblvectype))
2950 != CODE_FOR_nothing))
2951 {
2952 gimple_seq stmts = NULL;
2953 tree dbl;
2954 if (refnelts == nelts)
2955 {
2956 /* ??? Paradoxical subregs don't exist, so insert into
2957 the lower half of a wider zero vector. */
2958 dbl = gimple_build (&stmts, BIT_INSERT_EXPR, dblvectype,
2959 build_zero_cst (dblvectype), orig[0],
2960 bitsize_zero_node);
2961 }
2962 else if (refnelts == 2 * nelts)
2963 dbl = orig[0];
2964 else
2965 dbl = gimple_build (&stmts, BIT_FIELD_REF, dblvectype,
2966 orig[0], TYPE_SIZE (dblvectype),
2967 bitsize_zero_node);
2968 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
2969 gimple_assign_set_rhs_with_ops (gsi, unpack_op, dbl);
2970 }
2971 else if (CONVERT_EXPR_CODE_P (conv_code)
2972 && (TYPE_PRECISION (TREE_TYPE (TREE_TYPE (orig[0])))
2973 == 2 * TYPE_PRECISION (TREE_TYPE (type)))
2974 && mode_for_vector (as_a <scalar_mode>
2975 (TYPE_MODE
2976 (TREE_TYPE (TREE_TYPE (orig[0])))),
2977 nelts / 2).exists ()
2978 && (halfvectype
2979 = build_vector_type (TREE_TYPE (TREE_TYPE (orig[0])),
2980 nelts / 2))
2981 /* Only use it for vector modes or for vector booleans
2982 represented as scalar bitmasks. See PR95528. */
2983 && (VECTOR_MODE_P (TYPE_MODE (halfvectype))
2984 || VECTOR_BOOLEAN_TYPE_P (halfvectype))
2985 && (optab = optab_for_tree_code (VEC_PACK_TRUNC_EXPR,
2986 halfvectype,
2987 optab_default))
2988 && (optab_handler (optab, TYPE_MODE (halfvectype))
2989 != CODE_FOR_nothing))
2990 {
2991 gimple_seq stmts = NULL;
2992 tree low = gimple_build (&stmts, BIT_FIELD_REF, halfvectype,
2993 orig[0], TYPE_SIZE (halfvectype),
2994 bitsize_zero_node);
2995 tree hig = gimple_build (&stmts, BIT_FIELD_REF, halfvectype,
2996 orig[0], TYPE_SIZE (halfvectype),
2997 TYPE_SIZE (halfvectype));
2998 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
2999 gimple_assign_set_rhs_with_ops (gsi, VEC_PACK_TRUNC_EXPR,
3000 low, hig);
3001 }
3002 else
3003 return false;
3004 update_stmt (gsi_stmt (*gsi));
3005 return true;
3006 }
3007 if (nelts != refnelts)
3008 {
3009 gassign *lowpart
3010 = gimple_build_assign (make_ssa_name (conv_src_type),
3011 build3 (BIT_FIELD_REF, conv_src_type,
3012 orig[0], TYPE_SIZE (conv_src_type),
3013 bitsize_zero_node));
3014 gsi_insert_before (gsi, lowpart, GSI_SAME_STMT);
3015 orig[0] = gimple_assign_lhs (lowpart);
3016 }
3017 if (conv_code == ERROR_MARK)
3018 {
3019 tree src_type = TREE_TYPE (orig[0]);
3020 if (!useless_type_conversion_p (type, src_type))
3021 {
3022 gcc_assert (known_eq (TYPE_VECTOR_SUBPARTS (type),
3023 TYPE_VECTOR_SUBPARTS (src_type))
3024 && useless_type_conversion_p (TREE_TYPE (type),
3025 TREE_TYPE (src_type)));
3026 tree rhs = build1 (VIEW_CONVERT_EXPR, type, orig[0]);
3027 orig[0] = make_ssa_name (type);
3028 gassign *assign = gimple_build_assign (orig[0], rhs);
3029 gsi_insert_before (gsi, assign, GSI_SAME_STMT);
3030 }
3031 gimple_assign_set_rhs_from_tree (gsi, orig[0]);
3032 }
3033 else
3034 gimple_assign_set_rhs_with_ops (gsi, conv_code, orig[0],
3035 NULL_TREE, NULL_TREE);
3036 }
3037 else
3038 {
3039 /* If we combine a vector with a non-vector avoid cases where
3040 we'll obviously end up with more GIMPLE stmts which is when
3041 we'll later not fold this to a single insert into the vector
3042 and we had a single extract originally. See PR92819. */
3043 if (nelts == 2
3044 && refnelts > 2
3045 && orig[1] == error_mark_node
3046 && !maybe_blend[0])
3047 return false;
3048 tree mask_type, perm_type, conv_src_type;
3049 perm_type = TREE_TYPE (orig[0]);
3050 conv_src_type = (nelts == refnelts
3051 ? perm_type
3052 : build_vector_type (TREE_TYPE (perm_type), nelts));
3053 if (conv_code != ERROR_MARK
3054 && !supportable_convert_operation (conv_code, type, conv_src_type,
3055 &conv_code))
3056 return false;
3057
3058 /* Now that we know the number of elements of the source build the
3059 permute vector.
3060 ??? When the second vector has constant values we can shuffle
3061 it and its source indexes to make the permutation supported.
3062 For now it mimics a blend. */
3063 vec_perm_builder sel (refnelts, refnelts, 1);
3064 bool all_same_p = true;
3065 for (i = 0; i < elts.length (); ++i)
3066 {
3067 sel.quick_push (elts[i].second + elts[i].first * refnelts);
3068 all_same_p &= known_eq (sel[i], sel[0]);
3069 }
3070 /* And fill the tail with "something". It's really don't care,
3071 and ideally we'd allow VEC_PERM to have a smaller destination
3072 vector. As a heuristic:
3073
3074 (a) if what we have so far duplicates a single element, make the
3075 tail do the same
3076
3077 (b) otherwise preserve a uniform orig[0]. This facilitates
3078 later pattern-matching of VEC_PERM_EXPR to a BIT_INSERT_EXPR. */
3079 for (; i < refnelts; ++i)
3080 sel.quick_push (all_same_p
3081 ? sel[0]
3082 : (elts[0].second == 0 && elts[0].first == 0
3083 ? 0 : refnelts) + i);
3084 vec_perm_indices indices (sel, orig[1] ? 2 : 1, refnelts);
3085 if (!can_vec_perm_const_p (TYPE_MODE (perm_type), indices))
3086 return false;
3087 mask_type
3088 = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
3089 refnelts);
3090 if (GET_MODE_CLASS (TYPE_MODE (mask_type)) != MODE_VECTOR_INT
3091 || maybe_ne (GET_MODE_SIZE (TYPE_MODE (mask_type)),
3092 GET_MODE_SIZE (TYPE_MODE (perm_type))))
3093 return false;
3094 tree op2 = vec_perm_indices_to_tree (mask_type, indices);
3095 bool converted_orig1 = false;
3096 gimple_seq stmts = NULL;
3097 if (!orig[1])
3098 orig[1] = orig[0];
3099 else if (orig[1] == error_mark_node
3100 && one_nonconstant)
3101 {
3102 /* ??? We can see if we can safely convert to the original
3103 element type. */
3104 converted_orig1 = conv_code != ERROR_MARK;
3105 orig[1] = gimple_build_vector_from_val (&stmts, UNKNOWN_LOCATION,
3106 converted_orig1
3107 ? type : perm_type,
3108 one_nonconstant);
3109 }
3110 else if (orig[1] == error_mark_node)
3111 {
3112 /* ??? See if we can convert the vector to the original type. */
3113 converted_orig1 = conv_code != ERROR_MARK;
3114 unsigned n = converted_orig1 ? nelts : refnelts;
3115 tree_vector_builder vec (converted_orig1
3116 ? type : perm_type, n, 1);
3117 for (unsigned i = 0; i < n; ++i)
3118 if (i < nelts && constants[i])
3119 vec.quick_push (constants[i]);
3120 else
3121 /* ??? Push a don't-care value. */
3122 vec.quick_push (one_constant);
3123 orig[1] = vec.build ();
3124 }
3125 tree blend_op2 = NULL_TREE;
3126 if (converted_orig1)
3127 {
3128 /* Make sure we can do a blend in the target type. */
3129 vec_perm_builder sel (nelts, nelts, 1);
3130 for (i = 0; i < elts.length (); ++i)
3131 sel.quick_push (elts[i].first
3132 ? elts[i].second + nelts : i);
3133 vec_perm_indices indices (sel, 2, nelts);
3134 if (!can_vec_perm_const_p (TYPE_MODE (type), indices))
3135 return false;
3136 mask_type
3137 = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
3138 nelts);
3139 if (GET_MODE_CLASS (TYPE_MODE (mask_type)) != MODE_VECTOR_INT
3140 || maybe_ne (GET_MODE_SIZE (TYPE_MODE (mask_type)),
3141 GET_MODE_SIZE (TYPE_MODE (type))))
3142 return false;
3143 blend_op2 = vec_perm_indices_to_tree (mask_type, indices);
3144 }
3145 tree orig1_for_perm
3146 = converted_orig1 ? build_zero_cst (perm_type) : orig[1];
3147 tree res = gimple_build (&stmts, VEC_PERM_EXPR, perm_type,
3148 orig[0], orig1_for_perm, op2);
3149 if (nelts != refnelts)
3150 res = gimple_build (&stmts, BIT_FIELD_REF,
3151 conv_code != ERROR_MARK ? conv_src_type : type,
3152 res, TYPE_SIZE (type), bitsize_zero_node);
3153 if (conv_code != ERROR_MARK)
3154 res = gimple_build (&stmts, conv_code, type, res);
3155 else if (!useless_type_conversion_p (type, TREE_TYPE (res)))
3156 {
3157 gcc_assert (known_eq (TYPE_VECTOR_SUBPARTS (type),
3158 TYPE_VECTOR_SUBPARTS (perm_type))
3159 && useless_type_conversion_p (TREE_TYPE (type),
3160 TREE_TYPE (perm_type)));
3161 res = gimple_build (&stmts, VIEW_CONVERT_EXPR, type, res);
3162 }
3163 /* Blend in the actual constant. */
3164 if (converted_orig1)
3165 res = gimple_build (&stmts, VEC_PERM_EXPR, type,
3166 res, orig[1], blend_op2);
3167 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
3168 gimple_assign_set_rhs_with_ops (gsi, SSA_NAME, res);
3169 }
3170 update_stmt (gsi_stmt (*gsi));
3171 return true;
3172 }
3173
3174
3175 /* Rewrite the vector load at *GSI to component-wise loads if the load
3176 is only used in BIT_FIELD_REF extractions with eventual intermediate
3177 widening. */
3178
3179 static void
optimize_vector_load(gimple_stmt_iterator * gsi)3180 optimize_vector_load (gimple_stmt_iterator *gsi)
3181 {
3182 gimple *stmt = gsi_stmt (*gsi);
3183 tree lhs = gimple_assign_lhs (stmt);
3184 tree rhs = gimple_assign_rhs1 (stmt);
3185
3186 /* Gather BIT_FIELD_REFs to rewrite, looking through
3187 VEC_UNPACK_{LO,HI}_EXPR. */
3188 use_operand_p use_p;
3189 imm_use_iterator iter;
3190 bool rewrite = true;
3191 auto_vec<gimple *, 8> bf_stmts;
3192 auto_vec<tree, 8> worklist;
3193 worklist.quick_push (lhs);
3194 do
3195 {
3196 tree def = worklist.pop ();
3197 unsigned HOST_WIDE_INT def_eltsize
3198 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (TREE_TYPE (def))));
3199 FOR_EACH_IMM_USE_FAST (use_p, iter, def)
3200 {
3201 gimple *use_stmt = USE_STMT (use_p);
3202 if (is_gimple_debug (use_stmt))
3203 continue;
3204 if (!is_gimple_assign (use_stmt))
3205 {
3206 rewrite = false;
3207 break;
3208 }
3209 enum tree_code use_code = gimple_assign_rhs_code (use_stmt);
3210 tree use_rhs = gimple_assign_rhs1 (use_stmt);
3211 if (use_code == BIT_FIELD_REF
3212 && TREE_OPERAND (use_rhs, 0) == def
3213 /* If its on the VEC_UNPACK_{HI,LO}_EXPR
3214 def need to verify it is element aligned. */
3215 && (def == lhs
3216 || (known_eq (bit_field_size (use_rhs), def_eltsize)
3217 && constant_multiple_p (bit_field_offset (use_rhs),
3218 def_eltsize)
3219 /* We can simulate the VEC_UNPACK_{HI,LO}_EXPR
3220 via a NOP_EXPR only for integral types.
3221 ??? Support VEC_UNPACK_FLOAT_{HI,LO}_EXPR. */
3222 && INTEGRAL_TYPE_P (TREE_TYPE (use_rhs)))))
3223 {
3224 bf_stmts.safe_push (use_stmt);
3225 continue;
3226 }
3227 /* Walk through one level of VEC_UNPACK_{LO,HI}_EXPR. */
3228 if (def == lhs
3229 && (use_code == VEC_UNPACK_HI_EXPR
3230 || use_code == VEC_UNPACK_LO_EXPR)
3231 && use_rhs == lhs)
3232 {
3233 worklist.safe_push (gimple_assign_lhs (use_stmt));
3234 continue;
3235 }
3236 rewrite = false;
3237 break;
3238 }
3239 if (!rewrite)
3240 break;
3241 }
3242 while (!worklist.is_empty ());
3243
3244 if (!rewrite)
3245 {
3246 gsi_next (gsi);
3247 return;
3248 }
3249 /* We now have all ultimate uses of the load to rewrite in bf_stmts. */
3250
3251 /* Prepare the original ref to be wrapped in adjusted BIT_FIELD_REFs.
3252 For TARGET_MEM_REFs we have to separate the LEA from the reference. */
3253 tree load_rhs = rhs;
3254 if (TREE_CODE (load_rhs) == TARGET_MEM_REF)
3255 {
3256 if (TREE_CODE (TREE_OPERAND (load_rhs, 0)) == ADDR_EXPR)
3257 mark_addressable (TREE_OPERAND (TREE_OPERAND (load_rhs, 0), 0));
3258 tree ptrtype = build_pointer_type (TREE_TYPE (load_rhs));
3259 tree tem = make_ssa_name (ptrtype);
3260 gimple *new_stmt
3261 = gimple_build_assign (tem, build1 (ADDR_EXPR, TREE_TYPE (tem),
3262 unshare_expr (load_rhs)));
3263 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
3264 load_rhs = build2_loc (EXPR_LOCATION (load_rhs),
3265 MEM_REF, TREE_TYPE (load_rhs), tem,
3266 build_int_cst
3267 (TREE_TYPE (TREE_OPERAND (load_rhs, 1)), 0));
3268 }
3269
3270 /* Rewrite the BIT_FIELD_REFs to be actual loads, re-emitting them at
3271 the place of the original load. */
3272 for (gimple *use_stmt : bf_stmts)
3273 {
3274 tree bfr = gimple_assign_rhs1 (use_stmt);
3275 tree new_rhs = unshare_expr (load_rhs);
3276 if (TREE_OPERAND (bfr, 0) != lhs)
3277 {
3278 /* When the BIT_FIELD_REF is on the promoted vector we have to
3279 adjust it and emit a conversion afterwards. */
3280 gimple *def_stmt
3281 = SSA_NAME_DEF_STMT (TREE_OPERAND (bfr, 0));
3282 enum tree_code def_code
3283 = gimple_assign_rhs_code (def_stmt);
3284
3285 /* The adjusted BIT_FIELD_REF is of the promotion source
3286 vector size and at half of the offset... */
3287 new_rhs = fold_build3 (BIT_FIELD_REF,
3288 TREE_TYPE (TREE_TYPE (lhs)),
3289 new_rhs,
3290 TYPE_SIZE (TREE_TYPE (TREE_TYPE (lhs))),
3291 size_binop (EXACT_DIV_EXPR,
3292 TREE_OPERAND (bfr, 2),
3293 bitsize_int (2)));
3294 /* ... and offsetted by half of the vector if VEC_UNPACK_HI_EXPR. */
3295 if (def_code == (!BYTES_BIG_ENDIAN
3296 ? VEC_UNPACK_HI_EXPR : VEC_UNPACK_LO_EXPR))
3297 TREE_OPERAND (new_rhs, 2)
3298 = size_binop (PLUS_EXPR, TREE_OPERAND (new_rhs, 2),
3299 size_binop (EXACT_DIV_EXPR,
3300 TYPE_SIZE (TREE_TYPE (lhs)),
3301 bitsize_int (2)));
3302 tree tem = make_ssa_name (TREE_TYPE (TREE_TYPE (lhs)));
3303 gimple *new_stmt = gimple_build_assign (tem, new_rhs);
3304 location_t loc = gimple_location (use_stmt);
3305 gimple_set_location (new_stmt, loc);
3306 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
3307 /* Perform scalar promotion. */
3308 new_stmt = gimple_build_assign (gimple_assign_lhs (use_stmt),
3309 NOP_EXPR, tem);
3310 gimple_set_location (new_stmt, loc);
3311 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
3312 }
3313 else
3314 {
3315 /* When the BIT_FIELD_REF is on the original load result
3316 we can just wrap that. */
3317 tree new_rhs = fold_build3 (BIT_FIELD_REF, TREE_TYPE (bfr),
3318 unshare_expr (load_rhs),
3319 TREE_OPERAND (bfr, 1),
3320 TREE_OPERAND (bfr, 2));
3321 gimple *new_stmt = gimple_build_assign (gimple_assign_lhs (use_stmt),
3322 new_rhs);
3323 location_t loc = gimple_location (use_stmt);
3324 gimple_set_location (new_stmt, loc);
3325 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
3326 }
3327 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3328 unlink_stmt_vdef (use_stmt);
3329 gsi_remove (&gsi2, true);
3330 }
3331
3332 /* Finally get rid of the intermediate stmts. */
3333 gimple *use_stmt;
3334 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
3335 {
3336 if (is_gimple_debug (use_stmt))
3337 {
3338 if (gimple_debug_bind_p (use_stmt))
3339 {
3340 gimple_debug_bind_reset_value (use_stmt);
3341 update_stmt (use_stmt);
3342 }
3343 continue;
3344 }
3345 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3346 unlink_stmt_vdef (use_stmt);
3347 release_defs (use_stmt);
3348 gsi_remove (&gsi2, true);
3349 }
3350 /* And the original load. */
3351 release_defs (stmt);
3352 gsi_remove (gsi, true);
3353 }
3354
3355
3356 /* Primitive "lattice" function for gimple_simplify. */
3357
3358 static tree
fwprop_ssa_val(tree name)3359 fwprop_ssa_val (tree name)
3360 {
3361 /* First valueize NAME. */
3362 if (TREE_CODE (name) == SSA_NAME
3363 && SSA_NAME_VERSION (name) < lattice.length ())
3364 {
3365 tree val = lattice[SSA_NAME_VERSION (name)];
3366 if (val)
3367 name = val;
3368 }
3369 /* We continue matching along SSA use-def edges for SSA names
3370 that are not single-use. Currently there are no patterns
3371 that would cause any issues with that. */
3372 return name;
3373 }
3374
3375 /* Main entry point for the forward propagation and statement combine
3376 optimizer. */
3377
3378 namespace {
3379
3380 const pass_data pass_data_forwprop =
3381 {
3382 GIMPLE_PASS, /* type */
3383 "forwprop", /* name */
3384 OPTGROUP_NONE, /* optinfo_flags */
3385 TV_TREE_FORWPROP, /* tv_id */
3386 ( PROP_cfg | PROP_ssa ), /* properties_required */
3387 0, /* properties_provided */
3388 0, /* properties_destroyed */
3389 0, /* todo_flags_start */
3390 TODO_update_ssa, /* todo_flags_finish */
3391 };
3392
3393 class pass_forwprop : public gimple_opt_pass
3394 {
3395 public:
pass_forwprop(gcc::context * ctxt)3396 pass_forwprop (gcc::context *ctxt)
3397 : gimple_opt_pass (pass_data_forwprop, ctxt)
3398 {}
3399
3400 /* opt_pass methods: */
clone()3401 opt_pass * clone () { return new pass_forwprop (m_ctxt); }
gate(function *)3402 virtual bool gate (function *) { return flag_tree_forwprop; }
3403 virtual unsigned int execute (function *);
3404
3405 }; // class pass_forwprop
3406
3407 unsigned int
execute(function * fun)3408 pass_forwprop::execute (function *fun)
3409 {
3410 unsigned int todoflags = 0;
3411
3412 cfg_changed = false;
3413
3414 /* Combine stmts with the stmts defining their operands. Do that
3415 in an order that guarantees visiting SSA defs before SSA uses. */
3416 lattice.create (num_ssa_names);
3417 lattice.quick_grow_cleared (num_ssa_names);
3418 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (fun));
3419 int postorder_num = pre_and_rev_post_order_compute_fn (cfun, NULL,
3420 postorder, false);
3421 auto_vec<gimple *, 4> to_fixup;
3422 auto_vec<gimple *, 32> to_remove;
3423 to_purge = BITMAP_ALLOC (NULL);
3424 for (int i = 0; i < postorder_num; ++i)
3425 {
3426 gimple_stmt_iterator gsi;
3427 basic_block bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
3428
3429 /* Record degenerate PHIs in the lattice. */
3430 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
3431 gsi_next (&si))
3432 {
3433 gphi *phi = si.phi ();
3434 tree res = gimple_phi_result (phi);
3435 if (virtual_operand_p (res))
3436 continue;
3437
3438 use_operand_p use_p;
3439 ssa_op_iter it;
3440 tree first = NULL_TREE;
3441 bool all_same = true;
3442 FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
3443 {
3444 tree use = USE_FROM_PTR (use_p);
3445 if (! first)
3446 first = use;
3447 else if (! operand_equal_p (first, use, 0))
3448 {
3449 all_same = false;
3450 break;
3451 }
3452 }
3453 if (all_same)
3454 {
3455 if (may_propagate_copy (res, first))
3456 to_remove.safe_push (phi);
3457 fwprop_set_lattice_val (res, first);
3458 }
3459 }
3460
3461 /* Apply forward propagation to all stmts in the basic-block.
3462 Note we update GSI within the loop as necessary. */
3463 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
3464 {
3465 gimple *stmt = gsi_stmt (gsi);
3466 tree lhs, rhs;
3467 enum tree_code code;
3468
3469 if (!is_gimple_assign (stmt))
3470 {
3471 gsi_next (&gsi);
3472 continue;
3473 }
3474
3475 lhs = gimple_assign_lhs (stmt);
3476 rhs = gimple_assign_rhs1 (stmt);
3477 code = gimple_assign_rhs_code (stmt);
3478 if (TREE_CODE (lhs) != SSA_NAME
3479 || has_zero_uses (lhs))
3480 {
3481 gsi_next (&gsi);
3482 continue;
3483 }
3484
3485 /* If this statement sets an SSA_NAME to an address,
3486 try to propagate the address into the uses of the SSA_NAME. */
3487 if ((code == ADDR_EXPR
3488 /* Handle pointer conversions on invariant addresses
3489 as well, as this is valid gimple. */
3490 || (CONVERT_EXPR_CODE_P (code)
3491 && TREE_CODE (rhs) == ADDR_EXPR
3492 && POINTER_TYPE_P (TREE_TYPE (lhs))))
3493 && TREE_CODE (TREE_OPERAND (rhs, 0)) != TARGET_MEM_REF)
3494 {
3495 tree base = get_base_address (TREE_OPERAND (rhs, 0));
3496 if ((!base
3497 || !DECL_P (base)
3498 || decl_address_invariant_p (base))
3499 && !stmt_references_abnormal_ssa_name (stmt)
3500 && forward_propagate_addr_expr (lhs, rhs, true))
3501 {
3502 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
3503 release_defs (stmt);
3504 gsi_remove (&gsi, true);
3505 }
3506 else
3507 gsi_next (&gsi);
3508 }
3509 else if (code == POINTER_PLUS_EXPR)
3510 {
3511 tree off = gimple_assign_rhs2 (stmt);
3512 if (TREE_CODE (off) == INTEGER_CST
3513 && can_propagate_from (stmt)
3514 && !simple_iv_increment_p (stmt)
3515 /* ??? Better adjust the interface to that function
3516 instead of building new trees here. */
3517 && forward_propagate_addr_expr
3518 (lhs,
3519 build1_loc (gimple_location (stmt),
3520 ADDR_EXPR, TREE_TYPE (rhs),
3521 fold_build2 (MEM_REF,
3522 TREE_TYPE (TREE_TYPE (rhs)),
3523 rhs,
3524 fold_convert (ptr_type_node,
3525 off))), true))
3526 {
3527 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
3528 release_defs (stmt);
3529 gsi_remove (&gsi, true);
3530 }
3531 else if (is_gimple_min_invariant (rhs))
3532 {
3533 /* Make sure to fold &a[0] + off_1 here. */
3534 fold_stmt_inplace (&gsi);
3535 update_stmt (stmt);
3536 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
3537 gsi_next (&gsi);
3538 }
3539 else
3540 gsi_next (&gsi);
3541 }
3542 else if (TREE_CODE (TREE_TYPE (lhs)) == COMPLEX_TYPE
3543 && gimple_assign_load_p (stmt)
3544 && !gimple_has_volatile_ops (stmt)
3545 && (TREE_CODE (gimple_assign_rhs1 (stmt))
3546 != TARGET_MEM_REF)
3547 && !stmt_can_throw_internal (cfun, stmt))
3548 {
3549 /* Rewrite loads used only in real/imagpart extractions to
3550 component-wise loads. */
3551 use_operand_p use_p;
3552 imm_use_iterator iter;
3553 bool rewrite = true;
3554 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
3555 {
3556 gimple *use_stmt = USE_STMT (use_p);
3557 if (is_gimple_debug (use_stmt))
3558 continue;
3559 if (!is_gimple_assign (use_stmt)
3560 || (gimple_assign_rhs_code (use_stmt) != REALPART_EXPR
3561 && gimple_assign_rhs_code (use_stmt) != IMAGPART_EXPR)
3562 || TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) != lhs)
3563 {
3564 rewrite = false;
3565 break;
3566 }
3567 }
3568 if (rewrite)
3569 {
3570 gimple *use_stmt;
3571 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
3572 {
3573 if (is_gimple_debug (use_stmt))
3574 {
3575 if (gimple_debug_bind_p (use_stmt))
3576 {
3577 gimple_debug_bind_reset_value (use_stmt);
3578 update_stmt (use_stmt);
3579 }
3580 continue;
3581 }
3582
3583 tree new_rhs = build1 (gimple_assign_rhs_code (use_stmt),
3584 TREE_TYPE (TREE_TYPE (rhs)),
3585 unshare_expr (rhs));
3586 gimple *new_stmt
3587 = gimple_build_assign (gimple_assign_lhs (use_stmt),
3588 new_rhs);
3589
3590 location_t loc = gimple_location (use_stmt);
3591 gimple_set_location (new_stmt, loc);
3592 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3593 unlink_stmt_vdef (use_stmt);
3594 gsi_remove (&gsi2, true);
3595
3596 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
3597 }
3598
3599 release_defs (stmt);
3600 gsi_remove (&gsi, true);
3601 }
3602 else
3603 gsi_next (&gsi);
3604 }
3605 else if (TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE
3606 && (TYPE_MODE (TREE_TYPE (lhs)) == BLKmode
3607 /* After vector lowering rewrite all loads, but
3608 initially do not since this conflicts with
3609 vector CONSTRUCTOR to shuffle optimization. */
3610 || (fun->curr_properties & PROP_gimple_lvec))
3611 && gimple_assign_load_p (stmt)
3612 && !gimple_has_volatile_ops (stmt)
3613 && !stmt_can_throw_internal (cfun, stmt)
3614 && (!VAR_P (rhs) || !DECL_HARD_REGISTER (rhs)))
3615 optimize_vector_load (&gsi);
3616
3617 else if (code == COMPLEX_EXPR)
3618 {
3619 /* Rewrite stores of a single-use complex build expression
3620 to component-wise stores. */
3621 use_operand_p use_p;
3622 gimple *use_stmt;
3623 if (single_imm_use (lhs, &use_p, &use_stmt)
3624 && gimple_store_p (use_stmt)
3625 && !gimple_has_volatile_ops (use_stmt)
3626 && is_gimple_assign (use_stmt)
3627 && (TREE_CODE (gimple_assign_lhs (use_stmt))
3628 != TARGET_MEM_REF))
3629 {
3630 tree use_lhs = gimple_assign_lhs (use_stmt);
3631 if (auto_var_p (use_lhs))
3632 DECL_NOT_GIMPLE_REG_P (use_lhs) = 1;
3633 tree new_lhs = build1 (REALPART_EXPR,
3634 TREE_TYPE (TREE_TYPE (use_lhs)),
3635 unshare_expr (use_lhs));
3636 gimple *new_stmt = gimple_build_assign (new_lhs, rhs);
3637 location_t loc = gimple_location (use_stmt);
3638 gimple_set_location (new_stmt, loc);
3639 gimple_set_vuse (new_stmt, gimple_vuse (use_stmt));
3640 gimple_set_vdef (new_stmt, make_ssa_name (gimple_vop (cfun)));
3641 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
3642 gimple_set_vuse (use_stmt, gimple_vdef (new_stmt));
3643 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3644 gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
3645
3646 new_lhs = build1 (IMAGPART_EXPR,
3647 TREE_TYPE (TREE_TYPE (use_lhs)),
3648 unshare_expr (use_lhs));
3649 gimple_assign_set_lhs (use_stmt, new_lhs);
3650 gimple_assign_set_rhs1 (use_stmt, gimple_assign_rhs2 (stmt));
3651 update_stmt (use_stmt);
3652
3653 release_defs (stmt);
3654 gsi_remove (&gsi, true);
3655 }
3656 else
3657 gsi_next (&gsi);
3658 }
3659 else if (code == CONSTRUCTOR
3660 && VECTOR_TYPE_P (TREE_TYPE (rhs))
3661 && TYPE_MODE (TREE_TYPE (rhs)) == BLKmode
3662 && CONSTRUCTOR_NELTS (rhs) > 0
3663 && (!VECTOR_TYPE_P (TREE_TYPE (CONSTRUCTOR_ELT (rhs, 0)->value))
3664 || (TYPE_MODE (TREE_TYPE (CONSTRUCTOR_ELT (rhs, 0)->value))
3665 != BLKmode)))
3666 {
3667 /* Rewrite stores of a single-use vector constructors
3668 to component-wise stores if the mode isn't supported. */
3669 use_operand_p use_p;
3670 gimple *use_stmt;
3671 if (single_imm_use (lhs, &use_p, &use_stmt)
3672 && gimple_store_p (use_stmt)
3673 && !gimple_has_volatile_ops (use_stmt)
3674 && !stmt_can_throw_internal (cfun, use_stmt)
3675 && is_gimple_assign (use_stmt)
3676 && (TREE_CODE (gimple_assign_lhs (use_stmt))
3677 != TARGET_MEM_REF))
3678 {
3679 tree elt_t = TREE_TYPE (CONSTRUCTOR_ELT (rhs, 0)->value);
3680 unsigned HOST_WIDE_INT elt_w
3681 = tree_to_uhwi (TYPE_SIZE (elt_t));
3682 unsigned HOST_WIDE_INT n
3683 = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (rhs)));
3684 tree use_lhs = gimple_assign_lhs (use_stmt);
3685 if (auto_var_p (use_lhs))
3686 DECL_NOT_GIMPLE_REG_P (use_lhs) = 1;
3687 for (unsigned HOST_WIDE_INT bi = 0; bi < n; bi += elt_w)
3688 {
3689 unsigned HOST_WIDE_INT ci = bi / elt_w;
3690 tree new_rhs;
3691 if (ci < CONSTRUCTOR_NELTS (rhs))
3692 new_rhs = CONSTRUCTOR_ELT (rhs, ci)->value;
3693 else
3694 new_rhs = build_zero_cst (elt_t);
3695 tree new_lhs = build3 (BIT_FIELD_REF,
3696 elt_t,
3697 unshare_expr (use_lhs),
3698 bitsize_int (elt_w),
3699 bitsize_int (bi));
3700 gimple *new_stmt = gimple_build_assign (new_lhs, new_rhs);
3701 location_t loc = gimple_location (use_stmt);
3702 gimple_set_location (new_stmt, loc);
3703 gimple_set_vuse (new_stmt, gimple_vuse (use_stmt));
3704 gimple_set_vdef (new_stmt,
3705 make_ssa_name (gimple_vop (cfun)));
3706 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
3707 gimple_set_vuse (use_stmt, gimple_vdef (new_stmt));
3708 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3709 gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
3710 }
3711 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
3712 unlink_stmt_vdef (use_stmt);
3713 release_defs (use_stmt);
3714 gsi_remove (&gsi2, true);
3715 release_defs (stmt);
3716 gsi_remove (&gsi, true);
3717 }
3718 else
3719 gsi_next (&gsi);
3720 }
3721 else
3722 gsi_next (&gsi);
3723 }
3724
3725 /* Combine stmts with the stmts defining their operands.
3726 Note we update GSI within the loop as necessary. */
3727 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3728 {
3729 gimple *stmt = gsi_stmt (gsi);
3730
3731 /* Mark stmt as potentially needing revisiting. */
3732 gimple_set_plf (stmt, GF_PLF_1, false);
3733
3734 /* Substitute from our lattice. We need to do so only once. */
3735 bool substituted_p = false;
3736 use_operand_p usep;
3737 ssa_op_iter iter;
3738 FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_USE)
3739 {
3740 tree use = USE_FROM_PTR (usep);
3741 tree val = fwprop_ssa_val (use);
3742 if (val && val != use && may_propagate_copy (use, val))
3743 {
3744 propagate_value (usep, val);
3745 substituted_p = true;
3746 }
3747 }
3748 if (substituted_p
3749 && is_gimple_assign (stmt)
3750 && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
3751 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
3752
3753 bool changed;
3754 do
3755 {
3756 gimple *orig_stmt = stmt = gsi_stmt (gsi);
3757 bool was_noreturn = (is_gimple_call (stmt)
3758 && gimple_call_noreturn_p (stmt));
3759 changed = false;
3760
3761 if (fold_stmt (&gsi, fwprop_ssa_val))
3762 {
3763 changed = true;
3764 stmt = gsi_stmt (gsi);
3765 /* Cleanup the CFG if we simplified a condition to
3766 true or false. */
3767 if (gcond *cond = dyn_cast <gcond *> (stmt))
3768 if (gimple_cond_true_p (cond)
3769 || gimple_cond_false_p (cond))
3770 cfg_changed = true;
3771 }
3772
3773 if (changed || substituted_p)
3774 {
3775 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
3776 bitmap_set_bit (to_purge, bb->index);
3777 if (!was_noreturn
3778 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt))
3779 to_fixup.safe_push (stmt);
3780 update_stmt (stmt);
3781 substituted_p = false;
3782 }
3783
3784 switch (gimple_code (stmt))
3785 {
3786 case GIMPLE_ASSIGN:
3787 {
3788 tree rhs1 = gimple_assign_rhs1 (stmt);
3789 enum tree_code code = gimple_assign_rhs_code (stmt);
3790
3791 if (code == COND_EXPR)
3792 {
3793 /* In this case the entire COND_EXPR is in rhs1. */
3794 if (forward_propagate_into_cond (&gsi))
3795 {
3796 changed = true;
3797 stmt = gsi_stmt (gsi);
3798 }
3799 }
3800 else if (TREE_CODE_CLASS (code) == tcc_comparison)
3801 {
3802 int did_something;
3803 did_something = forward_propagate_into_comparison (&gsi);
3804 if (maybe_clean_or_replace_eh_stmt (stmt, gsi_stmt (gsi)))
3805 bitmap_set_bit (to_purge, bb->index);
3806 if (did_something == 2)
3807 cfg_changed = true;
3808 changed = did_something != 0;
3809 }
3810 else if ((code == PLUS_EXPR
3811 || code == BIT_IOR_EXPR
3812 || code == BIT_XOR_EXPR)
3813 && simplify_rotate (&gsi))
3814 changed = true;
3815 else if (code == VEC_PERM_EXPR)
3816 {
3817 int did_something = simplify_permutation (&gsi);
3818 if (did_something == 2)
3819 cfg_changed = true;
3820 changed = did_something != 0;
3821 }
3822 else if (code == BIT_FIELD_REF)
3823 changed = simplify_bitfield_ref (&gsi);
3824 else if (code == CONSTRUCTOR
3825 && TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
3826 changed = simplify_vector_constructor (&gsi);
3827 else if (code == ARRAY_REF)
3828 changed = simplify_count_trailing_zeroes (&gsi);
3829 break;
3830 }
3831
3832 case GIMPLE_SWITCH:
3833 changed = simplify_gimple_switch (as_a <gswitch *> (stmt));
3834 break;
3835
3836 case GIMPLE_COND:
3837 {
3838 int did_something = forward_propagate_into_gimple_cond
3839 (as_a <gcond *> (stmt));
3840 if (did_something == 2)
3841 cfg_changed = true;
3842 changed = did_something != 0;
3843 break;
3844 }
3845
3846 case GIMPLE_CALL:
3847 {
3848 tree callee = gimple_call_fndecl (stmt);
3849 if (callee != NULL_TREE
3850 && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
3851 changed = simplify_builtin_call (&gsi, callee);
3852 break;
3853 }
3854
3855 default:;
3856 }
3857
3858 if (changed)
3859 {
3860 /* If the stmt changed then re-visit it and the statements
3861 inserted before it. */
3862 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
3863 if (gimple_plf (gsi_stmt (gsi), GF_PLF_1))
3864 break;
3865 if (gsi_end_p (gsi))
3866 gsi = gsi_start_bb (bb);
3867 else
3868 gsi_next (&gsi);
3869 }
3870 }
3871 while (changed);
3872
3873 /* Stmt no longer needs to be revisited. */
3874 stmt = gsi_stmt (gsi);
3875 gcc_checking_assert (!gimple_plf (stmt, GF_PLF_1));
3876 gimple_set_plf (stmt, GF_PLF_1, true);
3877
3878 /* Fill up the lattice. */
3879 if (gimple_assign_single_p (stmt))
3880 {
3881 tree lhs = gimple_assign_lhs (stmt);
3882 tree rhs = gimple_assign_rhs1 (stmt);
3883 if (TREE_CODE (lhs) == SSA_NAME)
3884 {
3885 tree val = lhs;
3886 if (TREE_CODE (rhs) == SSA_NAME)
3887 val = fwprop_ssa_val (rhs);
3888 else if (is_gimple_min_invariant (rhs))
3889 val = rhs;
3890 /* If we can propagate the lattice-value mark the
3891 stmt for removal. */
3892 if (val != lhs
3893 && may_propagate_copy (lhs, val))
3894 to_remove.safe_push (stmt);
3895 fwprop_set_lattice_val (lhs, val);
3896 }
3897 }
3898 else if (gimple_nop_p (stmt))
3899 to_remove.safe_push (stmt);
3900 }
3901
3902 /* Substitute in destination PHI arguments. */
3903 edge_iterator ei;
3904 edge e;
3905 FOR_EACH_EDGE (e, ei, bb->succs)
3906 for (gphi_iterator gsi = gsi_start_phis (e->dest);
3907 !gsi_end_p (gsi); gsi_next (&gsi))
3908 {
3909 gphi *phi = gsi.phi ();
3910 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
3911 tree arg = USE_FROM_PTR (use_p);
3912 if (TREE_CODE (arg) != SSA_NAME
3913 || virtual_operand_p (arg))
3914 continue;
3915 tree val = fwprop_ssa_val (arg);
3916 if (val != arg
3917 && may_propagate_copy (arg, val))
3918 propagate_value (use_p, val);
3919 }
3920 }
3921 free (postorder);
3922 lattice.release ();
3923
3924 /* Remove stmts in reverse order to make debug stmt creation possible. */
3925 while (!to_remove.is_empty())
3926 {
3927 gimple *stmt = to_remove.pop ();
3928 if (dump_file && (dump_flags & TDF_DETAILS))
3929 {
3930 fprintf (dump_file, "Removing dead stmt ");
3931 print_gimple_stmt (dump_file, stmt, 0);
3932 fprintf (dump_file, "\n");
3933 }
3934 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
3935 if (gimple_code (stmt) == GIMPLE_PHI)
3936 remove_phi_node (&gsi, true);
3937 else
3938 {
3939 unlink_stmt_vdef (stmt);
3940 gsi_remove (&gsi, true);
3941 release_defs (stmt);
3942 }
3943 }
3944
3945 /* Fixup stmts that became noreturn calls. This may require splitting
3946 blocks and thus isn't possible during the walk. Do this
3947 in reverse order so we don't inadvertedly remove a stmt we want to
3948 fixup by visiting a dominating now noreturn call first. */
3949 while (!to_fixup.is_empty ())
3950 {
3951 gimple *stmt = to_fixup.pop ();
3952 if (dump_file && dump_flags & TDF_DETAILS)
3953 {
3954 fprintf (dump_file, "Fixing up noreturn call ");
3955 print_gimple_stmt (dump_file, stmt, 0);
3956 fprintf (dump_file, "\n");
3957 }
3958 cfg_changed |= fixup_noreturn_call (stmt);
3959 }
3960
3961 cfg_changed |= gimple_purge_all_dead_eh_edges (to_purge);
3962 BITMAP_FREE (to_purge);
3963
3964 if (get_range_query (cfun) != get_global_range_query ())
3965 disable_ranger (cfun);
3966
3967 if (cfg_changed)
3968 todoflags |= TODO_cleanup_cfg;
3969
3970 return todoflags;
3971 }
3972
3973 } // anon namespace
3974
3975 gimple_opt_pass *
make_pass_forwprop(gcc::context * ctxt)3976 make_pass_forwprop (gcc::context *ctxt)
3977 {
3978 return new pass_forwprop (ctxt);
3979 }
3980