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

source code of gcc/tree-ssa-forwprop.cc