1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
25 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
37 #include "basic-block.h"
38 #include "gimple-pretty-print.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
43 #include "gimple-expr.h"
47 #include "gimple-iterator.h"
48 #include "gimplify-me.h"
49 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
57 #include "tree-pass.h"
58 #include "langhooks.h"
60 #include "diagnostic.h"
64 #include "tree-ssa-propagate.h"
65 #include "tree-ssa-dom.h"
67 #include "tree-cfgcleanup.h"
68 #include "tree-into-ssa.h"
71 /* This pass propagates the RHS of assignment statements into use
72 sites of the LHS of the assignment. It's basically a specialized
73 form of tree combination. It is hoped all of this can disappear
74 when we have a generalized tree combiner.
76 One class of common cases we handle is forward propagating a single use
77 variable into a COND_EXPR.
81 if (x) goto ... else goto ...
83 Will be transformed into:
86 if (a COND b) goto ... else goto ...
88 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
90 Or (assuming c1 and c2 are constants):
94 if (x EQ/NEQ c2) goto ... else goto ...
96 Will be transformed into:
99 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
101 Similarly for x = a - c1.
107 if (x) goto ... else goto ...
109 Will be transformed into:
112 if (a == 0) goto ... else goto ...
114 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
115 For these cases, we propagate A into all, possibly more than one,
116 COND_EXPRs that use X.
122 if (x) goto ... else goto ...
124 Will be transformed into:
127 if (a != 0) goto ... else goto ...
129 (Assuming a is an integral type and x is a boolean or x is an
130 integral and a is a boolean.)
132 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
133 For these cases, we propagate A into all, possibly more than one,
134 COND_EXPRs that use X.
136 In addition to eliminating the variable and the statement which assigns
137 a value to the variable, we may be able to later thread the jump without
138 adding insane complexity in the dominator optimizer.
140 Also note these transformations can cascade. We handle this by having
141 a worklist of COND_EXPR statements to examine. As we make a change to
142 a statement, we put it back on the worklist to examine on the next
143 iteration of the main loop.
145 A second class of propagation opportunities arises for ADDR_EXPR
156 ptr = (type1*)&type2var;
159 Will get turned into (if type1 and type2 are the same size
160 and neither have volatile on them):
161 res = VIEW_CONVERT_EXPR<type1>(type2var)
166 ptr2 = ptr + <constant>;
170 ptr2 = &x[constant/elementsize];
175 offset = index * element_size;
176 offset_p = (pointer) offset;
177 ptr2 = ptr + offset_p
179 Will get turned into:
187 Provided that decl has known alignment >= 2, will get turned into
191 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
192 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
195 This will (of course) be extended as other needs arise. */
197 static bool forward_propagate_addr_expr (tree
, tree
, bool);
199 /* Set to true if we delete dead edges during the optimization. */
200 static bool cfg_changed
;
202 static tree
rhs_to_tree (tree type
, gimple stmt
);
204 /* Get the next statement we can propagate NAME's value into skipping
205 trivial copies. Returns the statement that is suitable as a
206 propagation destination or NULL_TREE if there is no such one.
207 This only returns destinations in a single-use chain. FINAL_NAME_P
208 if non-NULL is written to the ssa name that represents the use. */
211 get_prop_dest_stmt (tree name
, tree
*final_name_p
)
217 /* If name has multiple uses, bail out. */
218 if (!single_imm_use (name
, &use
, &use_stmt
))
221 /* If this is not a trivial copy, we found it. */
222 if (!gimple_assign_ssa_name_copy_p (use_stmt
)
223 || gimple_assign_rhs1 (use_stmt
) != name
)
226 /* Continue searching uses of the copy destination. */
227 name
= gimple_assign_lhs (use_stmt
);
231 *final_name_p
= name
;
236 /* Get the statement we can propagate from into NAME skipping
237 trivial copies. Returns the statement which defines the
238 propagation source or NULL_TREE if there is no such one.
239 If SINGLE_USE_ONLY is set considers only sources which have
240 a single use chain up to NAME. If SINGLE_USE_P is non-null,
241 it is set to whether the chain to NAME is a single use chain
242 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
245 get_prop_source_stmt (tree name
, bool single_use_only
, bool *single_use_p
)
247 bool single_use
= true;
250 gimple def_stmt
= SSA_NAME_DEF_STMT (name
);
252 if (!has_single_use (name
))
259 /* If name is defined by a PHI node or is the default def, bail out. */
260 if (!is_gimple_assign (def_stmt
))
263 /* If def_stmt is a simple copy, continue looking. */
264 if (gimple_assign_rhs_code (def_stmt
) == SSA_NAME
)
265 name
= gimple_assign_rhs1 (def_stmt
);
268 if (!single_use_only
&& single_use_p
)
269 *single_use_p
= single_use
;
276 /* Checks if the destination ssa name in DEF_STMT can be used as
277 propagation source. Returns true if so, otherwise false. */
280 can_propagate_from (gimple def_stmt
)
282 gcc_assert (is_gimple_assign (def_stmt
));
284 /* If the rhs has side-effects we cannot propagate from it. */
285 if (gimple_has_volatile_ops (def_stmt
))
288 /* If the rhs is a load we cannot propagate from it. */
289 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_reference
290 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
)) == tcc_declaration
)
293 /* Constants can be always propagated. */
294 if (gimple_assign_single_p (def_stmt
)
295 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt
)))
298 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
299 if (stmt_references_abnormal_ssa_name (def_stmt
))
302 /* If the definition is a conversion of a pointer to a function type,
303 then we can not apply optimizations as some targets require
304 function pointers to be canonicalized and in this case this
305 optimization could eliminate a necessary canonicalization. */
306 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
308 tree rhs
= gimple_assign_rhs1 (def_stmt
);
309 if (POINTER_TYPE_P (TREE_TYPE (rhs
))
310 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs
))) == FUNCTION_TYPE
)
317 /* Remove a chain of dead statements starting at the definition of
318 NAME. The chain is linked via the first operand of the defining statements.
319 If NAME was replaced in its only use then this function can be used
320 to clean up dead stmts. The function handles already released SSA
322 Returns true if cleanup-cfg has to run. */
325 remove_prop_source_from_use (tree name
)
327 gimple_stmt_iterator gsi
;
329 bool cfg_changed
= false;
334 if (SSA_NAME_IN_FREE_LIST (name
)
335 || SSA_NAME_IS_DEFAULT_DEF (name
)
336 || !has_zero_uses (name
))
339 stmt
= SSA_NAME_DEF_STMT (name
);
340 if (gimple_code (stmt
) == GIMPLE_PHI
341 || gimple_has_side_effects (stmt
))
344 bb
= gimple_bb (stmt
);
345 gsi
= gsi_for_stmt (stmt
);
346 unlink_stmt_vdef (stmt
);
347 if (gsi_remove (&gsi
, true))
348 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
351 name
= is_gimple_assign (stmt
) ? gimple_assign_rhs1 (stmt
) : NULL_TREE
;
352 } while (name
&& TREE_CODE (name
) == SSA_NAME
);
357 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
358 converted to type TYPE.
360 This should disappear, but is needed so we can combine expressions and use
361 the fold() interfaces. Long term, we need to develop folding and combine
362 routines that deal with gimple exclusively . */
365 rhs_to_tree (tree type
, gimple stmt
)
367 location_t loc
= gimple_location (stmt
);
368 enum tree_code code
= gimple_assign_rhs_code (stmt
);
369 if (get_gimple_rhs_class (code
) == GIMPLE_TERNARY_RHS
)
370 return fold_build3_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
371 gimple_assign_rhs2 (stmt
),
372 gimple_assign_rhs3 (stmt
));
373 else if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
374 return fold_build2_loc (loc
, code
, type
, gimple_assign_rhs1 (stmt
),
375 gimple_assign_rhs2 (stmt
));
376 else if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
377 return build1 (code
, type
, gimple_assign_rhs1 (stmt
));
378 else if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
379 return gimple_assign_rhs1 (stmt
);
384 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
385 the folded result in a form suitable for COND_EXPR_COND or
386 NULL_TREE, if there is no suitable simplified form. If
387 INVARIANT_ONLY is true only gimple_min_invariant results are
388 considered simplified. */
391 combine_cond_expr_cond (gimple stmt
, enum tree_code code
, tree type
,
392 tree op0
, tree op1
, bool invariant_only
)
396 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
398 fold_defer_overflow_warnings ();
399 t
= fold_binary_loc (gimple_location (stmt
), code
, type
, op0
, op1
);
402 fold_undefer_overflow_warnings (false, NULL
, 0);
406 /* Require that we got a boolean type out if we put one in. */
407 gcc_assert (TREE_CODE (TREE_TYPE (t
)) == TREE_CODE (type
));
409 /* Canonicalize the combined condition for use in a COND_EXPR. */
410 t
= canonicalize_cond_expr_cond (t
);
412 /* Bail out if we required an invariant but didn't get one. */
413 if (!t
|| (invariant_only
&& !is_gimple_min_invariant (t
)))
415 fold_undefer_overflow_warnings (false, NULL
, 0);
419 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt
), stmt
, 0);
424 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
425 of its operand. Return a new comparison tree or NULL_TREE if there
426 were no simplifying combines. */
429 forward_propagate_into_comparison_1 (gimple stmt
,
430 enum tree_code code
, tree type
,
433 tree tmp
= NULL_TREE
;
434 tree rhs0
= NULL_TREE
, rhs1
= NULL_TREE
;
435 bool single_use0_p
= false, single_use1_p
= false;
437 /* For comparisons use the first operand, that is likely to
438 simplify comparisons against constants. */
439 if (TREE_CODE (op0
) == SSA_NAME
)
441 gimple def_stmt
= get_prop_source_stmt (op0
, false, &single_use0_p
);
442 if (def_stmt
&& can_propagate_from (def_stmt
))
444 rhs0
= rhs_to_tree (TREE_TYPE (op1
), def_stmt
);
445 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
446 rhs0
, op1
, !single_use0_p
);
452 /* If that wasn't successful, try the second operand. */
453 if (TREE_CODE (op1
) == SSA_NAME
)
455 gimple def_stmt
= get_prop_source_stmt (op1
, false, &single_use1_p
);
456 if (def_stmt
&& can_propagate_from (def_stmt
))
458 rhs1
= rhs_to_tree (TREE_TYPE (op0
), def_stmt
);
459 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
460 op0
, rhs1
, !single_use1_p
);
466 /* If that wasn't successful either, try both operands. */
467 if (rhs0
!= NULL_TREE
468 && rhs1
!= NULL_TREE
)
469 tmp
= combine_cond_expr_cond (stmt
, code
, type
,
471 !(single_use0_p
&& single_use1_p
));
476 /* Propagate from the ssa name definition statements of the assignment
477 from a comparison at *GSI into the conditional if that simplifies it.
478 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
479 otherwise returns 0. */
482 forward_propagate_into_comparison (gimple_stmt_iterator
*gsi
)
484 gimple stmt
= gsi_stmt (*gsi
);
486 bool cfg_changed
= false;
487 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
488 tree rhs1
= gimple_assign_rhs1 (stmt
);
489 tree rhs2
= gimple_assign_rhs2 (stmt
);
491 /* Combine the comparison with defining statements. */
492 tmp
= forward_propagate_into_comparison_1 (stmt
,
493 gimple_assign_rhs_code (stmt
),
495 if (tmp
&& useless_type_conversion_p (type
, TREE_TYPE (tmp
)))
497 gimple_assign_set_rhs_from_tree (gsi
, tmp
);
499 update_stmt (gsi_stmt (*gsi
));
501 if (TREE_CODE (rhs1
) == SSA_NAME
)
502 cfg_changed
|= remove_prop_source_from_use (rhs1
);
503 if (TREE_CODE (rhs2
) == SSA_NAME
)
504 cfg_changed
|= remove_prop_source_from_use (rhs2
);
505 return cfg_changed
? 2 : 1;
511 /* Propagate from the ssa name definition statements of COND_EXPR
512 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
513 Returns zero if no statement was changed, one if there were
514 changes and two if cfg_cleanup needs to run.
516 This must be kept in sync with forward_propagate_into_cond. */
519 forward_propagate_into_gimple_cond (gimple stmt
)
522 enum tree_code code
= gimple_cond_code (stmt
);
523 bool cfg_changed
= false;
524 tree rhs1
= gimple_cond_lhs (stmt
);
525 tree rhs2
= gimple_cond_rhs (stmt
);
527 /* We can do tree combining on SSA_NAME and comparison expressions. */
528 if (TREE_CODE_CLASS (gimple_cond_code (stmt
)) != tcc_comparison
)
531 tmp
= forward_propagate_into_comparison_1 (stmt
, code
,
536 if (dump_file
&& tmp
)
538 fprintf (dump_file
, " Replaced '");
539 print_gimple_expr (dump_file
, stmt
, 0, 0);
540 fprintf (dump_file
, "' with '");
541 print_generic_expr (dump_file
, tmp
, 0);
542 fprintf (dump_file
, "'\n");
545 gimple_cond_set_condition_from_tree (stmt
, unshare_expr (tmp
));
548 if (TREE_CODE (rhs1
) == SSA_NAME
)
549 cfg_changed
|= remove_prop_source_from_use (rhs1
);
550 if (TREE_CODE (rhs2
) == SSA_NAME
)
551 cfg_changed
|= remove_prop_source_from_use (rhs2
);
552 return (cfg_changed
|| is_gimple_min_invariant (tmp
)) ? 2 : 1;
555 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
556 if ((TREE_CODE (TREE_TYPE (rhs1
)) == BOOLEAN_TYPE
557 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
558 && TYPE_PRECISION (TREE_TYPE (rhs1
)) == 1))
560 && integer_zerop (rhs2
))
562 && integer_onep (rhs2
))))
564 basic_block bb
= gimple_bb (stmt
);
565 gimple_cond_set_code (stmt
, NE_EXPR
);
566 gimple_cond_set_rhs (stmt
, build_zero_cst (TREE_TYPE (rhs1
)));
567 EDGE_SUCC (bb
, 0)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
568 EDGE_SUCC (bb
, 1)->flags
^= (EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
576 /* Propagate from the ssa name definition statements of COND_EXPR
577 in the rhs of statement STMT into the conditional if that simplifies it.
578 Returns true zero if the stmt was changed. */
581 forward_propagate_into_cond (gimple_stmt_iterator
*gsi_p
)
583 gimple stmt
= gsi_stmt (*gsi_p
);
584 tree tmp
= NULL_TREE
;
585 tree cond
= gimple_assign_rhs1 (stmt
);
586 enum tree_code code
= gimple_assign_rhs_code (stmt
);
589 /* We can do tree combining on SSA_NAME and comparison expressions. */
590 if (COMPARISON_CLASS_P (cond
))
591 tmp
= forward_propagate_into_comparison_1 (stmt
, TREE_CODE (cond
),
593 TREE_OPERAND (cond
, 0),
594 TREE_OPERAND (cond
, 1));
595 else if (TREE_CODE (cond
) == SSA_NAME
)
597 enum tree_code def_code
;
599 gimple def_stmt
= get_prop_source_stmt (name
, true, NULL
);
600 if (!def_stmt
|| !can_propagate_from (def_stmt
))
603 def_code
= gimple_assign_rhs_code (def_stmt
);
604 if (TREE_CODE_CLASS (def_code
) == tcc_comparison
)
605 tmp
= fold_build2_loc (gimple_location (def_stmt
),
608 gimple_assign_rhs1 (def_stmt
),
609 gimple_assign_rhs2 (def_stmt
));
610 else if (code
== COND_EXPR
611 && ((def_code
== BIT_NOT_EXPR
612 && TYPE_PRECISION (TREE_TYPE (cond
)) == 1)
613 || (def_code
== BIT_XOR_EXPR
614 && integer_onep (gimple_assign_rhs2 (def_stmt
)))))
616 tmp
= gimple_assign_rhs1 (def_stmt
);
622 && is_gimple_condexpr (tmp
))
624 if (dump_file
&& tmp
)
626 fprintf (dump_file
, " Replaced '");
627 print_generic_expr (dump_file
, cond
, 0);
628 fprintf (dump_file
, "' with '");
629 print_generic_expr (dump_file
, tmp
, 0);
630 fprintf (dump_file
, "'\n");
633 if ((code
== VEC_COND_EXPR
) ? integer_all_onesp (tmp
)
634 : integer_onep (tmp
))
635 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs2 (stmt
));
636 else if (integer_zerop (tmp
))
637 gimple_assign_set_rhs_from_tree (gsi_p
, gimple_assign_rhs3 (stmt
));
640 gimple_assign_set_rhs1 (stmt
, unshare_expr (tmp
));
643 tree t
= gimple_assign_rhs2 (stmt
);
644 gimple_assign_set_rhs2 (stmt
, gimple_assign_rhs3 (stmt
));
645 gimple_assign_set_rhs3 (stmt
, t
);
648 stmt
= gsi_stmt (*gsi_p
);
657 /* Propagate from the ssa name definition statements of COND_EXPR
658 values in the rhs of statement STMT into the conditional arms
659 if that simplifies it.
660 Returns true if the stmt was changed. */
663 combine_cond_exprs (gimple_stmt_iterator
*gsi_p
)
665 gimple stmt
= gsi_stmt (*gsi_p
);
666 tree cond
, val1
, val2
;
667 bool changed
= false;
669 cond
= gimple_assign_rhs1 (stmt
);
670 val1
= gimple_assign_rhs2 (stmt
);
671 if (TREE_CODE (val1
) == SSA_NAME
)
673 gimple def_stmt
= SSA_NAME_DEF_STMT (val1
);
674 if (is_gimple_assign (def_stmt
)
675 && gimple_assign_rhs_code (def_stmt
) == gimple_assign_rhs_code (stmt
)
676 && operand_equal_p (gimple_assign_rhs1 (def_stmt
), cond
, 0))
678 val1
= unshare_expr (gimple_assign_rhs2 (def_stmt
));
679 gimple_assign_set_rhs2 (stmt
, val1
);
683 val2
= gimple_assign_rhs3 (stmt
);
684 if (TREE_CODE (val2
) == SSA_NAME
)
686 gimple def_stmt
= SSA_NAME_DEF_STMT (val2
);
687 if (is_gimple_assign (def_stmt
)
688 && gimple_assign_rhs_code (def_stmt
) == gimple_assign_rhs_code (stmt
)
689 && operand_equal_p (gimple_assign_rhs1 (def_stmt
), cond
, 0))
691 val2
= unshare_expr (gimple_assign_rhs3 (def_stmt
));
692 gimple_assign_set_rhs3 (stmt
, val2
);
696 if (operand_equal_p (val1
, val2
, 0))
698 gimple_assign_set_rhs_from_tree (gsi_p
, val1
);
699 stmt
= gsi_stmt (*gsi_p
);
709 /* We've just substituted an ADDR_EXPR into stmt. Update all the
710 relevant data structures to match. */
713 tidy_after_forward_propagate_addr (gimple stmt
)
715 /* We may have turned a trapping insn into a non-trapping insn. */
716 if (maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
717 && gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
720 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == ADDR_EXPR
)
721 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt
));
724 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
725 ADDR_EXPR <whatever>.
727 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
728 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
729 node or for recovery of array indexing from pointer arithmetic.
731 Return true if the propagation was successful (the propagation can
732 be not totally successful, yet things may have been changed). */
735 forward_propagate_addr_expr_1 (tree name
, tree def_rhs
,
736 gimple_stmt_iterator
*use_stmt_gsi
,
739 tree lhs
, rhs
, rhs2
, array_ref
;
740 gimple use_stmt
= gsi_stmt (*use_stmt_gsi
);
741 enum tree_code rhs_code
;
744 gcc_assert (TREE_CODE (def_rhs
) == ADDR_EXPR
);
746 lhs
= gimple_assign_lhs (use_stmt
);
747 rhs_code
= gimple_assign_rhs_code (use_stmt
);
748 rhs
= gimple_assign_rhs1 (use_stmt
);
750 /* Do not perform copy-propagation but recurse through copy chains. */
751 if (TREE_CODE (lhs
) == SSA_NAME
752 && rhs_code
== SSA_NAME
)
753 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
755 /* The use statement could be a conversion. Recurse to the uses of the
756 lhs as copyprop does not copy through pointer to integer to pointer
757 conversions and FRE does not catch all cases either.
758 Treat the case of a single-use name and
759 a conversion to def_rhs type separate, though. */
760 if (TREE_CODE (lhs
) == SSA_NAME
761 && CONVERT_EXPR_CODE_P (rhs_code
))
763 /* If there is a point in a conversion chain where the types match
764 so we can remove a conversion re-materialize the address here
767 && useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (def_rhs
)))
769 gimple_assign_set_rhs1 (use_stmt
, unshare_expr (def_rhs
));
770 gimple_assign_set_rhs_code (use_stmt
, TREE_CODE (def_rhs
));
774 /* Else recurse if the conversion preserves the address value. */
775 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs
))
776 || POINTER_TYPE_P (TREE_TYPE (lhs
)))
777 && (TYPE_PRECISION (TREE_TYPE (lhs
))
778 >= TYPE_PRECISION (TREE_TYPE (def_rhs
))))
779 return forward_propagate_addr_expr (lhs
, def_rhs
, single_use_p
);
784 /* If this isn't a conversion chain from this on we only can propagate
785 into compatible pointer contexts. */
786 if (!types_compatible_p (TREE_TYPE (name
), TREE_TYPE (def_rhs
)))
789 /* Propagate through constant pointer adjustments. */
790 if (TREE_CODE (lhs
) == SSA_NAME
791 && rhs_code
== POINTER_PLUS_EXPR
793 && TREE_CODE (gimple_assign_rhs2 (use_stmt
)) == INTEGER_CST
)
796 /* As we come here with non-invariant addresses in def_rhs we need
797 to make sure we can build a valid constant offsetted address
798 for further propagation. Simply rely on fold building that
799 and check after the fact. */
800 new_def_rhs
= fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (rhs
)),
802 fold_convert (ptr_type_node
,
803 gimple_assign_rhs2 (use_stmt
)));
804 if (TREE_CODE (new_def_rhs
) == MEM_REF
805 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs
, 0)))
807 new_def_rhs
= build_fold_addr_expr_with_type (new_def_rhs
,
810 /* Recurse. If we could propagate into all uses of lhs do not
811 bother to replace into the current use but just pretend we did. */
812 if (TREE_CODE (new_def_rhs
) == ADDR_EXPR
813 && forward_propagate_addr_expr (lhs
, new_def_rhs
, single_use_p
))
816 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (new_def_rhs
)))
817 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, TREE_CODE (new_def_rhs
),
818 new_def_rhs
, NULL_TREE
);
819 else if (is_gimple_min_invariant (new_def_rhs
))
820 gimple_assign_set_rhs_with_ops (use_stmt_gsi
, NOP_EXPR
,
821 new_def_rhs
, NULL_TREE
);
824 gcc_assert (gsi_stmt (*use_stmt_gsi
) == use_stmt
);
825 update_stmt (use_stmt
);
829 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
830 ADDR_EXPR will not appear on the LHS. */
831 tree
*lhsp
= gimple_assign_lhs_ptr (use_stmt
);
832 while (handled_component_p (*lhsp
))
833 lhsp
= &TREE_OPERAND (*lhsp
, 0);
836 /* Now see if the LHS node is a MEM_REF using NAME. If so,
837 propagate the ADDR_EXPR into the use of NAME and fold the result. */
838 if (TREE_CODE (lhs
) == MEM_REF
839 && TREE_OPERAND (lhs
, 0) == name
)
842 HOST_WIDE_INT def_rhs_offset
;
843 /* If the address is invariant we can always fold it. */
844 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
847 offset_int off
= mem_ref_offset (lhs
);
849 off
+= def_rhs_offset
;
850 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
852 off
+= mem_ref_offset (def_rhs_base
);
853 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
856 new_ptr
= build_fold_addr_expr (def_rhs_base
);
857 TREE_OPERAND (lhs
, 0) = new_ptr
;
858 TREE_OPERAND (lhs
, 1)
859 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs
, 1)), off
);
860 tidy_after_forward_propagate_addr (use_stmt
);
861 /* Continue propagating into the RHS if this was not the only use. */
865 /* If the LHS is a plain dereference and the value type is the same as
866 that of the pointed-to type of the address we can put the
867 dereferenced address on the LHS preserving the original alias-type. */
868 else if (integer_zerop (TREE_OPERAND (lhs
, 1))
869 && ((gimple_assign_lhs (use_stmt
) == lhs
870 && useless_type_conversion_p
871 (TREE_TYPE (TREE_OPERAND (def_rhs
, 0)),
872 TREE_TYPE (gimple_assign_rhs1 (use_stmt
))))
873 || types_compatible_p (TREE_TYPE (lhs
),
874 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
875 /* Don't forward anything into clobber stmts if it would result
876 in the lhs no longer being a MEM_REF. */
877 && (!gimple_clobber_p (use_stmt
)
878 || TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == MEM_REF
))
880 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
881 tree new_offset
, new_base
, saved
, new_lhs
;
882 while (handled_component_p (*def_rhs_basep
))
883 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
884 saved
= *def_rhs_basep
;
885 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
887 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
888 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (lhs
, 1)),
889 TREE_OPERAND (*def_rhs_basep
, 1));
893 new_base
= build_fold_addr_expr (*def_rhs_basep
);
894 new_offset
= TREE_OPERAND (lhs
, 1);
896 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
897 new_base
, new_offset
);
898 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (lhs
);
899 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (lhs
);
900 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (lhs
);
901 new_lhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
903 TREE_THIS_VOLATILE (new_lhs
) = TREE_THIS_VOLATILE (lhs
);
904 TREE_SIDE_EFFECTS (new_lhs
) = TREE_SIDE_EFFECTS (lhs
);
905 *def_rhs_basep
= saved
;
906 tidy_after_forward_propagate_addr (use_stmt
);
907 /* Continue propagating into the RHS if this was not the
913 /* We can have a struct assignment dereferencing our name twice.
914 Note that we didn't propagate into the lhs to not falsely
915 claim we did when propagating into the rhs. */
919 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
920 nodes from the RHS. */
921 tree
*rhsp
= gimple_assign_rhs1_ptr (use_stmt
);
922 if (TREE_CODE (*rhsp
) == ADDR_EXPR
)
923 rhsp
= &TREE_OPERAND (*rhsp
, 0);
924 while (handled_component_p (*rhsp
))
925 rhsp
= &TREE_OPERAND (*rhsp
, 0);
928 /* Now see if the RHS node is a MEM_REF using NAME. If so,
929 propagate the ADDR_EXPR into the use of NAME and fold the result. */
930 if (TREE_CODE (rhs
) == MEM_REF
931 && TREE_OPERAND (rhs
, 0) == name
)
934 HOST_WIDE_INT def_rhs_offset
;
935 if ((def_rhs_base
= get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs
, 0),
938 offset_int off
= mem_ref_offset (rhs
);
940 off
+= def_rhs_offset
;
941 if (TREE_CODE (def_rhs_base
) == MEM_REF
)
943 off
+= mem_ref_offset (def_rhs_base
);
944 new_ptr
= TREE_OPERAND (def_rhs_base
, 0);
947 new_ptr
= build_fold_addr_expr (def_rhs_base
);
948 TREE_OPERAND (rhs
, 0) = new_ptr
;
949 TREE_OPERAND (rhs
, 1)
950 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs
, 1)), off
);
951 fold_stmt_inplace (use_stmt_gsi
);
952 tidy_after_forward_propagate_addr (use_stmt
);
955 /* If the RHS is a plain dereference and the value type is the same as
956 that of the pointed-to type of the address we can put the
957 dereferenced address on the RHS preserving the original alias-type. */
958 else if (integer_zerop (TREE_OPERAND (rhs
, 1))
959 && ((gimple_assign_rhs1 (use_stmt
) == rhs
960 && useless_type_conversion_p
961 (TREE_TYPE (gimple_assign_lhs (use_stmt
)),
962 TREE_TYPE (TREE_OPERAND (def_rhs
, 0))))
963 || types_compatible_p (TREE_TYPE (rhs
),
964 TREE_TYPE (TREE_OPERAND (def_rhs
, 0)))))
966 tree
*def_rhs_basep
= &TREE_OPERAND (def_rhs
, 0);
967 tree new_offset
, new_base
, saved
, new_rhs
;
968 while (handled_component_p (*def_rhs_basep
))
969 def_rhs_basep
= &TREE_OPERAND (*def_rhs_basep
, 0);
970 saved
= *def_rhs_basep
;
971 if (TREE_CODE (*def_rhs_basep
) == MEM_REF
)
973 new_base
= TREE_OPERAND (*def_rhs_basep
, 0);
974 new_offset
= fold_convert (TREE_TYPE (TREE_OPERAND (rhs
, 1)),
975 TREE_OPERAND (*def_rhs_basep
, 1));
979 new_base
= build_fold_addr_expr (*def_rhs_basep
);
980 new_offset
= TREE_OPERAND (rhs
, 1);
982 *def_rhs_basep
= build2 (MEM_REF
, TREE_TYPE (*def_rhs_basep
),
983 new_base
, new_offset
);
984 TREE_THIS_VOLATILE (*def_rhs_basep
) = TREE_THIS_VOLATILE (rhs
);
985 TREE_SIDE_EFFECTS (*def_rhs_basep
) = TREE_SIDE_EFFECTS (rhs
);
986 TREE_THIS_NOTRAP (*def_rhs_basep
) = TREE_THIS_NOTRAP (rhs
);
987 new_rhs
= unshare_expr (TREE_OPERAND (def_rhs
, 0));
989 TREE_THIS_VOLATILE (new_rhs
) = TREE_THIS_VOLATILE (rhs
);
990 TREE_SIDE_EFFECTS (new_rhs
) = TREE_SIDE_EFFECTS (rhs
);
991 *def_rhs_basep
= saved
;
992 fold_stmt_inplace (use_stmt_gsi
);
993 tidy_after_forward_propagate_addr (use_stmt
);
998 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
1000 if (gimple_assign_rhs_code (use_stmt
) != POINTER_PLUS_EXPR
1001 || gimple_assign_rhs1 (use_stmt
) != name
)
1004 /* The remaining cases are all for turning pointer arithmetic into
1005 array indexing. They only apply when we have the address of
1006 element zero in an array. If that is not the case then there
1007 is nothing to do. */
1008 array_ref
= TREE_OPERAND (def_rhs
, 0);
1009 if ((TREE_CODE (array_ref
) != ARRAY_REF
1010 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref
, 0))) != ARRAY_TYPE
1011 || TREE_CODE (TREE_OPERAND (array_ref
, 1)) != INTEGER_CST
)
1012 && TREE_CODE (TREE_TYPE (array_ref
)) != ARRAY_TYPE
)
1015 rhs2
= gimple_assign_rhs2 (use_stmt
);
1016 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
1017 if (TREE_CODE (rhs2
) == INTEGER_CST
)
1019 tree new_rhs
= build1_loc (gimple_location (use_stmt
),
1020 ADDR_EXPR
, TREE_TYPE (def_rhs
),
1021 fold_build2 (MEM_REF
,
1022 TREE_TYPE (TREE_TYPE (def_rhs
)),
1023 unshare_expr (def_rhs
),
1024 fold_convert (ptr_type_node
,
1026 gimple_assign_set_rhs_from_tree (use_stmt_gsi
, new_rhs
);
1027 use_stmt
= gsi_stmt (*use_stmt_gsi
);
1028 update_stmt (use_stmt
);
1029 tidy_after_forward_propagate_addr (use_stmt
);
1036 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1038 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1039 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1040 node or for recovery of array indexing from pointer arithmetic.
1042 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
1043 the single use in the previous invocation. Pass true when calling
1046 Returns true, if all uses have been propagated into. */
1049 forward_propagate_addr_expr (tree name
, tree rhs
, bool parent_single_use_p
)
1051 imm_use_iterator iter
;
1054 bool single_use_p
= parent_single_use_p
&& has_single_use (name
);
1056 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, name
)
1061 /* If the use is not in a simple assignment statement, then
1062 there is nothing we can do. */
1063 if (!is_gimple_assign (use_stmt
))
1065 if (!is_gimple_debug (use_stmt
))
1070 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1071 result
= forward_propagate_addr_expr_1 (name
, rhs
, &gsi
,
1073 /* If the use has moved to a different statement adjust
1074 the update machinery for the old statement too. */
1075 if (use_stmt
!= gsi_stmt (gsi
))
1077 update_stmt (use_stmt
);
1078 use_stmt
= gsi_stmt (gsi
);
1080 update_stmt (use_stmt
);
1083 /* Remove intermediate now unused copy and conversion chains. */
1084 use_rhs
= gimple_assign_rhs1 (use_stmt
);
1086 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
1087 && TREE_CODE (use_rhs
) == SSA_NAME
1088 && has_zero_uses (gimple_assign_lhs (use_stmt
)))
1090 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
1091 release_defs (use_stmt
);
1092 gsi_remove (&gsi
, true);
1096 return all
&& has_zero_uses (name
);
1100 /* Forward propagate the comparison defined in *DEFGSI like
1101 cond_1 = x CMP y to uses of the form
1105 Returns true if stmt is now unused. Advance DEFGSI to the next
1109 forward_propagate_comparison (gimple_stmt_iterator
*defgsi
)
1111 gimple stmt
= gsi_stmt (*defgsi
);
1112 tree name
= gimple_assign_lhs (stmt
);
1114 tree tmp
= NULL_TREE
;
1115 gimple_stmt_iterator gsi
;
1116 enum tree_code code
;
1119 /* Don't propagate ssa names that occur in abnormal phis. */
1120 if ((TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
1121 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt
)))
1122 || (TREE_CODE (gimple_assign_rhs2 (stmt
)) == SSA_NAME
1123 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt
))))
1126 /* Do not un-cse comparisons. But propagate through copies. */
1127 use_stmt
= get_prop_dest_stmt (name
, &name
);
1129 || !is_gimple_assign (use_stmt
))
1132 code
= gimple_assign_rhs_code (use_stmt
);
1133 lhs
= gimple_assign_lhs (use_stmt
);
1134 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1137 /* We can propagate the condition into a statement that
1138 computes the logical negation of the comparison result. */
1139 if ((code
== BIT_NOT_EXPR
1140 && TYPE_PRECISION (TREE_TYPE (lhs
)) == 1)
1141 || (code
== BIT_XOR_EXPR
1142 && integer_onep (gimple_assign_rhs2 (use_stmt
))))
1144 tree type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
1145 bool nans
= HONOR_NANS (TYPE_MODE (type
));
1146 enum tree_code inv_code
;
1147 inv_code
= invert_tree_comparison (gimple_assign_rhs_code (stmt
), nans
);
1148 if (inv_code
== ERROR_MARK
)
1151 tmp
= build2 (inv_code
, TREE_TYPE (lhs
), gimple_assign_rhs1 (stmt
),
1152 gimple_assign_rhs2 (stmt
));
1157 gsi
= gsi_for_stmt (use_stmt
);
1158 gimple_assign_set_rhs_from_tree (&gsi
, unshare_expr (tmp
));
1159 use_stmt
= gsi_stmt (gsi
);
1160 update_stmt (use_stmt
);
1162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1164 fprintf (dump_file
, " Replaced '");
1165 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1166 fprintf (dump_file
, "' with '");
1167 print_gimple_expr (dump_file
, use_stmt
, 0, dump_flags
);
1168 fprintf (dump_file
, "'\n");
1171 /* When we remove stmt now the iterator defgsi goes off it's current
1172 sequence, hence advance it now. */
1175 /* Remove defining statements. */
1176 return remove_prop_source_from_use (name
);
1184 /* GSI_P points to a statement which performs a narrowing integral
1187 Look for cases like:
1197 If T is narrower than X's type and C merely masks off bits outside
1198 of (T) and nothing else.
1200 Normally we'd let DCE remove the dead statement. But no DCE runs
1201 after the last forwprop/combine pass, so we remove the obviously
1202 dead code ourselves.
1204 Return TRUE if a change was made, FALSE otherwise. */
1207 simplify_conversion_from_bitmask (gimple_stmt_iterator
*gsi_p
)
1209 gimple stmt
= gsi_stmt (*gsi_p
);
1210 gimple rhs_def_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
1212 /* See if the input for the conversion was set via a BIT_AND_EXPR and
1213 the only use of the BIT_AND_EXPR result is the conversion. */
1214 if (is_gimple_assign (rhs_def_stmt
)
1215 && gimple_assign_rhs_code (rhs_def_stmt
) == BIT_AND_EXPR
1216 && has_single_use (gimple_assign_lhs (rhs_def_stmt
)))
1218 tree rhs_def_operand1
= gimple_assign_rhs1 (rhs_def_stmt
);
1219 tree rhs_def_operand2
= gimple_assign_rhs2 (rhs_def_stmt
);
1220 tree lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1222 /* Now verify suitability of the BIT_AND_EXPR's operands.
1223 The first must be an SSA_NAME that we can propagate and the
1224 second must be an integer constant that masks out all the
1225 bits outside the final result's type, but nothing else. */
1226 if (TREE_CODE (rhs_def_operand1
) == SSA_NAME
1227 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand1
)
1228 && TREE_CODE (rhs_def_operand2
) == INTEGER_CST
1229 && operand_equal_p (rhs_def_operand2
,
1230 build_low_bits_mask (TREE_TYPE (rhs_def_operand2
),
1231 TYPE_PRECISION (lhs_type
)),
1234 /* This is an optimizable case. Replace the source operand
1235 in the conversion with the first source operand of the
1237 gimple_assign_set_rhs1 (stmt
, rhs_def_operand1
);
1238 stmt
= gsi_stmt (*gsi_p
);
1241 /* There is no DCE after the last forwprop pass. It's
1242 easy to clean up the first order effects here. */
1243 gimple_stmt_iterator si
;
1244 si
= gsi_for_stmt (rhs_def_stmt
);
1245 gsi_remove (&si
, true);
1246 release_defs (rhs_def_stmt
);
1255 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1256 If so, we can change STMT into lhs = y which can later be copy
1257 propagated. Similarly for negation.
1259 This could trivially be formulated as a forward propagation
1260 to immediate uses. However, we already had an implementation
1261 from DOM which used backward propagation via the use-def links.
1263 It turns out that backward propagation is actually faster as
1264 there's less work to do for each NOT/NEG expression we find.
1265 Backwards propagation needs to look at the statement in a single
1266 backlink. Forward propagation needs to look at potentially more
1267 than one forward link.
1269 Returns true when the statement was changed. */
1272 simplify_not_neg_expr (gimple_stmt_iterator
*gsi_p
)
1274 gimple stmt
= gsi_stmt (*gsi_p
);
1275 tree rhs
= gimple_assign_rhs1 (stmt
);
1276 gimple rhs_def_stmt
= SSA_NAME_DEF_STMT (rhs
);
1278 /* See if the RHS_DEF_STMT has the same form as our statement. */
1279 if (is_gimple_assign (rhs_def_stmt
)
1280 && gimple_assign_rhs_code (rhs_def_stmt
) == gimple_assign_rhs_code (stmt
))
1282 tree rhs_def_operand
= gimple_assign_rhs1 (rhs_def_stmt
);
1284 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1285 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1286 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1288 gimple_assign_set_rhs_from_tree (gsi_p
, rhs_def_operand
);
1289 stmt
= gsi_stmt (*gsi_p
);
1298 /* Helper function for simplify_gimple_switch. Remove case labels that
1299 have values outside the range of the new type. */
1302 simplify_gimple_switch_label_vec (gimple stmt
, tree index_type
)
1304 unsigned int branch_num
= gimple_switch_num_labels (stmt
);
1305 auto_vec
<tree
> labels (branch_num
);
1306 unsigned int i
, len
;
1308 /* Collect the existing case labels in a VEC, and preprocess it as if
1309 we are gimplifying a GENERIC SWITCH_EXPR. */
1310 for (i
= 1; i
< branch_num
; i
++)
1311 labels
.quick_push (gimple_switch_label (stmt
, i
));
1312 preprocess_case_label_vec_for_gimple (labels
, index_type
, NULL
);
1314 /* If any labels were removed, replace the existing case labels
1315 in the GIMPLE_SWITCH statement with the correct ones.
1316 Note that the type updates were done in-place on the case labels,
1317 so we only have to replace the case labels in the GIMPLE_SWITCH
1318 if the number of labels changed. */
1319 len
= labels
.length ();
1320 if (len
< branch_num
- 1)
1322 bitmap target_blocks
;
1326 /* Corner case: *all* case labels have been removed as being
1327 out-of-range for INDEX_TYPE. Push one label and let the
1328 CFG cleanups deal with this further. */
1333 label
= CASE_LABEL (gimple_switch_default_label (stmt
));
1334 elt
= build_case_label (build_int_cst (index_type
, 0), NULL
, label
);
1335 labels
.quick_push (elt
);
1339 for (i
= 0; i
< labels
.length (); i
++)
1340 gimple_switch_set_label (stmt
, i
+ 1, labels
[i
]);
1341 for (i
++ ; i
< branch_num
; i
++)
1342 gimple_switch_set_label (stmt
, i
, NULL_TREE
);
1343 gimple_switch_set_num_labels (stmt
, len
+ 1);
1345 /* Cleanup any edges that are now dead. */
1346 target_blocks
= BITMAP_ALLOC (NULL
);
1347 for (i
= 0; i
< gimple_switch_num_labels (stmt
); i
++)
1349 tree elt
= gimple_switch_label (stmt
, i
);
1350 basic_block target
= label_to_block (CASE_LABEL (elt
));
1351 bitmap_set_bit (target_blocks
, target
->index
);
1353 for (ei
= ei_start (gimple_bb (stmt
)->succs
); (e
= ei_safe_edge (ei
)); )
1355 if (! bitmap_bit_p (target_blocks
, e
->dest
->index
))
1359 free_dominance_info (CDI_DOMINATORS
);
1364 BITMAP_FREE (target_blocks
);
1368 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1369 the condition which we may be able to optimize better. */
1372 simplify_gimple_switch (gimple stmt
)
1374 /* The optimization that we really care about is removing unnecessary
1375 casts. That will let us do much better in propagating the inferred
1376 constant at the switch target. */
1377 tree cond
= gimple_switch_index (stmt
);
1378 if (TREE_CODE (cond
) == SSA_NAME
)
1380 gimple def_stmt
= SSA_NAME_DEF_STMT (cond
);
1381 if (gimple_assign_cast_p (def_stmt
))
1383 tree def
= gimple_assign_rhs1 (def_stmt
);
1384 if (TREE_CODE (def
) != SSA_NAME
)
1387 /* If we have an extension or sign-change that preserves the
1388 values we check against then we can copy the source value into
1390 tree ti
= TREE_TYPE (def
);
1391 if (INTEGRAL_TYPE_P (ti
)
1392 && TYPE_PRECISION (ti
) <= TYPE_PRECISION (TREE_TYPE (cond
)))
1394 size_t n
= gimple_switch_num_labels (stmt
);
1395 tree min
= NULL_TREE
, max
= NULL_TREE
;
1398 min
= CASE_LOW (gimple_switch_label (stmt
, 1));
1399 if (CASE_HIGH (gimple_switch_label (stmt
, n
- 1)))
1400 max
= CASE_HIGH (gimple_switch_label (stmt
, n
- 1));
1402 max
= CASE_LOW (gimple_switch_label (stmt
, n
- 1));
1404 if ((!min
|| int_fits_type_p (min
, ti
))
1405 && (!max
|| int_fits_type_p (max
, ti
)))
1407 gimple_switch_set_index (stmt
, def
);
1408 simplify_gimple_switch_label_vec (stmt
, ti
);
1419 /* For pointers p2 and p1 return p2 - p1 if the
1420 difference is known and constant, otherwise return NULL. */
1423 constant_pointer_difference (tree p1
, tree p2
)
1426 #define CPD_ITERATIONS 5
1427 tree exps
[2][CPD_ITERATIONS
];
1428 tree offs
[2][CPD_ITERATIONS
];
1431 for (i
= 0; i
< 2; i
++)
1433 tree p
= i
? p1
: p2
;
1434 tree off
= size_zero_node
;
1436 enum tree_code code
;
1438 /* For each of p1 and p2 we need to iterate at least
1439 twice, to handle ADDR_EXPR directly in p1/p2,
1440 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1441 on definition's stmt RHS. Iterate a few extra times. */
1445 if (!POINTER_TYPE_P (TREE_TYPE (p
)))
1447 if (TREE_CODE (p
) == ADDR_EXPR
)
1449 tree q
= TREE_OPERAND (p
, 0);
1450 HOST_WIDE_INT offset
;
1451 tree base
= get_addr_base_and_unit_offset (q
, &offset
);
1456 off
= size_binop (PLUS_EXPR
, off
, size_int (offset
));
1458 if (TREE_CODE (q
) == MEM_REF
1459 && TREE_CODE (TREE_OPERAND (q
, 0)) == SSA_NAME
)
1461 p
= TREE_OPERAND (q
, 0);
1462 off
= size_binop (PLUS_EXPR
, off
,
1463 wide_int_to_tree (sizetype
,
1464 mem_ref_offset (q
)));
1473 if (TREE_CODE (p
) != SSA_NAME
)
1477 if (j
== CPD_ITERATIONS
)
1479 stmt
= SSA_NAME_DEF_STMT (p
);
1480 if (!is_gimple_assign (stmt
) || gimple_assign_lhs (stmt
) != p
)
1482 code
= gimple_assign_rhs_code (stmt
);
1483 if (code
== POINTER_PLUS_EXPR
)
1485 if (TREE_CODE (gimple_assign_rhs2 (stmt
)) != INTEGER_CST
)
1487 off
= size_binop (PLUS_EXPR
, off
, gimple_assign_rhs2 (stmt
));
1488 p
= gimple_assign_rhs1 (stmt
);
1490 else if (code
== ADDR_EXPR
|| code
== NOP_EXPR
)
1491 p
= gimple_assign_rhs1 (stmt
);
1499 for (i
= 0; i
< cnt
[0]; i
++)
1500 for (j
= 0; j
< cnt
[1]; j
++)
1501 if (exps
[0][i
] == exps
[1][j
])
1502 return size_binop (MINUS_EXPR
, offs
[0][i
], offs
[1][j
]);
1507 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1509 memcpy (p, "abcd", 4);
1510 memset (p + 4, ' ', 3);
1512 memcpy (p, "abcd ", 7);
1513 call if the latter can be stored by pieces during expansion. */
1516 simplify_builtin_call (gimple_stmt_iterator
*gsi_p
, tree callee2
)
1518 gimple stmt1
, stmt2
= gsi_stmt (*gsi_p
);
1519 tree vuse
= gimple_vuse (stmt2
);
1522 stmt1
= SSA_NAME_DEF_STMT (vuse
);
1524 switch (DECL_FUNCTION_CODE (callee2
))
1526 case BUILT_IN_MEMSET
:
1527 if (gimple_call_num_args (stmt2
) != 3
1528 || gimple_call_lhs (stmt2
)
1530 || BITS_PER_UNIT
!= 8)
1535 tree ptr1
, src1
, str1
, off1
, len1
, lhs1
;
1536 tree ptr2
= gimple_call_arg (stmt2
, 0);
1537 tree val2
= gimple_call_arg (stmt2
, 1);
1538 tree len2
= gimple_call_arg (stmt2
, 2);
1539 tree diff
, vdef
, new_str_cst
;
1541 unsigned int ptr1_align
;
1542 unsigned HOST_WIDE_INT src_len
;
1544 use_operand_p use_p
;
1546 if (!tree_fits_shwi_p (val2
)
1547 || !tree_fits_uhwi_p (len2
))
1549 if (is_gimple_call (stmt1
))
1551 /* If first stmt is a call, it needs to be memcpy
1552 or mempcpy, with string literal as second argument and
1554 callee1
= gimple_call_fndecl (stmt1
);
1555 if (callee1
== NULL_TREE
1556 || DECL_BUILT_IN_CLASS (callee1
) != BUILT_IN_NORMAL
1557 || gimple_call_num_args (stmt1
) != 3)
1559 if (DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMCPY
1560 && DECL_FUNCTION_CODE (callee1
) != BUILT_IN_MEMPCPY
)
1562 ptr1
= gimple_call_arg (stmt1
, 0);
1563 src1
= gimple_call_arg (stmt1
, 1);
1564 len1
= gimple_call_arg (stmt1
, 2);
1565 lhs1
= gimple_call_lhs (stmt1
);
1566 if (!tree_fits_uhwi_p (len1
))
1568 str1
= string_constant (src1
, &off1
);
1569 if (str1
== NULL_TREE
)
1571 if (!tree_fits_uhwi_p (off1
)
1572 || compare_tree_int (off1
, TREE_STRING_LENGTH (str1
) - 1) > 0
1573 || compare_tree_int (len1
, TREE_STRING_LENGTH (str1
)
1574 - tree_to_uhwi (off1
)) > 0
1575 || TREE_CODE (TREE_TYPE (str1
)) != ARRAY_TYPE
1576 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1
)))
1577 != TYPE_MODE (char_type_node
))
1580 else if (gimple_assign_single_p (stmt1
))
1582 /* Otherwise look for length 1 memcpy optimized into
1584 ptr1
= gimple_assign_lhs (stmt1
);
1585 src1
= gimple_assign_rhs1 (stmt1
);
1586 if (TREE_CODE (ptr1
) != MEM_REF
1587 || TYPE_MODE (TREE_TYPE (ptr1
)) != TYPE_MODE (char_type_node
)
1588 || !tree_fits_shwi_p (src1
))
1590 ptr1
= build_fold_addr_expr (ptr1
);
1591 callee1
= NULL_TREE
;
1592 len1
= size_one_node
;
1594 off1
= size_zero_node
;
1600 diff
= constant_pointer_difference (ptr1
, ptr2
);
1601 if (diff
== NULL
&& lhs1
!= NULL
)
1603 diff
= constant_pointer_difference (lhs1
, ptr2
);
1604 if (DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1606 diff
= size_binop (PLUS_EXPR
, diff
,
1607 fold_convert (sizetype
, len1
));
1609 /* If the difference between the second and first destination pointer
1610 is not constant, or is bigger than memcpy length, bail out. */
1612 || !tree_fits_uhwi_p (diff
)
1613 || tree_int_cst_lt (len1
, diff
))
1616 /* Use maximum of difference plus memset length and memcpy length
1617 as the new memcpy length, if it is too big, bail out. */
1618 src_len
= tree_to_uhwi (diff
);
1619 src_len
+= tree_to_uhwi (len2
);
1620 if (src_len
< tree_to_uhwi (len1
))
1621 src_len
= tree_to_uhwi (len1
);
1625 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1626 with bigger length will return different result. */
1627 if (lhs1
!= NULL_TREE
1628 && DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
1629 && (TREE_CODE (lhs1
) != SSA_NAME
1630 || !single_imm_use (lhs1
, &use_p
, &use_stmt
)
1631 || use_stmt
!= stmt2
))
1634 /* If anything reads memory in between memcpy and memset
1635 call, the modified memcpy call might change it. */
1636 vdef
= gimple_vdef (stmt1
);
1638 && (!single_imm_use (vdef
, &use_p
, &use_stmt
)
1639 || use_stmt
!= stmt2
))
1642 ptr1_align
= get_pointer_alignment (ptr1
);
1643 /* Construct the new source string literal. */
1644 src_buf
= XALLOCAVEC (char, src_len
+ 1);
1647 TREE_STRING_POINTER (str1
) + tree_to_uhwi (off1
),
1648 tree_to_uhwi (len1
));
1650 src_buf
[0] = tree_to_shwi (src1
);
1651 memset (src_buf
+ tree_to_uhwi (diff
),
1652 tree_to_shwi (val2
), tree_to_uhwi (len2
));
1653 src_buf
[src_len
] = '\0';
1654 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1655 handle embedded '\0's. */
1656 if (strlen (src_buf
) != src_len
)
1658 rtl_profile_for_bb (gimple_bb (stmt2
));
1659 /* If the new memcpy wouldn't be emitted by storing the literal
1660 by pieces, this optimization might enlarge .rodata too much,
1661 as commonly used string literals couldn't be shared any
1663 if (!can_store_by_pieces (src_len
,
1664 builtin_strncpy_read_str
,
1665 src_buf
, ptr1_align
, false))
1668 new_str_cst
= build_string_literal (src_len
, src_buf
);
1671 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1673 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1674 gimple_call_set_lhs (stmt1
, NULL_TREE
);
1675 gimple_call_set_arg (stmt1
, 1, new_str_cst
);
1676 gimple_call_set_arg (stmt1
, 2,
1677 build_int_cst (TREE_TYPE (len1
), src_len
));
1678 update_stmt (stmt1
);
1679 unlink_stmt_vdef (stmt2
);
1680 gsi_remove (gsi_p
, true);
1681 release_defs (stmt2
);
1682 if (lhs1
&& DECL_FUNCTION_CODE (callee1
) == BUILT_IN_MEMPCPY
)
1683 release_ssa_name (lhs1
);
1688 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1689 assignment, remove STMT1 and change memset call into
1691 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt1
);
1693 if (!is_gimple_val (ptr1
))
1694 ptr1
= force_gimple_operand_gsi (gsi_p
, ptr1
, true, NULL_TREE
,
1695 true, GSI_SAME_STMT
);
1696 gimple_call_set_fndecl (stmt2
,
1697 builtin_decl_explicit (BUILT_IN_MEMCPY
));
1698 gimple_call_set_arg (stmt2
, 0, ptr1
);
1699 gimple_call_set_arg (stmt2
, 1, new_str_cst
);
1700 gimple_call_set_arg (stmt2
, 2,
1701 build_int_cst (TREE_TYPE (len2
), src_len
));
1702 unlink_stmt_vdef (stmt1
);
1703 gsi_remove (&gsi
, true);
1704 release_defs (stmt1
);
1705 update_stmt (stmt2
);
1716 /* Checks if expression has type of one-bit precision, or is a known
1717 truth-valued expression. */
1719 truth_valued_ssa_name (tree name
)
1722 tree type
= TREE_TYPE (name
);
1724 if (!INTEGRAL_TYPE_P (type
))
1726 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1727 necessarily one and so ~X is not equal to !X. */
1728 if (TYPE_PRECISION (type
) == 1)
1730 def
= SSA_NAME_DEF_STMT (name
);
1731 if (is_gimple_assign (def
))
1732 return truth_value_p (gimple_assign_rhs_code (def
));
1736 /* Helper routine for simplify_bitwise_binary_1 function.
1737 Return for the SSA name NAME the expression X if it mets condition
1738 NAME = !X. Otherwise return NULL_TREE.
1739 Detected patterns for NAME = !X are:
1740 !X and X == 0 for X with integral type.
1741 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1743 lookup_logical_inverted_value (tree name
)
1746 enum tree_code code
;
1749 /* If name has none-intergal type, or isn't a SSA_NAME, then
1751 if (TREE_CODE (name
) != SSA_NAME
1752 || !INTEGRAL_TYPE_P (TREE_TYPE (name
)))
1754 def
= SSA_NAME_DEF_STMT (name
);
1755 if (!is_gimple_assign (def
))
1758 code
= gimple_assign_rhs_code (def
);
1759 op1
= gimple_assign_rhs1 (def
);
1762 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1763 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */
1764 if (code
== EQ_EXPR
|| code
== NE_EXPR
1765 || code
== BIT_XOR_EXPR
)
1766 op2
= gimple_assign_rhs2 (def
);
1771 if (truth_valued_ssa_name (name
))
1775 /* Check if we have X == 0 and X has an integral type. */
1776 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1
)))
1778 if (integer_zerop (op2
))
1782 /* Check if we have X != 1 and X is a truth-valued. */
1783 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1
)))
1785 if (integer_onep (op2
) && truth_valued_ssa_name (op1
))
1789 /* Check if we have X ^ 1 and X is truth valued. */
1790 if (integer_onep (op2
) && truth_valued_ssa_name (op1
))
1800 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1801 operations CODE, if one operand has the logically inverted
1802 value of the other. */
1804 simplify_bitwise_binary_1 (enum tree_code code
, tree type
,
1805 tree arg1
, tree arg2
)
1809 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1810 if (code
!= BIT_AND_EXPR
&& code
!= BIT_IOR_EXPR
1811 && code
!= BIT_XOR_EXPR
)
1814 /* First check if operands ARG1 and ARG2 are equal. If so
1815 return NULL_TREE as this optimization is handled fold_stmt. */
1818 /* See if we have in arguments logical-not patterns. */
1819 if (((anot
= lookup_logical_inverted_value (arg1
)) == NULL_TREE
1821 && ((anot
= lookup_logical_inverted_value (arg2
)) == NULL_TREE
1826 if (code
== BIT_AND_EXPR
)
1827 return fold_convert (type
, integer_zero_node
);
1828 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1829 if (truth_valued_ssa_name (anot
))
1830 return fold_convert (type
, integer_one_node
);
1832 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1836 /* Given a ssa_name in NAME see if it was defined by an assignment and
1837 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1838 to the second operand on the rhs. */
1841 defcodefor_name (tree name
, enum tree_code
*code
, tree
*arg1
, tree
*arg2
)
1844 enum tree_code code1
;
1848 enum gimple_rhs_class grhs_class
;
1850 code1
= TREE_CODE (name
);
1853 grhs_class
= get_gimple_rhs_class (code1
);
1855 if (code1
== SSA_NAME
)
1857 def
= SSA_NAME_DEF_STMT (name
);
1859 if (def
&& is_gimple_assign (def
)
1860 && can_propagate_from (def
))
1862 code1
= gimple_assign_rhs_code (def
);
1863 arg11
= gimple_assign_rhs1 (def
);
1864 arg21
= gimple_assign_rhs2 (def
);
1865 arg31
= gimple_assign_rhs2 (def
);
1868 else if (grhs_class
== GIMPLE_TERNARY_RHS
1869 || GIMPLE_BINARY_RHS
1871 || GIMPLE_SINGLE_RHS
)
1872 extract_ops_from_tree_1 (name
, &code1
, &arg11
, &arg21
, &arg31
);
1878 /* Ignore arg3 currently. */
1881 /* Return true if a conversion of an operand from type FROM to type TO
1882 should be applied after performing the operation instead. */
1885 hoist_conversion_for_bitop_p (tree to
, tree from
)
1887 /* That's a good idea if the conversion widens the operand, thus
1888 after hoisting the conversion the operation will be narrower. */
1889 if (TYPE_PRECISION (from
) < TYPE_PRECISION (to
))
1892 /* It's also a good idea if the conversion is to a non-integer mode. */
1893 if (GET_MODE_CLASS (TYPE_MODE (to
)) != MODE_INT
)
1896 /* Or if the precision of TO is not the same as the precision
1898 if (TYPE_PRECISION (to
) != GET_MODE_PRECISION (TYPE_MODE (to
)))
1904 /* GSI points to a statement of the form
1906 result = OP0 CODE OP1
1908 Where OP0 and OP1 are single bit SSA_NAMEs and CODE is either
1909 BIT_AND_EXPR or BIT_IOR_EXPR.
1911 If OP0 is fed by a bitwise negation of another single bit SSA_NAME,
1912 then we can simplify the two statements into a single LT_EXPR or LE_EXPR
1913 when code is BIT_AND_EXPR and BIT_IOR_EXPR respectively.
1915 If a simplification is made, return TRUE, else return FALSE. */
1917 simplify_bitwise_binary_boolean (gimple_stmt_iterator
*gsi
,
1918 enum tree_code code
,
1921 gimple op0_def_stmt
= SSA_NAME_DEF_STMT (op0
);
1923 if (!is_gimple_assign (op0_def_stmt
)
1924 || (gimple_assign_rhs_code (op0_def_stmt
) != BIT_NOT_EXPR
))
1927 tree x
= gimple_assign_rhs1 (op0_def_stmt
);
1928 if (TREE_CODE (x
) == SSA_NAME
1929 && INTEGRAL_TYPE_P (TREE_TYPE (x
))
1930 && TYPE_PRECISION (TREE_TYPE (x
)) == 1
1931 && TYPE_UNSIGNED (TREE_TYPE (x
)) == TYPE_UNSIGNED (TREE_TYPE (op1
)))
1933 enum tree_code newcode
;
1935 gimple stmt
= gsi_stmt (*gsi
);
1936 gimple_assign_set_rhs1 (stmt
, x
);
1937 gimple_assign_set_rhs2 (stmt
, op1
);
1938 if (code
== BIT_AND_EXPR
)
1939 newcode
= TYPE_UNSIGNED (TREE_TYPE (x
)) ? LT_EXPR
: GT_EXPR
;
1941 newcode
= TYPE_UNSIGNED (TREE_TYPE (x
)) ? LE_EXPR
: GE_EXPR
;
1942 gimple_assign_set_rhs_code (stmt
, newcode
);
1950 /* Simplify bitwise binary operations.
1951 Return true if a transformation applied, otherwise return false. */
1954 simplify_bitwise_binary (gimple_stmt_iterator
*gsi
)
1956 gimple stmt
= gsi_stmt (*gsi
);
1957 tree arg1
= gimple_assign_rhs1 (stmt
);
1958 tree arg2
= gimple_assign_rhs2 (stmt
);
1959 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1961 tree def1_arg1
, def1_arg2
, def2_arg1
, def2_arg2
;
1962 enum tree_code def1_code
, def2_code
;
1964 defcodefor_name (arg1
, &def1_code
, &def1_arg1
, &def1_arg2
);
1965 defcodefor_name (arg2
, &def2_code
, &def2_arg1
, &def2_arg2
);
1967 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST))
1969 if (TREE_CODE (arg2
) == INTEGER_CST
1970 && CONVERT_EXPR_CODE_P (def1_code
)
1971 && hoist_conversion_for_bitop_p (TREE_TYPE (arg1
), TREE_TYPE (def1_arg1
))
1972 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1
))
1973 && int_fits_type_p (arg2
, TREE_TYPE (def1_arg1
)))
1976 tree tem
= make_ssa_name (TREE_TYPE (def1_arg1
), NULL
);
1978 gimple_build_assign_with_ops (code
, tem
, def1_arg1
,
1979 fold_convert_loc (gimple_location (stmt
),
1980 TREE_TYPE (def1_arg1
),
1982 gimple_set_location (newop
, gimple_location (stmt
));
1983 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
1984 gimple_assign_set_rhs_with_ops_1 (gsi
, NOP_EXPR
,
1985 tem
, NULL_TREE
, NULL_TREE
);
1986 update_stmt (gsi_stmt (*gsi
));
1990 /* For bitwise binary operations apply operand conversions to the
1991 binary operation result instead of to the operands. This allows
1992 to combine successive conversions and bitwise binary operations. */
1993 if (CONVERT_EXPR_CODE_P (def1_code
)
1994 && CONVERT_EXPR_CODE_P (def2_code
)
1995 && types_compatible_p (TREE_TYPE (def1_arg1
), TREE_TYPE (def2_arg1
))
1996 && hoist_conversion_for_bitop_p (TREE_TYPE (arg1
), TREE_TYPE (def1_arg1
)))
1999 tree tem
= make_ssa_name (TREE_TYPE (def1_arg1
), NULL
);
2000 newop
= gimple_build_assign_with_ops (code
, tem
, def1_arg1
, def2_arg1
);
2001 gimple_set_location (newop
, gimple_location (stmt
));
2002 gsi_insert_before (gsi
, newop
, GSI_SAME_STMT
);
2003 gimple_assign_set_rhs_with_ops_1 (gsi
, NOP_EXPR
,
2004 tem
, NULL_TREE
, NULL_TREE
);
2005 update_stmt (gsi_stmt (*gsi
));
2010 /* Simplify (A & B) OP0 (C & B) to (A OP0 C) & B. */
2011 if (def1_code
== def2_code
2012 && def1_code
== BIT_AND_EXPR
2013 && operand_equal_for_phi_arg_p (def1_arg2
,
2019 tree inner
= fold_build2 (code
, TREE_TYPE (arg2
), a
, c
);
2020 /* If A OP0 C (this usually means C is the same as A) is 0
2021 then fold it down correctly. */
2022 if (integer_zerop (inner
))
2024 gimple_assign_set_rhs_from_tree (gsi
, inner
);
2028 /* If A OP0 C (this usually means C is the same as A) is a ssa_name
2029 then fold it down correctly. */
2030 else if (TREE_CODE (inner
) == SSA_NAME
)
2032 tree outer
= fold_build2 (def1_code
, TREE_TYPE (inner
),
2034 gimple_assign_set_rhs_from_tree (gsi
, outer
);
2042 tem
= make_ssa_name (TREE_TYPE (arg2
), NULL
);
2043 newop
= gimple_build_assign_with_ops (code
, tem
, a
, c
);
2044 gimple_set_location (newop
, gimple_location (stmt
));
2045 /* Make sure to re-process the new stmt as it's walking upwards. */
2046 gsi_insert_before (gsi
, newop
, GSI_NEW_STMT
);
2047 gimple_assign_set_rhs1 (stmt
, tem
);
2048 gimple_assign_set_rhs2 (stmt
, b
);
2049 gimple_assign_set_rhs_code (stmt
, def1_code
);
2055 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
2056 if (code
== BIT_AND_EXPR
2057 && def1_code
== BIT_IOR_EXPR
2058 && CONSTANT_CLASS_P (arg2
)
2059 && CONSTANT_CLASS_P (def1_arg2
))
2061 tree cst
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (arg2
),
2065 if (integer_zerop (cst
))
2067 gimple_assign_set_rhs1 (stmt
, def1_arg1
);
2071 tem
= make_ssa_name (TREE_TYPE (arg2
), NULL
);
2072 newop
= gimple_build_assign_with_ops (BIT_AND_EXPR
,
2073 tem
, def1_arg1
, arg2
);
2074 gimple_set_location (newop
, gimple_location (stmt
));
2075 /* Make sure to re-process the new stmt as it's walking upwards. */
2076 gsi_insert_before (gsi
, newop
, GSI_NEW_STMT
);
2077 gimple_assign_set_rhs1 (stmt
, tem
);
2078 gimple_assign_set_rhs2 (stmt
, cst
);
2079 gimple_assign_set_rhs_code (stmt
, BIT_IOR_EXPR
);
2084 /* Combine successive equal operations with constants. */
2085 if ((code
== BIT_AND_EXPR
2086 || code
== BIT_IOR_EXPR
2087 || code
== BIT_XOR_EXPR
)
2088 && def1_code
== code
2089 && CONSTANT_CLASS_P (arg2
)
2090 && CONSTANT_CLASS_P (def1_arg2
))
2092 tree cst
= fold_build2 (code
, TREE_TYPE (arg2
),
2094 gimple_assign_set_rhs1 (stmt
, def1_arg1
);
2095 gimple_assign_set_rhs2 (stmt
, cst
);
2100 /* Try simple folding for X op !X, and X op X. */
2101 res
= simplify_bitwise_binary_1 (code
, TREE_TYPE (arg1
), arg1
, arg2
);
2102 if (res
!= NULL_TREE
)
2104 gimple_assign_set_rhs_from_tree (gsi
, res
);
2105 update_stmt (gsi_stmt (*gsi
));
2109 if (code
== BIT_AND_EXPR
|| code
== BIT_IOR_EXPR
)
2111 enum tree_code ocode
= code
== BIT_AND_EXPR
? BIT_IOR_EXPR
: BIT_AND_EXPR
;
2112 if (def1_code
== ocode
)
2115 enum tree_code coden
;
2117 /* ( X | Y) & X -> X */
2118 /* ( X & Y) | X -> X */
2122 gimple_assign_set_rhs_from_tree (gsi
, x
);
2123 update_stmt (gsi_stmt (*gsi
));
2127 defcodefor_name (def1_arg1
, &coden
, &a1
, &a2
);
2128 /* (~X | Y) & X -> X & Y */
2129 /* (~X & Y) | X -> X | Y */
2130 if (coden
== BIT_NOT_EXPR
&& a1
== x
)
2132 gimple_assign_set_rhs_with_ops (gsi
, code
,
2134 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2138 defcodefor_name (def1_arg2
, &coden
, &a1
, &a2
);
2139 /* (Y | ~X) & X -> X & Y */
2140 /* (Y & ~X) | X -> X | Y */
2141 if (coden
== BIT_NOT_EXPR
&& a1
== x
)
2143 gimple_assign_set_rhs_with_ops (gsi
, code
,
2145 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2150 if (def2_code
== ocode
)
2152 enum tree_code coden
;
2155 /* X & ( X | Y) -> X */
2156 /* X | ( X & Y) -> X */
2160 gimple_assign_set_rhs_from_tree (gsi
, x
);
2161 update_stmt (gsi_stmt (*gsi
));
2164 defcodefor_name (def2_arg1
, &coden
, &a1
, NULL
);
2165 /* (~X | Y) & X -> X & Y */
2166 /* (~X & Y) | X -> X | Y */
2167 if (coden
== BIT_NOT_EXPR
&& a1
== x
)
2169 gimple_assign_set_rhs_with_ops (gsi
, code
,
2171 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2175 defcodefor_name (def2_arg2
, &coden
, &a1
, NULL
);
2176 /* (Y | ~X) & X -> X & Y */
2177 /* (Y & ~X) | X -> X | Y */
2178 if (coden
== BIT_NOT_EXPR
&& a1
== x
)
2180 gimple_assign_set_rhs_with_ops (gsi
, code
,
2182 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2188 /* If arg1 and arg2 are booleans (or any single bit type)
2189 then try to simplify:
2196 But only do this if our result feeds into a comparison as
2197 this transformation is not always a win, particularly on
2198 targets with and-not instructions. */
2199 if (TREE_CODE (arg1
) == SSA_NAME
2200 && TREE_CODE (arg2
) == SSA_NAME
2201 && INTEGRAL_TYPE_P (TREE_TYPE (arg1
))
2202 && TYPE_PRECISION (TREE_TYPE (arg1
)) == 1
2203 && TYPE_PRECISION (TREE_TYPE (arg2
)) == 1
2204 && (TYPE_UNSIGNED (TREE_TYPE (arg1
))
2205 == TYPE_UNSIGNED (TREE_TYPE (arg2
))))
2207 use_operand_p use_p
;
2210 if (single_imm_use (gimple_assign_lhs (stmt
), &use_p
, &use_stmt
))
2212 if (gimple_code (use_stmt
) == GIMPLE_COND
2213 && gimple_cond_lhs (use_stmt
) == gimple_assign_lhs (stmt
)
2214 && integer_zerop (gimple_cond_rhs (use_stmt
))
2215 && gimple_cond_code (use_stmt
) == NE_EXPR
)
2217 if (simplify_bitwise_binary_boolean (gsi
, code
, arg1
, arg2
))
2219 if (simplify_bitwise_binary_boolean (gsi
, code
, arg2
, arg1
))
2229 /* Recognize rotation patterns. Return true if a transformation
2230 applied, otherwise return false.
2232 We are looking for X with unsigned type T with bitsize B, OP being
2233 +, | or ^, some type T2 wider than T and
2234 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
2235 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
2236 (X << Y) OP (X >> (B - Y))
2237 (X << (int) Y) OP (X >> (int) (B - Y))
2238 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
2239 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
2240 (X << Y) | (X >> ((-Y) & (B - 1)))
2241 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
2242 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
2243 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
2245 and transform these into:
2249 Note, in the patterns with T2 type, the type of OP operands
2250 might be even a signed type, but should have precision B. */
2253 simplify_rotate (gimple_stmt_iterator
*gsi
)
2255 gimple stmt
= gsi_stmt (*gsi
);
2256 tree arg
[2], rtype
, rotcnt
= NULL_TREE
;
2257 tree def_arg1
[2], def_arg2
[2];
2258 enum tree_code def_code
[2];
2261 bool swapped_p
= false;
2264 arg
[0] = gimple_assign_rhs1 (stmt
);
2265 arg
[1] = gimple_assign_rhs2 (stmt
);
2266 rtype
= TREE_TYPE (arg
[0]);
2268 /* Only create rotates in complete modes. Other cases are not
2269 expanded properly. */
2270 if (!INTEGRAL_TYPE_P (rtype
)
2271 || TYPE_PRECISION (rtype
) != GET_MODE_PRECISION (TYPE_MODE (rtype
)))
2274 for (i
= 0; i
< 2; i
++)
2275 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
2277 /* Look through narrowing conversions. */
2278 if (CONVERT_EXPR_CODE_P (def_code
[0])
2279 && CONVERT_EXPR_CODE_P (def_code
[1])
2280 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[0]))
2281 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1
[1]))
2282 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0]))
2283 == TYPE_PRECISION (TREE_TYPE (def_arg1
[1]))
2284 && TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) > TYPE_PRECISION (rtype
)
2285 && has_single_use (arg
[0])
2286 && has_single_use (arg
[1]))
2288 for (i
= 0; i
< 2; i
++)
2290 arg
[i
] = def_arg1
[i
];
2291 defcodefor_name (arg
[i
], &def_code
[i
], &def_arg1
[i
], &def_arg2
[i
]);
2295 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
2296 for (i
= 0; i
< 2; i
++)
2297 if (def_code
[i
] != LSHIFT_EXPR
&& def_code
[i
] != RSHIFT_EXPR
)
2299 else if (!has_single_use (arg
[i
]))
2301 if (def_code
[0] == def_code
[1])
2304 /* If we've looked through narrowing conversions before, look through
2305 widening conversions from unsigned type with the same precision
2307 if (TYPE_PRECISION (TREE_TYPE (def_arg1
[0])) != TYPE_PRECISION (rtype
))
2308 for (i
= 0; i
< 2; i
++)
2311 enum tree_code code
;
2312 defcodefor_name (def_arg1
[i
], &code
, &tem
, NULL
);
2313 if (!CONVERT_EXPR_CODE_P (code
)
2314 || !INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2315 || TYPE_PRECISION (TREE_TYPE (tem
)) != TYPE_PRECISION (rtype
))
2319 /* Both shifts have to use the same first operand. */
2320 if (TREE_CODE (def_arg1
[0]) != SSA_NAME
|| def_arg1
[0] != def_arg1
[1])
2322 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1
[0])))
2325 /* CNT1 + CNT2 == B case above. */
2326 if (tree_fits_uhwi_p (def_arg2
[0])
2327 && tree_fits_uhwi_p (def_arg2
[1])
2328 && tree_to_uhwi (def_arg2
[0])
2329 + tree_to_uhwi (def_arg2
[1]) == TYPE_PRECISION (rtype
))
2330 rotcnt
= def_arg2
[0];
2331 else if (TREE_CODE (def_arg2
[0]) != SSA_NAME
2332 || TREE_CODE (def_arg2
[1]) != SSA_NAME
)
2336 tree cdef_arg1
[2], cdef_arg2
[2], def_arg2_alt
[2];
2337 enum tree_code cdef_code
[2];
2338 /* Look through conversion of the shift count argument.
2339 The C/C++ FE cast any shift count argument to integer_type_node.
2340 The only problem might be if the shift count type maximum value
2341 is equal or smaller than number of bits in rtype. */
2342 for (i
= 0; i
< 2; i
++)
2344 def_arg2_alt
[i
] = def_arg2
[i
];
2345 defcodefor_name (def_arg2
[i
], &cdef_code
[i
],
2346 &cdef_arg1
[i
], &cdef_arg2
[i
]);
2347 if (CONVERT_EXPR_CODE_P (cdef_code
[i
])
2348 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1
[i
]))
2349 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
2350 > floor_log2 (TYPE_PRECISION (rtype
))
2351 && TYPE_PRECISION (TREE_TYPE (cdef_arg1
[i
]))
2352 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (cdef_arg1
[i
]))))
2354 def_arg2_alt
[i
] = cdef_arg1
[i
];
2355 defcodefor_name (def_arg2_alt
[i
], &cdef_code
[i
],
2356 &cdef_arg1
[i
], &cdef_arg2
[i
]);
2359 for (i
= 0; i
< 2; i
++)
2360 /* Check for one shift count being Y and the other B - Y,
2361 with optional casts. */
2362 if (cdef_code
[i
] == MINUS_EXPR
2363 && tree_fits_shwi_p (cdef_arg1
[i
])
2364 && tree_to_shwi (cdef_arg1
[i
]) == TYPE_PRECISION (rtype
)
2365 && TREE_CODE (cdef_arg2
[i
]) == SSA_NAME
)
2368 enum tree_code code
;
2370 if (cdef_arg2
[i
] == def_arg2
[1 - i
]
2371 || cdef_arg2
[i
] == def_arg2_alt
[1 - i
])
2373 rotcnt
= cdef_arg2
[i
];
2376 defcodefor_name (cdef_arg2
[i
], &code
, &tem
, NULL
);
2377 if (CONVERT_EXPR_CODE_P (code
)
2378 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2379 && TYPE_PRECISION (TREE_TYPE (tem
))
2380 > floor_log2 (TYPE_PRECISION (rtype
))
2381 && TYPE_PRECISION (TREE_TYPE (tem
))
2382 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
2383 && (tem
== def_arg2
[1 - i
]
2384 || tem
== def_arg2_alt
[1 - i
]))
2390 /* The above sequence isn't safe for Y being 0,
2391 because then one of the shifts triggers undefined behavior.
2392 This alternative is safe even for rotation count of 0.
2393 One shift count is Y and the other (-Y) & (B - 1). */
2394 else if (cdef_code
[i
] == BIT_AND_EXPR
2395 && tree_fits_shwi_p (cdef_arg2
[i
])
2396 && tree_to_shwi (cdef_arg2
[i
])
2397 == TYPE_PRECISION (rtype
) - 1
2398 && TREE_CODE (cdef_arg1
[i
]) == SSA_NAME
2399 && gimple_assign_rhs_code (stmt
) == BIT_IOR_EXPR
)
2402 enum tree_code code
;
2404 defcodefor_name (cdef_arg1
[i
], &code
, &tem
, NULL
);
2405 if (CONVERT_EXPR_CODE_P (code
)
2406 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2407 && TYPE_PRECISION (TREE_TYPE (tem
))
2408 > floor_log2 (TYPE_PRECISION (rtype
))
2409 && TYPE_PRECISION (TREE_TYPE (tem
))
2410 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
))))
2411 defcodefor_name (tem
, &code
, &tem
, NULL
);
2413 if (code
== NEGATE_EXPR
)
2415 if (tem
== def_arg2
[1 - i
] || tem
== def_arg2_alt
[1 - i
])
2420 defcodefor_name (tem
, &code
, &tem
, NULL
);
2421 if (CONVERT_EXPR_CODE_P (code
)
2422 && INTEGRAL_TYPE_P (TREE_TYPE (tem
))
2423 && TYPE_PRECISION (TREE_TYPE (tem
))
2424 > floor_log2 (TYPE_PRECISION (rtype
))
2425 && TYPE_PRECISION (TREE_TYPE (tem
))
2426 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem
)))
2427 && (tem
== def_arg2
[1 - i
]
2428 || tem
== def_arg2_alt
[1 - i
]))
2435 if (rotcnt
== NULL_TREE
)
2440 if (!useless_type_conversion_p (TREE_TYPE (def_arg2
[0]),
2441 TREE_TYPE (rotcnt
)))
2443 g
= gimple_build_assign_with_ops (NOP_EXPR
,
2444 make_ssa_name (TREE_TYPE (def_arg2
[0]),
2447 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
2448 rotcnt
= gimple_assign_lhs (g
);
2450 lhs
= gimple_assign_lhs (stmt
);
2451 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
2452 lhs
= make_ssa_name (TREE_TYPE (def_arg1
[0]), NULL
);
2453 g
= gimple_build_assign_with_ops (((def_code
[0] == LSHIFT_EXPR
) ^ swapped_p
)
2454 ? LROTATE_EXPR
: RROTATE_EXPR
,
2455 lhs
, def_arg1
[0], rotcnt
);
2456 if (!useless_type_conversion_p (rtype
, TREE_TYPE (def_arg1
[0])))
2458 gsi_insert_before (gsi
, g
, GSI_SAME_STMT
);
2459 g
= gimple_build_assign_with_ops (NOP_EXPR
, gimple_assign_lhs (stmt
),
2462 gsi_replace (gsi
, g
, false);
2466 /* Perform re-associations of the plus or minus statement STMT that are
2467 always permitted. Returns true if the CFG was changed. */
2470 associate_plusminus (gimple_stmt_iterator
*gsi
)
2472 gimple stmt
= gsi_stmt (*gsi
);
2473 tree rhs1
= gimple_assign_rhs1 (stmt
);
2474 tree rhs2
= gimple_assign_rhs2 (stmt
);
2475 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2478 /* We can't reassociate at all for saturating types. */
2479 if (TYPE_SATURATING (TREE_TYPE (rhs1
)))
2482 /* First contract negates. */
2487 /* A +- (-B) -> A -+ B. */
2488 if (TREE_CODE (rhs2
) == SSA_NAME
)
2490 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2491 if (is_gimple_assign (def_stmt
)
2492 && gimple_assign_rhs_code (def_stmt
) == NEGATE_EXPR
2493 && can_propagate_from (def_stmt
))
2495 code
= (code
== MINUS_EXPR
) ? PLUS_EXPR
: MINUS_EXPR
;
2496 gimple_assign_set_rhs_code (stmt
, code
);
2497 rhs2
= gimple_assign_rhs1 (def_stmt
);
2498 gimple_assign_set_rhs2 (stmt
, rhs2
);
2499 gimple_set_modified (stmt
, true);
2504 /* (-A) + B -> B - A. */
2505 if (TREE_CODE (rhs1
) == SSA_NAME
2506 && code
== PLUS_EXPR
)
2508 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2509 if (is_gimple_assign (def_stmt
)
2510 && gimple_assign_rhs_code (def_stmt
) == NEGATE_EXPR
2511 && can_propagate_from (def_stmt
))
2514 gimple_assign_set_rhs_code (stmt
, code
);
2516 gimple_assign_set_rhs1 (stmt
, rhs1
);
2517 rhs2
= gimple_assign_rhs1 (def_stmt
);
2518 gimple_assign_set_rhs2 (stmt
, rhs2
);
2519 gimple_set_modified (stmt
, true);
2526 /* We can't reassociate floating-point or fixed-point plus or minus
2527 because of saturation to +-Inf. */
2528 if (FLOAT_TYPE_P (TREE_TYPE (rhs1
))
2529 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1
)))
2532 /* Second match patterns that allow contracting a plus-minus pair
2533 irrespective of overflow issues.
2535 (A +- B) - A -> +- B
2537 (CST +- A) +- CST -> CST +- A
2538 (A +- CST) +- CST -> A +- CST
2541 A - (A +- B) -> -+ B
2542 A +- (B +- A) -> +- B
2543 CST +- (CST +- A) -> CST +- A
2544 CST +- (A +- CST) -> CST +- A
2546 (T)(P + A) - (T)P -> (T)A
2548 via commutating the addition and contracting operations to zero
2549 by reassociation. */
2551 if (TREE_CODE (rhs1
) == SSA_NAME
)
2553 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2554 if (is_gimple_assign (def_stmt
) && can_propagate_from (def_stmt
))
2556 enum tree_code def_code
= gimple_assign_rhs_code (def_stmt
);
2557 if (def_code
== PLUS_EXPR
2558 || def_code
== MINUS_EXPR
)
2560 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
2561 tree def_rhs2
= gimple_assign_rhs2 (def_stmt
);
2562 if (operand_equal_p (def_rhs1
, rhs2
, 0)
2563 && code
== MINUS_EXPR
)
2565 /* (A +- B) - A -> +- B. */
2566 code
= ((def_code
== PLUS_EXPR
)
2567 ? TREE_CODE (def_rhs2
) : NEGATE_EXPR
);
2570 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2571 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2572 gimple_set_modified (stmt
, true);
2574 else if (operand_equal_p (def_rhs2
, rhs2
, 0)
2575 && code
!= def_code
)
2577 /* (A +- B) -+ B -> A. */
2578 code
= TREE_CODE (def_rhs1
);
2581 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2582 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2583 gimple_set_modified (stmt
, true);
2585 else if (CONSTANT_CLASS_P (rhs2
)
2586 && CONSTANT_CLASS_P (def_rhs1
))
2588 /* (CST +- A) +- CST -> CST +- A. */
2589 tree cst
= fold_binary (code
, TREE_TYPE (rhs1
),
2591 if (cst
&& !TREE_OVERFLOW (cst
))
2594 gimple_assign_set_rhs_code (stmt
, code
);
2596 gimple_assign_set_rhs1 (stmt
, rhs1
);
2598 gimple_assign_set_rhs2 (stmt
, rhs2
);
2599 gimple_set_modified (stmt
, true);
2602 else if (CONSTANT_CLASS_P (rhs2
)
2603 && CONSTANT_CLASS_P (def_rhs2
))
2605 /* (A +- CST) +- CST -> A +- CST. */
2606 enum tree_code mix
= (code
== def_code
)
2607 ? PLUS_EXPR
: MINUS_EXPR
;
2608 tree cst
= fold_binary (mix
, TREE_TYPE (rhs1
),
2610 if (cst
&& !TREE_OVERFLOW (cst
))
2613 gimple_assign_set_rhs_code (stmt
, code
);
2615 gimple_assign_set_rhs1 (stmt
, rhs1
);
2617 gimple_assign_set_rhs2 (stmt
, rhs2
);
2618 gimple_set_modified (stmt
, true);
2622 else if (def_code
== BIT_NOT_EXPR
&& code
== PLUS_EXPR
)
2624 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
2625 if (operand_equal_p (def_rhs1
, rhs2
, 0))
2628 rhs1
= build_all_ones_cst (TREE_TYPE (rhs2
));
2630 code
= TREE_CODE (rhs1
);
2631 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2632 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2633 gimple_set_modified (stmt
, true);
2635 else if ((TREE_CODE (TREE_TYPE (rhs2
)) != COMPLEX_TYPE
2636 && integer_onep (rhs2
))
2637 || (TREE_CODE (rhs2
) == COMPLEX_CST
2638 && integer_onep (TREE_REALPART (rhs2
))
2639 && integer_onep (TREE_IMAGPART (rhs2
))))
2645 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2646 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2647 gimple_set_modified (stmt
, true);
2650 else if (code
== MINUS_EXPR
2651 && CONVERT_EXPR_CODE_P (def_code
)
2652 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
2653 && TREE_CODE (rhs2
) == SSA_NAME
)
2655 /* (T)(P + A) - (T)P -> (T)A. */
2656 gimple def_stmt2
= SSA_NAME_DEF_STMT (rhs2
);
2657 if (is_gimple_assign (def_stmt2
)
2658 && can_propagate_from (def_stmt2
)
2659 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2
))
2660 && TREE_CODE (gimple_assign_rhs1 (def_stmt2
)) == SSA_NAME
)
2662 /* Now we have (T)X - (T)P. */
2663 tree p
= gimple_assign_rhs1 (def_stmt2
);
2664 def_stmt2
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt
));
2665 if (is_gimple_assign (def_stmt2
)
2666 && can_propagate_from (def_stmt2
)
2667 && (gimple_assign_rhs_code (def_stmt2
) == POINTER_PLUS_EXPR
2668 || gimple_assign_rhs_code (def_stmt2
) == PLUS_EXPR
)
2669 && gimple_assign_rhs1 (def_stmt2
) == p
)
2671 /* And finally (T)(P + A) - (T)P. */
2672 tree a
= gimple_assign_rhs2 (def_stmt2
);
2673 if (TYPE_PRECISION (TREE_TYPE (rhs1
))
2674 <= TYPE_PRECISION (TREE_TYPE (a
))
2675 /* For integer types, if A has a smaller type
2676 than T the result depends on the possible
2678 E.g. T=size_t, A=(unsigned)429497295, P>0.
2679 However, if an overflow in P + A would cause
2680 undefined behavior, we can assume that there
2682 || (INTEGRAL_TYPE_P (TREE_TYPE (p
))
2683 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (p
)))
2684 /* For pointer types, if the conversion of A to the
2685 final type requires a sign- or zero-extension,
2686 then we have to punt - it is not defined which
2688 || (POINTER_TYPE_P (TREE_TYPE (p
))
2689 && TREE_CODE (a
) == INTEGER_CST
2690 && tree_int_cst_sign_bit (a
) == 0))
2692 if (issue_strict_overflow_warning
2693 (WARN_STRICT_OVERFLOW_MISC
)
2694 && TYPE_PRECISION (TREE_TYPE (rhs1
))
2695 > TYPE_PRECISION (TREE_TYPE (a
))
2696 && INTEGRAL_TYPE_P (TREE_TYPE (p
)))
2697 warning_at (gimple_location (stmt
),
2698 OPT_Wstrict_overflow
,
2699 "assuming signed overflow does not "
2700 "occur when assuming that "
2701 "(T)(P + A) - (T)P is always (T)A");
2702 if (useless_type_conversion_p (TREE_TYPE (rhs1
),
2704 code
= TREE_CODE (a
);
2709 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
,
2711 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2712 gimple_set_modified (stmt
, true);
2720 if (rhs2
&& TREE_CODE (rhs2
) == SSA_NAME
)
2722 gimple def_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2723 if (is_gimple_assign (def_stmt
) && can_propagate_from (def_stmt
))
2725 enum tree_code def_code
= gimple_assign_rhs_code (def_stmt
);
2726 if (def_code
== PLUS_EXPR
2727 || def_code
== MINUS_EXPR
)
2729 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
2730 tree def_rhs2
= gimple_assign_rhs2 (def_stmt
);
2731 if (operand_equal_p (def_rhs1
, rhs1
, 0)
2732 && code
== MINUS_EXPR
)
2734 /* A - (A +- B) -> -+ B. */
2735 code
= ((def_code
== PLUS_EXPR
)
2736 ? NEGATE_EXPR
: TREE_CODE (def_rhs2
));
2739 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2740 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2741 gimple_set_modified (stmt
, true);
2743 else if (operand_equal_p (def_rhs2
, rhs1
, 0)
2744 && code
!= def_code
)
2746 /* A +- (B +- A) -> +- B. */
2747 code
= ((code
== PLUS_EXPR
)
2748 ? TREE_CODE (def_rhs1
) : NEGATE_EXPR
);
2751 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2752 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2753 gimple_set_modified (stmt
, true);
2755 else if (CONSTANT_CLASS_P (rhs1
)
2756 && CONSTANT_CLASS_P (def_rhs1
))
2758 /* CST +- (CST +- A) -> CST +- A. */
2759 tree cst
= fold_binary (code
, TREE_TYPE (rhs2
),
2761 if (cst
&& !TREE_OVERFLOW (cst
))
2763 code
= (code
== def_code
? PLUS_EXPR
: MINUS_EXPR
);
2764 gimple_assign_set_rhs_code (stmt
, code
);
2766 gimple_assign_set_rhs1 (stmt
, rhs1
);
2768 gimple_assign_set_rhs2 (stmt
, rhs2
);
2769 gimple_set_modified (stmt
, true);
2772 else if (CONSTANT_CLASS_P (rhs1
)
2773 && CONSTANT_CLASS_P (def_rhs2
))
2775 /* CST +- (A +- CST) -> CST +- A. */
2776 tree cst
= fold_binary (def_code
== code
2777 ? PLUS_EXPR
: MINUS_EXPR
,
2780 if (cst
&& !TREE_OVERFLOW (cst
))
2783 gimple_assign_set_rhs1 (stmt
, rhs1
);
2785 gimple_assign_set_rhs2 (stmt
, rhs2
);
2786 gimple_set_modified (stmt
, true);
2790 else if (def_code
== BIT_NOT_EXPR
)
2792 tree def_rhs1
= gimple_assign_rhs1 (def_stmt
);
2793 if (code
== PLUS_EXPR
2794 && operand_equal_p (def_rhs1
, rhs1
, 0))
2797 rhs1
= build_all_ones_cst (TREE_TYPE (rhs1
));
2799 code
= TREE_CODE (rhs1
);
2800 gimple_assign_set_rhs_with_ops (gsi
, code
, rhs1
, NULL_TREE
);
2801 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2802 gimple_set_modified (stmt
, true);
2809 if (gimple_modified_p (stmt
))
2811 fold_stmt_inplace (gsi
);
2819 /* Associate operands of a POINTER_PLUS_EXPR assignmen at *GSI. Returns
2820 true if anything changed, false otherwise. */
2823 associate_pointerplus_align (gimple_stmt_iterator
*gsi
)
2825 gimple stmt
= gsi_stmt (*gsi
);
2827 tree ptr
, rhs
, algn
;
2830 tem = (sizetype) ptr;
2834 and produce the simpler and easier to analyze with respect to alignment
2835 ... = ptr & ~algn; */
2836 ptr
= gimple_assign_rhs1 (stmt
);
2837 rhs
= gimple_assign_rhs2 (stmt
);
2838 if (TREE_CODE (rhs
) != SSA_NAME
)
2840 def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2841 if (!is_gimple_assign (def_stmt
)
2842 || gimple_assign_rhs_code (def_stmt
) != NEGATE_EXPR
)
2844 rhs
= gimple_assign_rhs1 (def_stmt
);
2845 if (TREE_CODE (rhs
) != SSA_NAME
)
2847 def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2848 if (!is_gimple_assign (def_stmt
)
2849 || gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
2851 rhs
= gimple_assign_rhs1 (def_stmt
);
2852 algn
= gimple_assign_rhs2 (def_stmt
);
2853 if (TREE_CODE (rhs
) != SSA_NAME
2854 || TREE_CODE (algn
) != INTEGER_CST
)
2856 def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2857 if (!is_gimple_assign (def_stmt
)
2858 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
2860 if (gimple_assign_rhs1 (def_stmt
) != ptr
)
2863 algn
= wide_int_to_tree (TREE_TYPE (ptr
), wi::bit_not (algn
));
2864 gimple_assign_set_rhs_with_ops (gsi
, BIT_AND_EXPR
, ptr
, algn
);
2865 fold_stmt_inplace (gsi
);
2871 /* Associate operands of a POINTER_PLUS_EXPR assignmen at *GSI. Returns
2872 true if anything changed, false otherwise. */
2875 associate_pointerplus_diff (gimple_stmt_iterator
*gsi
)
2877 gimple stmt
= gsi_stmt (*gsi
);
2885 tem4 = (unsigned long) tem3;
2889 ptr1
= gimple_assign_rhs1 (stmt
);
2890 rhs
= gimple_assign_rhs2 (stmt
);
2891 if (TREE_CODE (rhs
) != SSA_NAME
)
2893 gimple minus
= SSA_NAME_DEF_STMT (rhs
);
2894 /* Conditionally look through a sign-changing conversion. */
2895 if (is_gimple_assign (minus
)
2896 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (minus
))
2897 && (TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (minus
)))
2898 == TYPE_PRECISION (TREE_TYPE (rhs
)))
2899 && TREE_CODE (gimple_assign_rhs1 (minus
)) == SSA_NAME
)
2900 minus
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (minus
));
2901 if (!is_gimple_assign (minus
))
2903 if (gimple_assign_rhs_code (minus
) != MINUS_EXPR
)
2905 rhs
= gimple_assign_rhs2 (minus
);
2906 if (TREE_CODE (rhs
) != SSA_NAME
)
2908 def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2909 if (!is_gimple_assign (def_stmt
)
2910 || ! CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
))
2911 || gimple_assign_rhs1 (def_stmt
) != ptr1
)
2913 rhs
= gimple_assign_rhs1 (minus
);
2914 if (TREE_CODE (rhs
) != SSA_NAME
)
2916 def_stmt
= SSA_NAME_DEF_STMT (rhs
);
2917 if (!is_gimple_assign (def_stmt
)
2918 || ! CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
2920 rhs
= gimple_assign_rhs1 (def_stmt
);
2921 if (! useless_type_conversion_p (TREE_TYPE (ptr1
), TREE_TYPE (rhs
)))
2924 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (rhs
), rhs
, NULL_TREE
);
2930 /* Associate operands of a POINTER_PLUS_EXPR assignmen at *GSI. Returns
2931 true if anything changed, false otherwise. */
2934 associate_pointerplus (gimple_stmt_iterator
*gsi
)
2936 gimple stmt
= gsi_stmt (*gsi
);
2938 tree ptr
, off1
, off2
;
2940 if (associate_pointerplus_align (gsi
)
2941 || associate_pointerplus_diff (gsi
))
2944 /* Associate (p +p off1) +p off2 as (p +p (off1 + off2)). */
2945 ptr
= gimple_assign_rhs1 (stmt
);
2946 off1
= gimple_assign_rhs2 (stmt
);
2947 if (TREE_CODE (ptr
) != SSA_NAME
2948 || !has_single_use (ptr
))
2950 def_stmt
= SSA_NAME_DEF_STMT (ptr
);
2951 if (!is_gimple_assign (def_stmt
)
2952 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
2953 || !can_propagate_from (def_stmt
))
2955 ptr
= gimple_assign_rhs1 (def_stmt
);
2956 off2
= gimple_assign_rhs2 (def_stmt
);
2957 if (!types_compatible_p (TREE_TYPE (off1
), TREE_TYPE (off2
)))
2960 tree off
= make_ssa_name (TREE_TYPE (off1
), NULL
);
2961 gimple ostmt
= gimple_build_assign_with_ops (PLUS_EXPR
, off
, off1
, off2
);
2962 gsi_insert_before (gsi
, ostmt
, GSI_SAME_STMT
);
2964 gimple_assign_set_rhs_with_ops (gsi
, POINTER_PLUS_EXPR
, ptr
, off
);
2970 /* Combine two conversions in a row for the second conversion at *GSI.
2971 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2972 run. Else it returns 0. */
2975 combine_conversions (gimple_stmt_iterator
*gsi
)
2977 gimple stmt
= gsi_stmt (*gsi
);
2980 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2981 enum tree_code code2
;
2983 gcc_checking_assert (CONVERT_EXPR_CODE_P (code
)
2984 || code
== FLOAT_EXPR
2985 || code
== FIX_TRUNC_EXPR
);
2987 lhs
= gimple_assign_lhs (stmt
);
2988 op0
= gimple_assign_rhs1 (stmt
);
2989 if (useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (op0
)))
2991 gimple_assign_set_rhs_code (stmt
, TREE_CODE (op0
));
2995 if (TREE_CODE (op0
) != SSA_NAME
)
2998 def_stmt
= SSA_NAME_DEF_STMT (op0
);
2999 if (!is_gimple_assign (def_stmt
))
3002 code2
= gimple_assign_rhs_code (def_stmt
);
3004 if (CONVERT_EXPR_CODE_P (code2
) || code2
== FLOAT_EXPR
)
3006 tree defop0
= gimple_assign_rhs1 (def_stmt
);
3007 tree type
= TREE_TYPE (lhs
);
3008 tree inside_type
= TREE_TYPE (defop0
);
3009 tree inter_type
= TREE_TYPE (op0
);
3010 int inside_int
= INTEGRAL_TYPE_P (inside_type
);
3011 int inside_ptr
= POINTER_TYPE_P (inside_type
);
3012 int inside_float
= FLOAT_TYPE_P (inside_type
);
3013 int inside_vec
= TREE_CODE (inside_type
) == VECTOR_TYPE
;
3014 unsigned int inside_prec
= TYPE_PRECISION (inside_type
);
3015 int inside_unsignedp
= TYPE_UNSIGNED (inside_type
);
3016 int inter_int
= INTEGRAL_TYPE_P (inter_type
);
3017 int inter_ptr
= POINTER_TYPE_P (inter_type
);
3018 int inter_float
= FLOAT_TYPE_P (inter_type
);
3019 int inter_vec
= TREE_CODE (inter_type
) == VECTOR_TYPE
;
3020 unsigned int inter_prec
= TYPE_PRECISION (inter_type
);
3021 int inter_unsignedp
= TYPE_UNSIGNED (inter_type
);
3022 int final_int
= INTEGRAL_TYPE_P (type
);
3023 int final_ptr
= POINTER_TYPE_P (type
);
3024 int final_float
= FLOAT_TYPE_P (type
);
3025 int final_vec
= TREE_CODE (type
) == VECTOR_TYPE
;
3026 unsigned int final_prec
= TYPE_PRECISION (type
);
3027 int final_unsignedp
= TYPE_UNSIGNED (type
);
3029 /* Don't propagate ssa names that occur in abnormal phis. */
3030 if (TREE_CODE (defop0
) == SSA_NAME
3031 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defop0
))
3034 /* In addition to the cases of two conversions in a row
3035 handled below, if we are converting something to its own
3036 type via an object of identical or wider precision, neither
3037 conversion is needed. */
3038 if (useless_type_conversion_p (type
, inside_type
)
3039 && (((inter_int
|| inter_ptr
) && final_int
)
3040 || (inter_float
&& final_float
))
3041 && inter_prec
>= final_prec
)
3043 gimple_assign_set_rhs1 (stmt
, unshare_expr (defop0
));
3044 gimple_assign_set_rhs_code (stmt
, TREE_CODE (defop0
));
3046 return remove_prop_source_from_use (op0
) ? 2 : 1;
3049 /* Likewise, if the intermediate and initial types are either both
3050 float or both integer, we don't need the middle conversion if the
3051 former is wider than the latter and doesn't change the signedness
3052 (for integers). Avoid this if the final type is a pointer since
3053 then we sometimes need the middle conversion. Likewise if the
3054 final type has a precision not equal to the size of its mode. */
3055 if (((inter_int
&& inside_int
)
3056 || (inter_float
&& inside_float
)
3057 || (inter_vec
&& inside_vec
))
3058 && inter_prec
>= inside_prec
3059 && (inter_float
|| inter_vec
3060 || inter_unsignedp
== inside_unsignedp
)
3061 && ! (final_prec
!= GET_MODE_PRECISION (TYPE_MODE (type
))
3062 && TYPE_MODE (type
) == TYPE_MODE (inter_type
))
3064 && (! final_vec
|| inter_prec
== inside_prec
))
3066 gimple_assign_set_rhs1 (stmt
, defop0
);
3068 return remove_prop_source_from_use (op0
) ? 2 : 1;
3071 /* If we have a sign-extension of a zero-extended value, we can
3072 replace that by a single zero-extension. Likewise if the
3073 final conversion does not change precision we can drop the
3074 intermediate conversion. */
3075 if (inside_int
&& inter_int
&& final_int
3076 && ((inside_prec
< inter_prec
&& inter_prec
< final_prec
3077 && inside_unsignedp
&& !inter_unsignedp
)
3078 || final_prec
== inter_prec
))
3080 gimple_assign_set_rhs1 (stmt
, defop0
);
3082 return remove_prop_source_from_use (op0
) ? 2 : 1;
3085 /* Two conversions in a row are not needed unless:
3086 - some conversion is floating-point (overstrict for now), or
3087 - some conversion is a vector (overstrict for now), or
3088 - the intermediate type is narrower than both initial and
3090 - the intermediate type and innermost type differ in signedness,
3091 and the outermost type is wider than the intermediate, or
3092 - the initial type is a pointer type and the precisions of the
3093 intermediate and final types differ, or
3094 - the final type is a pointer type and the precisions of the
3095 initial and intermediate types differ. */
3096 if (! inside_float
&& ! inter_float
&& ! final_float
3097 && ! inside_vec
&& ! inter_vec
&& ! final_vec
3098 && (inter_prec
>= inside_prec
|| inter_prec
>= final_prec
)
3099 && ! (inside_int
&& inter_int
3100 && inter_unsignedp
!= inside_unsignedp
3101 && inter_prec
< final_prec
)
3102 && ((inter_unsignedp
&& inter_prec
> inside_prec
)
3103 == (final_unsignedp
&& final_prec
> inter_prec
))
3104 && ! (inside_ptr
&& inter_prec
!= final_prec
)
3105 && ! (final_ptr
&& inside_prec
!= inter_prec
)
3106 && ! (final_prec
!= GET_MODE_PRECISION (TYPE_MODE (type
))
3107 && TYPE_MODE (type
) == TYPE_MODE (inter_type
)))
3109 gimple_assign_set_rhs1 (stmt
, defop0
);
3111 return remove_prop_source_from_use (op0
) ? 2 : 1;
3114 /* A truncation to an unsigned type should be canonicalized as
3115 bitwise and of a mask. */
3116 if (final_int
&& inter_int
&& inside_int
3117 && final_prec
== inside_prec
3118 && final_prec
> inter_prec
3122 tem
= fold_build2 (BIT_AND_EXPR
, inside_type
,
3126 wi::mask (inter_prec
, false,
3127 TYPE_PRECISION (inside_type
))));
3128 if (!useless_type_conversion_p (type
, inside_type
))
3130 tem
= force_gimple_operand_gsi (gsi
, tem
, true, NULL_TREE
, true,
3132 gimple_assign_set_rhs1 (stmt
, tem
);
3135 gimple_assign_set_rhs_from_tree (gsi
, tem
);
3136 update_stmt (gsi_stmt (*gsi
));
3140 /* If we are converting an integer to a floating-point that can
3141 represent it exactly and back to an integer, we can skip the
3142 floating-point conversion. */
3143 if (inside_int
&& inter_float
&& final_int
&&
3144 (unsigned) significand_size (TYPE_MODE (inter_type
))
3145 >= inside_prec
- !inside_unsignedp
)
3147 if (useless_type_conversion_p (type
, inside_type
))
3149 gimple_assign_set_rhs1 (stmt
, unshare_expr (defop0
));
3150 gimple_assign_set_rhs_code (stmt
, TREE_CODE (defop0
));
3152 return remove_prop_source_from_use (op0
) ? 2 : 1;
3156 gimple_assign_set_rhs1 (stmt
, defop0
);
3157 gimple_assign_set_rhs_code (stmt
, CONVERT_EXPR
);
3159 return remove_prop_source_from_use (op0
) ? 2 : 1;
3167 /* Combine an element access with a shuffle. Returns true if there were
3168 any changes made, else it returns false. */
3171 simplify_bitfield_ref (gimple_stmt_iterator
*gsi
)
3173 gimple stmt
= gsi_stmt (*gsi
);
3175 tree op
, op0
, op1
, op2
;
3177 unsigned idx
, n
, size
;
3178 enum tree_code code
;
3180 op
= gimple_assign_rhs1 (stmt
);
3181 gcc_checking_assert (TREE_CODE (op
) == BIT_FIELD_REF
);
3183 op0
= TREE_OPERAND (op
, 0);
3184 if (TREE_CODE (op0
) != SSA_NAME
3185 || TREE_CODE (TREE_TYPE (op0
)) != VECTOR_TYPE
)
3188 def_stmt
= get_prop_source_stmt (op0
, false, NULL
);
3189 if (!def_stmt
|| !can_propagate_from (def_stmt
))
3192 op1
= TREE_OPERAND (op
, 1);
3193 op2
= TREE_OPERAND (op
, 2);
3194 code
= gimple_assign_rhs_code (def_stmt
);
3196 if (code
== CONSTRUCTOR
)
3198 tree tem
= fold_ternary (BIT_FIELD_REF
, TREE_TYPE (op
),
3199 gimple_assign_rhs1 (def_stmt
), op1
, op2
);
3200 if (!tem
|| !valid_gimple_rhs_p (tem
))
3202 gimple_assign_set_rhs_from_tree (gsi
, tem
);
3203 update_stmt (gsi_stmt (*gsi
));
3207 elem_type
= TREE_TYPE (TREE_TYPE (op0
));
3208 if (TREE_TYPE (op
) != elem_type
)
3211 size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
3212 n
= TREE_INT_CST_LOW (op1
) / size
;
3215 idx
= TREE_INT_CST_LOW (op2
) / size
;
3217 if (code
== VEC_PERM_EXPR
)
3219 tree p
, m
, index
, tem
;
3221 m
= gimple_assign_rhs3 (def_stmt
);
3222 if (TREE_CODE (m
) != VECTOR_CST
)
3224 nelts
= VECTOR_CST_NELTS (m
);
3225 idx
= TREE_INT_CST_LOW (VECTOR_CST_ELT (m
, idx
));
3229 p
= gimple_assign_rhs1 (def_stmt
);
3233 p
= gimple_assign_rhs2 (def_stmt
);
3236 index
= build_int_cst (TREE_TYPE (TREE_TYPE (m
)), idx
* size
);
3237 tem
= build3 (BIT_FIELD_REF
, TREE_TYPE (op
),
3238 unshare_expr (p
), op1
, index
);
3239 gimple_assign_set_rhs1 (stmt
, tem
);
3241 update_stmt (gsi_stmt (*gsi
));
3248 /* Determine whether applying the 2 permutations (mask1 then mask2)
3249 gives back one of the input. */
3252 is_combined_permutation_identity (tree mask1
, tree mask2
)
3255 unsigned int nelts
, i
, j
;
3256 bool maybe_identity1
= true;
3257 bool maybe_identity2
= true;
3259 gcc_checking_assert (TREE_CODE (mask1
) == VECTOR_CST
3260 && TREE_CODE (mask2
) == VECTOR_CST
);
3261 mask
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (mask1
), mask1
, mask1
, mask2
);
3262 gcc_assert (TREE_CODE (mask
) == VECTOR_CST
);
3264 nelts
= VECTOR_CST_NELTS (mask
);
3265 for (i
= 0; i
< nelts
; i
++)
3267 tree val
= VECTOR_CST_ELT (mask
, i
);
3268 gcc_assert (TREE_CODE (val
) == INTEGER_CST
);
3269 j
= TREE_INT_CST_LOW (val
) & (2 * nelts
- 1);
3271 maybe_identity2
= false;
3272 else if (j
== i
+ nelts
)
3273 maybe_identity1
= false;
3277 return maybe_identity1
? 1 : maybe_identity2
? 2 : 0;
3280 /* Combine a shuffle with its arguments. Returns 1 if there were any
3281 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
3284 simplify_permutation (gimple_stmt_iterator
*gsi
)
3286 gimple stmt
= gsi_stmt (*gsi
);
3288 tree op0
, op1
, op2
, op3
, arg0
, arg1
;
3289 enum tree_code code
;
3290 bool single_use_op0
= false;
3292 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == VEC_PERM_EXPR
);
3294 op0
= gimple_assign_rhs1 (stmt
);
3295 op1
= gimple_assign_rhs2 (stmt
);
3296 op2
= gimple_assign_rhs3 (stmt
);
3298 if (TREE_CODE (op2
) != VECTOR_CST
)
3301 if (TREE_CODE (op0
) == VECTOR_CST
)
3306 else if (TREE_CODE (op0
) == SSA_NAME
)
3308 def_stmt
= get_prop_source_stmt (op0
, false, &single_use_op0
);
3309 if (!def_stmt
|| !can_propagate_from (def_stmt
))
3312 code
= gimple_assign_rhs_code (def_stmt
);
3313 arg0
= gimple_assign_rhs1 (def_stmt
);
3318 /* Two consecutive shuffles. */
3319 if (code
== VEC_PERM_EXPR
)
3326 op3
= gimple_assign_rhs3 (def_stmt
);
3327 if (TREE_CODE (op3
) != VECTOR_CST
)
3329 ident
= is_combined_permutation_identity (op3
, op2
);
3332 orig
= (ident
== 1) ? gimple_assign_rhs1 (def_stmt
)
3333 : gimple_assign_rhs2 (def_stmt
);
3334 gimple_assign_set_rhs1 (stmt
, unshare_expr (orig
));
3335 gimple_assign_set_rhs_code (stmt
, TREE_CODE (orig
));
3336 gimple_set_num_ops (stmt
, 2);
3338 return remove_prop_source_from_use (op0
) ? 2 : 1;
3341 /* Shuffle of a constructor. */
3342 else if (code
== CONSTRUCTOR
|| code
== VECTOR_CST
)
3348 if (TREE_CODE (op0
) == SSA_NAME
&& !single_use_op0
)
3351 if (TREE_CODE (op1
) == VECTOR_CST
)
3353 else if (TREE_CODE (op1
) == SSA_NAME
)
3355 enum tree_code code2
;
3357 gimple def_stmt2
= get_prop_source_stmt (op1
, true, NULL
);
3358 if (!def_stmt2
|| !can_propagate_from (def_stmt2
))
3361 code2
= gimple_assign_rhs_code (def_stmt2
);
3362 if (code2
!= CONSTRUCTOR
&& code2
!= VECTOR_CST
)
3364 arg1
= gimple_assign_rhs1 (def_stmt2
);
3371 /* Already used twice in this statement. */
3372 if (TREE_CODE (op0
) == SSA_NAME
&& num_imm_uses (op0
) > 2)
3376 opt
= fold_ternary (VEC_PERM_EXPR
, TREE_TYPE (op0
), arg0
, arg1
, op2
);
3378 || (TREE_CODE (opt
) != CONSTRUCTOR
&& TREE_CODE (opt
) != VECTOR_CST
))
3380 gimple_assign_set_rhs_from_tree (gsi
, opt
);
3381 update_stmt (gsi_stmt (*gsi
));
3382 if (TREE_CODE (op0
) == SSA_NAME
)
3383 ret
= remove_prop_source_from_use (op0
);
3384 if (op0
!= op1
&& TREE_CODE (op1
) == SSA_NAME
)
3385 ret
|= remove_prop_source_from_use (op1
);
3392 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
3395 simplify_vector_constructor (gimple_stmt_iterator
*gsi
)
3397 gimple stmt
= gsi_stmt (*gsi
);
3399 tree op
, op2
, orig
, type
, elem_type
;
3400 unsigned elem_size
, nelts
, i
;
3401 enum tree_code code
;
3402 constructor_elt
*elt
;
3406 gcc_checking_assert (gimple_assign_rhs_code (stmt
) == CONSTRUCTOR
);
3408 op
= gimple_assign_rhs1 (stmt
);
3409 type
= TREE_TYPE (op
);
3410 gcc_checking_assert (TREE_CODE (type
) == VECTOR_TYPE
);
3412 nelts
= TYPE_VECTOR_SUBPARTS (type
);
3413 elem_type
= TREE_TYPE (type
);
3414 elem_size
= TREE_INT_CST_LOW (TYPE_SIZE (elem_type
));
3416 sel
= XALLOCAVEC (unsigned char, nelts
);
3419 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op
), i
, elt
)
3426 if (TREE_CODE (elt
->value
) != SSA_NAME
)
3428 def_stmt
= get_prop_source_stmt (elt
->value
, false, NULL
);
3431 code
= gimple_assign_rhs_code (def_stmt
);
3432 if (code
!= BIT_FIELD_REF
)
3434 op1
= gimple_assign_rhs1 (def_stmt
);
3435 ref
= TREE_OPERAND (op1
, 0);
3443 if (TREE_CODE (ref
) != SSA_NAME
)
3445 if (!useless_type_conversion_p (type
, TREE_TYPE (ref
)))
3449 if (TREE_INT_CST_LOW (TREE_OPERAND (op1
, 1)) != elem_size
)
3451 sel
[i
] = TREE_INT_CST_LOW (TREE_OPERAND (op1
, 2)) / elem_size
;
3452 if (sel
[i
] != i
) maybe_ident
= false;
3458 gimple_assign_set_rhs_from_tree (gsi
, orig
);
3461 tree mask_type
, *mask_elts
;
3463 if (!can_vec_perm_p (TYPE_MODE (type
), false, sel
))
3466 = build_vector_type (build_nonstandard_integer_type (elem_size
, 1),
3468 if (GET_MODE_CLASS (TYPE_MODE (mask_type
)) != MODE_VECTOR_INT
3469 || GET_MODE_SIZE (TYPE_MODE (mask_type
))
3470 != GET_MODE_SIZE (TYPE_MODE (type
)))
3472 mask_elts
= XALLOCAVEC (tree
, nelts
);
3473 for (i
= 0; i
< nelts
; i
++)
3474 mask_elts
[i
] = build_int_cst (TREE_TYPE (mask_type
), sel
[i
]);
3475 op2
= build_vector (mask_type
, mask_elts
);
3476 gimple_assign_set_rhs_with_ops_1 (gsi
, VEC_PERM_EXPR
, orig
, orig
, op2
);
3478 update_stmt (gsi_stmt (*gsi
));
3482 /* Simplify multiplications.
3483 Return true if a transformation applied, otherwise return false. */
3486 simplify_mult (gimple_stmt_iterator
*gsi
)
3488 gimple stmt
= gsi_stmt (*gsi
);
3489 tree arg1
= gimple_assign_rhs1 (stmt
);
3490 tree arg2
= gimple_assign_rhs2 (stmt
);
3492 if (TREE_CODE (arg1
) != SSA_NAME
)
3495 gimple def_stmt
= SSA_NAME_DEF_STMT (arg1
);
3496 if (!is_gimple_assign (def_stmt
))
3499 /* Look through a sign-changing conversion. */
3500 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt
)))
3502 if (TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (def_stmt
)))
3503 != TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt
)))
3504 || TREE_CODE (gimple_assign_rhs1 (def_stmt
)) != SSA_NAME
)
3506 def_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt
));
3507 if (!is_gimple_assign (def_stmt
))
3511 if (gimple_assign_rhs_code (def_stmt
) == EXACT_DIV_EXPR
)
3513 if (operand_equal_p (gimple_assign_rhs2 (def_stmt
), arg2
, 0))
3515 tree res
= gimple_assign_rhs1 (def_stmt
);
3516 if (useless_type_conversion_p (TREE_TYPE (arg1
), TREE_TYPE (res
)))
3517 gimple_assign_set_rhs_with_ops (gsi
, TREE_CODE (res
), res
,
3520 gimple_assign_set_rhs_with_ops (gsi
, NOP_EXPR
, res
, NULL_TREE
);
3521 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3531 /* Const-and-copy lattice for fold_all_stmts. */
3532 static vec
<tree
> lattice
;
3534 /* Primitive "lattice" function for gimple_simplify. */
3537 fwprop_ssa_val (tree name
)
3539 /* First valueize NAME. */
3540 if (TREE_CODE (name
) == SSA_NAME
3541 && SSA_NAME_VERSION (name
) < lattice
.length ())
3543 tree val
= lattice
[SSA_NAME_VERSION (name
)];
3547 /* We continue matching along SSA use-def edges for SSA names
3548 that are not single-use. Currently there are no patterns
3549 that would cause any issues with that. */
3553 /* Fold all stmts using fold_stmt following only single-use chains
3554 and using a simple const-and-copy lattice. */
3557 fold_all_stmts (struct function
*fun
)
3559 bool cfg_changed
= false;
3561 /* Combine stmts with the stmts defining their operands. Do that
3562 in an order that guarantees visiting SSA defs before SSA uses. */
3563 lattice
.create (num_ssa_names
);
3564 lattice
.quick_grow_cleared (num_ssa_names
);
3565 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (fun
));
3566 int postorder_num
= inverted_post_order_compute (postorder
);
3567 for (int i
= 0; i
< postorder_num
; ++i
)
3569 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, postorder
[i
]);
3570 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3571 !gsi_end_p (gsi
); gsi_next (&gsi
))
3573 gimple stmt
= gsi_stmt (gsi
);
3574 gimple orig_stmt
= stmt
;
3576 if (fold_stmt (&gsi
, fwprop_ssa_val
))
3578 stmt
= gsi_stmt (gsi
);
3579 if (maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
)
3580 && gimple_purge_dead_eh_edges (bb
))
3582 /* Cleanup the CFG if we simplified a condition to
3584 if (gimple_code (stmt
) == GIMPLE_COND
3585 && (gimple_cond_true_p (stmt
)
3586 || gimple_cond_false_p (stmt
)))
3591 /* Fill up the lattice. */
3592 if (gimple_assign_single_p (stmt
))
3594 tree lhs
= gimple_assign_lhs (stmt
);
3595 tree rhs
= gimple_assign_rhs1 (stmt
);
3596 if (TREE_CODE (lhs
) == SSA_NAME
)
3598 if (TREE_CODE (rhs
) == SSA_NAME
)
3599 lattice
[SSA_NAME_VERSION (lhs
)] = fwprop_ssa_val (rhs
);
3600 else if (is_gimple_min_invariant (rhs
))
3601 lattice
[SSA_NAME_VERSION (lhs
)] = rhs
;
3603 lattice
[SSA_NAME_VERSION (lhs
)] = lhs
;
3614 /* Main entry point for the forward propagation and statement combine
3619 const pass_data pass_data_forwprop
=
3621 GIMPLE_PASS
, /* type */
3622 "forwprop", /* name */
3623 OPTGROUP_NONE
, /* optinfo_flags */
3624 TV_TREE_FORWPROP
, /* tv_id */
3625 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3626 0, /* properties_provided */
3627 0, /* properties_destroyed */
3628 0, /* todo_flags_start */
3629 TODO_update_ssa
, /* todo_flags_finish */
3632 class pass_forwprop
: public gimple_opt_pass
3635 pass_forwprop (gcc::context
*ctxt
)
3636 : gimple_opt_pass (pass_data_forwprop
, ctxt
)
3639 /* opt_pass methods: */
3640 opt_pass
* clone () { return new pass_forwprop (m_ctxt
); }
3641 virtual bool gate (function
*) { return flag_tree_forwprop
; }
3642 virtual unsigned int execute (function
*);
3644 }; // class pass_forwprop
3647 pass_forwprop::execute (function
*fun
)
3650 unsigned int todoflags
= 0;
3652 cfg_changed
= false;
3654 FOR_EACH_BB_FN (bb
, fun
)
3656 gimple_stmt_iterator gsi
;
3658 /* Apply forward propagation to all stmts in the basic-block.
3659 Note we update GSI within the loop as necessary. */
3660 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3662 gimple stmt
= gsi_stmt (gsi
);
3664 enum tree_code code
;
3666 if (!is_gimple_assign (stmt
))
3672 lhs
= gimple_assign_lhs (stmt
);
3673 rhs
= gimple_assign_rhs1 (stmt
);
3674 code
= gimple_assign_rhs_code (stmt
);
3675 if (TREE_CODE (lhs
) != SSA_NAME
3676 || has_zero_uses (lhs
))
3682 /* If this statement sets an SSA_NAME to an address,
3683 try to propagate the address into the uses of the SSA_NAME. */
3684 if (code
== ADDR_EXPR
3685 /* Handle pointer conversions on invariant addresses
3686 as well, as this is valid gimple. */
3687 || (CONVERT_EXPR_CODE_P (code
)
3688 && TREE_CODE (rhs
) == ADDR_EXPR
3689 && POINTER_TYPE_P (TREE_TYPE (lhs
))))
3691 tree base
= get_base_address (TREE_OPERAND (rhs
, 0));
3694 || decl_address_invariant_p (base
))
3695 && !stmt_references_abnormal_ssa_name (stmt
)
3696 && forward_propagate_addr_expr (lhs
, rhs
, true))
3698 release_defs (stmt
);
3699 gsi_remove (&gsi
, true);
3704 else if (code
== POINTER_PLUS_EXPR
)
3706 tree off
= gimple_assign_rhs2 (stmt
);
3707 if (TREE_CODE (off
) == INTEGER_CST
3708 && can_propagate_from (stmt
)
3709 && !simple_iv_increment_p (stmt
)
3710 /* ??? Better adjust the interface to that function
3711 instead of building new trees here. */
3712 && forward_propagate_addr_expr
3714 build1_loc (gimple_location (stmt
),
3715 ADDR_EXPR
, TREE_TYPE (rhs
),
3716 fold_build2 (MEM_REF
,
3717 TREE_TYPE (TREE_TYPE (rhs
)),
3719 fold_convert (ptr_type_node
,
3722 release_defs (stmt
);
3723 gsi_remove (&gsi
, true);
3725 else if (is_gimple_min_invariant (rhs
))
3727 /* Make sure to fold &a[0] + off_1 here. */
3728 fold_stmt_inplace (&gsi
);
3730 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3736 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3738 if (forward_propagate_comparison (&gsi
))
3745 /* Combine stmts with the stmts defining their operands.
3746 Note we update GSI within the loop as necessary. */
3747 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
3749 gimple stmt
= gsi_stmt (gsi
);
3750 bool changed
= false;
3752 /* Mark stmt as potentially needing revisiting. */
3753 gimple_set_plf (stmt
, GF_PLF_1
, false);
3755 switch (gimple_code (stmt
))
3759 tree rhs1
= gimple_assign_rhs1 (stmt
);
3760 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3762 if ((code
== BIT_NOT_EXPR
3763 || code
== NEGATE_EXPR
)
3764 && TREE_CODE (rhs1
) == SSA_NAME
)
3765 changed
= simplify_not_neg_expr (&gsi
);
3766 else if (code
== COND_EXPR
3767 || code
== VEC_COND_EXPR
)
3769 /* In this case the entire COND_EXPR is in rhs1. */
3770 if (forward_propagate_into_cond (&gsi
)
3771 || combine_cond_exprs (&gsi
))
3774 stmt
= gsi_stmt (gsi
);
3777 else if (TREE_CODE_CLASS (code
) == tcc_comparison
)
3780 did_something
= forward_propagate_into_comparison (&gsi
);
3781 if (did_something
== 2)
3783 changed
= did_something
!= 0;
3785 else if ((code
== PLUS_EXPR
3786 || code
== BIT_IOR_EXPR
3787 || code
== BIT_XOR_EXPR
)
3788 && simplify_rotate (&gsi
))
3790 else if (code
== BIT_AND_EXPR
3791 || code
== BIT_IOR_EXPR
3792 || code
== BIT_XOR_EXPR
)
3793 changed
= simplify_bitwise_binary (&gsi
);
3794 else if (code
== MULT_EXPR
)
3796 changed
= simplify_mult (&gsi
);
3798 && maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
3799 && gimple_purge_dead_eh_edges (bb
))
3802 else if (code
== PLUS_EXPR
3803 || code
== MINUS_EXPR
)
3805 changed
= associate_plusminus (&gsi
);
3807 && maybe_clean_or_replace_eh_stmt (stmt
, stmt
)
3808 && gimple_purge_dead_eh_edges (bb
))
3811 else if (code
== POINTER_PLUS_EXPR
)
3812 changed
= associate_pointerplus (&gsi
);
3813 else if (CONVERT_EXPR_CODE_P (code
)
3814 || code
== FLOAT_EXPR
3815 || code
== FIX_TRUNC_EXPR
)
3817 int did_something
= combine_conversions (&gsi
);
3818 if (did_something
== 2)
3821 /* If we have a narrowing conversion to an integral
3822 type that is fed by a BIT_AND_EXPR, we might be
3823 able to remove the BIT_AND_EXPR if it merely
3824 masks off bits outside the final type (and nothing
3826 if (! did_something
)
3828 tree outer_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
3829 tree inner_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
3830 if (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
3831 && INTEGRAL_TYPE_P (outer_type
)
3832 && INTEGRAL_TYPE_P (inner_type
)
3833 && (TYPE_PRECISION (outer_type
)
3834 <= TYPE_PRECISION (inner_type
)))
3835 did_something
= simplify_conversion_from_bitmask (&gsi
);
3838 changed
= did_something
!= 0;
3840 else if (code
== VEC_PERM_EXPR
)
3842 int did_something
= simplify_permutation (&gsi
);
3843 if (did_something
== 2)
3845 changed
= did_something
!= 0;
3847 else if (code
== BIT_FIELD_REF
)
3848 changed
= simplify_bitfield_ref (&gsi
);
3849 else if (code
== CONSTRUCTOR
3850 && TREE_CODE (TREE_TYPE (rhs1
)) == VECTOR_TYPE
)
3851 changed
= simplify_vector_constructor (&gsi
);
3856 changed
= simplify_gimple_switch (stmt
);
3862 did_something
= forward_propagate_into_gimple_cond (stmt
);
3863 if (did_something
== 2)
3865 changed
= did_something
!= 0;
3871 tree callee
= gimple_call_fndecl (stmt
);
3872 if (callee
!= NULL_TREE
3873 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
3874 changed
= simplify_builtin_call (&gsi
, callee
);
3883 /* If the stmt changed then re-visit it and the statements
3884 inserted before it. */
3885 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
3886 if (gimple_plf (gsi_stmt (gsi
), GF_PLF_1
))
3888 if (gsi_end_p (gsi
))
3889 gsi
= gsi_start_bb (bb
);
3895 /* Stmt no longer needs to be revisited. */
3896 gimple_set_plf (stmt
, GF_PLF_1
, true);
3902 /* At the end fold all statements. */
3903 cfg_changed
|= fold_all_stmts (fun
);
3906 todoflags
|= TODO_cleanup_cfg
;
3914 make_pass_forwprop (gcc::context
*ctxt
)
3916 return new pass_forwprop (ctxt
);