1 /* Statement simplification on GIMPLE.
2 Copyright (C) 2010-2013 Free Software Foundation, Inc.
3 Split out from tree-ssa-ccp.c.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "stringpool.h"
29 #include "stor-layout.h"
34 #include "basic-block.h"
35 #include "tree-ssa-alias.h"
36 #include "internal-fn.h"
37 #include "gimple-fold.h"
38 #include "gimple-expr.h"
42 #include "gimple-iterator.h"
43 #include "gimple-ssa.h"
44 #include "tree-ssanames.h"
45 #include "tree-into-ssa.h"
48 #include "tree-ssa-propagate.h"
50 #include "ipa-utils.h"
51 #include "gimple-pretty-print.h"
52 #include "tree-ssa-address.h"
53 #include "langhooks.h"
55 /* Return true when DECL can be referenced from current unit.
56 FROM_DECL (if non-null) specify constructor of variable DECL was taken from.
57 We can get declarations that are not possible to reference for various
60 1) When analyzing C++ virtual tables.
61 C++ virtual tables do have known constructors even
62 when they are keyed to other compilation unit.
63 Those tables can contain pointers to methods and vars
64 in other units. Those methods have both STATIC and EXTERNAL
66 2) In WHOPR mode devirtualization might lead to reference
67 to method that was partitioned elsehwere.
68 In this case we have static VAR_DECL or FUNCTION_DECL
69 that has no corresponding callgraph/varpool node
71 3) COMDAT functions referred by external vtables that
72 we devirtualize only during final compilation stage.
73 At this time we already decided that we will not output
74 the function body and thus we can't reference the symbol
78 can_refer_decl_in_current_unit_p (tree decl
, tree from_decl
)
81 struct cgraph_node
*node
;
84 if (DECL_ABSTRACT (decl
))
87 /* We are concerned only about static/external vars and functions. */
88 if ((!TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
89 || (TREE_CODE (decl
) != VAR_DECL
&& TREE_CODE (decl
) != FUNCTION_DECL
))
92 /* Static objects can be referred only if they was not optimized out yet. */
93 if (!TREE_PUBLIC (decl
) && !DECL_EXTERNAL (decl
))
95 snode
= symtab_get_node (decl
);
98 node
= dyn_cast
<cgraph_node
> (snode
);
99 return !node
|| !node
->global
.inlined_to
;
102 /* We will later output the initializer, so we can refer to it.
103 So we are concerned only when DECL comes from initializer of
106 || TREE_CODE (from_decl
) != VAR_DECL
107 || !DECL_EXTERNAL (from_decl
)
109 && symtab_get_node (from_decl
)->in_other_partition
))
111 /* We are folding reference from external vtable. The vtable may reffer
112 to a symbol keyed to other compilation unit. The other compilation
113 unit may be in separate DSO and the symbol may be hidden. */
114 if (DECL_VISIBILITY_SPECIFIED (decl
)
115 && DECL_EXTERNAL (decl
)
116 && (!(snode
= symtab_get_node (decl
)) || !snode
->in_other_partition
))
118 /* When function is public, we always can introduce new reference.
119 Exception are the COMDAT functions where introducing a direct
120 reference imply need to include function body in the curren tunit. */
121 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
123 /* We are not at ltrans stage; so don't worry about WHOPR.
124 Also when still gimplifying all referred comdat functions will be
127 As observed in PR20991 for already optimized out comdat virtual functions
128 it may be tempting to not necessarily give up because the copy will be
129 output elsewhere when corresponding vtable is output.
130 This is however not possible - ABI specify that COMDATs are output in
131 units where they are used and when the other unit was compiled with LTO
132 it is possible that vtable was kept public while the function itself
134 if (!flag_ltrans
&& (!DECL_COMDAT (decl
) || !cgraph_function_flags_ready
))
137 /* OK we are seeing either COMDAT or static variable. In this case we must
138 check that the definition is still around so we can refer it. */
139 if (TREE_CODE (decl
) == FUNCTION_DECL
)
141 node
= cgraph_get_node (decl
);
142 /* Check that we still have function body and that we didn't took
143 the decision to eliminate offline copy of the function yet.
144 The second is important when devirtualization happens during final
145 compilation stage when making a new reference no longer makes callee
147 if (!node
|| !node
->definition
|| node
->global
.inlined_to
)
149 gcc_checking_assert (!TREE_ASM_WRITTEN (decl
));
153 else if (TREE_CODE (decl
) == VAR_DECL
)
155 vnode
= varpool_get_node (decl
);
156 if (!vnode
|| !vnode
->definition
)
158 gcc_checking_assert (!TREE_ASM_WRITTEN (decl
));
165 /* CVAL is value taken from DECL_INITIAL of variable. Try to transform it into
166 acceptable form for is_gimple_min_invariant.
167 FROM_DECL (if non-NULL) specify variable whose constructor contains CVAL. */
170 canonicalize_constructor_val (tree cval
, tree from_decl
)
172 tree orig_cval
= cval
;
174 if (TREE_CODE (cval
) == POINTER_PLUS_EXPR
175 && TREE_CODE (TREE_OPERAND (cval
, 1)) == INTEGER_CST
)
177 tree ptr
= TREE_OPERAND (cval
, 0);
178 if (is_gimple_min_invariant (ptr
))
179 cval
= build1_loc (EXPR_LOCATION (cval
),
180 ADDR_EXPR
, TREE_TYPE (ptr
),
181 fold_build2 (MEM_REF
, TREE_TYPE (TREE_TYPE (ptr
)),
183 fold_convert (ptr_type_node
,
184 TREE_OPERAND (cval
, 1))));
186 if (TREE_CODE (cval
) == ADDR_EXPR
)
188 tree base
= NULL_TREE
;
189 if (TREE_CODE (TREE_OPERAND (cval
, 0)) == COMPOUND_LITERAL_EXPR
)
191 base
= COMPOUND_LITERAL_EXPR_DECL (TREE_OPERAND (cval
, 0));
193 TREE_OPERAND (cval
, 0) = base
;
196 base
= get_base_address (TREE_OPERAND (cval
, 0));
200 if ((TREE_CODE (base
) == VAR_DECL
201 || TREE_CODE (base
) == FUNCTION_DECL
)
202 && !can_refer_decl_in_current_unit_p (base
, from_decl
))
204 if (TREE_CODE (base
) == VAR_DECL
)
205 TREE_ADDRESSABLE (base
) = 1;
206 else if (TREE_CODE (base
) == FUNCTION_DECL
)
208 /* Make sure we create a cgraph node for functions we'll reference.
209 They can be non-existent if the reference comes from an entry
210 of an external vtable for example. */
211 cgraph_get_create_node (base
);
213 /* Fixup types in global initializers. */
214 if (TREE_TYPE (TREE_TYPE (cval
)) != TREE_TYPE (TREE_OPERAND (cval
, 0)))
215 cval
= build_fold_addr_expr (TREE_OPERAND (cval
, 0));
217 if (!useless_type_conversion_p (TREE_TYPE (orig_cval
), TREE_TYPE (cval
)))
218 cval
= fold_convert (TREE_TYPE (orig_cval
), cval
);
221 if (TREE_OVERFLOW_P (cval
))
222 return drop_tree_overflow (cval
);
226 /* If SYM is a constant variable with known value, return the value.
227 NULL_TREE is returned otherwise. */
230 get_symbol_constant_value (tree sym
)
232 tree val
= ctor_for_folding (sym
);
233 if (val
!= error_mark_node
)
237 val
= canonicalize_constructor_val (unshare_expr (val
), sym
);
238 if (val
&& is_gimple_min_invariant (val
))
243 /* Variables declared 'const' without an initializer
244 have zero as the initializer if they may not be
245 overridden at link or run time. */
247 && (INTEGRAL_TYPE_P (TREE_TYPE (sym
))
248 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym
))))
249 return build_zero_cst (TREE_TYPE (sym
));
257 /* Subroutine of fold_stmt. We perform several simplifications of the
258 memory reference tree EXPR and make sure to re-gimplify them properly
259 after propagation of constant addresses. IS_LHS is true if the
260 reference is supposed to be an lvalue. */
263 maybe_fold_reference (tree expr
, bool is_lhs
)
268 if ((TREE_CODE (expr
) == VIEW_CONVERT_EXPR
269 || TREE_CODE (expr
) == REALPART_EXPR
270 || TREE_CODE (expr
) == IMAGPART_EXPR
)
271 && CONSTANT_CLASS_P (TREE_OPERAND (expr
, 0)))
272 return fold_unary_loc (EXPR_LOCATION (expr
),
275 TREE_OPERAND (expr
, 0));
276 else if (TREE_CODE (expr
) == BIT_FIELD_REF
277 && CONSTANT_CLASS_P (TREE_OPERAND (expr
, 0)))
278 return fold_ternary_loc (EXPR_LOCATION (expr
),
281 TREE_OPERAND (expr
, 0),
282 TREE_OPERAND (expr
, 1),
283 TREE_OPERAND (expr
, 2));
285 while (handled_component_p (*t
))
286 t
= &TREE_OPERAND (*t
, 0);
288 /* Canonicalize MEM_REFs invariant address operand. Do this first
289 to avoid feeding non-canonical MEM_REFs elsewhere. */
290 if (TREE_CODE (*t
) == MEM_REF
291 && !is_gimple_mem_ref_addr (TREE_OPERAND (*t
, 0)))
293 bool volatile_p
= TREE_THIS_VOLATILE (*t
);
294 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*t
),
295 TREE_OPERAND (*t
, 0),
296 TREE_OPERAND (*t
, 1));
299 TREE_THIS_VOLATILE (tem
) = volatile_p
;
301 tem
= maybe_fold_reference (expr
, is_lhs
);
309 && (result
= fold_const_aggregate_ref (expr
))
310 && is_gimple_min_invariant (result
))
313 /* Fold back MEM_REFs to reference trees. */
314 if (TREE_CODE (*t
) == MEM_REF
315 && TREE_CODE (TREE_OPERAND (*t
, 0)) == ADDR_EXPR
316 && integer_zerop (TREE_OPERAND (*t
, 1))
317 && (TREE_THIS_VOLATILE (*t
)
318 == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t
, 0), 0)))
319 && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t
, 1)))
320 && (TYPE_MAIN_VARIANT (TREE_TYPE (*t
))
321 == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t
, 1)))))
322 /* We have to look out here to not drop a required conversion
323 from the rhs to the lhs if is_lhs, but we don't have the
324 rhs here to verify that. Thus require strict type
326 && types_compatible_p (TREE_TYPE (*t
),
327 TREE_TYPE (TREE_OPERAND
328 (TREE_OPERAND (*t
, 0), 0))))
331 *t
= TREE_OPERAND (TREE_OPERAND (*t
, 0), 0);
332 tem
= maybe_fold_reference (expr
, is_lhs
);
337 else if (TREE_CODE (*t
) == TARGET_MEM_REF
)
339 tree tem
= maybe_fold_tmr (*t
);
343 tem
= maybe_fold_reference (expr
, is_lhs
);
354 /* Attempt to fold an assignment statement pointed-to by SI. Returns a
355 replacement rhs for the statement or NULL_TREE if no simplification
356 could be made. It is assumed that the operands have been previously
360 fold_gimple_assign (gimple_stmt_iterator
*si
)
362 gimple stmt
= gsi_stmt (*si
);
363 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
364 location_t loc
= gimple_location (stmt
);
366 tree result
= NULL_TREE
;
368 switch (get_gimple_rhs_class (subcode
))
370 case GIMPLE_SINGLE_RHS
:
372 tree rhs
= gimple_assign_rhs1 (stmt
);
374 if (REFERENCE_CLASS_P (rhs
))
375 return maybe_fold_reference (rhs
, false);
377 else if (TREE_CODE (rhs
) == ADDR_EXPR
)
379 tree ref
= TREE_OPERAND (rhs
, 0);
380 tree tem
= maybe_fold_reference (ref
, true);
382 && TREE_CODE (tem
) == MEM_REF
383 && integer_zerop (TREE_OPERAND (tem
, 1)))
384 result
= fold_convert (TREE_TYPE (rhs
), TREE_OPERAND (tem
, 0));
386 result
= fold_convert (TREE_TYPE (rhs
),
387 build_fold_addr_expr_loc (loc
, tem
));
388 else if (TREE_CODE (ref
) == MEM_REF
389 && integer_zerop (TREE_OPERAND (ref
, 1)))
390 result
= fold_convert (TREE_TYPE (rhs
), TREE_OPERAND (ref
, 0));
393 else if (TREE_CODE (rhs
) == CONSTRUCTOR
394 && TREE_CODE (TREE_TYPE (rhs
)) == VECTOR_TYPE
395 && (CONSTRUCTOR_NELTS (rhs
)
396 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs
))))
398 /* Fold a constant vector CONSTRUCTOR to VECTOR_CST. */
402 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs
), i
, val
)
403 if (TREE_CODE (val
) != INTEGER_CST
404 && TREE_CODE (val
) != REAL_CST
405 && TREE_CODE (val
) != FIXED_CST
)
408 return build_vector_from_ctor (TREE_TYPE (rhs
),
409 CONSTRUCTOR_ELTS (rhs
));
412 else if (DECL_P (rhs
))
413 return get_symbol_constant_value (rhs
);
415 /* If we couldn't fold the RHS, hand over to the generic
417 if (result
== NULL_TREE
)
420 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR
421 that may have been added by fold, and "useless" type
422 conversions that might now be apparent due to propagation. */
423 STRIP_USELESS_TYPE_CONVERSION (result
);
425 if (result
!= rhs
&& valid_gimple_rhs_p (result
))
432 case GIMPLE_UNARY_RHS
:
434 tree rhs
= gimple_assign_rhs1 (stmt
);
436 result
= fold_unary_loc (loc
, subcode
, gimple_expr_type (stmt
), rhs
);
439 /* If the operation was a conversion do _not_ mark a
440 resulting constant with TREE_OVERFLOW if the original
441 constant was not. These conversions have implementation
442 defined behavior and retaining the TREE_OVERFLOW flag
443 here would confuse later passes such as VRP. */
444 if (CONVERT_EXPR_CODE_P (subcode
)
445 && TREE_CODE (result
) == INTEGER_CST
446 && TREE_CODE (rhs
) == INTEGER_CST
)
447 TREE_OVERFLOW (result
) = TREE_OVERFLOW (rhs
);
449 STRIP_USELESS_TYPE_CONVERSION (result
);
450 if (valid_gimple_rhs_p (result
))
456 case GIMPLE_BINARY_RHS
:
457 /* Try to canonicalize for boolean-typed X the comparisons
458 X == 0, X == 1, X != 0, and X != 1. */
459 if (gimple_assign_rhs_code (stmt
) == EQ_EXPR
460 || gimple_assign_rhs_code (stmt
) == NE_EXPR
)
462 tree lhs
= gimple_assign_lhs (stmt
);
463 tree op1
= gimple_assign_rhs1 (stmt
);
464 tree op2
= gimple_assign_rhs2 (stmt
);
465 tree type
= TREE_TYPE (op1
);
467 /* Check whether the comparison operands are of the same boolean
468 type as the result type is.
469 Check that second operand is an integer-constant with value
471 if (TREE_CODE (op2
) == INTEGER_CST
472 && (integer_zerop (op2
) || integer_onep (op2
))
473 && useless_type_conversion_p (TREE_TYPE (lhs
), type
))
475 enum tree_code cmp_code
= gimple_assign_rhs_code (stmt
);
476 bool is_logical_not
= false;
478 /* X == 0 and X != 1 is a logical-not.of X
479 X == 1 and X != 0 is X */
480 if ((cmp_code
== EQ_EXPR
&& integer_zerop (op2
))
481 || (cmp_code
== NE_EXPR
&& integer_onep (op2
)))
482 is_logical_not
= true;
484 if (is_logical_not
== false)
486 /* Only for one-bit precision typed X the transformation
487 !X -> ~X is valied. */
488 else if (TYPE_PRECISION (type
) == 1)
489 result
= build1_loc (gimple_location (stmt
), BIT_NOT_EXPR
,
491 /* Otherwise we use !X -> X ^ 1. */
493 result
= build2_loc (gimple_location (stmt
), BIT_XOR_EXPR
,
494 type
, op1
, build_int_cst (type
, 1));
500 result
= fold_binary_loc (loc
, subcode
,
501 TREE_TYPE (gimple_assign_lhs (stmt
)),
502 gimple_assign_rhs1 (stmt
),
503 gimple_assign_rhs2 (stmt
));
507 STRIP_USELESS_TYPE_CONVERSION (result
);
508 if (valid_gimple_rhs_p (result
))
513 case GIMPLE_TERNARY_RHS
:
514 /* Try to fold a conditional expression. */
515 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
517 tree op0
= gimple_assign_rhs1 (stmt
);
520 location_t cond_loc
= gimple_location (stmt
);
522 if (COMPARISON_CLASS_P (op0
))
524 fold_defer_overflow_warnings ();
525 tem
= fold_binary_loc (cond_loc
,
526 TREE_CODE (op0
), TREE_TYPE (op0
),
527 TREE_OPERAND (op0
, 0),
528 TREE_OPERAND (op0
, 1));
529 /* This is actually a conditional expression, not a GIMPLE
530 conditional statement, however, the valid_gimple_rhs_p
531 test still applies. */
532 set
= (tem
&& is_gimple_condexpr (tem
)
533 && valid_gimple_rhs_p (tem
));
534 fold_undefer_overflow_warnings (set
, stmt
, 0);
536 else if (is_gimple_min_invariant (op0
))
545 result
= fold_build3_loc (cond_loc
, COND_EXPR
,
546 TREE_TYPE (gimple_assign_lhs (stmt
)), tem
,
547 gimple_assign_rhs2 (stmt
),
548 gimple_assign_rhs3 (stmt
));
552 result
= fold_ternary_loc (loc
, subcode
,
553 TREE_TYPE (gimple_assign_lhs (stmt
)),
554 gimple_assign_rhs1 (stmt
),
555 gimple_assign_rhs2 (stmt
),
556 gimple_assign_rhs3 (stmt
));
560 STRIP_USELESS_TYPE_CONVERSION (result
);
561 if (valid_gimple_rhs_p (result
))
566 case GIMPLE_INVALID_RHS
:
573 /* Attempt to fold a conditional statement. Return true if any changes were
574 made. We only attempt to fold the condition expression, and do not perform
575 any transformation that would require alteration of the cfg. It is
576 assumed that the operands have been previously folded. */
579 fold_gimple_cond (gimple stmt
)
581 tree result
= fold_binary_loc (gimple_location (stmt
),
582 gimple_cond_code (stmt
),
584 gimple_cond_lhs (stmt
),
585 gimple_cond_rhs (stmt
));
589 STRIP_USELESS_TYPE_CONVERSION (result
);
590 if (is_gimple_condexpr (result
) && valid_gimple_rhs_p (result
))
592 gimple_cond_set_condition_from_tree (stmt
, result
);
600 /* Convert EXPR into a GIMPLE value suitable for substitution on the
601 RHS of an assignment. Insert the necessary statements before
602 iterator *SI_P. The statement at *SI_P, which must be a GIMPLE_CALL
603 is replaced. If the call is expected to produces a result, then it
604 is replaced by an assignment of the new RHS to the result variable.
605 If the result is to be ignored, then the call is replaced by a
606 GIMPLE_NOP. A proper VDEF chain is retained by making the first
607 VUSE and the last VDEF of the whole sequence be the same as the replaced
608 statement and using new SSA names for stores in between. */
611 gimplify_and_update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
614 gimple stmt
, new_stmt
;
615 gimple_stmt_iterator i
;
616 gimple_seq stmts
= NULL
;
620 stmt
= gsi_stmt (*si_p
);
622 gcc_assert (is_gimple_call (stmt
));
624 push_gimplify_context (gimple_in_ssa_p (cfun
));
626 lhs
= gimple_call_lhs (stmt
);
627 if (lhs
== NULL_TREE
)
629 gimplify_and_add (expr
, &stmts
);
630 /* We can end up with folding a memcpy of an empty class assignment
631 which gets optimized away by C++ gimplification. */
632 if (gimple_seq_empty_p (stmts
))
634 pop_gimplify_context (NULL
);
635 if (gimple_in_ssa_p (cfun
))
637 unlink_stmt_vdef (stmt
);
640 gsi_replace (si_p
, gimple_build_nop (), true);
646 tree tmp
= get_initialized_tmp_var (expr
, &stmts
, NULL
);
647 new_stmt
= gimple_build_assign (lhs
, tmp
);
648 i
= gsi_last (stmts
);
649 gsi_insert_after_without_update (&i
, new_stmt
,
650 GSI_CONTINUE_LINKING
);
653 pop_gimplify_context (NULL
);
655 if (gimple_has_location (stmt
))
656 annotate_all_with_location (stmts
, gimple_location (stmt
));
658 /* First iterate over the replacement statements backward, assigning
659 virtual operands to their defining statements. */
661 for (i
= gsi_last (stmts
); !gsi_end_p (i
); gsi_prev (&i
))
663 new_stmt
= gsi_stmt (i
);
664 if ((gimple_assign_single_p (new_stmt
)
665 && !is_gimple_reg (gimple_assign_lhs (new_stmt
)))
666 || (is_gimple_call (new_stmt
)
667 && (gimple_call_flags (new_stmt
)
668 & (ECF_NOVOPS
| ECF_PURE
| ECF_CONST
| ECF_NORETURN
)) == 0))
672 vdef
= gimple_vdef (stmt
);
674 vdef
= make_ssa_name (gimple_vop (cfun
), new_stmt
);
675 gimple_set_vdef (new_stmt
, vdef
);
676 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
677 SSA_NAME_DEF_STMT (vdef
) = new_stmt
;
678 laststore
= new_stmt
;
682 /* Second iterate over the statements forward, assigning virtual
683 operands to their uses. */
684 reaching_vuse
= gimple_vuse (stmt
);
685 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
687 new_stmt
= gsi_stmt (i
);
688 /* If the new statement possibly has a VUSE, update it with exact SSA
689 name we know will reach this one. */
690 if (gimple_has_mem_ops (new_stmt
))
691 gimple_set_vuse (new_stmt
, reaching_vuse
);
692 gimple_set_modified (new_stmt
, true);
693 if (gimple_vdef (new_stmt
))
694 reaching_vuse
= gimple_vdef (new_stmt
);
697 /* If the new sequence does not do a store release the virtual
698 definition of the original statement. */
700 && reaching_vuse
== gimple_vuse (stmt
))
702 tree vdef
= gimple_vdef (stmt
);
704 && TREE_CODE (vdef
) == SSA_NAME
)
706 unlink_stmt_vdef (stmt
);
707 release_ssa_name (vdef
);
711 /* Finally replace the original statement with the sequence. */
712 gsi_replace_with_seq (si_p
, stmts
, false);
715 /* Return the string length, maximum string length or maximum value of
717 If ARG is an SSA name variable, follow its use-def chains. If LENGTH
718 is not NULL and, for TYPE == 0, its value is not equal to the length
719 we determine or if we are unable to determine the length or value,
720 return false. VISITED is a bitmap of visited variables.
721 TYPE is 0 if string length should be returned, 1 for maximum string
722 length and 2 for maximum value ARG can have. */
725 get_maxval_strlen (tree arg
, tree
*length
, bitmap visited
, int type
)
730 if (TREE_CODE (arg
) != SSA_NAME
)
732 /* We can end up with &(*iftmp_1)[0] here as well, so handle it. */
733 if (TREE_CODE (arg
) == ADDR_EXPR
734 && TREE_CODE (TREE_OPERAND (arg
, 0)) == ARRAY_REF
735 && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg
, 0), 1)))
737 tree aop0
= TREE_OPERAND (TREE_OPERAND (arg
, 0), 0);
738 if (TREE_CODE (aop0
) == INDIRECT_REF
739 && TREE_CODE (TREE_OPERAND (aop0
, 0)) == SSA_NAME
)
740 return get_maxval_strlen (TREE_OPERAND (aop0
, 0),
741 length
, visited
, type
);
747 if (TREE_CODE (val
) != INTEGER_CST
748 || tree_int_cst_sgn (val
) < 0)
752 val
= c_strlen (arg
, 1);
760 if (TREE_CODE (*length
) != INTEGER_CST
761 || TREE_CODE (val
) != INTEGER_CST
)
764 if (tree_int_cst_lt (*length
, val
))
768 else if (simple_cst_equal (val
, *length
) != 1)
776 /* If ARG is registered for SSA update we cannot look at its defining
778 if (name_registered_for_update_p (arg
))
781 /* If we were already here, break the infinite cycle. */
782 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (arg
)))
786 def_stmt
= SSA_NAME_DEF_STMT (var
);
788 switch (gimple_code (def_stmt
))
791 /* The RHS of the statement defining VAR must either have a
792 constant length or come from another SSA_NAME with a constant
794 if (gimple_assign_single_p (def_stmt
)
795 || gimple_assign_unary_nop_p (def_stmt
))
797 tree rhs
= gimple_assign_rhs1 (def_stmt
);
798 return get_maxval_strlen (rhs
, length
, visited
, type
);
800 else if (gimple_assign_rhs_code (def_stmt
) == COND_EXPR
)
802 tree op2
= gimple_assign_rhs2 (def_stmt
);
803 tree op3
= gimple_assign_rhs3 (def_stmt
);
804 return get_maxval_strlen (op2
, length
, visited
, type
)
805 && get_maxval_strlen (op3
, length
, visited
, type
);
811 /* All the arguments of the PHI node must have the same constant
815 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
817 tree arg
= gimple_phi_arg (def_stmt
, i
)->def
;
819 /* If this PHI has itself as an argument, we cannot
820 determine the string length of this argument. However,
821 if we can find a constant string length for the other
822 PHI args then we can still be sure that this is a
823 constant string length. So be optimistic and just
824 continue with the next argument. */
825 if (arg
== gimple_phi_result (def_stmt
))
828 if (!get_maxval_strlen (arg
, length
, visited
, type
))
840 /* Fold builtin call in statement STMT. Returns a simplified tree.
841 We may return a non-constant expression, including another call
842 to a different function and with different arguments, e.g.,
843 substituting memcpy for strcpy when the string length is known.
844 Note that some builtins expand into inline code that may not
845 be valid in GIMPLE. Callers must take care. */
848 gimple_fold_builtin (gimple stmt
)
856 location_t loc
= gimple_location (stmt
);
858 gcc_assert (is_gimple_call (stmt
));
860 ignore
= (gimple_call_lhs (stmt
) == NULL
);
862 /* First try the generic builtin folder. If that succeeds, return the
864 result
= fold_call_stmt (stmt
, ignore
);
872 /* Ignore MD builtins. */
873 callee
= gimple_call_fndecl (stmt
);
874 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_MD
)
877 /* Give up for always_inline inline builtins until they are
879 if (avoid_folding_inline_builtin (callee
))
882 /* If the builtin could not be folded, and it has no argument list,
884 nargs
= gimple_call_num_args (stmt
);
888 /* Limit the work only for builtins we know how to simplify. */
889 switch (DECL_FUNCTION_CODE (callee
))
891 case BUILT_IN_STRLEN
:
893 case BUILT_IN_FPUTS_UNLOCKED
:
897 case BUILT_IN_STRCPY
:
898 case BUILT_IN_STRNCPY
:
902 case BUILT_IN_MEMCPY_CHK
:
903 case BUILT_IN_MEMPCPY_CHK
:
904 case BUILT_IN_MEMMOVE_CHK
:
905 case BUILT_IN_MEMSET_CHK
:
906 case BUILT_IN_STRNCPY_CHK
:
907 case BUILT_IN_STPNCPY_CHK
:
911 case BUILT_IN_STRCPY_CHK
:
912 case BUILT_IN_STPCPY_CHK
:
916 case BUILT_IN_SNPRINTF_CHK
:
917 case BUILT_IN_VSNPRINTF_CHK
:
925 if (arg_idx
>= nargs
)
928 /* Try to use the dataflow information gathered by the CCP process. */
929 visited
= BITMAP_ALLOC (NULL
);
930 bitmap_clear (visited
);
932 memset (val
, 0, sizeof (val
));
933 a
= gimple_call_arg (stmt
, arg_idx
);
934 if (!get_maxval_strlen (a
, &val
[arg_idx
], visited
, type
))
935 val
[arg_idx
] = NULL_TREE
;
937 BITMAP_FREE (visited
);
940 switch (DECL_FUNCTION_CODE (callee
))
942 case BUILT_IN_STRLEN
:
943 if (val
[0] && nargs
== 1)
946 fold_convert (TREE_TYPE (gimple_call_lhs (stmt
)), val
[0]);
948 /* If the result is not a valid gimple value, or not a cast
949 of a valid gimple value, then we cannot use the result. */
950 if (is_gimple_val (new_val
)
951 || (CONVERT_EXPR_P (new_val
)
952 && is_gimple_val (TREE_OPERAND (new_val
, 0))))
957 case BUILT_IN_STRCPY
:
958 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 2)
959 result
= fold_builtin_strcpy (loc
, callee
,
960 gimple_call_arg (stmt
, 0),
961 gimple_call_arg (stmt
, 1),
965 case BUILT_IN_STRNCPY
:
966 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 3)
967 result
= fold_builtin_strncpy (loc
, callee
,
968 gimple_call_arg (stmt
, 0),
969 gimple_call_arg (stmt
, 1),
970 gimple_call_arg (stmt
, 2),
976 result
= fold_builtin_fputs (loc
, gimple_call_arg (stmt
, 0),
977 gimple_call_arg (stmt
, 1),
978 ignore
, false, val
[0]);
981 case BUILT_IN_FPUTS_UNLOCKED
:
983 result
= fold_builtin_fputs (loc
, gimple_call_arg (stmt
, 0),
984 gimple_call_arg (stmt
, 1),
985 ignore
, true, val
[0]);
988 case BUILT_IN_MEMCPY_CHK
:
989 case BUILT_IN_MEMPCPY_CHK
:
990 case BUILT_IN_MEMMOVE_CHK
:
991 case BUILT_IN_MEMSET_CHK
:
992 if (val
[2] && is_gimple_val (val
[2]) && nargs
== 4)
993 result
= fold_builtin_memory_chk (loc
, callee
,
994 gimple_call_arg (stmt
, 0),
995 gimple_call_arg (stmt
, 1),
996 gimple_call_arg (stmt
, 2),
997 gimple_call_arg (stmt
, 3),
999 DECL_FUNCTION_CODE (callee
));
1002 case BUILT_IN_STRCPY_CHK
:
1003 case BUILT_IN_STPCPY_CHK
:
1004 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 3)
1005 result
= fold_builtin_stxcpy_chk (loc
, callee
,
1006 gimple_call_arg (stmt
, 0),
1007 gimple_call_arg (stmt
, 1),
1008 gimple_call_arg (stmt
, 2),
1010 DECL_FUNCTION_CODE (callee
));
1013 case BUILT_IN_STRNCPY_CHK
:
1014 case BUILT_IN_STPNCPY_CHK
:
1015 if (val
[2] && is_gimple_val (val
[2]) && nargs
== 4)
1016 result
= fold_builtin_stxncpy_chk (loc
, gimple_call_arg (stmt
, 0),
1017 gimple_call_arg (stmt
, 1),
1018 gimple_call_arg (stmt
, 2),
1019 gimple_call_arg (stmt
, 3),
1021 DECL_FUNCTION_CODE (callee
));
1024 case BUILT_IN_SNPRINTF_CHK
:
1025 case BUILT_IN_VSNPRINTF_CHK
:
1026 if (val
[1] && is_gimple_val (val
[1]))
1027 result
= gimple_fold_builtin_snprintf_chk (stmt
, val
[1],
1028 DECL_FUNCTION_CODE (callee
));
1035 if (result
&& ignore
)
1036 result
= fold_ignored_result (result
);
1041 /* Return a binfo to be used for devirtualization of calls based on an object
1042 represented by a declaration (i.e. a global or automatically allocated one)
1043 or NULL if it cannot be found or is not safe. CST is expected to be an
1044 ADDR_EXPR of such object or the function will return NULL. Currently it is
1045 safe to use such binfo only if it has no base binfo (i.e. no ancestors)
1046 EXPECTED_TYPE is type of the class virtual belongs to. */
1049 gimple_extract_devirt_binfo_from_cst (tree cst
, tree expected_type
)
1051 HOST_WIDE_INT offset
, size
, max_size
;
1052 tree base
, type
, binfo
;
1053 bool last_artificial
= false;
1055 if (!flag_devirtualize
1056 || TREE_CODE (cst
) != ADDR_EXPR
1057 || TREE_CODE (TREE_TYPE (TREE_TYPE (cst
))) != RECORD_TYPE
)
1060 cst
= TREE_OPERAND (cst
, 0);
1061 base
= get_ref_base_and_extent (cst
, &offset
, &size
, &max_size
);
1062 type
= TREE_TYPE (base
);
1066 || TREE_CODE (type
) != RECORD_TYPE
)
1069 /* Find the sub-object the constant actually refers to and mark whether it is
1070 an artificial one (as opposed to a user-defined one). */
1073 HOST_WIDE_INT pos
, size
;
1076 if (types_same_for_odr (type
, expected_type
))
1081 for (fld
= TYPE_FIELDS (type
); fld
; fld
= DECL_CHAIN (fld
))
1083 if (TREE_CODE (fld
) != FIELD_DECL
)
1086 pos
= int_bit_position (fld
);
1087 size
= tree_to_uhwi (DECL_SIZE (fld
));
1088 if (pos
<= offset
&& (pos
+ size
) > offset
)
1091 if (!fld
|| TREE_CODE (TREE_TYPE (fld
)) != RECORD_TYPE
)
1094 last_artificial
= DECL_ARTIFICIAL (fld
);
1095 type
= TREE_TYPE (fld
);
1098 /* Artificial sub-objects are ancestors, we do not want to use them for
1099 devirtualization, at least not here. */
1100 if (last_artificial
)
1102 binfo
= TYPE_BINFO (type
);
1103 if (!binfo
|| BINFO_N_BASE_BINFOS (binfo
) > 0)
1109 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1110 The statement may be replaced by another statement, e.g., if the call
1111 simplifies to a constant value. Return true if any changes were made.
1112 It is assumed that the operands have been previously folded. */
1115 gimple_fold_call (gimple_stmt_iterator
*gsi
, bool inplace
)
1117 gimple stmt
= gsi_stmt (*gsi
);
1119 bool changed
= false;
1122 /* Fold *& in call arguments. */
1123 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
1124 if (REFERENCE_CLASS_P (gimple_call_arg (stmt
, i
)))
1126 tree tmp
= maybe_fold_reference (gimple_call_arg (stmt
, i
), false);
1129 gimple_call_set_arg (stmt
, i
, tmp
);
1134 /* Check for virtual calls that became direct calls. */
1135 callee
= gimple_call_fn (stmt
);
1136 if (callee
&& TREE_CODE (callee
) == OBJ_TYPE_REF
)
1138 if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee
)) != NULL_TREE
)
1140 if (dump_file
&& virtual_method_call_p (callee
)
1141 && !possible_polymorphic_call_target_p
1142 (callee
, cgraph_get_node (gimple_call_addr_fndecl
1143 (OBJ_TYPE_REF_EXPR (callee
)))))
1146 "Type inheritnace inconsistent devirtualization of ");
1147 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1148 fprintf (dump_file
, " to ");
1149 print_generic_expr (dump_file
, callee
, TDF_SLIM
);
1150 fprintf (dump_file
, "\n");
1153 gimple_call_set_fn (stmt
, OBJ_TYPE_REF_EXPR (callee
));
1156 else if (flag_devirtualize
&& virtual_method_call_p (callee
))
1159 vec
<cgraph_node
*>targets
1160 = possible_polymorphic_call_targets (callee
, &final
);
1161 if (final
&& targets
.length () <= 1)
1164 if (targets
.length () == 1)
1165 fndecl
= targets
[0]->decl
;
1167 fndecl
= builtin_decl_implicit (BUILT_IN_UNREACHABLE
);
1168 gimple_call_set_fndecl (stmt
, fndecl
);
1177 /* Check for builtins that CCP can handle using information not
1178 available in the generic fold routines. */
1179 callee
= gimple_call_fndecl (stmt
);
1180 if (callee
&& DECL_BUILT_IN (callee
))
1182 tree result
= gimple_fold_builtin (stmt
);
1185 if (!update_call_from_tree (gsi
, result
))
1186 gimplify_and_update_call_from_tree (gsi
, result
);
1189 else if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_MD
)
1190 changed
|= targetm
.gimple_fold_builtin (gsi
);
1196 /* Worker for both fold_stmt and fold_stmt_inplace. The INPLACE argument
1197 distinguishes both cases. */
1200 fold_stmt_1 (gimple_stmt_iterator
*gsi
, bool inplace
)
1202 bool changed
= false;
1203 gimple stmt
= gsi_stmt (*gsi
);
1206 /* Fold the main computation performed by the statement. */
1207 switch (gimple_code (stmt
))
1211 unsigned old_num_ops
= gimple_num_ops (stmt
);
1212 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
1213 tree lhs
= gimple_assign_lhs (stmt
);
1215 /* First canonicalize operand order. This avoids building new
1216 trees if this is the only thing fold would later do. */
1217 if ((commutative_tree_code (subcode
)
1218 || commutative_ternary_tree_code (subcode
))
1219 && tree_swap_operands_p (gimple_assign_rhs1 (stmt
),
1220 gimple_assign_rhs2 (stmt
), false))
1222 tree tem
= gimple_assign_rhs1 (stmt
);
1223 gimple_assign_set_rhs1 (stmt
, gimple_assign_rhs2 (stmt
));
1224 gimple_assign_set_rhs2 (stmt
, tem
);
1227 new_rhs
= fold_gimple_assign (gsi
);
1229 && !useless_type_conversion_p (TREE_TYPE (lhs
),
1230 TREE_TYPE (new_rhs
)))
1231 new_rhs
= fold_convert (TREE_TYPE (lhs
), new_rhs
);
1234 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs
)) < old_num_ops
))
1236 gimple_assign_set_rhs_from_tree (gsi
, new_rhs
);
1243 changed
|= fold_gimple_cond (stmt
);
1247 changed
|= gimple_fold_call (gsi
, inplace
);
1251 /* Fold *& in asm operands. */
1254 const char **oconstraints
;
1255 const char *constraint
;
1256 bool allows_mem
, allows_reg
;
1258 noutputs
= gimple_asm_noutputs (stmt
);
1259 oconstraints
= XALLOCAVEC (const char *, noutputs
);
1261 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
1263 tree link
= gimple_asm_output_op (stmt
, i
);
1264 tree op
= TREE_VALUE (link
);
1266 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1267 if (REFERENCE_CLASS_P (op
)
1268 && (op
= maybe_fold_reference (op
, true)) != NULL_TREE
)
1270 TREE_VALUE (link
) = op
;
1274 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
1276 tree link
= gimple_asm_input_op (stmt
, i
);
1277 tree op
= TREE_VALUE (link
);
1279 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
1280 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0,
1281 oconstraints
, &allows_mem
, &allows_reg
);
1282 if (REFERENCE_CLASS_P (op
)
1283 && (op
= maybe_fold_reference (op
, !allows_reg
&& allows_mem
))
1286 TREE_VALUE (link
) = op
;
1294 if (gimple_debug_bind_p (stmt
))
1296 tree val
= gimple_debug_bind_get_value (stmt
);
1298 && REFERENCE_CLASS_P (val
))
1300 tree tem
= maybe_fold_reference (val
, false);
1303 gimple_debug_bind_set_value (stmt
, tem
);
1308 && TREE_CODE (val
) == ADDR_EXPR
)
1310 tree ref
= TREE_OPERAND (val
, 0);
1311 tree tem
= maybe_fold_reference (ref
, false);
1314 tem
= build_fold_addr_expr_with_type (tem
, TREE_TYPE (val
));
1315 gimple_debug_bind_set_value (stmt
, tem
);
1325 stmt
= gsi_stmt (*gsi
);
1327 /* Fold *& on the lhs. */
1328 if (gimple_has_lhs (stmt
))
1330 tree lhs
= gimple_get_lhs (stmt
);
1331 if (lhs
&& REFERENCE_CLASS_P (lhs
))
1333 tree new_lhs
= maybe_fold_reference (lhs
, true);
1336 gimple_set_lhs (stmt
, new_lhs
);
1345 /* Fold the statement pointed to by GSI. In some cases, this function may
1346 replace the whole statement with a new one. Returns true iff folding
1348 The statement pointed to by GSI should be in valid gimple form but may
1349 be in unfolded state as resulting from for example constant propagation
1350 which can produce *&x = 0. */
1353 fold_stmt (gimple_stmt_iterator
*gsi
)
1355 return fold_stmt_1 (gsi
, false);
1358 /* Perform the minimal folding on statement *GSI. Only operations like
1359 *&x created by constant propagation are handled. The statement cannot
1360 be replaced with a new one. Return true if the statement was
1361 changed, false otherwise.
1362 The statement *GSI should be in valid gimple form but may
1363 be in unfolded state as resulting from for example constant propagation
1364 which can produce *&x = 0. */
1367 fold_stmt_inplace (gimple_stmt_iterator
*gsi
)
1369 gimple stmt
= gsi_stmt (*gsi
);
1370 bool changed
= fold_stmt_1 (gsi
, true);
1371 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1375 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1376 if EXPR is null or we don't know how.
1377 If non-null, the result always has boolean type. */
1380 canonicalize_bool (tree expr
, bool invert
)
1386 if (integer_nonzerop (expr
))
1387 return boolean_false_node
;
1388 else if (integer_zerop (expr
))
1389 return boolean_true_node
;
1390 else if (TREE_CODE (expr
) == SSA_NAME
)
1391 return fold_build2 (EQ_EXPR
, boolean_type_node
, expr
,
1392 build_int_cst (TREE_TYPE (expr
), 0));
1393 else if (TREE_CODE_CLASS (TREE_CODE (expr
)) == tcc_comparison
)
1394 return fold_build2 (invert_tree_comparison (TREE_CODE (expr
), false),
1396 TREE_OPERAND (expr
, 0),
1397 TREE_OPERAND (expr
, 1));
1403 if (TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
)
1405 if (integer_nonzerop (expr
))
1406 return boolean_true_node
;
1407 else if (integer_zerop (expr
))
1408 return boolean_false_node
;
1409 else if (TREE_CODE (expr
) == SSA_NAME
)
1410 return fold_build2 (NE_EXPR
, boolean_type_node
, expr
,
1411 build_int_cst (TREE_TYPE (expr
), 0));
1412 else if (TREE_CODE_CLASS (TREE_CODE (expr
)) == tcc_comparison
)
1413 return fold_build2 (TREE_CODE (expr
),
1415 TREE_OPERAND (expr
, 0),
1416 TREE_OPERAND (expr
, 1));
1422 /* Check to see if a boolean expression EXPR is logically equivalent to the
1423 comparison (OP1 CODE OP2). Check for various identities involving
1427 same_bool_comparison_p (const_tree expr
, enum tree_code code
,
1428 const_tree op1
, const_tree op2
)
1432 /* The obvious case. */
1433 if (TREE_CODE (expr
) == code
1434 && operand_equal_p (TREE_OPERAND (expr
, 0), op1
, 0)
1435 && operand_equal_p (TREE_OPERAND (expr
, 1), op2
, 0))
1438 /* Check for comparing (name, name != 0) and the case where expr
1439 is an SSA_NAME with a definition matching the comparison. */
1440 if (TREE_CODE (expr
) == SSA_NAME
1441 && TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
)
1443 if (operand_equal_p (expr
, op1
, 0))
1444 return ((code
== NE_EXPR
&& integer_zerop (op2
))
1445 || (code
== EQ_EXPR
&& integer_nonzerop (op2
)));
1446 s
= SSA_NAME_DEF_STMT (expr
);
1447 if (is_gimple_assign (s
)
1448 && gimple_assign_rhs_code (s
) == code
1449 && operand_equal_p (gimple_assign_rhs1 (s
), op1
, 0)
1450 && operand_equal_p (gimple_assign_rhs2 (s
), op2
, 0))
1454 /* If op1 is of the form (name != 0) or (name == 0), and the definition
1455 of name is a comparison, recurse. */
1456 if (TREE_CODE (op1
) == SSA_NAME
1457 && TREE_CODE (TREE_TYPE (op1
)) == BOOLEAN_TYPE
)
1459 s
= SSA_NAME_DEF_STMT (op1
);
1460 if (is_gimple_assign (s
)
1461 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
1463 enum tree_code c
= gimple_assign_rhs_code (s
);
1464 if ((c
== NE_EXPR
&& integer_zerop (op2
))
1465 || (c
== EQ_EXPR
&& integer_nonzerop (op2
)))
1466 return same_bool_comparison_p (expr
, c
,
1467 gimple_assign_rhs1 (s
),
1468 gimple_assign_rhs2 (s
));
1469 if ((c
== EQ_EXPR
&& integer_zerop (op2
))
1470 || (c
== NE_EXPR
&& integer_nonzerop (op2
)))
1471 return same_bool_comparison_p (expr
,
1472 invert_tree_comparison (c
, false),
1473 gimple_assign_rhs1 (s
),
1474 gimple_assign_rhs2 (s
));
1480 /* Check to see if two boolean expressions OP1 and OP2 are logically
1484 same_bool_result_p (const_tree op1
, const_tree op2
)
1486 /* Simple cases first. */
1487 if (operand_equal_p (op1
, op2
, 0))
1490 /* Check the cases where at least one of the operands is a comparison.
1491 These are a bit smarter than operand_equal_p in that they apply some
1492 identifies on SSA_NAMEs. */
1493 if (TREE_CODE_CLASS (TREE_CODE (op2
)) == tcc_comparison
1494 && same_bool_comparison_p (op1
, TREE_CODE (op2
),
1495 TREE_OPERAND (op2
, 0),
1496 TREE_OPERAND (op2
, 1)))
1498 if (TREE_CODE_CLASS (TREE_CODE (op1
)) == tcc_comparison
1499 && same_bool_comparison_p (op2
, TREE_CODE (op1
),
1500 TREE_OPERAND (op1
, 0),
1501 TREE_OPERAND (op1
, 1)))
1508 /* Forward declarations for some mutually recursive functions. */
1511 and_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1512 enum tree_code code2
, tree op2a
, tree op2b
);
1514 and_var_with_comparison (tree var
, bool invert
,
1515 enum tree_code code2
, tree op2a
, tree op2b
);
1517 and_var_with_comparison_1 (gimple stmt
,
1518 enum tree_code code2
, tree op2a
, tree op2b
);
1520 or_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1521 enum tree_code code2
, tree op2a
, tree op2b
);
1523 or_var_with_comparison (tree var
, bool invert
,
1524 enum tree_code code2
, tree op2a
, tree op2b
);
1526 or_var_with_comparison_1 (gimple stmt
,
1527 enum tree_code code2
, tree op2a
, tree op2b
);
1529 /* Helper function for and_comparisons_1: try to simplify the AND of the
1530 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1531 If INVERT is true, invert the value of the VAR before doing the AND.
1532 Return NULL_EXPR if we can't simplify this to a single expression. */
1535 and_var_with_comparison (tree var
, bool invert
,
1536 enum tree_code code2
, tree op2a
, tree op2b
)
1539 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1541 /* We can only deal with variables whose definitions are assignments. */
1542 if (!is_gimple_assign (stmt
))
1545 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1546 !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1547 Then we only have to consider the simpler non-inverted cases. */
1549 t
= or_var_with_comparison_1 (stmt
,
1550 invert_tree_comparison (code2
, false),
1553 t
= and_var_with_comparison_1 (stmt
, code2
, op2a
, op2b
);
1554 return canonicalize_bool (t
, invert
);
1557 /* Try to simplify the AND of the ssa variable defined by the assignment
1558 STMT with the comparison specified by (OP2A CODE2 OP2B).
1559 Return NULL_EXPR if we can't simplify this to a single expression. */
1562 and_var_with_comparison_1 (gimple stmt
,
1563 enum tree_code code2
, tree op2a
, tree op2b
)
1565 tree var
= gimple_assign_lhs (stmt
);
1566 tree true_test_var
= NULL_TREE
;
1567 tree false_test_var
= NULL_TREE
;
1568 enum tree_code innercode
= gimple_assign_rhs_code (stmt
);
1570 /* Check for identities like (var AND (var == 0)) => false. */
1571 if (TREE_CODE (op2a
) == SSA_NAME
1572 && TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
)
1574 if ((code2
== NE_EXPR
&& integer_zerop (op2b
))
1575 || (code2
== EQ_EXPR
&& integer_nonzerop (op2b
)))
1577 true_test_var
= op2a
;
1578 if (var
== true_test_var
)
1581 else if ((code2
== EQ_EXPR
&& integer_zerop (op2b
))
1582 || (code2
== NE_EXPR
&& integer_nonzerop (op2b
)))
1584 false_test_var
= op2a
;
1585 if (var
== false_test_var
)
1586 return boolean_false_node
;
1590 /* If the definition is a comparison, recurse on it. */
1591 if (TREE_CODE_CLASS (innercode
) == tcc_comparison
)
1593 tree t
= and_comparisons_1 (innercode
,
1594 gimple_assign_rhs1 (stmt
),
1595 gimple_assign_rhs2 (stmt
),
1603 /* If the definition is an AND or OR expression, we may be able to
1604 simplify by reassociating. */
1605 if (TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
1606 && (innercode
== BIT_AND_EXPR
|| innercode
== BIT_IOR_EXPR
))
1608 tree inner1
= gimple_assign_rhs1 (stmt
);
1609 tree inner2
= gimple_assign_rhs2 (stmt
);
1612 tree partial
= NULL_TREE
;
1613 bool is_and
= (innercode
== BIT_AND_EXPR
);
1615 /* Check for boolean identities that don't require recursive examination
1617 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1618 inner1 AND (inner1 OR inner2) => inner1
1619 !inner1 AND (inner1 AND inner2) => false
1620 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1621 Likewise for similar cases involving inner2. */
1622 if (inner1
== true_test_var
)
1623 return (is_and
? var
: inner1
);
1624 else if (inner2
== true_test_var
)
1625 return (is_and
? var
: inner2
);
1626 else if (inner1
== false_test_var
)
1628 ? boolean_false_node
1629 : and_var_with_comparison (inner2
, false, code2
, op2a
, op2b
));
1630 else if (inner2
== false_test_var
)
1632 ? boolean_false_node
1633 : and_var_with_comparison (inner1
, false, code2
, op2a
, op2b
));
1635 /* Next, redistribute/reassociate the AND across the inner tests.
1636 Compute the first partial result, (inner1 AND (op2a code op2b)) */
1637 if (TREE_CODE (inner1
) == SSA_NAME
1638 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner1
))
1639 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
1640 && (t
= maybe_fold_and_comparisons (gimple_assign_rhs_code (s
),
1641 gimple_assign_rhs1 (s
),
1642 gimple_assign_rhs2 (s
),
1643 code2
, op2a
, op2b
)))
1645 /* Handle the AND case, where we are reassociating:
1646 (inner1 AND inner2) AND (op2a code2 op2b)
1648 If the partial result t is a constant, we win. Otherwise
1649 continue on to try reassociating with the other inner test. */
1652 if (integer_onep (t
))
1654 else if (integer_zerop (t
))
1655 return boolean_false_node
;
1658 /* Handle the OR case, where we are redistributing:
1659 (inner1 OR inner2) AND (op2a code2 op2b)
1660 => (t OR (inner2 AND (op2a code2 op2b))) */
1661 else if (integer_onep (t
))
1662 return boolean_true_node
;
1664 /* Save partial result for later. */
1668 /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1669 if (TREE_CODE (inner2
) == SSA_NAME
1670 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner2
))
1671 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
1672 && (t
= maybe_fold_and_comparisons (gimple_assign_rhs_code (s
),
1673 gimple_assign_rhs1 (s
),
1674 gimple_assign_rhs2 (s
),
1675 code2
, op2a
, op2b
)))
1677 /* Handle the AND case, where we are reassociating:
1678 (inner1 AND inner2) AND (op2a code2 op2b)
1679 => (inner1 AND t) */
1682 if (integer_onep (t
))
1684 else if (integer_zerop (t
))
1685 return boolean_false_node
;
1686 /* If both are the same, we can apply the identity
1688 else if (partial
&& same_bool_result_p (t
, partial
))
1692 /* Handle the OR case. where we are redistributing:
1693 (inner1 OR inner2) AND (op2a code2 op2b)
1694 => (t OR (inner1 AND (op2a code2 op2b)))
1695 => (t OR partial) */
1698 if (integer_onep (t
))
1699 return boolean_true_node
;
1702 /* We already got a simplification for the other
1703 operand to the redistributed OR expression. The
1704 interesting case is when at least one is false.
1705 Or, if both are the same, we can apply the identity
1707 if (integer_zerop (partial
))
1709 else if (integer_zerop (t
))
1711 else if (same_bool_result_p (t
, partial
))
1720 /* Try to simplify the AND of two comparisons defined by
1721 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1722 If this can be done without constructing an intermediate value,
1723 return the resulting tree; otherwise NULL_TREE is returned.
1724 This function is deliberately asymmetric as it recurses on SSA_DEFs
1725 in the first comparison but not the second. */
1728 and_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1729 enum tree_code code2
, tree op2a
, tree op2b
)
1731 tree truth_type
= truth_type_for (TREE_TYPE (op1a
));
1733 /* First check for ((x CODE1 y) AND (x CODE2 y)). */
1734 if (operand_equal_p (op1a
, op2a
, 0)
1735 && operand_equal_p (op1b
, op2b
, 0))
1737 /* Result will be either NULL_TREE, or a combined comparison. */
1738 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
1739 TRUTH_ANDIF_EXPR
, code1
, code2
,
1740 truth_type
, op1a
, op1b
);
1745 /* Likewise the swapped case of the above. */
1746 if (operand_equal_p (op1a
, op2b
, 0)
1747 && operand_equal_p (op1b
, op2a
, 0))
1749 /* Result will be either NULL_TREE, or a combined comparison. */
1750 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
1751 TRUTH_ANDIF_EXPR
, code1
,
1752 swap_tree_comparison (code2
),
1753 truth_type
, op1a
, op1b
);
1758 /* If both comparisons are of the same value against constants, we might
1759 be able to merge them. */
1760 if (operand_equal_p (op1a
, op2a
, 0)
1761 && TREE_CODE (op1b
) == INTEGER_CST
1762 && TREE_CODE (op2b
) == INTEGER_CST
)
1764 int cmp
= tree_int_cst_compare (op1b
, op2b
);
1766 /* If we have (op1a == op1b), we should either be able to
1767 return that or FALSE, depending on whether the constant op1b
1768 also satisfies the other comparison against op2b. */
1769 if (code1
== EQ_EXPR
)
1775 case EQ_EXPR
: val
= (cmp
== 0); break;
1776 case NE_EXPR
: val
= (cmp
!= 0); break;
1777 case LT_EXPR
: val
= (cmp
< 0); break;
1778 case GT_EXPR
: val
= (cmp
> 0); break;
1779 case LE_EXPR
: val
= (cmp
<= 0); break;
1780 case GE_EXPR
: val
= (cmp
>= 0); break;
1781 default: done
= false;
1786 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
1788 return boolean_false_node
;
1791 /* Likewise if the second comparison is an == comparison. */
1792 else if (code2
== EQ_EXPR
)
1798 case EQ_EXPR
: val
= (cmp
== 0); break;
1799 case NE_EXPR
: val
= (cmp
!= 0); break;
1800 case LT_EXPR
: val
= (cmp
> 0); break;
1801 case GT_EXPR
: val
= (cmp
< 0); break;
1802 case LE_EXPR
: val
= (cmp
>= 0); break;
1803 case GE_EXPR
: val
= (cmp
<= 0); break;
1804 default: done
= false;
1809 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
1811 return boolean_false_node
;
1815 /* Same business with inequality tests. */
1816 else if (code1
== NE_EXPR
)
1821 case EQ_EXPR
: val
= (cmp
!= 0); break;
1822 case NE_EXPR
: val
= (cmp
== 0); break;
1823 case LT_EXPR
: val
= (cmp
>= 0); break;
1824 case GT_EXPR
: val
= (cmp
<= 0); break;
1825 case LE_EXPR
: val
= (cmp
> 0); break;
1826 case GE_EXPR
: val
= (cmp
< 0); break;
1831 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
1833 else if (code2
== NE_EXPR
)
1838 case EQ_EXPR
: val
= (cmp
== 0); break;
1839 case NE_EXPR
: val
= (cmp
!= 0); break;
1840 case LT_EXPR
: val
= (cmp
<= 0); break;
1841 case GT_EXPR
: val
= (cmp
>= 0); break;
1842 case LE_EXPR
: val
= (cmp
< 0); break;
1843 case GE_EXPR
: val
= (cmp
> 0); break;
1848 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
1851 /* Chose the more restrictive of two < or <= comparisons. */
1852 else if ((code1
== LT_EXPR
|| code1
== LE_EXPR
)
1853 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
1855 if ((cmp
< 0) || (cmp
== 0 && code1
== LT_EXPR
))
1856 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
1858 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
1861 /* Likewise chose the more restrictive of two > or >= comparisons. */
1862 else if ((code1
== GT_EXPR
|| code1
== GE_EXPR
)
1863 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
1865 if ((cmp
> 0) || (cmp
== 0 && code1
== GT_EXPR
))
1866 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
1868 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
1871 /* Check for singleton ranges. */
1873 && ((code1
== LE_EXPR
&& code2
== GE_EXPR
)
1874 || (code1
== GE_EXPR
&& code2
== LE_EXPR
)))
1875 return fold_build2 (EQ_EXPR
, boolean_type_node
, op1a
, op2b
);
1877 /* Check for disjoint ranges. */
1879 && (code1
== LT_EXPR
|| code1
== LE_EXPR
)
1880 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
1881 return boolean_false_node
;
1883 && (code1
== GT_EXPR
|| code1
== GE_EXPR
)
1884 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
1885 return boolean_false_node
;
1888 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
1889 NAME's definition is a truth value. See if there are any simplifications
1890 that can be done against the NAME's definition. */
1891 if (TREE_CODE (op1a
) == SSA_NAME
1892 && (code1
== NE_EXPR
|| code1
== EQ_EXPR
)
1893 && (integer_zerop (op1b
) || integer_onep (op1b
)))
1895 bool invert
= ((code1
== EQ_EXPR
&& integer_zerop (op1b
))
1896 || (code1
== NE_EXPR
&& integer_onep (op1b
)));
1897 gimple stmt
= SSA_NAME_DEF_STMT (op1a
);
1898 switch (gimple_code (stmt
))
1901 /* Try to simplify by copy-propagating the definition. */
1902 return and_var_with_comparison (op1a
, invert
, code2
, op2a
, op2b
);
1905 /* If every argument to the PHI produces the same result when
1906 ANDed with the second comparison, we win.
1907 Do not do this unless the type is bool since we need a bool
1908 result here anyway. */
1909 if (TREE_CODE (TREE_TYPE (op1a
)) == BOOLEAN_TYPE
)
1911 tree result
= NULL_TREE
;
1913 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
1915 tree arg
= gimple_phi_arg_def (stmt
, i
);
1917 /* If this PHI has itself as an argument, ignore it.
1918 If all the other args produce the same result,
1920 if (arg
== gimple_phi_result (stmt
))
1922 else if (TREE_CODE (arg
) == INTEGER_CST
)
1924 if (invert
? integer_nonzerop (arg
) : integer_zerop (arg
))
1927 result
= boolean_false_node
;
1928 else if (!integer_zerop (result
))
1932 result
= fold_build2 (code2
, boolean_type_node
,
1934 else if (!same_bool_comparison_p (result
,
1938 else if (TREE_CODE (arg
) == SSA_NAME
1939 && !SSA_NAME_IS_DEFAULT_DEF (arg
))
1942 gimple def_stmt
= SSA_NAME_DEF_STMT (arg
);
1943 /* In simple cases we can look through PHI nodes,
1944 but we have to be careful with loops.
1946 if (! dom_info_available_p (CDI_DOMINATORS
)
1947 || gimple_bb (def_stmt
) == gimple_bb (stmt
)
1948 || dominated_by_p (CDI_DOMINATORS
,
1949 gimple_bb (def_stmt
),
1952 temp
= and_var_with_comparison (arg
, invert
, code2
,
1958 else if (!same_bool_result_p (result
, temp
))
1974 /* Try to simplify the AND of two comparisons, specified by
1975 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
1976 If this can be simplified to a single expression (without requiring
1977 introducing more SSA variables to hold intermediate values),
1978 return the resulting tree. Otherwise return NULL_TREE.
1979 If the result expression is non-null, it has boolean type. */
1982 maybe_fold_and_comparisons (enum tree_code code1
, tree op1a
, tree op1b
,
1983 enum tree_code code2
, tree op2a
, tree op2b
)
1985 tree t
= and_comparisons_1 (code1
, op1a
, op1b
, code2
, op2a
, op2b
);
1989 return and_comparisons_1 (code2
, op2a
, op2b
, code1
, op1a
, op1b
);
1992 /* Helper function for or_comparisons_1: try to simplify the OR of the
1993 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1994 If INVERT is true, invert the value of VAR before doing the OR.
1995 Return NULL_EXPR if we can't simplify this to a single expression. */
1998 or_var_with_comparison (tree var
, bool invert
,
1999 enum tree_code code2
, tree op2a
, tree op2b
)
2002 gimple stmt
= SSA_NAME_DEF_STMT (var
);
2004 /* We can only deal with variables whose definitions are assignments. */
2005 if (!is_gimple_assign (stmt
))
2008 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
2009 !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
2010 Then we only have to consider the simpler non-inverted cases. */
2012 t
= and_var_with_comparison_1 (stmt
,
2013 invert_tree_comparison (code2
, false),
2016 t
= or_var_with_comparison_1 (stmt
, code2
, op2a
, op2b
);
2017 return canonicalize_bool (t
, invert
);
2020 /* Try to simplify the OR of the ssa variable defined by the assignment
2021 STMT with the comparison specified by (OP2A CODE2 OP2B).
2022 Return NULL_EXPR if we can't simplify this to a single expression. */
2025 or_var_with_comparison_1 (gimple stmt
,
2026 enum tree_code code2
, tree op2a
, tree op2b
)
2028 tree var
= gimple_assign_lhs (stmt
);
2029 tree true_test_var
= NULL_TREE
;
2030 tree false_test_var
= NULL_TREE
;
2031 enum tree_code innercode
= gimple_assign_rhs_code (stmt
);
2033 /* Check for identities like (var OR (var != 0)) => true . */
2034 if (TREE_CODE (op2a
) == SSA_NAME
2035 && TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
)
2037 if ((code2
== NE_EXPR
&& integer_zerop (op2b
))
2038 || (code2
== EQ_EXPR
&& integer_nonzerop (op2b
)))
2040 true_test_var
= op2a
;
2041 if (var
== true_test_var
)
2044 else if ((code2
== EQ_EXPR
&& integer_zerop (op2b
))
2045 || (code2
== NE_EXPR
&& integer_nonzerop (op2b
)))
2047 false_test_var
= op2a
;
2048 if (var
== false_test_var
)
2049 return boolean_true_node
;
2053 /* If the definition is a comparison, recurse on it. */
2054 if (TREE_CODE_CLASS (innercode
) == tcc_comparison
)
2056 tree t
= or_comparisons_1 (innercode
,
2057 gimple_assign_rhs1 (stmt
),
2058 gimple_assign_rhs2 (stmt
),
2066 /* If the definition is an AND or OR expression, we may be able to
2067 simplify by reassociating. */
2068 if (TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
2069 && (innercode
== BIT_AND_EXPR
|| innercode
== BIT_IOR_EXPR
))
2071 tree inner1
= gimple_assign_rhs1 (stmt
);
2072 tree inner2
= gimple_assign_rhs2 (stmt
);
2075 tree partial
= NULL_TREE
;
2076 bool is_or
= (innercode
== BIT_IOR_EXPR
);
2078 /* Check for boolean identities that don't require recursive examination
2080 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2081 inner1 OR (inner1 AND inner2) => inner1
2082 !inner1 OR (inner1 OR inner2) => true
2083 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2085 if (inner1
== true_test_var
)
2086 return (is_or
? var
: inner1
);
2087 else if (inner2
== true_test_var
)
2088 return (is_or
? var
: inner2
);
2089 else if (inner1
== false_test_var
)
2092 : or_var_with_comparison (inner2
, false, code2
, op2a
, op2b
));
2093 else if (inner2
== false_test_var
)
2096 : or_var_with_comparison (inner1
, false, code2
, op2a
, op2b
));
2098 /* Next, redistribute/reassociate the OR across the inner tests.
2099 Compute the first partial result, (inner1 OR (op2a code op2b)) */
2100 if (TREE_CODE (inner1
) == SSA_NAME
2101 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner1
))
2102 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
2103 && (t
= maybe_fold_or_comparisons (gimple_assign_rhs_code (s
),
2104 gimple_assign_rhs1 (s
),
2105 gimple_assign_rhs2 (s
),
2106 code2
, op2a
, op2b
)))
2108 /* Handle the OR case, where we are reassociating:
2109 (inner1 OR inner2) OR (op2a code2 op2b)
2111 If the partial result t is a constant, we win. Otherwise
2112 continue on to try reassociating with the other inner test. */
2115 if (integer_onep (t
))
2116 return boolean_true_node
;
2117 else if (integer_zerop (t
))
2121 /* Handle the AND case, where we are redistributing:
2122 (inner1 AND inner2) OR (op2a code2 op2b)
2123 => (t AND (inner2 OR (op2a code op2b))) */
2124 else if (integer_zerop (t
))
2125 return boolean_false_node
;
2127 /* Save partial result for later. */
2131 /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2132 if (TREE_CODE (inner2
) == SSA_NAME
2133 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner2
))
2134 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
2135 && (t
= maybe_fold_or_comparisons (gimple_assign_rhs_code (s
),
2136 gimple_assign_rhs1 (s
),
2137 gimple_assign_rhs2 (s
),
2138 code2
, op2a
, op2b
)))
2140 /* Handle the OR case, where we are reassociating:
2141 (inner1 OR inner2) OR (op2a code2 op2b)
2143 => (t OR partial) */
2146 if (integer_zerop (t
))
2148 else if (integer_onep (t
))
2149 return boolean_true_node
;
2150 /* If both are the same, we can apply the identity
2152 else if (partial
&& same_bool_result_p (t
, partial
))
2156 /* Handle the AND case, where we are redistributing:
2157 (inner1 AND inner2) OR (op2a code2 op2b)
2158 => (t AND (inner1 OR (op2a code2 op2b)))
2159 => (t AND partial) */
2162 if (integer_zerop (t
))
2163 return boolean_false_node
;
2166 /* We already got a simplification for the other
2167 operand to the redistributed AND expression. The
2168 interesting case is when at least one is true.
2169 Or, if both are the same, we can apply the identity
2171 if (integer_onep (partial
))
2173 else if (integer_onep (t
))
2175 else if (same_bool_result_p (t
, partial
))
2184 /* Try to simplify the OR of two comparisons defined by
2185 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2186 If this can be done without constructing an intermediate value,
2187 return the resulting tree; otherwise NULL_TREE is returned.
2188 This function is deliberately asymmetric as it recurses on SSA_DEFs
2189 in the first comparison but not the second. */
2192 or_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
2193 enum tree_code code2
, tree op2a
, tree op2b
)
2195 tree truth_type
= truth_type_for (TREE_TYPE (op1a
));
2197 /* First check for ((x CODE1 y) OR (x CODE2 y)). */
2198 if (operand_equal_p (op1a
, op2a
, 0)
2199 && operand_equal_p (op1b
, op2b
, 0))
2201 /* Result will be either NULL_TREE, or a combined comparison. */
2202 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
2203 TRUTH_ORIF_EXPR
, code1
, code2
,
2204 truth_type
, op1a
, op1b
);
2209 /* Likewise the swapped case of the above. */
2210 if (operand_equal_p (op1a
, op2b
, 0)
2211 && operand_equal_p (op1b
, op2a
, 0))
2213 /* Result will be either NULL_TREE, or a combined comparison. */
2214 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
2215 TRUTH_ORIF_EXPR
, code1
,
2216 swap_tree_comparison (code2
),
2217 truth_type
, op1a
, op1b
);
2222 /* If both comparisons are of the same value against constants, we might
2223 be able to merge them. */
2224 if (operand_equal_p (op1a
, op2a
, 0)
2225 && TREE_CODE (op1b
) == INTEGER_CST
2226 && TREE_CODE (op2b
) == INTEGER_CST
)
2228 int cmp
= tree_int_cst_compare (op1b
, op2b
);
2230 /* If we have (op1a != op1b), we should either be able to
2231 return that or TRUE, depending on whether the constant op1b
2232 also satisfies the other comparison against op2b. */
2233 if (code1
== NE_EXPR
)
2239 case EQ_EXPR
: val
= (cmp
== 0); break;
2240 case NE_EXPR
: val
= (cmp
!= 0); break;
2241 case LT_EXPR
: val
= (cmp
< 0); break;
2242 case GT_EXPR
: val
= (cmp
> 0); break;
2243 case LE_EXPR
: val
= (cmp
<= 0); break;
2244 case GE_EXPR
: val
= (cmp
>= 0); break;
2245 default: done
= false;
2250 return boolean_true_node
;
2252 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2255 /* Likewise if the second comparison is a != comparison. */
2256 else if (code2
== NE_EXPR
)
2262 case EQ_EXPR
: val
= (cmp
== 0); break;
2263 case NE_EXPR
: val
= (cmp
!= 0); break;
2264 case LT_EXPR
: val
= (cmp
> 0); break;
2265 case GT_EXPR
: val
= (cmp
< 0); break;
2266 case LE_EXPR
: val
= (cmp
>= 0); break;
2267 case GE_EXPR
: val
= (cmp
<= 0); break;
2268 default: done
= false;
2273 return boolean_true_node
;
2275 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2279 /* See if an equality test is redundant with the other comparison. */
2280 else if (code1
== EQ_EXPR
)
2285 case EQ_EXPR
: val
= (cmp
== 0); break;
2286 case NE_EXPR
: val
= (cmp
!= 0); break;
2287 case LT_EXPR
: val
= (cmp
< 0); break;
2288 case GT_EXPR
: val
= (cmp
> 0); break;
2289 case LE_EXPR
: val
= (cmp
<= 0); break;
2290 case GE_EXPR
: val
= (cmp
>= 0); break;
2295 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2297 else if (code2
== EQ_EXPR
)
2302 case EQ_EXPR
: val
= (cmp
== 0); break;
2303 case NE_EXPR
: val
= (cmp
!= 0); break;
2304 case LT_EXPR
: val
= (cmp
> 0); break;
2305 case GT_EXPR
: val
= (cmp
< 0); break;
2306 case LE_EXPR
: val
= (cmp
>= 0); break;
2307 case GE_EXPR
: val
= (cmp
<= 0); break;
2312 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2315 /* Chose the less restrictive of two < or <= comparisons. */
2316 else if ((code1
== LT_EXPR
|| code1
== LE_EXPR
)
2317 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2319 if ((cmp
< 0) || (cmp
== 0 && code1
== LT_EXPR
))
2320 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2322 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2325 /* Likewise chose the less restrictive of two > or >= comparisons. */
2326 else if ((code1
== GT_EXPR
|| code1
== GE_EXPR
)
2327 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2329 if ((cmp
> 0) || (cmp
== 0 && code1
== GT_EXPR
))
2330 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2332 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2335 /* Check for singleton ranges. */
2337 && ((code1
== LT_EXPR
&& code2
== GT_EXPR
)
2338 || (code1
== GT_EXPR
&& code2
== LT_EXPR
)))
2339 return fold_build2 (NE_EXPR
, boolean_type_node
, op1a
, op2b
);
2341 /* Check for less/greater pairs that don't restrict the range at all. */
2343 && (code1
== LT_EXPR
|| code1
== LE_EXPR
)
2344 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2345 return boolean_true_node
;
2347 && (code1
== GT_EXPR
|| code1
== GE_EXPR
)
2348 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2349 return boolean_true_node
;
2352 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2353 NAME's definition is a truth value. See if there are any simplifications
2354 that can be done against the NAME's definition. */
2355 if (TREE_CODE (op1a
) == SSA_NAME
2356 && (code1
== NE_EXPR
|| code1
== EQ_EXPR
)
2357 && (integer_zerop (op1b
) || integer_onep (op1b
)))
2359 bool invert
= ((code1
== EQ_EXPR
&& integer_zerop (op1b
))
2360 || (code1
== NE_EXPR
&& integer_onep (op1b
)));
2361 gimple stmt
= SSA_NAME_DEF_STMT (op1a
);
2362 switch (gimple_code (stmt
))
2365 /* Try to simplify by copy-propagating the definition. */
2366 return or_var_with_comparison (op1a
, invert
, code2
, op2a
, op2b
);
2369 /* If every argument to the PHI produces the same result when
2370 ORed with the second comparison, we win.
2371 Do not do this unless the type is bool since we need a bool
2372 result here anyway. */
2373 if (TREE_CODE (TREE_TYPE (op1a
)) == BOOLEAN_TYPE
)
2375 tree result
= NULL_TREE
;
2377 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
2379 tree arg
= gimple_phi_arg_def (stmt
, i
);
2381 /* If this PHI has itself as an argument, ignore it.
2382 If all the other args produce the same result,
2384 if (arg
== gimple_phi_result (stmt
))
2386 else if (TREE_CODE (arg
) == INTEGER_CST
)
2388 if (invert
? integer_zerop (arg
) : integer_nonzerop (arg
))
2391 result
= boolean_true_node
;
2392 else if (!integer_onep (result
))
2396 result
= fold_build2 (code2
, boolean_type_node
,
2398 else if (!same_bool_comparison_p (result
,
2402 else if (TREE_CODE (arg
) == SSA_NAME
2403 && !SSA_NAME_IS_DEFAULT_DEF (arg
))
2406 gimple def_stmt
= SSA_NAME_DEF_STMT (arg
);
2407 /* In simple cases we can look through PHI nodes,
2408 but we have to be careful with loops.
2410 if (! dom_info_available_p (CDI_DOMINATORS
)
2411 || gimple_bb (def_stmt
) == gimple_bb (stmt
)
2412 || dominated_by_p (CDI_DOMINATORS
,
2413 gimple_bb (def_stmt
),
2416 temp
= or_var_with_comparison (arg
, invert
, code2
,
2422 else if (!same_bool_result_p (result
, temp
))
2438 /* Try to simplify the OR of two comparisons, specified by
2439 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2440 If this can be simplified to a single expression (without requiring
2441 introducing more SSA variables to hold intermediate values),
2442 return the resulting tree. Otherwise return NULL_TREE.
2443 If the result expression is non-null, it has boolean type. */
2446 maybe_fold_or_comparisons (enum tree_code code1
, tree op1a
, tree op1b
,
2447 enum tree_code code2
, tree op2a
, tree op2b
)
2449 tree t
= or_comparisons_1 (code1
, op1a
, op1b
, code2
, op2a
, op2b
);
2453 return or_comparisons_1 (code2
, op2a
, op2b
, code1
, op1a
, op1b
);
2457 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2459 Either NULL_TREE, a simplified but non-constant or a constant
2462 ??? This should go into a gimple-fold-inline.h file to be eventually
2463 privatized with the single valueize function used in the various TUs
2464 to avoid the indirect function call overhead. */
2467 gimple_fold_stmt_to_constant_1 (gimple stmt
, tree (*valueize
) (tree
))
2469 location_t loc
= gimple_location (stmt
);
2470 switch (gimple_code (stmt
))
2474 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
2476 switch (get_gimple_rhs_class (subcode
))
2478 case GIMPLE_SINGLE_RHS
:
2480 tree rhs
= gimple_assign_rhs1 (stmt
);
2481 enum tree_code_class kind
= TREE_CODE_CLASS (subcode
);
2483 if (TREE_CODE (rhs
) == SSA_NAME
)
2485 /* If the RHS is an SSA_NAME, return its known constant value,
2487 return (*valueize
) (rhs
);
2489 /* Handle propagating invariant addresses into address
2491 else if (TREE_CODE (rhs
) == ADDR_EXPR
2492 && !is_gimple_min_invariant (rhs
))
2494 HOST_WIDE_INT offset
= 0;
2496 base
= get_addr_base_and_unit_offset_1 (TREE_OPERAND (rhs
, 0),
2500 && (CONSTANT_CLASS_P (base
)
2501 || decl_address_invariant_p (base
)))
2502 return build_invariant_address (TREE_TYPE (rhs
),
2505 else if (TREE_CODE (rhs
) == CONSTRUCTOR
2506 && TREE_CODE (TREE_TYPE (rhs
)) == VECTOR_TYPE
2507 && (CONSTRUCTOR_NELTS (rhs
)
2508 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs
))))
2513 vec
= XALLOCAVEC (tree
,
2514 TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs
)));
2515 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs
), i
, val
)
2517 val
= (*valueize
) (val
);
2518 if (TREE_CODE (val
) == INTEGER_CST
2519 || TREE_CODE (val
) == REAL_CST
2520 || TREE_CODE (val
) == FIXED_CST
)
2526 return build_vector (TREE_TYPE (rhs
), vec
);
2529 if (kind
== tcc_reference
)
2531 if ((TREE_CODE (rhs
) == VIEW_CONVERT_EXPR
2532 || TREE_CODE (rhs
) == REALPART_EXPR
2533 || TREE_CODE (rhs
) == IMAGPART_EXPR
)
2534 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
2536 tree val
= (*valueize
) (TREE_OPERAND (rhs
, 0));
2537 return fold_unary_loc (EXPR_LOCATION (rhs
),
2539 TREE_TYPE (rhs
), val
);
2541 else if (TREE_CODE (rhs
) == BIT_FIELD_REF
2542 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
2544 tree val
= (*valueize
) (TREE_OPERAND (rhs
, 0));
2545 return fold_ternary_loc (EXPR_LOCATION (rhs
),
2547 TREE_TYPE (rhs
), val
,
2548 TREE_OPERAND (rhs
, 1),
2549 TREE_OPERAND (rhs
, 2));
2551 else if (TREE_CODE (rhs
) == MEM_REF
2552 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
2554 tree val
= (*valueize
) (TREE_OPERAND (rhs
, 0));
2555 if (TREE_CODE (val
) == ADDR_EXPR
2556 && is_gimple_min_invariant (val
))
2558 tree tem
= fold_build2 (MEM_REF
, TREE_TYPE (rhs
),
2560 TREE_OPERAND (rhs
, 1));
2565 return fold_const_aggregate_ref_1 (rhs
, valueize
);
2567 else if (kind
== tcc_declaration
)
2568 return get_symbol_constant_value (rhs
);
2572 case GIMPLE_UNARY_RHS
:
2574 /* Handle unary operators that can appear in GIMPLE form.
2575 Note that we know the single operand must be a constant,
2576 so this should almost always return a simplified RHS. */
2577 tree lhs
= gimple_assign_lhs (stmt
);
2578 tree op0
= (*valueize
) (gimple_assign_rhs1 (stmt
));
2580 /* Conversions are useless for CCP purposes if they are
2581 value-preserving. Thus the restrictions that
2582 useless_type_conversion_p places for restrict qualification
2583 of pointer types should not apply here.
2584 Substitution later will only substitute to allowed places. */
2585 if (CONVERT_EXPR_CODE_P (subcode
)
2586 && POINTER_TYPE_P (TREE_TYPE (lhs
))
2587 && POINTER_TYPE_P (TREE_TYPE (op0
))
2588 && TYPE_ADDR_SPACE (TREE_TYPE (lhs
))
2589 == TYPE_ADDR_SPACE (TREE_TYPE (op0
))
2590 && TYPE_MODE (TREE_TYPE (lhs
))
2591 == TYPE_MODE (TREE_TYPE (op0
)))
2595 fold_unary_ignore_overflow_loc (loc
, subcode
,
2596 gimple_expr_type (stmt
), op0
);
2599 case GIMPLE_BINARY_RHS
:
2601 /* Handle binary operators that can appear in GIMPLE form. */
2602 tree op0
= (*valueize
) (gimple_assign_rhs1 (stmt
));
2603 tree op1
= (*valueize
) (gimple_assign_rhs2 (stmt
));
2605 /* Translate &x + CST into an invariant form suitable for
2606 further propagation. */
2607 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
2608 && TREE_CODE (op0
) == ADDR_EXPR
2609 && TREE_CODE (op1
) == INTEGER_CST
)
2611 tree off
= fold_convert (ptr_type_node
, op1
);
2612 return build_fold_addr_expr_loc
2614 fold_build2 (MEM_REF
,
2615 TREE_TYPE (TREE_TYPE (op0
)),
2616 unshare_expr (op0
), off
));
2619 return fold_binary_loc (loc
, subcode
,
2620 gimple_expr_type (stmt
), op0
, op1
);
2623 case GIMPLE_TERNARY_RHS
:
2625 /* Handle ternary operators that can appear in GIMPLE form. */
2626 tree op0
= (*valueize
) (gimple_assign_rhs1 (stmt
));
2627 tree op1
= (*valueize
) (gimple_assign_rhs2 (stmt
));
2628 tree op2
= (*valueize
) (gimple_assign_rhs3 (stmt
));
2630 /* Fold embedded expressions in ternary codes. */
2631 if ((subcode
== COND_EXPR
2632 || subcode
== VEC_COND_EXPR
)
2633 && COMPARISON_CLASS_P (op0
))
2635 tree op00
= (*valueize
) (TREE_OPERAND (op0
, 0));
2636 tree op01
= (*valueize
) (TREE_OPERAND (op0
, 1));
2637 tree tem
= fold_binary_loc (loc
, TREE_CODE (op0
),
2638 TREE_TYPE (op0
), op00
, op01
);
2643 return fold_ternary_loc (loc
, subcode
,
2644 gimple_expr_type (stmt
), op0
, op1
, op2
);
2656 if (gimple_call_internal_p (stmt
))
2658 enum tree_code subcode
= ERROR_MARK
;
2659 switch (gimple_call_internal_fn (stmt
))
2661 case IFN_UBSAN_CHECK_ADD
:
2662 subcode
= PLUS_EXPR
;
2664 case IFN_UBSAN_CHECK_SUB
:
2665 subcode
= MINUS_EXPR
;
2667 case IFN_UBSAN_CHECK_MUL
:
2668 subcode
= MULT_EXPR
;
2673 tree op0
= (*valueize
) (gimple_call_arg (stmt
, 0));
2674 tree op1
= (*valueize
) (gimple_call_arg (stmt
, 1));
2676 if (TREE_CODE (op0
) != INTEGER_CST
2677 || TREE_CODE (op1
) != INTEGER_CST
)
2679 tree res
= fold_binary_loc (loc
, subcode
,
2680 TREE_TYPE (gimple_call_arg (stmt
, 0)),
2683 && TREE_CODE (res
) == INTEGER_CST
2684 && !TREE_OVERFLOW (res
))
2689 fn
= (*valueize
) (gimple_call_fn (stmt
));
2690 if (TREE_CODE (fn
) == ADDR_EXPR
2691 && TREE_CODE (TREE_OPERAND (fn
, 0)) == FUNCTION_DECL
2692 && DECL_BUILT_IN (TREE_OPERAND (fn
, 0)))
2694 tree
*args
= XALLOCAVEC (tree
, gimple_call_num_args (stmt
));
2697 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
2698 args
[i
] = (*valueize
) (gimple_call_arg (stmt
, i
));
2699 call
= build_call_array_loc (loc
,
2700 gimple_call_return_type (stmt
),
2701 fn
, gimple_call_num_args (stmt
), args
);
2702 retval
= fold_call_expr (EXPR_LOCATION (call
), call
, false);
2704 /* fold_call_expr wraps the result inside a NOP_EXPR. */
2705 STRIP_NOPS (retval
);
2716 /* Fold STMT to a constant using VALUEIZE to valueize SSA names.
2717 Returns NULL_TREE if folding to a constant is not possible, otherwise
2718 returns a constant according to is_gimple_min_invariant. */
2721 gimple_fold_stmt_to_constant (gimple stmt
, tree (*valueize
) (tree
))
2723 tree res
= gimple_fold_stmt_to_constant_1 (stmt
, valueize
);
2724 if (res
&& is_gimple_min_invariant (res
))
2730 /* The following set of functions are supposed to fold references using
2731 their constant initializers. */
2733 static tree
fold_ctor_reference (tree type
, tree ctor
,
2734 unsigned HOST_WIDE_INT offset
,
2735 unsigned HOST_WIDE_INT size
, tree
);
2737 /* See if we can find constructor defining value of BASE.
2738 When we know the consructor with constant offset (such as
2739 base is array[40] and we do know constructor of array), then
2740 BIT_OFFSET is adjusted accordingly.
2742 As a special case, return error_mark_node when constructor
2743 is not explicitly available, but it is known to be zero
2744 such as 'static const int a;'. */
2746 get_base_constructor (tree base
, HOST_WIDE_INT
*bit_offset
,
2747 tree (*valueize
)(tree
))
2749 HOST_WIDE_INT bit_offset2
, size
, max_size
;
2750 if (TREE_CODE (base
) == MEM_REF
)
2752 if (!integer_zerop (TREE_OPERAND (base
, 1)))
2754 if (!tree_fits_shwi_p (TREE_OPERAND (base
, 1)))
2756 *bit_offset
+= (mem_ref_offset (base
).low
2761 && TREE_CODE (TREE_OPERAND (base
, 0)) == SSA_NAME
)
2762 base
= valueize (TREE_OPERAND (base
, 0));
2763 if (!base
|| TREE_CODE (base
) != ADDR_EXPR
)
2765 base
= TREE_OPERAND (base
, 0);
2768 /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its
2769 DECL_INITIAL. If BASE is a nested reference into another
2770 ARRAY_REF or COMPONENT_REF, make a recursive call to resolve
2771 the inner reference. */
2772 switch (TREE_CODE (base
))
2777 tree init
= ctor_for_folding (base
);
2779 /* Our semantic is exact opposite of ctor_for_folding;
2780 NULL means unknown, while error_mark_node is 0. */
2781 if (init
== error_mark_node
)
2784 return error_mark_node
;
2790 base
= get_ref_base_and_extent (base
, &bit_offset2
, &size
, &max_size
);
2791 if (max_size
== -1 || size
!= max_size
)
2793 *bit_offset
+= bit_offset2
;
2794 return get_base_constructor (base
, bit_offset
, valueize
);
2805 /* CTOR is STRING_CST. Fold reference of type TYPE and size SIZE
2806 to the memory at bit OFFSET.
2808 We do only simple job of folding byte accesses. */
2811 fold_string_cst_ctor_reference (tree type
, tree ctor
,
2812 unsigned HOST_WIDE_INT offset
,
2813 unsigned HOST_WIDE_INT size
)
2815 if (INTEGRAL_TYPE_P (type
)
2816 && (TYPE_MODE (type
)
2817 == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor
))))
2818 && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor
))))
2820 && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor
)))) == 1
2821 && size
== BITS_PER_UNIT
2822 && !(offset
% BITS_PER_UNIT
))
2824 offset
/= BITS_PER_UNIT
;
2825 if (offset
< (unsigned HOST_WIDE_INT
) TREE_STRING_LENGTH (ctor
))
2826 return build_int_cst_type (type
, (TREE_STRING_POINTER (ctor
)
2829 const char a[20]="hello";
2832 might lead to offset greater than string length. In this case we
2833 know value is either initialized to 0 or out of bounds. Return 0
2835 return build_zero_cst (type
);
2840 /* CTOR is CONSTRUCTOR of an array type. Fold reference of type TYPE and size
2841 SIZE to the memory at bit OFFSET. */
2844 fold_array_ctor_reference (tree type
, tree ctor
,
2845 unsigned HOST_WIDE_INT offset
,
2846 unsigned HOST_WIDE_INT size
,
2849 unsigned HOST_WIDE_INT cnt
;
2851 double_int low_bound
, elt_size
;
2852 double_int index
, max_index
;
2853 double_int access_index
;
2854 tree domain_type
= NULL_TREE
, index_type
= NULL_TREE
;
2855 HOST_WIDE_INT inner_offset
;
2857 /* Compute low bound and elt size. */
2858 if (TREE_CODE (TREE_TYPE (ctor
)) == ARRAY_TYPE
)
2859 domain_type
= TYPE_DOMAIN (TREE_TYPE (ctor
));
2860 if (domain_type
&& TYPE_MIN_VALUE (domain_type
))
2862 /* Static constructors for variably sized objects makes no sense. */
2863 gcc_assert (TREE_CODE (TYPE_MIN_VALUE (domain_type
)) == INTEGER_CST
);
2864 index_type
= TREE_TYPE (TYPE_MIN_VALUE (domain_type
));
2865 low_bound
= tree_to_double_int (TYPE_MIN_VALUE (domain_type
));
2868 low_bound
= double_int_zero
;
2869 /* Static constructors for variably sized objects makes no sense. */
2870 gcc_assert (TREE_CODE (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor
))))
2873 tree_to_double_int (TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (ctor
))));
2876 /* We can handle only constantly sized accesses that are known to not
2877 be larger than size of array element. */
2878 if (!TYPE_SIZE_UNIT (type
)
2879 || TREE_CODE (TYPE_SIZE_UNIT (type
)) != INTEGER_CST
2880 || elt_size
.slt (tree_to_double_int (TYPE_SIZE_UNIT (type
))))
2883 /* Compute the array index we look for. */
2884 access_index
= double_int::from_uhwi (offset
/ BITS_PER_UNIT
)
2885 .udiv (elt_size
, TRUNC_DIV_EXPR
);
2886 access_index
+= low_bound
;
2888 access_index
= access_index
.ext (TYPE_PRECISION (index_type
),
2889 TYPE_UNSIGNED (index_type
));
2891 /* And offset within the access. */
2892 inner_offset
= offset
% (elt_size
.to_uhwi () * BITS_PER_UNIT
);
2894 /* See if the array field is large enough to span whole access. We do not
2895 care to fold accesses spanning multiple array indexes. */
2896 if (inner_offset
+ size
> elt_size
.to_uhwi () * BITS_PER_UNIT
)
2899 index
= low_bound
- double_int_one
;
2901 index
= index
.ext (TYPE_PRECISION (index_type
), TYPE_UNSIGNED (index_type
));
2903 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor
), cnt
, cfield
, cval
)
2905 /* Array constructor might explicitely set index, or specify range
2906 or leave index NULL meaning that it is next index after previous
2910 if (TREE_CODE (cfield
) == INTEGER_CST
)
2911 max_index
= index
= tree_to_double_int (cfield
);
2914 gcc_assert (TREE_CODE (cfield
) == RANGE_EXPR
);
2915 index
= tree_to_double_int (TREE_OPERAND (cfield
, 0));
2916 max_index
= tree_to_double_int (TREE_OPERAND (cfield
, 1));
2921 index
+= double_int_one
;
2923 index
= index
.ext (TYPE_PRECISION (index_type
),
2924 TYPE_UNSIGNED (index_type
));
2928 /* Do we have match? */
2929 if (access_index
.cmp (index
, 1) >= 0
2930 && access_index
.cmp (max_index
, 1) <= 0)
2931 return fold_ctor_reference (type
, cval
, inner_offset
, size
,
2934 /* When memory is not explicitely mentioned in constructor,
2935 it is 0 (or out of range). */
2936 return build_zero_cst (type
);
2939 /* CTOR is CONSTRUCTOR of an aggregate or vector.
2940 Fold reference of type TYPE and size SIZE to the memory at bit OFFSET. */
2943 fold_nonarray_ctor_reference (tree type
, tree ctor
,
2944 unsigned HOST_WIDE_INT offset
,
2945 unsigned HOST_WIDE_INT size
,
2948 unsigned HOST_WIDE_INT cnt
;
2951 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor
), cnt
, cfield
,
2954 tree byte_offset
= DECL_FIELD_OFFSET (cfield
);
2955 tree field_offset
= DECL_FIELD_BIT_OFFSET (cfield
);
2956 tree field_size
= DECL_SIZE (cfield
);
2957 double_int bitoffset
;
2958 double_int byte_offset_cst
= tree_to_double_int (byte_offset
);
2959 double_int bits_per_unit_cst
= double_int::from_uhwi (BITS_PER_UNIT
);
2960 double_int bitoffset_end
, access_end
;
2962 /* Variable sized objects in static constructors makes no sense,
2963 but field_size can be NULL for flexible array members. */
2964 gcc_assert (TREE_CODE (field_offset
) == INTEGER_CST
2965 && TREE_CODE (byte_offset
) == INTEGER_CST
2966 && (field_size
!= NULL_TREE
2967 ? TREE_CODE (field_size
) == INTEGER_CST
2968 : TREE_CODE (TREE_TYPE (cfield
)) == ARRAY_TYPE
));
2970 /* Compute bit offset of the field. */
2971 bitoffset
= tree_to_double_int (field_offset
)
2972 + byte_offset_cst
* bits_per_unit_cst
;
2973 /* Compute bit offset where the field ends. */
2974 if (field_size
!= NULL_TREE
)
2975 bitoffset_end
= bitoffset
+ tree_to_double_int (field_size
);
2977 bitoffset_end
= double_int_zero
;
2979 access_end
= double_int::from_uhwi (offset
)
2980 + double_int::from_uhwi (size
);
2982 /* Is there any overlap between [OFFSET, OFFSET+SIZE) and
2983 [BITOFFSET, BITOFFSET_END)? */
2984 if (access_end
.cmp (bitoffset
, 0) > 0
2985 && (field_size
== NULL_TREE
2986 || double_int::from_uhwi (offset
).slt (bitoffset_end
)))
2988 double_int inner_offset
= double_int::from_uhwi (offset
) - bitoffset
;
2989 /* We do have overlap. Now see if field is large enough to
2990 cover the access. Give up for accesses spanning multiple
2992 if (access_end
.cmp (bitoffset_end
, 0) > 0)
2994 if (double_int::from_uhwi (offset
).slt (bitoffset
))
2996 return fold_ctor_reference (type
, cval
,
2997 inner_offset
.to_uhwi (), size
,
3001 /* When memory is not explicitely mentioned in constructor, it is 0. */
3002 return build_zero_cst (type
);
3005 /* CTOR is value initializing memory, fold reference of type TYPE and size SIZE
3006 to the memory at bit OFFSET. */
3009 fold_ctor_reference (tree type
, tree ctor
, unsigned HOST_WIDE_INT offset
,
3010 unsigned HOST_WIDE_INT size
, tree from_decl
)
3014 /* We found the field with exact match. */
3015 if (useless_type_conversion_p (type
, TREE_TYPE (ctor
))
3017 return canonicalize_constructor_val (unshare_expr (ctor
), from_decl
);
3019 /* We are at the end of walk, see if we can view convert the
3021 if (!AGGREGATE_TYPE_P (TREE_TYPE (ctor
)) && !offset
3022 /* VIEW_CONVERT_EXPR is defined only for matching sizes. */
3023 && operand_equal_p (TYPE_SIZE (type
),
3024 TYPE_SIZE (TREE_TYPE (ctor
)), 0))
3026 ret
= canonicalize_constructor_val (unshare_expr (ctor
), from_decl
);
3027 ret
= fold_unary (VIEW_CONVERT_EXPR
, type
, ret
);
3032 if (TREE_CODE (ctor
) == STRING_CST
)
3033 return fold_string_cst_ctor_reference (type
, ctor
, offset
, size
);
3034 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
3037 if (TREE_CODE (TREE_TYPE (ctor
)) == ARRAY_TYPE
3038 || TREE_CODE (TREE_TYPE (ctor
)) == VECTOR_TYPE
)
3039 return fold_array_ctor_reference (type
, ctor
, offset
, size
,
3042 return fold_nonarray_ctor_reference (type
, ctor
, offset
, size
,
3049 /* Return the tree representing the element referenced by T if T is an
3050 ARRAY_REF or COMPONENT_REF into constant aggregates valuezing SSA
3051 names using VALUEIZE. Return NULL_TREE otherwise. */
3054 fold_const_aggregate_ref_1 (tree t
, tree (*valueize
) (tree
))
3056 tree ctor
, idx
, base
;
3057 HOST_WIDE_INT offset
, size
, max_size
;
3060 if (TREE_THIS_VOLATILE (t
))
3063 if (TREE_CODE_CLASS (TREE_CODE (t
)) == tcc_declaration
)
3064 return get_symbol_constant_value (t
);
3066 tem
= fold_read_from_constant_string (t
);
3070 switch (TREE_CODE (t
))
3073 case ARRAY_RANGE_REF
:
3074 /* Constant indexes are handled well by get_base_constructor.
3075 Only special case variable offsets.
3076 FIXME: This code can't handle nested references with variable indexes
3077 (they will be handled only by iteration of ccp). Perhaps we can bring
3078 get_ref_base_and_extent here and make it use a valueize callback. */
3079 if (TREE_CODE (TREE_OPERAND (t
, 1)) == SSA_NAME
3081 && (idx
= (*valueize
) (TREE_OPERAND (t
, 1)))
3082 && TREE_CODE (idx
) == INTEGER_CST
)
3084 tree low_bound
, unit_size
;
3087 /* If the resulting bit-offset is constant, track it. */
3088 if ((low_bound
= array_ref_low_bound (t
),
3089 TREE_CODE (low_bound
) == INTEGER_CST
)
3090 && (unit_size
= array_ref_element_size (t
),
3091 tree_fits_uhwi_p (unit_size
))
3092 && (doffset
= (TREE_INT_CST (idx
) - TREE_INT_CST (low_bound
))
3093 .sext (TYPE_PRECISION (TREE_TYPE (idx
))),
3094 doffset
.fits_shwi ()))
3096 offset
= doffset
.to_shwi ();
3097 offset
*= tree_to_uhwi (unit_size
);
3098 offset
*= BITS_PER_UNIT
;
3100 base
= TREE_OPERAND (t
, 0);
3101 ctor
= get_base_constructor (base
, &offset
, valueize
);
3102 /* Empty constructor. Always fold to 0. */
3103 if (ctor
== error_mark_node
)
3104 return build_zero_cst (TREE_TYPE (t
));
3105 /* Out of bound array access. Value is undefined,
3109 /* We can not determine ctor. */
3112 return fold_ctor_reference (TREE_TYPE (t
), ctor
, offset
,
3113 tree_to_uhwi (unit_size
)
3122 case TARGET_MEM_REF
:
3124 base
= get_ref_base_and_extent (t
, &offset
, &size
, &max_size
);
3125 ctor
= get_base_constructor (base
, &offset
, valueize
);
3127 /* Empty constructor. Always fold to 0. */
3128 if (ctor
== error_mark_node
)
3129 return build_zero_cst (TREE_TYPE (t
));
3130 /* We do not know precise address. */
3131 if (max_size
== -1 || max_size
!= size
)
3133 /* We can not determine ctor. */
3137 /* Out of bound array access. Value is undefined, but don't fold. */
3141 return fold_ctor_reference (TREE_TYPE (t
), ctor
, offset
, size
,
3147 tree c
= fold_const_aggregate_ref_1 (TREE_OPERAND (t
, 0), valueize
);
3148 if (c
&& TREE_CODE (c
) == COMPLEX_CST
)
3149 return fold_build1_loc (EXPR_LOCATION (t
),
3150 TREE_CODE (t
), TREE_TYPE (t
), c
);
3162 fold_const_aggregate_ref (tree t
)
3164 return fold_const_aggregate_ref_1 (t
, NULL
);
3167 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
3168 is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
3169 KNOWN_BINFO carries the binfo describing the true type of
3170 OBJ_TYPE_REF_OBJECT(REF). */
3173 gimple_get_virt_method_for_binfo (HOST_WIDE_INT token
, tree known_binfo
)
3175 unsigned HOST_WIDE_INT offset
, size
;
3176 tree v
, fn
, vtable
, init
;
3178 vtable
= v
= BINFO_VTABLE (known_binfo
);
3179 /* If there is no virtual methods table, leave the OBJ_TYPE_REF alone. */
3183 if (TREE_CODE (v
) == POINTER_PLUS_EXPR
)
3185 offset
= tree_to_uhwi (TREE_OPERAND (v
, 1)) * BITS_PER_UNIT
;
3186 v
= TREE_OPERAND (v
, 0);
3191 if (TREE_CODE (v
) != ADDR_EXPR
)
3193 v
= TREE_OPERAND (v
, 0);
3195 if (TREE_CODE (v
) != VAR_DECL
3196 || !DECL_VIRTUAL_P (v
))
3198 init
= ctor_for_folding (v
);
3200 /* The virtual tables should always be born with constructors.
3201 and we always should assume that they are avaialble for
3202 folding. At the moment we do not stream them in all cases,
3203 but it should never happen that ctor seem unreachable. */
3205 if (init
== error_mark_node
)
3207 gcc_assert (in_lto_p
);
3210 gcc_checking_assert (TREE_CODE (TREE_TYPE (v
)) == ARRAY_TYPE
);
3211 size
= tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (v
))));
3212 offset
+= token
* size
;
3213 fn
= fold_ctor_reference (TREE_TYPE (TREE_TYPE (v
)), init
,
3215 if (!fn
|| integer_zerop (fn
))
3217 gcc_assert (TREE_CODE (fn
) == ADDR_EXPR
3218 || TREE_CODE (fn
) == FDESC_EXPR
);
3219 fn
= TREE_OPERAND (fn
, 0);
3220 gcc_assert (TREE_CODE (fn
) == FUNCTION_DECL
);
3222 /* When cgraph node is missing and function is not public, we cannot
3223 devirtualize. This can happen in WHOPR when the actual method
3224 ends up in other partition, because we found devirtualization
3225 possibility too late. */
3226 if (!can_refer_decl_in_current_unit_p (fn
, vtable
))
3229 /* Make sure we create a cgraph node for functions we'll reference.
3230 They can be non-existent if the reference comes from an entry
3231 of an external vtable for example. */
3232 cgraph_get_create_node (fn
);
3237 /* Return true iff VAL is a gimple expression that is known to be
3238 non-negative. Restricted to floating-point inputs. */
3241 gimple_val_nonnegative_real_p (tree val
)
3245 gcc_assert (val
&& SCALAR_FLOAT_TYPE_P (TREE_TYPE (val
)));
3247 /* Use existing logic for non-gimple trees. */
3248 if (tree_expr_nonnegative_p (val
))
3251 if (TREE_CODE (val
) != SSA_NAME
)
3254 /* Currently we look only at the immediately defining statement
3255 to make this determination, since recursion on defining
3256 statements of operands can lead to quadratic behavior in the
3257 worst case. This is expected to catch almost all occurrences
3258 in practice. It would be possible to implement limited-depth
3259 recursion if important cases are lost. Alternatively, passes
3260 that need this information (such as the pow/powi lowering code
3261 in the cse_sincos pass) could be revised to provide it through
3262 dataflow propagation. */
3264 def_stmt
= SSA_NAME_DEF_STMT (val
);
3266 if (is_gimple_assign (def_stmt
))
3270 /* See fold-const.c:tree_expr_nonnegative_p for additional
3271 cases that could be handled with recursion. */
3273 switch (gimple_assign_rhs_code (def_stmt
))
3276 /* Always true for floating-point operands. */
3280 /* True if the two operands are identical (since we are
3281 restricted to floating-point inputs). */
3282 op0
= gimple_assign_rhs1 (def_stmt
);
3283 op1
= gimple_assign_rhs2 (def_stmt
);
3286 || operand_equal_p (op0
, op1
, 0))
3293 else if (is_gimple_call (def_stmt
))
3295 tree fndecl
= gimple_call_fndecl (def_stmt
);
3297 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3301 switch (DECL_FUNCTION_CODE (fndecl
))
3303 CASE_FLT_FN (BUILT_IN_ACOS
):
3304 CASE_FLT_FN (BUILT_IN_ACOSH
):
3305 CASE_FLT_FN (BUILT_IN_CABS
):
3306 CASE_FLT_FN (BUILT_IN_COSH
):
3307 CASE_FLT_FN (BUILT_IN_ERFC
):
3308 CASE_FLT_FN (BUILT_IN_EXP
):
3309 CASE_FLT_FN (BUILT_IN_EXP10
):
3310 CASE_FLT_FN (BUILT_IN_EXP2
):
3311 CASE_FLT_FN (BUILT_IN_FABS
):
3312 CASE_FLT_FN (BUILT_IN_FDIM
):
3313 CASE_FLT_FN (BUILT_IN_HYPOT
):
3314 CASE_FLT_FN (BUILT_IN_POW10
):
3317 CASE_FLT_FN (BUILT_IN_SQRT
):
3318 /* sqrt(-0.0) is -0.0, and sqrt is not defined over other
3319 nonnegative inputs. */
3320 if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (val
))))
3325 CASE_FLT_FN (BUILT_IN_POWI
):
3326 /* True if the second argument is an even integer. */
3327 arg1
= gimple_call_arg (def_stmt
, 1);
3329 if (TREE_CODE (arg1
) == INTEGER_CST
3330 && (TREE_INT_CST_LOW (arg1
) & 1) == 0)
3335 CASE_FLT_FN (BUILT_IN_POW
):
3336 /* True if the second argument is an even integer-valued
3338 arg1
= gimple_call_arg (def_stmt
, 1);
3340 if (TREE_CODE (arg1
) == REAL_CST
)
3345 c
= TREE_REAL_CST (arg1
);
3346 n
= real_to_integer (&c
);
3350 REAL_VALUE_TYPE cint
;
3351 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
3352 if (real_identical (&c
, &cint
))
3368 /* Given a pointer value OP0, return a simplified version of an
3369 indirection through OP0, or NULL_TREE if no simplification is
3370 possible. Note that the resulting type may be different from
3371 the type pointed to in the sense that it is still compatible
3372 from the langhooks point of view. */
3375 gimple_fold_indirect_ref (tree t
)
3377 tree ptype
= TREE_TYPE (t
), type
= TREE_TYPE (ptype
);
3382 subtype
= TREE_TYPE (sub
);
3383 if (!POINTER_TYPE_P (subtype
))
3386 if (TREE_CODE (sub
) == ADDR_EXPR
)
3388 tree op
= TREE_OPERAND (sub
, 0);
3389 tree optype
= TREE_TYPE (op
);
3391 if (useless_type_conversion_p (type
, optype
))
3394 /* *(foo *)&fooarray => fooarray[0] */
3395 if (TREE_CODE (optype
) == ARRAY_TYPE
3396 && TREE_CODE (TYPE_SIZE (TREE_TYPE (optype
))) == INTEGER_CST
3397 && useless_type_conversion_p (type
, TREE_TYPE (optype
)))
3399 tree type_domain
= TYPE_DOMAIN (optype
);
3400 tree min_val
= size_zero_node
;
3401 if (type_domain
&& TYPE_MIN_VALUE (type_domain
))
3402 min_val
= TYPE_MIN_VALUE (type_domain
);
3403 if (TREE_CODE (min_val
) == INTEGER_CST
)
3404 return build4 (ARRAY_REF
, type
, op
, min_val
, NULL_TREE
, NULL_TREE
);
3406 /* *(foo *)&complexfoo => __real__ complexfoo */
3407 else if (TREE_CODE (optype
) == COMPLEX_TYPE
3408 && useless_type_conversion_p (type
, TREE_TYPE (optype
)))
3409 return fold_build1 (REALPART_EXPR
, type
, op
);
3410 /* *(foo *)&vectorfoo => BIT_FIELD_REF<vectorfoo,...> */
3411 else if (TREE_CODE (optype
) == VECTOR_TYPE
3412 && useless_type_conversion_p (type
, TREE_TYPE (optype
)))
3414 tree part_width
= TYPE_SIZE (type
);
3415 tree index
= bitsize_int (0);
3416 return fold_build3 (BIT_FIELD_REF
, type
, op
, part_width
, index
);
3420 /* *(p + CST) -> ... */
3421 if (TREE_CODE (sub
) == POINTER_PLUS_EXPR
3422 && TREE_CODE (TREE_OPERAND (sub
, 1)) == INTEGER_CST
)
3424 tree addr
= TREE_OPERAND (sub
, 0);
3425 tree off
= TREE_OPERAND (sub
, 1);
3429 addrtype
= TREE_TYPE (addr
);
3431 /* ((foo*)&vectorfoo)[1] -> BIT_FIELD_REF<vectorfoo,...> */
3432 if (TREE_CODE (addr
) == ADDR_EXPR
3433 && TREE_CODE (TREE_TYPE (addrtype
)) == VECTOR_TYPE
3434 && useless_type_conversion_p (type
, TREE_TYPE (TREE_TYPE (addrtype
)))
3435 && tree_fits_uhwi_p (off
))
3437 unsigned HOST_WIDE_INT offset
= tree_to_uhwi (off
);
3438 tree part_width
= TYPE_SIZE (type
);
3439 unsigned HOST_WIDE_INT part_widthi
3440 = tree_to_shwi (part_width
) / BITS_PER_UNIT
;
3441 unsigned HOST_WIDE_INT indexi
= offset
* BITS_PER_UNIT
;
3442 tree index
= bitsize_int (indexi
);
3443 if (offset
/ part_widthi
3444 < TYPE_VECTOR_SUBPARTS (TREE_TYPE (addrtype
)))
3445 return fold_build3 (BIT_FIELD_REF
, type
, TREE_OPERAND (addr
, 0),
3449 /* ((foo*)&complexfoo)[1] -> __imag__ complexfoo */
3450 if (TREE_CODE (addr
) == ADDR_EXPR
3451 && TREE_CODE (TREE_TYPE (addrtype
)) == COMPLEX_TYPE
3452 && useless_type_conversion_p (type
, TREE_TYPE (TREE_TYPE (addrtype
))))
3454 tree size
= TYPE_SIZE_UNIT (type
);
3455 if (tree_int_cst_equal (size
, off
))
3456 return fold_build1 (IMAGPART_EXPR
, type
, TREE_OPERAND (addr
, 0));
3459 /* *(p + CST) -> MEM_REF <p, CST>. */
3460 if (TREE_CODE (addr
) != ADDR_EXPR
3461 || DECL_P (TREE_OPERAND (addr
, 0)))
3462 return fold_build2 (MEM_REF
, type
,
3464 build_int_cst_wide (ptype
,
3465 TREE_INT_CST_LOW (off
),
3466 TREE_INT_CST_HIGH (off
)));
3469 /* *(foo *)fooarrptr => (*fooarrptr)[0] */
3470 if (TREE_CODE (TREE_TYPE (subtype
)) == ARRAY_TYPE
3471 && TREE_CODE (TYPE_SIZE (TREE_TYPE (TREE_TYPE (subtype
)))) == INTEGER_CST
3472 && useless_type_conversion_p (type
, TREE_TYPE (TREE_TYPE (subtype
))))
3475 tree min_val
= size_zero_node
;
3477 sub
= gimple_fold_indirect_ref (sub
);
3479 sub
= build1 (INDIRECT_REF
, TREE_TYPE (subtype
), osub
);
3480 type_domain
= TYPE_DOMAIN (TREE_TYPE (sub
));
3481 if (type_domain
&& TYPE_MIN_VALUE (type_domain
))
3482 min_val
= TYPE_MIN_VALUE (type_domain
);
3483 if (TREE_CODE (min_val
) == INTEGER_CST
)
3484 return build4 (ARRAY_REF
, type
, sub
, min_val
, NULL_TREE
, NULL_TREE
);