1 /* Statement simplification on GIMPLE.
2 Copyright (C) 2010 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"
28 #include "tree-dump.h"
29 #include "tree-flow.h"
30 #include "tree-pass.h"
31 #include "tree-ssa-propagate.h"
34 /* Return true when DECL can be referenced from current unit.
35 We can get declarations that are not possible to reference for
38 1) When analyzing C++ virtual tables.
39 C++ virtual tables do have known constructors even
40 when they are keyed to other compilation unit.
41 Those tables can contain pointers to methods and vars
42 in other units. Those methods have both STATIC and EXTERNAL
44 2) In WHOPR mode devirtualization might lead to reference
45 to method that was partitioned elsehwere.
46 In this case we have static VAR_DECL or FUNCTION_DECL
47 that has no corresponding callgraph/varpool node
49 3) COMDAT functions referred by external vtables that
50 we devirtualize only during final copmilation stage.
51 At this time we already decided that we will not output
52 the function body and thus we can't reference the symbol
56 can_refer_decl_in_current_unit_p (tree decl
)
58 struct varpool_node
*vnode
;
59 struct cgraph_node
*node
;
61 if (!TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
63 /* External flag is set, so we deal with C++ reference
64 to static object from other file. */
65 if (DECL_EXTERNAL (decl
) && TREE_STATIC (decl
)
66 && TREE_CODE (decl
) == VAR_DECL
)
68 /* Just be sure it is not big in frontend setting
69 flags incorrectly. Those variables should never
71 gcc_checking_assert (!(vnode
= varpool_get_node (decl
))
72 || !vnode
->finalized
);
75 /* When function is public, we always can introduce new reference.
76 Exception are the COMDAT functions where introducing a direct
77 reference imply need to include function body in the curren tunit. */
78 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
80 /* We are not at ltrans stage; so don't worry about WHOPR.
81 Also when still gimplifying all referred comdat functions will be
83 if (!flag_ltrans
&& (!DECL_COMDAT (decl
) || !cgraph_function_flags_ready
))
85 /* If we already output the function body, we are safe. */
86 if (TREE_ASM_WRITTEN (decl
))
88 if (TREE_CODE (decl
) == FUNCTION_DECL
)
90 node
= cgraph_get_node (decl
);
91 /* Check that we still have function body and that we didn't took
92 the decision to eliminate offline copy of the function yet.
93 The second is important when devirtualization happens during final
94 compilation stage when making a new reference no longer makes callee
96 if (!node
|| !node
->analyzed
|| node
->global
.inlined_to
)
99 else if (TREE_CODE (decl
) == VAR_DECL
)
101 vnode
= varpool_get_node (decl
);
102 if (!vnode
|| !vnode
->finalized
)
108 /* CVAL is value taken from DECL_INITIAL of variable. Try to transorm it into
109 acceptable form for is_gimple_min_invariant. */
112 canonicalize_constructor_val (tree cval
)
115 if (TREE_CODE (cval
) == POINTER_PLUS_EXPR
)
117 tree t
= maybe_fold_offset_to_address (EXPR_LOCATION (cval
),
118 TREE_OPERAND (cval
, 0),
119 TREE_OPERAND (cval
, 1),
124 if (TREE_CODE (cval
) == ADDR_EXPR
)
126 tree base
= get_base_address (TREE_OPERAND (cval
, 0));
129 && (TREE_CODE (base
) == VAR_DECL
130 || TREE_CODE (base
) == FUNCTION_DECL
)
131 && !can_refer_decl_in_current_unit_p (base
))
133 if (base
&& TREE_CODE (base
) == VAR_DECL
)
134 add_referenced_var (base
);
135 /* We never have the chance to fixup types in global initializers
136 during gimplification. Do so here. */
137 if (TREE_TYPE (TREE_TYPE (cval
)) != TREE_TYPE (TREE_OPERAND (cval
, 0)))
138 cval
= build_fold_addr_expr (TREE_OPERAND (cval
, 0));
143 /* If SYM is a constant variable with known value, return the value.
144 NULL_TREE is returned otherwise. */
147 get_symbol_constant_value (tree sym
)
149 if (const_value_known_p (sym
))
151 tree val
= DECL_INITIAL (sym
);
154 val
= canonicalize_constructor_val (val
);
155 if (val
&& is_gimple_min_invariant (val
))
160 /* Variables declared 'const' without an initializer
161 have zero as the initializer if they may not be
162 overridden at link or run time. */
164 && (INTEGRAL_TYPE_P (TREE_TYPE (sym
))
165 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (sym
))))
166 return build_zero_cst (TREE_TYPE (sym
));
173 /* Return true if we may propagate the address expression ADDR into the
174 dereference DEREF and cancel them. */
177 may_propagate_address_into_dereference (tree addr
, tree deref
)
179 gcc_assert (TREE_CODE (deref
) == MEM_REF
180 && TREE_CODE (addr
) == ADDR_EXPR
);
182 /* Don't propagate if ADDR's operand has incomplete type. */
183 if (!COMPLETE_TYPE_P (TREE_TYPE (TREE_OPERAND (addr
, 0))))
186 /* If the address is invariant then we do not need to preserve restrict
187 qualifications. But we do need to preserve volatile qualifiers until
188 we can annotate the folded dereference itself properly. */
189 if (is_gimple_min_invariant (addr
)
190 && (!TREE_THIS_VOLATILE (deref
)
191 || TYPE_VOLATILE (TREE_TYPE (addr
))))
192 return useless_type_conversion_p (TREE_TYPE (deref
),
193 TREE_TYPE (TREE_OPERAND (addr
, 0)));
195 /* Else both the address substitution and the folding must result in
196 a valid useless type conversion sequence. */
197 return (useless_type_conversion_p (TREE_TYPE (TREE_OPERAND (deref
, 0)),
199 && useless_type_conversion_p (TREE_TYPE (deref
),
200 TREE_TYPE (TREE_OPERAND (addr
, 0))));
204 /* A subroutine of fold_stmt. Attempts to fold *(A+O) to A[X].
205 BASE is an array type. OFFSET is a byte displacement.
207 LOC is the location of the original expression. */
210 maybe_fold_offset_to_array_ref (location_t loc
, tree base
, tree offset
)
212 tree min_idx
, idx
, idx_type
, elt_offset
= integer_zero_node
;
213 tree array_type
, elt_type
, elt_size
;
216 /* If BASE is an ARRAY_REF, we can pick up another offset (this time
217 measured in units of the size of elements type) from that ARRAY_REF).
218 We can't do anything if either is variable.
220 The case we handle here is *(&A[N]+O). */
221 if (TREE_CODE (base
) == ARRAY_REF
)
223 tree low_bound
= array_ref_low_bound (base
);
225 elt_offset
= TREE_OPERAND (base
, 1);
226 if (TREE_CODE (low_bound
) != INTEGER_CST
227 || TREE_CODE (elt_offset
) != INTEGER_CST
)
230 elt_offset
= int_const_binop (MINUS_EXPR
, elt_offset
, low_bound
, 0);
231 base
= TREE_OPERAND (base
, 0);
234 /* Ignore stupid user tricks of indexing non-array variables. */
235 array_type
= TREE_TYPE (base
);
236 if (TREE_CODE (array_type
) != ARRAY_TYPE
)
238 elt_type
= TREE_TYPE (array_type
);
240 /* Use signed size type for intermediate computation on the index. */
241 idx_type
= ssizetype
;
243 /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the
244 element type (so we can use the alignment if it's not constant).
245 Otherwise, compute the offset as an index by using a division. If the
246 division isn't exact, then don't do anything. */
247 elt_size
= TYPE_SIZE_UNIT (elt_type
);
250 if (integer_zerop (offset
))
252 if (TREE_CODE (elt_size
) != INTEGER_CST
)
253 elt_size
= size_int (TYPE_ALIGN (elt_type
));
255 idx
= build_int_cst (idx_type
, 0);
259 unsigned HOST_WIDE_INT lquo
, lrem
;
260 HOST_WIDE_INT hquo
, hrem
;
263 /* The final array offset should be signed, so we need
264 to sign-extend the (possibly pointer) offset here
265 and use signed division. */
266 soffset
= double_int_sext (tree_to_double_int (offset
),
267 TYPE_PRECISION (TREE_TYPE (offset
)));
268 if (TREE_CODE (elt_size
) != INTEGER_CST
269 || div_and_round_double (TRUNC_DIV_EXPR
, 0,
270 soffset
.low
, soffset
.high
,
271 TREE_INT_CST_LOW (elt_size
),
272 TREE_INT_CST_HIGH (elt_size
),
273 &lquo
, &hquo
, &lrem
, &hrem
)
277 idx
= build_int_cst_wide (idx_type
, lquo
, hquo
);
280 /* Assume the low bound is zero. If there is a domain type, get the
281 low bound, if any, convert the index into that type, and add the
283 min_idx
= build_int_cst (idx_type
, 0);
284 domain_type
= TYPE_DOMAIN (array_type
);
287 idx_type
= domain_type
;
288 if (TYPE_MIN_VALUE (idx_type
))
289 min_idx
= TYPE_MIN_VALUE (idx_type
);
291 min_idx
= fold_convert (idx_type
, min_idx
);
293 if (TREE_CODE (min_idx
) != INTEGER_CST
)
296 elt_offset
= fold_convert (idx_type
, elt_offset
);
299 if (!integer_zerop (min_idx
))
300 idx
= int_const_binop (PLUS_EXPR
, idx
, min_idx
, 0);
301 if (!integer_zerop (elt_offset
))
302 idx
= int_const_binop (PLUS_EXPR
, idx
, elt_offset
, 0);
304 /* Make sure to possibly truncate late after offsetting. */
305 idx
= fold_convert (idx_type
, idx
);
307 /* We don't want to construct access past array bounds. For example
310 should not be simplified into (*c)[14] or tree-vrp will
312 This is only an issue for multi-dimensional arrays. */
313 if (TREE_CODE (elt_type
) == ARRAY_TYPE
316 if (TYPE_MAX_VALUE (domain_type
)
317 && TREE_CODE (TYPE_MAX_VALUE (domain_type
)) == INTEGER_CST
318 && tree_int_cst_lt (TYPE_MAX_VALUE (domain_type
), idx
))
320 else if (TYPE_MIN_VALUE (domain_type
)
321 && TREE_CODE (TYPE_MIN_VALUE (domain_type
)) == INTEGER_CST
322 && tree_int_cst_lt (idx
, TYPE_MIN_VALUE (domain_type
)))
324 else if (compare_tree_int (idx
, 0) < 0)
329 tree t
= build4 (ARRAY_REF
, elt_type
, base
, idx
, NULL_TREE
, NULL_TREE
);
330 SET_EXPR_LOCATION (t
, loc
);
336 /* Attempt to express (ORIG_TYPE)BASE+OFFSET as BASE[index].
337 LOC is the location of original expression.
339 Before attempting the conversion strip off existing ADDR_EXPRs. */
342 maybe_fold_offset_to_reference (location_t loc
, tree base
, tree offset
,
348 if (TREE_CODE (base
) != ADDR_EXPR
)
351 base
= TREE_OPERAND (base
, 0);
352 if (types_compatible_p (orig_type
, TREE_TYPE (base
))
353 && integer_zerop (offset
))
356 ret
= maybe_fold_offset_to_array_ref (loc
, base
, offset
);
357 if (ret
&& types_compatible_p (orig_type
, TREE_TYPE (ret
)))
362 /* Attempt to express (ORIG_TYPE)ADDR+OFFSET as (*ADDR)[index].
363 LOC is the location of the original expression. */
366 maybe_fold_offset_to_address (location_t loc
, tree addr
, tree offset
,
372 if (TREE_CODE (addr
) != ADDR_EXPR
)
374 base
= TREE_OPERAND (addr
, 0);
375 ret
= maybe_fold_offset_to_array_ref (loc
, base
, offset
);
378 ret
= build_fold_addr_expr (ret
);
379 if (!useless_type_conversion_p (orig_type
, TREE_TYPE (ret
)))
381 SET_EXPR_LOCATION (ret
, loc
);
388 /* A quaint feature extant in our address arithmetic is that there
389 can be hidden type changes here. The type of the result need
390 not be the same as the type of the input pointer.
392 What we're after here is an expression of the form
393 (T *)(&array + const)
394 where array is OP0, const is OP1, RES_TYPE is T and
395 the cast doesn't actually exist, but is implicit in the
396 type of the POINTER_PLUS_EXPR. We'd like to turn this into
398 which may be able to propagate further. */
401 maybe_fold_stmt_addition (location_t loc
, tree res_type
, tree op0
, tree op1
)
406 /* The first operand should be an ADDR_EXPR. */
407 if (TREE_CODE (op0
) != ADDR_EXPR
)
409 op0
= TREE_OPERAND (op0
, 0);
411 /* It had better be a constant. */
412 if (TREE_CODE (op1
) != INTEGER_CST
)
414 /* Or op0 should now be A[0] and the non-constant offset defined
415 via a multiplication by the array element size. */
416 if (TREE_CODE (op0
) == ARRAY_REF
417 /* As we will end up creating a variable index array access
418 in the outermost array dimension make sure there isn't
419 a more inner array that the index could overflow to. */
420 && TREE_CODE (TREE_OPERAND (op0
, 0)) != ARRAY_REF
421 && integer_zerop (TREE_OPERAND (op0
, 1))
422 && TREE_CODE (op1
) == SSA_NAME
)
424 gimple offset_def
= SSA_NAME_DEF_STMT (op1
);
425 tree elsz
= TYPE_SIZE_UNIT (TREE_TYPE (op0
));
426 if (!host_integerp (elsz
, 1)
427 || !is_gimple_assign (offset_def
))
430 /* Do not build array references of something that we can't
431 see the true number of array dimensions for. */
432 if (!DECL_P (TREE_OPERAND (op0
, 0))
433 && !handled_component_p (TREE_OPERAND (op0
, 0)))
436 if (gimple_assign_rhs_code (offset_def
) == MULT_EXPR
437 && TREE_CODE (gimple_assign_rhs2 (offset_def
)) == INTEGER_CST
438 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def
), elsz
))
439 return build_fold_addr_expr
440 (build4 (ARRAY_REF
, TREE_TYPE (op0
),
441 TREE_OPERAND (op0
, 0),
442 gimple_assign_rhs1 (offset_def
),
443 TREE_OPERAND (op0
, 2),
444 TREE_OPERAND (op0
, 3)));
445 else if (integer_onep (elsz
)
446 && gimple_assign_rhs_code (offset_def
) != MULT_EXPR
)
447 return build_fold_addr_expr
448 (build4 (ARRAY_REF
, TREE_TYPE (op0
),
449 TREE_OPERAND (op0
, 0),
451 TREE_OPERAND (op0
, 2),
452 TREE_OPERAND (op0
, 3)));
454 else if (TREE_CODE (TREE_TYPE (op0
)) == ARRAY_TYPE
456 && TREE_CODE (TREE_TYPE (TREE_TYPE (op0
))) != ARRAY_TYPE
457 && TREE_CODE (op1
) == SSA_NAME
)
459 gimple offset_def
= SSA_NAME_DEF_STMT (op1
);
460 tree elsz
= TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (op0
)));
461 if (!host_integerp (elsz
, 1)
462 || !is_gimple_assign (offset_def
))
465 /* Do not build array references of something that we can't
466 see the true number of array dimensions for. */
468 && !handled_component_p (op0
))
471 if (gimple_assign_rhs_code (offset_def
) == MULT_EXPR
472 && TREE_CODE (gimple_assign_rhs2 (offset_def
)) == INTEGER_CST
473 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def
), elsz
))
474 return build_fold_addr_expr
475 (build4 (ARRAY_REF
, TREE_TYPE (TREE_TYPE (op0
)),
476 op0
, gimple_assign_rhs1 (offset_def
),
477 integer_zero_node
, NULL_TREE
));
478 else if (integer_onep (elsz
)
479 && gimple_assign_rhs_code (offset_def
) != MULT_EXPR
)
480 return build_fold_addr_expr
481 (build4 (ARRAY_REF
, TREE_TYPE (TREE_TYPE (op0
)),
483 integer_zero_node
, NULL_TREE
));
489 /* If the first operand is an ARRAY_REF, expand it so that we can fold
490 the offset into it. */
491 while (TREE_CODE (op0
) == ARRAY_REF
)
493 tree array_obj
= TREE_OPERAND (op0
, 0);
494 tree array_idx
= TREE_OPERAND (op0
, 1);
495 tree elt_type
= TREE_TYPE (op0
);
496 tree elt_size
= TYPE_SIZE_UNIT (elt_type
);
499 if (TREE_CODE (array_idx
) != INTEGER_CST
)
501 if (TREE_CODE (elt_size
) != INTEGER_CST
)
504 /* Un-bias the index by the min index of the array type. */
505 min_idx
= TYPE_DOMAIN (TREE_TYPE (array_obj
));
508 min_idx
= TYPE_MIN_VALUE (min_idx
);
511 if (TREE_CODE (min_idx
) != INTEGER_CST
)
514 array_idx
= fold_convert (TREE_TYPE (min_idx
), array_idx
);
515 if (!integer_zerop (min_idx
))
516 array_idx
= int_const_binop (MINUS_EXPR
, array_idx
,
521 /* Convert the index to a byte offset. */
522 array_idx
= fold_convert (sizetype
, array_idx
);
523 array_idx
= int_const_binop (MULT_EXPR
, array_idx
, elt_size
, 0);
525 /* Update the operands for the next round, or for folding. */
526 op1
= int_const_binop (PLUS_EXPR
,
531 ptd_type
= TREE_TYPE (res_type
);
532 /* If we want a pointer to void, reconstruct the reference from the
533 array element type. A pointer to that can be trivially converted
534 to void *. This happens as we fold (void *)(ptr p+ off). */
535 if (VOID_TYPE_P (ptd_type
)
536 && TREE_CODE (TREE_TYPE (op0
)) == ARRAY_TYPE
)
537 ptd_type
= TREE_TYPE (TREE_TYPE (op0
));
539 /* At which point we can try some of the same things as for indirects. */
540 t
= maybe_fold_offset_to_array_ref (loc
, op0
, op1
);
543 t
= build_fold_addr_expr (t
);
544 if (!useless_type_conversion_p (res_type
, TREE_TYPE (t
)))
546 SET_EXPR_LOCATION (t
, loc
);
552 /* Subroutine of fold_stmt. We perform several simplifications of the
553 memory reference tree EXPR and make sure to re-gimplify them properly
554 after propagation of constant addresses. IS_LHS is true if the
555 reference is supposed to be an lvalue. */
558 maybe_fold_reference (tree expr
, bool is_lhs
)
564 && (result
= fold_const_aggregate_ref (expr
))
565 && is_gimple_min_invariant (result
))
568 /* ??? We might want to open-code the relevant remaining cases
569 to avoid using the generic fold. */
570 if (handled_component_p (*t
)
571 && CONSTANT_CLASS_P (TREE_OPERAND (*t
, 0)))
573 tree tem
= fold (*t
);
578 while (handled_component_p (*t
))
579 t
= &TREE_OPERAND (*t
, 0);
581 /* Fold back MEM_REFs to reference trees. */
582 if (TREE_CODE (*t
) == MEM_REF
583 && TREE_CODE (TREE_OPERAND (*t
, 0)) == ADDR_EXPR
584 && integer_zerop (TREE_OPERAND (*t
, 1))
585 && (TREE_THIS_VOLATILE (*t
)
586 == TREE_THIS_VOLATILE (TREE_OPERAND (TREE_OPERAND (*t
, 0), 0)))
587 && !TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (TREE_OPERAND (*t
, 1)))
588 && (TYPE_MAIN_VARIANT (TREE_TYPE (*t
))
589 == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (TREE_OPERAND (*t
, 1)))))
590 /* We have to look out here to not drop a required conversion
591 from the rhs to the lhs if is_lhs, but we don't have the
592 rhs here to verify that. Thus require strict type
594 && types_compatible_p (TREE_TYPE (*t
),
595 TREE_TYPE (TREE_OPERAND
596 (TREE_OPERAND (*t
, 0), 0))))
599 *t
= TREE_OPERAND (TREE_OPERAND (*t
, 0), 0);
600 tem
= maybe_fold_reference (expr
, is_lhs
);
605 /* Canonicalize MEM_REFs invariant address operand. */
606 else if (TREE_CODE (*t
) == MEM_REF
607 && !is_gimple_mem_ref_addr (TREE_OPERAND (*t
, 0)))
609 bool volatile_p
= TREE_THIS_VOLATILE (*t
);
610 tree tem
= fold_binary (MEM_REF
, TREE_TYPE (*t
),
611 TREE_OPERAND (*t
, 0),
612 TREE_OPERAND (*t
, 1));
615 TREE_THIS_VOLATILE (tem
) = volatile_p
;
617 tem
= maybe_fold_reference (expr
, is_lhs
);
623 else if (TREE_CODE (*t
) == TARGET_MEM_REF
)
625 tree tem
= maybe_fold_tmr (*t
);
629 tem
= maybe_fold_reference (expr
, is_lhs
);
638 tree tem
= get_symbol_constant_value (*t
);
640 && useless_type_conversion_p (TREE_TYPE (*t
), TREE_TYPE (tem
)))
642 *t
= unshare_expr (tem
);
643 tem
= maybe_fold_reference (expr
, is_lhs
);
654 /* Attempt to fold an assignment statement pointed-to by SI. Returns a
655 replacement rhs for the statement or NULL_TREE if no simplification
656 could be made. It is assumed that the operands have been previously
660 fold_gimple_assign (gimple_stmt_iterator
*si
)
662 gimple stmt
= gsi_stmt (*si
);
663 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
664 location_t loc
= gimple_location (stmt
);
666 tree result
= NULL_TREE
;
668 switch (get_gimple_rhs_class (subcode
))
670 case GIMPLE_SINGLE_RHS
:
672 tree rhs
= gimple_assign_rhs1 (stmt
);
674 /* Try to fold a conditional expression. */
675 if (TREE_CODE (rhs
) == COND_EXPR
)
677 tree op0
= COND_EXPR_COND (rhs
);
680 location_t cond_loc
= EXPR_LOCATION (rhs
);
682 if (COMPARISON_CLASS_P (op0
))
684 fold_defer_overflow_warnings ();
685 tem
= fold_binary_loc (cond_loc
,
686 TREE_CODE (op0
), TREE_TYPE (op0
),
687 TREE_OPERAND (op0
, 0),
688 TREE_OPERAND (op0
, 1));
689 /* This is actually a conditional expression, not a GIMPLE
690 conditional statement, however, the valid_gimple_rhs_p
691 test still applies. */
692 set
= (tem
&& is_gimple_condexpr (tem
)
693 && valid_gimple_rhs_p (tem
));
694 fold_undefer_overflow_warnings (set
, stmt
, 0);
696 else if (is_gimple_min_invariant (op0
))
705 result
= fold_build3_loc (cond_loc
, COND_EXPR
, TREE_TYPE (rhs
), tem
,
706 COND_EXPR_THEN (rhs
), COND_EXPR_ELSE (rhs
));
709 else if (REFERENCE_CLASS_P (rhs
))
710 return maybe_fold_reference (rhs
, false);
712 else if (TREE_CODE (rhs
) == ADDR_EXPR
)
714 tree ref
= TREE_OPERAND (rhs
, 0);
715 tree tem
= maybe_fold_reference (ref
, true);
717 && TREE_CODE (tem
) == MEM_REF
718 && integer_zerop (TREE_OPERAND (tem
, 1)))
719 result
= fold_convert (TREE_TYPE (rhs
), TREE_OPERAND (tem
, 0));
721 result
= fold_convert (TREE_TYPE (rhs
),
722 build_fold_addr_expr_loc (loc
, tem
));
723 else if (TREE_CODE (ref
) == MEM_REF
724 && integer_zerop (TREE_OPERAND (ref
, 1)))
725 result
= fold_convert (TREE_TYPE (rhs
), TREE_OPERAND (ref
, 0));
728 else if (TREE_CODE (rhs
) == CONSTRUCTOR
729 && TREE_CODE (TREE_TYPE (rhs
)) == VECTOR_TYPE
730 && (CONSTRUCTOR_NELTS (rhs
)
731 == TYPE_VECTOR_SUBPARTS (TREE_TYPE (rhs
))))
733 /* Fold a constant vector CONSTRUCTOR to VECTOR_CST. */
737 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (rhs
), i
, val
)
738 if (TREE_CODE (val
) != INTEGER_CST
739 && TREE_CODE (val
) != REAL_CST
740 && TREE_CODE (val
) != FIXED_CST
)
743 return build_vector_from_ctor (TREE_TYPE (rhs
),
744 CONSTRUCTOR_ELTS (rhs
));
747 else if (DECL_P (rhs
))
748 return unshare_expr (get_symbol_constant_value (rhs
));
750 /* If we couldn't fold the RHS, hand over to the generic
752 if (result
== NULL_TREE
)
755 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR
756 that may have been added by fold, and "useless" type
757 conversions that might now be apparent due to propagation. */
758 STRIP_USELESS_TYPE_CONVERSION (result
);
760 if (result
!= rhs
&& valid_gimple_rhs_p (result
))
767 case GIMPLE_UNARY_RHS
:
769 tree rhs
= gimple_assign_rhs1 (stmt
);
771 result
= fold_unary_loc (loc
, subcode
, gimple_expr_type (stmt
), rhs
);
774 /* If the operation was a conversion do _not_ mark a
775 resulting constant with TREE_OVERFLOW if the original
776 constant was not. These conversions have implementation
777 defined behavior and retaining the TREE_OVERFLOW flag
778 here would confuse later passes such as VRP. */
779 if (CONVERT_EXPR_CODE_P (subcode
)
780 && TREE_CODE (result
) == INTEGER_CST
781 && TREE_CODE (rhs
) == INTEGER_CST
)
782 TREE_OVERFLOW (result
) = TREE_OVERFLOW (rhs
);
784 STRIP_USELESS_TYPE_CONVERSION (result
);
785 if (valid_gimple_rhs_p (result
))
788 else if (CONVERT_EXPR_CODE_P (subcode
)
789 && POINTER_TYPE_P (gimple_expr_type (stmt
))
790 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
))))
792 tree type
= gimple_expr_type (stmt
);
793 tree t
= maybe_fold_offset_to_address (loc
,
794 gimple_assign_rhs1 (stmt
),
795 integer_zero_node
, type
);
802 case GIMPLE_BINARY_RHS
:
803 /* Try to fold pointer addition. */
804 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
806 tree type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
807 if (TREE_CODE (TREE_TYPE (type
)) == ARRAY_TYPE
)
809 type
= build_pointer_type (TREE_TYPE (TREE_TYPE (type
)));
810 if (!useless_type_conversion_p
811 (TREE_TYPE (gimple_assign_lhs (stmt
)), type
))
812 type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
814 result
= maybe_fold_stmt_addition (gimple_location (stmt
),
816 gimple_assign_rhs1 (stmt
),
817 gimple_assign_rhs2 (stmt
));
821 result
= fold_binary_loc (loc
, subcode
,
822 TREE_TYPE (gimple_assign_lhs (stmt
)),
823 gimple_assign_rhs1 (stmt
),
824 gimple_assign_rhs2 (stmt
));
828 STRIP_USELESS_TYPE_CONVERSION (result
);
829 if (valid_gimple_rhs_p (result
))
832 /* Fold might have produced non-GIMPLE, so if we trust it blindly
833 we lose canonicalization opportunities. Do not go again
834 through fold here though, or the same non-GIMPLE will be
836 if (commutative_tree_code (subcode
)
837 && tree_swap_operands_p (gimple_assign_rhs1 (stmt
),
838 gimple_assign_rhs2 (stmt
), false))
839 return build2 (subcode
, TREE_TYPE (gimple_assign_lhs (stmt
)),
840 gimple_assign_rhs2 (stmt
),
841 gimple_assign_rhs1 (stmt
));
845 case GIMPLE_TERNARY_RHS
:
846 result
= fold_ternary_loc (loc
, subcode
,
847 TREE_TYPE (gimple_assign_lhs (stmt
)),
848 gimple_assign_rhs1 (stmt
),
849 gimple_assign_rhs2 (stmt
),
850 gimple_assign_rhs3 (stmt
));
854 STRIP_USELESS_TYPE_CONVERSION (result
);
855 if (valid_gimple_rhs_p (result
))
858 /* Fold might have produced non-GIMPLE, so if we trust it blindly
859 we lose canonicalization opportunities. Do not go again
860 through fold here though, or the same non-GIMPLE will be
862 if (commutative_ternary_tree_code (subcode
)
863 && tree_swap_operands_p (gimple_assign_rhs1 (stmt
),
864 gimple_assign_rhs2 (stmt
), false))
865 return build3 (subcode
, TREE_TYPE (gimple_assign_lhs (stmt
)),
866 gimple_assign_rhs2 (stmt
),
867 gimple_assign_rhs1 (stmt
),
868 gimple_assign_rhs3 (stmt
));
872 case GIMPLE_INVALID_RHS
:
879 /* Attempt to fold a conditional statement. Return true if any changes were
880 made. We only attempt to fold the condition expression, and do not perform
881 any transformation that would require alteration of the cfg. It is
882 assumed that the operands have been previously folded. */
885 fold_gimple_cond (gimple stmt
)
887 tree result
= fold_binary_loc (gimple_location (stmt
),
888 gimple_cond_code (stmt
),
890 gimple_cond_lhs (stmt
),
891 gimple_cond_rhs (stmt
));
895 STRIP_USELESS_TYPE_CONVERSION (result
);
896 if (is_gimple_condexpr (result
) && valid_gimple_rhs_p (result
))
898 gimple_cond_set_condition_from_tree (stmt
, result
);
906 /* Convert EXPR into a GIMPLE value suitable for substitution on the
907 RHS of an assignment. Insert the necessary statements before
908 iterator *SI_P. The statement at *SI_P, which must be a GIMPLE_CALL
909 is replaced. If the call is expected to produces a result, then it
910 is replaced by an assignment of the new RHS to the result variable.
911 If the result is to be ignored, then the call is replaced by a
912 GIMPLE_NOP. A proper VDEF chain is retained by making the first
913 VUSE and the last VDEF of the whole sequence be the same as the replaced
914 statement and using new SSA names for stores in between. */
917 gimplify_and_update_call_from_tree (gimple_stmt_iterator
*si_p
, tree expr
)
920 tree tmp
= NULL_TREE
; /* Silence warning. */
921 gimple stmt
, new_stmt
;
922 gimple_stmt_iterator i
;
923 gimple_seq stmts
= gimple_seq_alloc();
924 struct gimplify_ctx gctx
;
926 gimple laststore
= NULL
;
929 stmt
= gsi_stmt (*si_p
);
931 gcc_assert (is_gimple_call (stmt
));
933 lhs
= gimple_call_lhs (stmt
);
934 reaching_vuse
= gimple_vuse (stmt
);
936 push_gimplify_context (&gctx
);
938 if (lhs
== NULL_TREE
)
940 gimplify_and_add (expr
, &stmts
);
941 /* We can end up with folding a memcpy of an empty class assignment
942 which gets optimized away by C++ gimplification. */
943 if (gimple_seq_empty_p (stmts
))
945 pop_gimplify_context (NULL
);
946 if (gimple_in_ssa_p (cfun
))
948 unlink_stmt_vdef (stmt
);
951 gsi_remove (si_p
, true);
956 tmp
= get_initialized_tmp_var (expr
, &stmts
, NULL
);
958 pop_gimplify_context (NULL
);
960 if (gimple_has_location (stmt
))
961 annotate_all_with_location (stmts
, gimple_location (stmt
));
963 /* The replacement can expose previously unreferenced variables. */
964 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
968 gsi_insert_before (si_p
, last
, GSI_NEW_STMT
);
971 new_stmt
= gsi_stmt (i
);
972 if (gimple_in_ssa_p (cfun
))
974 find_new_referenced_vars (new_stmt
);
975 mark_symbols_for_renaming (new_stmt
);
977 /* If the new statement has a VUSE, update it with exact SSA name we
978 know will reach this one. */
979 if (gimple_vuse (new_stmt
))
981 /* If we've also seen a previous store create a new VDEF for
982 the latter one, and make that the new reaching VUSE. */
985 reaching_vuse
= make_ssa_name (gimple_vop (cfun
), laststore
);
986 gimple_set_vdef (laststore
, reaching_vuse
);
987 update_stmt (laststore
);
990 gimple_set_vuse (new_stmt
, reaching_vuse
);
991 gimple_set_modified (new_stmt
, true);
993 if (gimple_assign_single_p (new_stmt
)
994 && !is_gimple_reg (gimple_assign_lhs (new_stmt
)))
996 laststore
= new_stmt
;
1001 if (lhs
== NULL_TREE
)
1003 /* If we replace a call without LHS that has a VDEF and our new
1004 sequence ends with a store we must make that store have the same
1005 vdef in order not to break the sequencing. This can happen
1006 for instance when folding memcpy calls into assignments. */
1007 if (gimple_vdef (stmt
) && laststore
)
1009 gimple_set_vdef (laststore
, gimple_vdef (stmt
));
1010 if (TREE_CODE (gimple_vdef (stmt
)) == SSA_NAME
)
1011 SSA_NAME_DEF_STMT (gimple_vdef (stmt
)) = laststore
;
1012 update_stmt (laststore
);
1014 else if (gimple_in_ssa_p (cfun
))
1016 unlink_stmt_vdef (stmt
);
1017 release_defs (stmt
);
1025 gsi_insert_before (si_p
, last
, GSI_NEW_STMT
);
1028 if (laststore
&& is_gimple_reg (lhs
))
1030 gimple_set_vdef (laststore
, gimple_vdef (stmt
));
1031 update_stmt (laststore
);
1032 if (TREE_CODE (gimple_vdef (stmt
)) == SSA_NAME
)
1033 SSA_NAME_DEF_STMT (gimple_vdef (stmt
)) = laststore
;
1038 reaching_vuse
= make_ssa_name (gimple_vop (cfun
), laststore
);
1039 gimple_set_vdef (laststore
, reaching_vuse
);
1040 update_stmt (laststore
);
1043 new_stmt
= gimple_build_assign (lhs
, tmp
);
1044 if (!is_gimple_reg (tmp
))
1045 gimple_set_vuse (new_stmt
, reaching_vuse
);
1046 if (!is_gimple_reg (lhs
))
1048 gimple_set_vdef (new_stmt
, gimple_vdef (stmt
));
1049 if (TREE_CODE (gimple_vdef (stmt
)) == SSA_NAME
)
1050 SSA_NAME_DEF_STMT (gimple_vdef (stmt
)) = new_stmt
;
1052 else if (reaching_vuse
== gimple_vuse (stmt
))
1053 unlink_stmt_vdef (stmt
);
1056 gimple_set_location (new_stmt
, gimple_location (stmt
));
1057 gsi_replace (si_p
, new_stmt
, false);
1060 /* Return the string length, maximum string length or maximum value of
1062 If ARG is an SSA name variable, follow its use-def chains. If LENGTH
1063 is not NULL and, for TYPE == 0, its value is not equal to the length
1064 we determine or if we are unable to determine the length or value,
1065 return false. VISITED is a bitmap of visited variables.
1066 TYPE is 0 if string length should be returned, 1 for maximum string
1067 length and 2 for maximum value ARG can have. */
1070 get_maxval_strlen (tree arg
, tree
*length
, bitmap visited
, int type
)
1075 if (TREE_CODE (arg
) != SSA_NAME
)
1077 if (TREE_CODE (arg
) == COND_EXPR
)
1078 return get_maxval_strlen (COND_EXPR_THEN (arg
), length
, visited
, type
)
1079 && get_maxval_strlen (COND_EXPR_ELSE (arg
), length
, visited
, type
);
1080 /* We can end up with &(*iftmp_1)[0] here as well, so handle it. */
1081 else if (TREE_CODE (arg
) == ADDR_EXPR
1082 && TREE_CODE (TREE_OPERAND (arg
, 0)) == ARRAY_REF
1083 && integer_zerop (TREE_OPERAND (TREE_OPERAND (arg
, 0), 1)))
1085 tree aop0
= TREE_OPERAND (TREE_OPERAND (arg
, 0), 0);
1086 if (TREE_CODE (aop0
) == INDIRECT_REF
1087 && TREE_CODE (TREE_OPERAND (aop0
, 0)) == SSA_NAME
)
1088 return get_maxval_strlen (TREE_OPERAND (aop0
, 0),
1089 length
, visited
, type
);
1095 if (TREE_CODE (val
) != INTEGER_CST
1096 || tree_int_cst_sgn (val
) < 0)
1100 val
= c_strlen (arg
, 1);
1108 if (TREE_CODE (*length
) != INTEGER_CST
1109 || TREE_CODE (val
) != INTEGER_CST
)
1112 if (tree_int_cst_lt (*length
, val
))
1116 else if (simple_cst_equal (val
, *length
) != 1)
1124 /* If we were already here, break the infinite cycle. */
1125 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (arg
)))
1129 def_stmt
= SSA_NAME_DEF_STMT (var
);
1131 switch (gimple_code (def_stmt
))
1134 /* The RHS of the statement defining VAR must either have a
1135 constant length or come from another SSA_NAME with a constant
1137 if (gimple_assign_single_p (def_stmt
)
1138 || gimple_assign_unary_nop_p (def_stmt
))
1140 tree rhs
= gimple_assign_rhs1 (def_stmt
);
1141 return get_maxval_strlen (rhs
, length
, visited
, type
);
1147 /* All the arguments of the PHI node must have the same constant
1151 for (i
= 0; i
< gimple_phi_num_args (def_stmt
); i
++)
1153 tree arg
= gimple_phi_arg (def_stmt
, i
)->def
;
1155 /* If this PHI has itself as an argument, we cannot
1156 determine the string length of this argument. However,
1157 if we can find a constant string length for the other
1158 PHI args then we can still be sure that this is a
1159 constant string length. So be optimistic and just
1160 continue with the next argument. */
1161 if (arg
== gimple_phi_result (def_stmt
))
1164 if (!get_maxval_strlen (arg
, length
, visited
, type
))
1176 /* Fold builtin call in statement STMT. Returns a simplified tree.
1177 We may return a non-constant expression, including another call
1178 to a different function and with different arguments, e.g.,
1179 substituting memcpy for strcpy when the string length is known.
1180 Note that some builtins expand into inline code that may not
1181 be valid in GIMPLE. Callers must take care. */
1184 gimple_fold_builtin (gimple stmt
)
1186 tree result
, val
[3];
1192 location_t loc
= gimple_location (stmt
);
1194 gcc_assert (is_gimple_call (stmt
));
1196 ignore
= (gimple_call_lhs (stmt
) == NULL
);
1198 /* First try the generic builtin folder. If that succeeds, return the
1200 result
= fold_call_stmt (stmt
, ignore
);
1204 STRIP_NOPS (result
);
1208 /* Ignore MD builtins. */
1209 callee
= gimple_call_fndecl (stmt
);
1210 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_MD
)
1213 /* If the builtin could not be folded, and it has no argument list,
1215 nargs
= gimple_call_num_args (stmt
);
1219 /* Limit the work only for builtins we know how to simplify. */
1220 switch (DECL_FUNCTION_CODE (callee
))
1222 case BUILT_IN_STRLEN
:
1223 case BUILT_IN_FPUTS
:
1224 case BUILT_IN_FPUTS_UNLOCKED
:
1228 case BUILT_IN_STRCPY
:
1229 case BUILT_IN_STRNCPY
:
1233 case BUILT_IN_MEMCPY_CHK
:
1234 case BUILT_IN_MEMPCPY_CHK
:
1235 case BUILT_IN_MEMMOVE_CHK
:
1236 case BUILT_IN_MEMSET_CHK
:
1237 case BUILT_IN_STRNCPY_CHK
:
1241 case BUILT_IN_STRCPY_CHK
:
1242 case BUILT_IN_STPCPY_CHK
:
1246 case BUILT_IN_SNPRINTF_CHK
:
1247 case BUILT_IN_VSNPRINTF_CHK
:
1255 if (arg_idx
>= nargs
)
1258 /* Try to use the dataflow information gathered by the CCP process. */
1259 visited
= BITMAP_ALLOC (NULL
);
1260 bitmap_clear (visited
);
1262 memset (val
, 0, sizeof (val
));
1263 a
= gimple_call_arg (stmt
, arg_idx
);
1264 if (!get_maxval_strlen (a
, &val
[arg_idx
], visited
, type
))
1265 val
[arg_idx
] = NULL_TREE
;
1267 BITMAP_FREE (visited
);
1270 switch (DECL_FUNCTION_CODE (callee
))
1272 case BUILT_IN_STRLEN
:
1273 if (val
[0] && nargs
== 1)
1276 fold_convert (TREE_TYPE (gimple_call_lhs (stmt
)), val
[0]);
1278 /* If the result is not a valid gimple value, or not a cast
1279 of a valid gimple value, then we cannot use the result. */
1280 if (is_gimple_val (new_val
)
1281 || (CONVERT_EXPR_P (new_val
)
1282 && is_gimple_val (TREE_OPERAND (new_val
, 0))))
1287 case BUILT_IN_STRCPY
:
1288 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 2)
1289 result
= fold_builtin_strcpy (loc
, callee
,
1290 gimple_call_arg (stmt
, 0),
1291 gimple_call_arg (stmt
, 1),
1295 case BUILT_IN_STRNCPY
:
1296 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 3)
1297 result
= fold_builtin_strncpy (loc
, callee
,
1298 gimple_call_arg (stmt
, 0),
1299 gimple_call_arg (stmt
, 1),
1300 gimple_call_arg (stmt
, 2),
1304 case BUILT_IN_FPUTS
:
1306 result
= fold_builtin_fputs (loc
, gimple_call_arg (stmt
, 0),
1307 gimple_call_arg (stmt
, 1),
1308 ignore
, false, val
[0]);
1311 case BUILT_IN_FPUTS_UNLOCKED
:
1313 result
= fold_builtin_fputs (loc
, gimple_call_arg (stmt
, 0),
1314 gimple_call_arg (stmt
, 1),
1315 ignore
, true, val
[0]);
1318 case BUILT_IN_MEMCPY_CHK
:
1319 case BUILT_IN_MEMPCPY_CHK
:
1320 case BUILT_IN_MEMMOVE_CHK
:
1321 case BUILT_IN_MEMSET_CHK
:
1322 if (val
[2] && is_gimple_val (val
[2]) && nargs
== 4)
1323 result
= fold_builtin_memory_chk (loc
, callee
,
1324 gimple_call_arg (stmt
, 0),
1325 gimple_call_arg (stmt
, 1),
1326 gimple_call_arg (stmt
, 2),
1327 gimple_call_arg (stmt
, 3),
1329 DECL_FUNCTION_CODE (callee
));
1332 case BUILT_IN_STRCPY_CHK
:
1333 case BUILT_IN_STPCPY_CHK
:
1334 if (val
[1] && is_gimple_val (val
[1]) && nargs
== 3)
1335 result
= fold_builtin_stxcpy_chk (loc
, callee
,
1336 gimple_call_arg (stmt
, 0),
1337 gimple_call_arg (stmt
, 1),
1338 gimple_call_arg (stmt
, 2),
1340 DECL_FUNCTION_CODE (callee
));
1343 case BUILT_IN_STRNCPY_CHK
:
1344 if (val
[2] && is_gimple_val (val
[2]) && nargs
== 4)
1345 result
= fold_builtin_strncpy_chk (loc
, gimple_call_arg (stmt
, 0),
1346 gimple_call_arg (stmt
, 1),
1347 gimple_call_arg (stmt
, 2),
1348 gimple_call_arg (stmt
, 3),
1352 case BUILT_IN_SNPRINTF_CHK
:
1353 case BUILT_IN_VSNPRINTF_CHK
:
1354 if (val
[1] && is_gimple_val (val
[1]))
1355 result
= gimple_fold_builtin_snprintf_chk (stmt
, val
[1],
1356 DECL_FUNCTION_CODE (callee
));
1363 if (result
&& ignore
)
1364 result
= fold_ignored_result (result
);
1368 /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
1369 is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
1370 KNOWN_BINFO carries the binfo describing the true type of
1371 OBJ_TYPE_REF_OBJECT(REF). If a call to the function must be accompanied
1372 with a this adjustment, the constant which should be added to this pointer
1373 is stored to *DELTA. If REFUSE_THUNKS is true, return NULL if the function
1374 is a thunk (other than a this adjustment which is dealt with by DELTA). */
1377 gimple_get_virt_mehtod_for_binfo (HOST_WIDE_INT token
, tree known_binfo
,
1378 tree
*delta
, bool refuse_thunks
)
1382 struct cgraph_node
*node
;
1384 v
= BINFO_VIRTUALS (known_binfo
);
1385 /* If there is no virtual methods leave the OBJ_TYPE_REF alone. */
1391 i
+= (TARGET_VTABLE_USES_DESCRIPTORS
1392 ? TARGET_VTABLE_USES_DESCRIPTORS
: 1);
1396 fndecl
= TREE_VALUE (v
);
1397 node
= cgraph_get_node_or_alias (fndecl
);
1400 /* Bail out if it is a thunk declaration. Since simple this_adjusting
1401 thunks are represented by a constant in TREE_PURPOSE of items in
1402 BINFO_VIRTUALS, this is a more complicate type which we cannot handle as
1405 FIXME: Remove the following condition once we are able to represent
1406 thunk information on call graph edges. */
1407 || (node
->same_body_alias
&& node
->thunk
.thunk_p
)))
1410 /* When cgraph node is missing and function is not public, we cannot
1411 devirtualize. This can happen in WHOPR when the actual method
1412 ends up in other partition, because we found devirtualization
1413 possibility too late. */
1414 if (!can_refer_decl_in_current_unit_p (TREE_VALUE (v
)))
1417 *delta
= TREE_PURPOSE (v
);
1418 gcc_checking_assert (host_integerp (*delta
, 0));
1422 /* Generate code adjusting the first parameter of a call statement determined
1426 gimple_adjust_this_by_delta (gimple_stmt_iterator
*gsi
, tree delta
)
1428 gimple call_stmt
= gsi_stmt (*gsi
);
1432 delta
= fold_convert (sizetype
, delta
);
1433 gcc_assert (gimple_call_num_args (call_stmt
) >= 1);
1434 parm
= gimple_call_arg (call_stmt
, 0);
1435 gcc_assert (POINTER_TYPE_P (TREE_TYPE (parm
)));
1436 tmp
= create_tmp_var (TREE_TYPE (parm
), NULL
);
1437 add_referenced_var (tmp
);
1439 tmp
= make_ssa_name (tmp
, NULL
);
1440 new_stmt
= gimple_build_assign_with_ops (POINTER_PLUS_EXPR
, tmp
, parm
, delta
);
1441 SSA_NAME_DEF_STMT (tmp
) = new_stmt
;
1442 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1443 gimple_call_set_arg (call_stmt
, 0, tmp
);
1446 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1447 The statement may be replaced by another statement, e.g., if the call
1448 simplifies to a constant value. Return true if any changes were made.
1449 It is assumed that the operands have been previously folded. */
1452 gimple_fold_call (gimple_stmt_iterator
*gsi
, bool inplace
)
1454 gimple stmt
= gsi_stmt (*gsi
);
1456 tree callee
= gimple_call_fndecl (stmt
);
1458 /* Check for builtins that CCP can handle using information not
1459 available in the generic fold routines. */
1460 if (!inplace
&& callee
&& DECL_BUILT_IN (callee
))
1462 tree result
= gimple_fold_builtin (stmt
);
1466 if (!update_call_from_tree (gsi
, result
))
1467 gimplify_and_update_call_from_tree (gsi
, result
);
1474 /* Worker for both fold_stmt and fold_stmt_inplace. The INPLACE argument
1475 distinguishes both cases. */
1478 fold_stmt_1 (gimple_stmt_iterator
*gsi
, bool inplace
)
1480 bool changed
= false;
1481 gimple stmt
= gsi_stmt (*gsi
);
1484 /* Fold the main computation performed by the statement. */
1485 switch (gimple_code (stmt
))
1489 unsigned old_num_ops
= gimple_num_ops (stmt
);
1490 tree new_rhs
= fold_gimple_assign (gsi
);
1491 tree lhs
= gimple_assign_lhs (stmt
);
1493 && !useless_type_conversion_p (TREE_TYPE (lhs
),
1494 TREE_TYPE (new_rhs
)))
1495 new_rhs
= fold_convert (TREE_TYPE (lhs
), new_rhs
);
1498 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs
)) < old_num_ops
))
1500 gimple_assign_set_rhs_from_tree (gsi
, new_rhs
);
1507 changed
|= fold_gimple_cond (stmt
);
1511 /* Fold *& in call arguments. */
1512 for (i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
1513 if (REFERENCE_CLASS_P (gimple_call_arg (stmt
, i
)))
1515 tree tmp
= maybe_fold_reference (gimple_call_arg (stmt
, i
), false);
1518 gimple_call_set_arg (stmt
, i
, tmp
);
1522 changed
|= gimple_fold_call (gsi
, inplace
);
1526 /* Fold *& in asm operands. */
1527 for (i
= 0; i
< gimple_asm_noutputs (stmt
); ++i
)
1529 tree link
= gimple_asm_output_op (stmt
, i
);
1530 tree op
= TREE_VALUE (link
);
1531 if (REFERENCE_CLASS_P (op
)
1532 && (op
= maybe_fold_reference (op
, true)) != NULL_TREE
)
1534 TREE_VALUE (link
) = op
;
1538 for (i
= 0; i
< gimple_asm_ninputs (stmt
); ++i
)
1540 tree link
= gimple_asm_input_op (stmt
, i
);
1541 tree op
= TREE_VALUE (link
);
1542 if (REFERENCE_CLASS_P (op
)
1543 && (op
= maybe_fold_reference (op
, false)) != NULL_TREE
)
1545 TREE_VALUE (link
) = op
;
1552 if (gimple_debug_bind_p (stmt
))
1554 tree val
= gimple_debug_bind_get_value (stmt
);
1556 && REFERENCE_CLASS_P (val
))
1558 tree tem
= maybe_fold_reference (val
, false);
1561 gimple_debug_bind_set_value (stmt
, tem
);
1571 stmt
= gsi_stmt (*gsi
);
1573 /* Fold *& on the lhs. */
1574 if (gimple_has_lhs (stmt
))
1576 tree lhs
= gimple_get_lhs (stmt
);
1577 if (lhs
&& REFERENCE_CLASS_P (lhs
))
1579 tree new_lhs
= maybe_fold_reference (lhs
, true);
1582 gimple_set_lhs (stmt
, new_lhs
);
1591 /* Fold the statement pointed to by GSI. In some cases, this function may
1592 replace the whole statement with a new one. Returns true iff folding
1594 The statement pointed to by GSI should be in valid gimple form but may
1595 be in unfolded state as resulting from for example constant propagation
1596 which can produce *&x = 0. */
1599 fold_stmt (gimple_stmt_iterator
*gsi
)
1601 return fold_stmt_1 (gsi
, false);
1604 /* Perform the minimal folding on statement STMT. Only operations like
1605 *&x created by constant propagation are handled. The statement cannot
1606 be replaced with a new one. Return true if the statement was
1607 changed, false otherwise.
1608 The statement STMT should be in valid gimple form but may
1609 be in unfolded state as resulting from for example constant propagation
1610 which can produce *&x = 0. */
1613 fold_stmt_inplace (gimple stmt
)
1615 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1616 bool changed
= fold_stmt_1 (&gsi
, true);
1617 gcc_assert (gsi_stmt (gsi
) == stmt
);
1621 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1622 if EXPR is null or we don't know how.
1623 If non-null, the result always has boolean type. */
1626 canonicalize_bool (tree expr
, bool invert
)
1632 if (integer_nonzerop (expr
))
1633 return boolean_false_node
;
1634 else if (integer_zerop (expr
))
1635 return boolean_true_node
;
1636 else if (TREE_CODE (expr
) == SSA_NAME
)
1637 return fold_build2 (EQ_EXPR
, boolean_type_node
, expr
,
1638 build_int_cst (TREE_TYPE (expr
), 0));
1639 else if (TREE_CODE_CLASS (TREE_CODE (expr
)) == tcc_comparison
)
1640 return fold_build2 (invert_tree_comparison (TREE_CODE (expr
), false),
1642 TREE_OPERAND (expr
, 0),
1643 TREE_OPERAND (expr
, 1));
1649 if (TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
)
1651 if (integer_nonzerop (expr
))
1652 return boolean_true_node
;
1653 else if (integer_zerop (expr
))
1654 return boolean_false_node
;
1655 else if (TREE_CODE (expr
) == SSA_NAME
)
1656 return fold_build2 (NE_EXPR
, boolean_type_node
, expr
,
1657 build_int_cst (TREE_TYPE (expr
), 0));
1658 else if (TREE_CODE_CLASS (TREE_CODE (expr
)) == tcc_comparison
)
1659 return fold_build2 (TREE_CODE (expr
),
1661 TREE_OPERAND (expr
, 0),
1662 TREE_OPERAND (expr
, 1));
1668 /* Check to see if a boolean expression EXPR is logically equivalent to the
1669 comparison (OP1 CODE OP2). Check for various identities involving
1673 same_bool_comparison_p (const_tree expr
, enum tree_code code
,
1674 const_tree op1
, const_tree op2
)
1678 /* The obvious case. */
1679 if (TREE_CODE (expr
) == code
1680 && operand_equal_p (TREE_OPERAND (expr
, 0), op1
, 0)
1681 && operand_equal_p (TREE_OPERAND (expr
, 1), op2
, 0))
1684 /* Check for comparing (name, name != 0) and the case where expr
1685 is an SSA_NAME with a definition matching the comparison. */
1686 if (TREE_CODE (expr
) == SSA_NAME
1687 && TREE_CODE (TREE_TYPE (expr
)) == BOOLEAN_TYPE
)
1689 if (operand_equal_p (expr
, op1
, 0))
1690 return ((code
== NE_EXPR
&& integer_zerop (op2
))
1691 || (code
== EQ_EXPR
&& integer_nonzerop (op2
)));
1692 s
= SSA_NAME_DEF_STMT (expr
);
1693 if (is_gimple_assign (s
)
1694 && gimple_assign_rhs_code (s
) == code
1695 && operand_equal_p (gimple_assign_rhs1 (s
), op1
, 0)
1696 && operand_equal_p (gimple_assign_rhs2 (s
), op2
, 0))
1700 /* If op1 is of the form (name != 0) or (name == 0), and the definition
1701 of name is a comparison, recurse. */
1702 if (TREE_CODE (op1
) == SSA_NAME
1703 && TREE_CODE (TREE_TYPE (op1
)) == BOOLEAN_TYPE
)
1705 s
= SSA_NAME_DEF_STMT (op1
);
1706 if (is_gimple_assign (s
)
1707 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
1709 enum tree_code c
= gimple_assign_rhs_code (s
);
1710 if ((c
== NE_EXPR
&& integer_zerop (op2
))
1711 || (c
== EQ_EXPR
&& integer_nonzerop (op2
)))
1712 return same_bool_comparison_p (expr
, c
,
1713 gimple_assign_rhs1 (s
),
1714 gimple_assign_rhs2 (s
));
1715 if ((c
== EQ_EXPR
&& integer_zerop (op2
))
1716 || (c
== NE_EXPR
&& integer_nonzerop (op2
)))
1717 return same_bool_comparison_p (expr
,
1718 invert_tree_comparison (c
, false),
1719 gimple_assign_rhs1 (s
),
1720 gimple_assign_rhs2 (s
));
1726 /* Check to see if two boolean expressions OP1 and OP2 are logically
1730 same_bool_result_p (const_tree op1
, const_tree op2
)
1732 /* Simple cases first. */
1733 if (operand_equal_p (op1
, op2
, 0))
1736 /* Check the cases where at least one of the operands is a comparison.
1737 These are a bit smarter than operand_equal_p in that they apply some
1738 identifies on SSA_NAMEs. */
1739 if (TREE_CODE_CLASS (TREE_CODE (op2
)) == tcc_comparison
1740 && same_bool_comparison_p (op1
, TREE_CODE (op2
),
1741 TREE_OPERAND (op2
, 0),
1742 TREE_OPERAND (op2
, 1)))
1744 if (TREE_CODE_CLASS (TREE_CODE (op1
)) == tcc_comparison
1745 && same_bool_comparison_p (op2
, TREE_CODE (op1
),
1746 TREE_OPERAND (op1
, 0),
1747 TREE_OPERAND (op1
, 1)))
1754 /* Forward declarations for some mutually recursive functions. */
1757 and_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1758 enum tree_code code2
, tree op2a
, tree op2b
);
1760 and_var_with_comparison (tree var
, bool invert
,
1761 enum tree_code code2
, tree op2a
, tree op2b
);
1763 and_var_with_comparison_1 (gimple stmt
,
1764 enum tree_code code2
, tree op2a
, tree op2b
);
1766 or_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1767 enum tree_code code2
, tree op2a
, tree op2b
);
1769 or_var_with_comparison (tree var
, bool invert
,
1770 enum tree_code code2
, tree op2a
, tree op2b
);
1772 or_var_with_comparison_1 (gimple stmt
,
1773 enum tree_code code2
, tree op2a
, tree op2b
);
1775 /* Helper function for and_comparisons_1: try to simplify the AND of the
1776 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1777 If INVERT is true, invert the value of the VAR before doing the AND.
1778 Return NULL_EXPR if we can't simplify this to a single expression. */
1781 and_var_with_comparison (tree var
, bool invert
,
1782 enum tree_code code2
, tree op2a
, tree op2b
)
1785 gimple stmt
= SSA_NAME_DEF_STMT (var
);
1787 /* We can only deal with variables whose definitions are assignments. */
1788 if (!is_gimple_assign (stmt
))
1791 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1792 !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1793 Then we only have to consider the simpler non-inverted cases. */
1795 t
= or_var_with_comparison_1 (stmt
,
1796 invert_tree_comparison (code2
, false),
1799 t
= and_var_with_comparison_1 (stmt
, code2
, op2a
, op2b
);
1800 return canonicalize_bool (t
, invert
);
1803 /* Try to simplify the AND of the ssa variable defined by the assignment
1804 STMT with the comparison specified by (OP2A CODE2 OP2B).
1805 Return NULL_EXPR if we can't simplify this to a single expression. */
1808 and_var_with_comparison_1 (gimple stmt
,
1809 enum tree_code code2
, tree op2a
, tree op2b
)
1811 tree var
= gimple_assign_lhs (stmt
);
1812 tree true_test_var
= NULL_TREE
;
1813 tree false_test_var
= NULL_TREE
;
1814 enum tree_code innercode
= gimple_assign_rhs_code (stmt
);
1816 /* Check for identities like (var AND (var == 0)) => false. */
1817 if (TREE_CODE (op2a
) == SSA_NAME
1818 && TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
)
1820 if ((code2
== NE_EXPR
&& integer_zerop (op2b
))
1821 || (code2
== EQ_EXPR
&& integer_nonzerop (op2b
)))
1823 true_test_var
= op2a
;
1824 if (var
== true_test_var
)
1827 else if ((code2
== EQ_EXPR
&& integer_zerop (op2b
))
1828 || (code2
== NE_EXPR
&& integer_nonzerop (op2b
)))
1830 false_test_var
= op2a
;
1831 if (var
== false_test_var
)
1832 return boolean_false_node
;
1836 /* If the definition is a comparison, recurse on it. */
1837 if (TREE_CODE_CLASS (innercode
) == tcc_comparison
)
1839 tree t
= and_comparisons_1 (innercode
,
1840 gimple_assign_rhs1 (stmt
),
1841 gimple_assign_rhs2 (stmt
),
1849 /* If the definition is an AND or OR expression, we may be able to
1850 simplify by reassociating. */
1851 if (innercode
== TRUTH_AND_EXPR
1852 || innercode
== TRUTH_OR_EXPR
1853 || (TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
1854 && (innercode
== BIT_AND_EXPR
|| innercode
== BIT_IOR_EXPR
)))
1856 tree inner1
= gimple_assign_rhs1 (stmt
);
1857 tree inner2
= gimple_assign_rhs2 (stmt
);
1860 tree partial
= NULL_TREE
;
1861 bool is_and
= (innercode
== TRUTH_AND_EXPR
|| innercode
== BIT_AND_EXPR
);
1863 /* Check for boolean identities that don't require recursive examination
1865 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1866 inner1 AND (inner1 OR inner2) => inner1
1867 !inner1 AND (inner1 AND inner2) => false
1868 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1869 Likewise for similar cases involving inner2. */
1870 if (inner1
== true_test_var
)
1871 return (is_and
? var
: inner1
);
1872 else if (inner2
== true_test_var
)
1873 return (is_and
? var
: inner2
);
1874 else if (inner1
== false_test_var
)
1876 ? boolean_false_node
1877 : and_var_with_comparison (inner2
, false, code2
, op2a
, op2b
));
1878 else if (inner2
== false_test_var
)
1880 ? boolean_false_node
1881 : and_var_with_comparison (inner1
, false, code2
, op2a
, op2b
));
1883 /* Next, redistribute/reassociate the AND across the inner tests.
1884 Compute the first partial result, (inner1 AND (op2a code op2b)) */
1885 if (TREE_CODE (inner1
) == SSA_NAME
1886 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner1
))
1887 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
1888 && (t
= maybe_fold_and_comparisons (gimple_assign_rhs_code (s
),
1889 gimple_assign_rhs1 (s
),
1890 gimple_assign_rhs2 (s
),
1891 code2
, op2a
, op2b
)))
1893 /* Handle the AND case, where we are reassociating:
1894 (inner1 AND inner2) AND (op2a code2 op2b)
1896 If the partial result t is a constant, we win. Otherwise
1897 continue on to try reassociating with the other inner test. */
1900 if (integer_onep (t
))
1902 else if (integer_zerop (t
))
1903 return boolean_false_node
;
1906 /* Handle the OR case, where we are redistributing:
1907 (inner1 OR inner2) AND (op2a code2 op2b)
1908 => (t OR (inner2 AND (op2a code2 op2b))) */
1909 else if (integer_onep (t
))
1910 return boolean_true_node
;
1912 /* Save partial result for later. */
1916 /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1917 if (TREE_CODE (inner2
) == SSA_NAME
1918 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner2
))
1919 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
1920 && (t
= maybe_fold_and_comparisons (gimple_assign_rhs_code (s
),
1921 gimple_assign_rhs1 (s
),
1922 gimple_assign_rhs2 (s
),
1923 code2
, op2a
, op2b
)))
1925 /* Handle the AND case, where we are reassociating:
1926 (inner1 AND inner2) AND (op2a code2 op2b)
1927 => (inner1 AND t) */
1930 if (integer_onep (t
))
1932 else if (integer_zerop (t
))
1933 return boolean_false_node
;
1934 /* If both are the same, we can apply the identity
1936 else if (partial
&& same_bool_result_p (t
, partial
))
1940 /* Handle the OR case. where we are redistributing:
1941 (inner1 OR inner2) AND (op2a code2 op2b)
1942 => (t OR (inner1 AND (op2a code2 op2b)))
1943 => (t OR partial) */
1946 if (integer_onep (t
))
1947 return boolean_true_node
;
1950 /* We already got a simplification for the other
1951 operand to the redistributed OR expression. The
1952 interesting case is when at least one is false.
1953 Or, if both are the same, we can apply the identity
1955 if (integer_zerop (partial
))
1957 else if (integer_zerop (t
))
1959 else if (same_bool_result_p (t
, partial
))
1968 /* Try to simplify the AND of two comparisons defined by
1969 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
1970 If this can be done without constructing an intermediate value,
1971 return the resulting tree; otherwise NULL_TREE is returned.
1972 This function is deliberately asymmetric as it recurses on SSA_DEFs
1973 in the first comparison but not the second. */
1976 and_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
1977 enum tree_code code2
, tree op2a
, tree op2b
)
1979 /* First check for ((x CODE1 y) AND (x CODE2 y)). */
1980 if (operand_equal_p (op1a
, op2a
, 0)
1981 && operand_equal_p (op1b
, op2b
, 0))
1983 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
1984 TRUTH_ANDIF_EXPR
, code1
, code2
,
1985 boolean_type_node
, op1a
, op1b
);
1990 /* Likewise the swapped case of the above. */
1991 if (operand_equal_p (op1a
, op2b
, 0)
1992 && operand_equal_p (op1b
, op2a
, 0))
1994 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
1995 TRUTH_ANDIF_EXPR
, code1
,
1996 swap_tree_comparison (code2
),
1997 boolean_type_node
, op1a
, op1b
);
2002 /* If both comparisons are of the same value against constants, we might
2003 be able to merge them. */
2004 if (operand_equal_p (op1a
, op2a
, 0)
2005 && TREE_CODE (op1b
) == INTEGER_CST
2006 && TREE_CODE (op2b
) == INTEGER_CST
)
2008 int cmp
= tree_int_cst_compare (op1b
, op2b
);
2010 /* If we have (op1a == op1b), we should either be able to
2011 return that or FALSE, depending on whether the constant op1b
2012 also satisfies the other comparison against op2b. */
2013 if (code1
== EQ_EXPR
)
2019 case EQ_EXPR
: val
= (cmp
== 0); break;
2020 case NE_EXPR
: val
= (cmp
!= 0); break;
2021 case LT_EXPR
: val
= (cmp
< 0); break;
2022 case GT_EXPR
: val
= (cmp
> 0); break;
2023 case LE_EXPR
: val
= (cmp
<= 0); break;
2024 case GE_EXPR
: val
= (cmp
>= 0); break;
2025 default: done
= false;
2030 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2032 return boolean_false_node
;
2035 /* Likewise if the second comparison is an == comparison. */
2036 else if (code2
== EQ_EXPR
)
2042 case EQ_EXPR
: val
= (cmp
== 0); break;
2043 case NE_EXPR
: val
= (cmp
!= 0); break;
2044 case LT_EXPR
: val
= (cmp
> 0); break;
2045 case GT_EXPR
: val
= (cmp
< 0); break;
2046 case LE_EXPR
: val
= (cmp
>= 0); break;
2047 case GE_EXPR
: val
= (cmp
<= 0); break;
2048 default: done
= false;
2053 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2055 return boolean_false_node
;
2059 /* Same business with inequality tests. */
2060 else if (code1
== NE_EXPR
)
2065 case EQ_EXPR
: val
= (cmp
!= 0); break;
2066 case NE_EXPR
: val
= (cmp
== 0); break;
2067 case LT_EXPR
: val
= (cmp
>= 0); break;
2068 case GT_EXPR
: val
= (cmp
<= 0); break;
2069 case LE_EXPR
: val
= (cmp
> 0); break;
2070 case GE_EXPR
: val
= (cmp
< 0); break;
2075 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2077 else if (code2
== NE_EXPR
)
2082 case EQ_EXPR
: val
= (cmp
== 0); break;
2083 case NE_EXPR
: val
= (cmp
!= 0); break;
2084 case LT_EXPR
: val
= (cmp
<= 0); break;
2085 case GT_EXPR
: val
= (cmp
>= 0); break;
2086 case LE_EXPR
: val
= (cmp
< 0); break;
2087 case GE_EXPR
: val
= (cmp
> 0); break;
2092 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2095 /* Chose the more restrictive of two < or <= comparisons. */
2096 else if ((code1
== LT_EXPR
|| code1
== LE_EXPR
)
2097 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2099 if ((cmp
< 0) || (cmp
== 0 && code1
== LT_EXPR
))
2100 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2102 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2105 /* Likewise chose the more restrictive of two > or >= comparisons. */
2106 else if ((code1
== GT_EXPR
|| code1
== GE_EXPR
)
2107 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2109 if ((cmp
> 0) || (cmp
== 0 && code1
== GT_EXPR
))
2110 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2112 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2115 /* Check for singleton ranges. */
2117 && ((code1
== LE_EXPR
&& code2
== GE_EXPR
)
2118 || (code1
== GE_EXPR
&& code2
== LE_EXPR
)))
2119 return fold_build2 (EQ_EXPR
, boolean_type_node
, op1a
, op2b
);
2121 /* Check for disjoint ranges. */
2123 && (code1
== LT_EXPR
|| code1
== LE_EXPR
)
2124 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2125 return boolean_false_node
;
2127 && (code1
== GT_EXPR
|| code1
== GE_EXPR
)
2128 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2129 return boolean_false_node
;
2132 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2133 NAME's definition is a truth value. See if there are any simplifications
2134 that can be done against the NAME's definition. */
2135 if (TREE_CODE (op1a
) == SSA_NAME
2136 && (code1
== NE_EXPR
|| code1
== EQ_EXPR
)
2137 && (integer_zerop (op1b
) || integer_onep (op1b
)))
2139 bool invert
= ((code1
== EQ_EXPR
&& integer_zerop (op1b
))
2140 || (code1
== NE_EXPR
&& integer_onep (op1b
)));
2141 gimple stmt
= SSA_NAME_DEF_STMT (op1a
);
2142 switch (gimple_code (stmt
))
2145 /* Try to simplify by copy-propagating the definition. */
2146 return and_var_with_comparison (op1a
, invert
, code2
, op2a
, op2b
);
2149 /* If every argument to the PHI produces the same result when
2150 ANDed with the second comparison, we win.
2151 Do not do this unless the type is bool since we need a bool
2152 result here anyway. */
2153 if (TREE_CODE (TREE_TYPE (op1a
)) == BOOLEAN_TYPE
)
2155 tree result
= NULL_TREE
;
2157 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
2159 tree arg
= gimple_phi_arg_def (stmt
, i
);
2161 /* If this PHI has itself as an argument, ignore it.
2162 If all the other args produce the same result,
2164 if (arg
== gimple_phi_result (stmt
))
2166 else if (TREE_CODE (arg
) == INTEGER_CST
)
2168 if (invert
? integer_nonzerop (arg
) : integer_zerop (arg
))
2171 result
= boolean_false_node
;
2172 else if (!integer_zerop (result
))
2176 result
= fold_build2 (code2
, boolean_type_node
,
2178 else if (!same_bool_comparison_p (result
,
2182 else if (TREE_CODE (arg
) == SSA_NAME
)
2184 tree temp
= and_var_with_comparison (arg
, invert
,
2190 else if (!same_bool_result_p (result
, temp
))
2206 /* Try to simplify the AND of two comparisons, specified by
2207 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2208 If this can be simplified to a single expression (without requiring
2209 introducing more SSA variables to hold intermediate values),
2210 return the resulting tree. Otherwise return NULL_TREE.
2211 If the result expression is non-null, it has boolean type. */
2214 maybe_fold_and_comparisons (enum tree_code code1
, tree op1a
, tree op1b
,
2215 enum tree_code code2
, tree op2a
, tree op2b
)
2217 tree t
= and_comparisons_1 (code1
, op1a
, op1b
, code2
, op2a
, op2b
);
2221 return and_comparisons_1 (code2
, op2a
, op2b
, code1
, op1a
, op1b
);
2224 /* Helper function for or_comparisons_1: try to simplify the OR of the
2225 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
2226 If INVERT is true, invert the value of VAR before doing the OR.
2227 Return NULL_EXPR if we can't simplify this to a single expression. */
2230 or_var_with_comparison (tree var
, bool invert
,
2231 enum tree_code code2
, tree op2a
, tree op2b
)
2234 gimple stmt
= SSA_NAME_DEF_STMT (var
);
2236 /* We can only deal with variables whose definitions are assignments. */
2237 if (!is_gimple_assign (stmt
))
2240 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
2241 !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
2242 Then we only have to consider the simpler non-inverted cases. */
2244 t
= and_var_with_comparison_1 (stmt
,
2245 invert_tree_comparison (code2
, false),
2248 t
= or_var_with_comparison_1 (stmt
, code2
, op2a
, op2b
);
2249 return canonicalize_bool (t
, invert
);
2252 /* Try to simplify the OR of the ssa variable defined by the assignment
2253 STMT with the comparison specified by (OP2A CODE2 OP2B).
2254 Return NULL_EXPR if we can't simplify this to a single expression. */
2257 or_var_with_comparison_1 (gimple stmt
,
2258 enum tree_code code2
, tree op2a
, tree op2b
)
2260 tree var
= gimple_assign_lhs (stmt
);
2261 tree true_test_var
= NULL_TREE
;
2262 tree false_test_var
= NULL_TREE
;
2263 enum tree_code innercode
= gimple_assign_rhs_code (stmt
);
2265 /* Check for identities like (var OR (var != 0)) => true . */
2266 if (TREE_CODE (op2a
) == SSA_NAME
2267 && TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
)
2269 if ((code2
== NE_EXPR
&& integer_zerop (op2b
))
2270 || (code2
== EQ_EXPR
&& integer_nonzerop (op2b
)))
2272 true_test_var
= op2a
;
2273 if (var
== true_test_var
)
2276 else if ((code2
== EQ_EXPR
&& integer_zerop (op2b
))
2277 || (code2
== NE_EXPR
&& integer_nonzerop (op2b
)))
2279 false_test_var
= op2a
;
2280 if (var
== false_test_var
)
2281 return boolean_true_node
;
2285 /* If the definition is a comparison, recurse on it. */
2286 if (TREE_CODE_CLASS (innercode
) == tcc_comparison
)
2288 tree t
= or_comparisons_1 (innercode
,
2289 gimple_assign_rhs1 (stmt
),
2290 gimple_assign_rhs2 (stmt
),
2298 /* If the definition is an AND or OR expression, we may be able to
2299 simplify by reassociating. */
2300 if (innercode
== TRUTH_AND_EXPR
2301 || innercode
== TRUTH_OR_EXPR
2302 || (TREE_CODE (TREE_TYPE (var
)) == BOOLEAN_TYPE
2303 && (innercode
== BIT_AND_EXPR
|| innercode
== BIT_IOR_EXPR
)))
2305 tree inner1
= gimple_assign_rhs1 (stmt
);
2306 tree inner2
= gimple_assign_rhs2 (stmt
);
2309 tree partial
= NULL_TREE
;
2310 bool is_or
= (innercode
== TRUTH_OR_EXPR
|| innercode
== BIT_IOR_EXPR
);
2312 /* Check for boolean identities that don't require recursive examination
2314 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2315 inner1 OR (inner1 AND inner2) => inner1
2316 !inner1 OR (inner1 OR inner2) => true
2317 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2319 if (inner1
== true_test_var
)
2320 return (is_or
? var
: inner1
);
2321 else if (inner2
== true_test_var
)
2322 return (is_or
? var
: inner2
);
2323 else if (inner1
== false_test_var
)
2326 : or_var_with_comparison (inner2
, false, code2
, op2a
, op2b
));
2327 else if (inner2
== false_test_var
)
2330 : or_var_with_comparison (inner1
, false, code2
, op2a
, op2b
));
2332 /* Next, redistribute/reassociate the OR across the inner tests.
2333 Compute the first partial result, (inner1 OR (op2a code op2b)) */
2334 if (TREE_CODE (inner1
) == SSA_NAME
2335 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner1
))
2336 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
2337 && (t
= maybe_fold_or_comparisons (gimple_assign_rhs_code (s
),
2338 gimple_assign_rhs1 (s
),
2339 gimple_assign_rhs2 (s
),
2340 code2
, op2a
, op2b
)))
2342 /* Handle the OR case, where we are reassociating:
2343 (inner1 OR inner2) OR (op2a code2 op2b)
2345 If the partial result t is a constant, we win. Otherwise
2346 continue on to try reassociating with the other inner test. */
2349 if (integer_onep (t
))
2350 return boolean_true_node
;
2351 else if (integer_zerop (t
))
2355 /* Handle the AND case, where we are redistributing:
2356 (inner1 AND inner2) OR (op2a code2 op2b)
2357 => (t AND (inner2 OR (op2a code op2b))) */
2358 else if (integer_zerop (t
))
2359 return boolean_false_node
;
2361 /* Save partial result for later. */
2365 /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2366 if (TREE_CODE (inner2
) == SSA_NAME
2367 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (inner2
))
2368 && TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
2369 && (t
= maybe_fold_or_comparisons (gimple_assign_rhs_code (s
),
2370 gimple_assign_rhs1 (s
),
2371 gimple_assign_rhs2 (s
),
2372 code2
, op2a
, op2b
)))
2374 /* Handle the OR case, where we are reassociating:
2375 (inner1 OR inner2) OR (op2a code2 op2b)
2377 => (t OR partial) */
2380 if (integer_zerop (t
))
2382 else if (integer_onep (t
))
2383 return boolean_true_node
;
2384 /* If both are the same, we can apply the identity
2386 else if (partial
&& same_bool_result_p (t
, partial
))
2390 /* Handle the AND case, where we are redistributing:
2391 (inner1 AND inner2) OR (op2a code2 op2b)
2392 => (t AND (inner1 OR (op2a code2 op2b)))
2393 => (t AND partial) */
2396 if (integer_zerop (t
))
2397 return boolean_false_node
;
2400 /* We already got a simplification for the other
2401 operand to the redistributed AND expression. The
2402 interesting case is when at least one is true.
2403 Or, if both are the same, we can apply the identity
2405 if (integer_onep (partial
))
2407 else if (integer_onep (t
))
2409 else if (same_bool_result_p (t
, partial
))
2418 /* Try to simplify the OR of two comparisons defined by
2419 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2420 If this can be done without constructing an intermediate value,
2421 return the resulting tree; otherwise NULL_TREE is returned.
2422 This function is deliberately asymmetric as it recurses on SSA_DEFs
2423 in the first comparison but not the second. */
2426 or_comparisons_1 (enum tree_code code1
, tree op1a
, tree op1b
,
2427 enum tree_code code2
, tree op2a
, tree op2b
)
2429 /* First check for ((x CODE1 y) OR (x CODE2 y)). */
2430 if (operand_equal_p (op1a
, op2a
, 0)
2431 && operand_equal_p (op1b
, op2b
, 0))
2433 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
2434 TRUTH_ORIF_EXPR
, code1
, code2
,
2435 boolean_type_node
, op1a
, op1b
);
2440 /* Likewise the swapped case of the above. */
2441 if (operand_equal_p (op1a
, op2b
, 0)
2442 && operand_equal_p (op1b
, op2a
, 0))
2444 tree t
= combine_comparisons (UNKNOWN_LOCATION
,
2445 TRUTH_ORIF_EXPR
, code1
,
2446 swap_tree_comparison (code2
),
2447 boolean_type_node
, op1a
, op1b
);
2452 /* If both comparisons are of the same value against constants, we might
2453 be able to merge them. */
2454 if (operand_equal_p (op1a
, op2a
, 0)
2455 && TREE_CODE (op1b
) == INTEGER_CST
2456 && TREE_CODE (op2b
) == INTEGER_CST
)
2458 int cmp
= tree_int_cst_compare (op1b
, op2b
);
2460 /* If we have (op1a != op1b), we should either be able to
2461 return that or TRUE, depending on whether the constant op1b
2462 also satisfies the other comparison against op2b. */
2463 if (code1
== NE_EXPR
)
2469 case EQ_EXPR
: val
= (cmp
== 0); break;
2470 case NE_EXPR
: val
= (cmp
!= 0); break;
2471 case LT_EXPR
: val
= (cmp
< 0); break;
2472 case GT_EXPR
: val
= (cmp
> 0); break;
2473 case LE_EXPR
: val
= (cmp
<= 0); break;
2474 case GE_EXPR
: val
= (cmp
>= 0); break;
2475 default: done
= false;
2480 return boolean_true_node
;
2482 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2485 /* Likewise if the second comparison is a != comparison. */
2486 else if (code2
== NE_EXPR
)
2492 case EQ_EXPR
: val
= (cmp
== 0); break;
2493 case NE_EXPR
: val
= (cmp
!= 0); break;
2494 case LT_EXPR
: val
= (cmp
> 0); break;
2495 case GT_EXPR
: val
= (cmp
< 0); break;
2496 case LE_EXPR
: val
= (cmp
>= 0); break;
2497 case GE_EXPR
: val
= (cmp
<= 0); break;
2498 default: done
= false;
2503 return boolean_true_node
;
2505 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2509 /* See if an equality test is redundant with the other comparison. */
2510 else if (code1
== EQ_EXPR
)
2515 case EQ_EXPR
: val
= (cmp
== 0); break;
2516 case NE_EXPR
: val
= (cmp
!= 0); break;
2517 case LT_EXPR
: val
= (cmp
< 0); break;
2518 case GT_EXPR
: val
= (cmp
> 0); break;
2519 case LE_EXPR
: val
= (cmp
<= 0); break;
2520 case GE_EXPR
: val
= (cmp
>= 0); break;
2525 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2527 else if (code2
== EQ_EXPR
)
2532 case EQ_EXPR
: val
= (cmp
== 0); break;
2533 case NE_EXPR
: val
= (cmp
!= 0); break;
2534 case LT_EXPR
: val
= (cmp
> 0); break;
2535 case GT_EXPR
: val
= (cmp
< 0); break;
2536 case LE_EXPR
: val
= (cmp
>= 0); break;
2537 case GE_EXPR
: val
= (cmp
<= 0); break;
2542 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2545 /* Chose the less restrictive of two < or <= comparisons. */
2546 else if ((code1
== LT_EXPR
|| code1
== LE_EXPR
)
2547 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2549 if ((cmp
< 0) || (cmp
== 0 && code1
== LT_EXPR
))
2550 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2552 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2555 /* Likewise chose the less restrictive of two > or >= comparisons. */
2556 else if ((code1
== GT_EXPR
|| code1
== GE_EXPR
)
2557 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2559 if ((cmp
> 0) || (cmp
== 0 && code1
== GT_EXPR
))
2560 return fold_build2 (code2
, boolean_type_node
, op2a
, op2b
);
2562 return fold_build2 (code1
, boolean_type_node
, op1a
, op1b
);
2565 /* Check for singleton ranges. */
2567 && ((code1
== LT_EXPR
&& code2
== GT_EXPR
)
2568 || (code1
== GT_EXPR
&& code2
== LT_EXPR
)))
2569 return fold_build2 (NE_EXPR
, boolean_type_node
, op1a
, op2b
);
2571 /* Check for less/greater pairs that don't restrict the range at all. */
2573 && (code1
== LT_EXPR
|| code1
== LE_EXPR
)
2574 && (code2
== GT_EXPR
|| code2
== GE_EXPR
))
2575 return boolean_true_node
;
2577 && (code1
== GT_EXPR
|| code1
== GE_EXPR
)
2578 && (code2
== LT_EXPR
|| code2
== LE_EXPR
))
2579 return boolean_true_node
;
2582 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2583 NAME's definition is a truth value. See if there are any simplifications
2584 that can be done against the NAME's definition. */
2585 if (TREE_CODE (op1a
) == SSA_NAME
2586 && (code1
== NE_EXPR
|| code1
== EQ_EXPR
)
2587 && (integer_zerop (op1b
) || integer_onep (op1b
)))
2589 bool invert
= ((code1
== EQ_EXPR
&& integer_zerop (op1b
))
2590 || (code1
== NE_EXPR
&& integer_onep (op1b
)));
2591 gimple stmt
= SSA_NAME_DEF_STMT (op1a
);
2592 switch (gimple_code (stmt
))
2595 /* Try to simplify by copy-propagating the definition. */
2596 return or_var_with_comparison (op1a
, invert
, code2
, op2a
, op2b
);
2599 /* If every argument to the PHI produces the same result when
2600 ORed with the second comparison, we win.
2601 Do not do this unless the type is bool since we need a bool
2602 result here anyway. */
2603 if (TREE_CODE (TREE_TYPE (op1a
)) == BOOLEAN_TYPE
)
2605 tree result
= NULL_TREE
;
2607 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
2609 tree arg
= gimple_phi_arg_def (stmt
, i
);
2611 /* If this PHI has itself as an argument, ignore it.
2612 If all the other args produce the same result,
2614 if (arg
== gimple_phi_result (stmt
))
2616 else if (TREE_CODE (arg
) == INTEGER_CST
)
2618 if (invert
? integer_zerop (arg
) : integer_nonzerop (arg
))
2621 result
= boolean_true_node
;
2622 else if (!integer_onep (result
))
2626 result
= fold_build2 (code2
, boolean_type_node
,
2628 else if (!same_bool_comparison_p (result
,
2632 else if (TREE_CODE (arg
) == SSA_NAME
)
2634 tree temp
= or_var_with_comparison (arg
, invert
,
2640 else if (!same_bool_result_p (result
, temp
))
2656 /* Try to simplify the OR of two comparisons, specified by
2657 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2658 If this can be simplified to a single expression (without requiring
2659 introducing more SSA variables to hold intermediate values),
2660 return the resulting tree. Otherwise return NULL_TREE.
2661 If the result expression is non-null, it has boolean type. */
2664 maybe_fold_or_comparisons (enum tree_code code1
, tree op1a
, tree op1b
,
2665 enum tree_code code2
, tree op2a
, tree op2b
)
2667 tree t
= or_comparisons_1 (code1
, op1a
, op1b
, code2
, op2a
, op2b
);
2671 return or_comparisons_1 (code2
, op2a
, op2b
, code1
, op1a
, op1b
);