1 /* Statement simplification on GIMPLE.
2 Copyright (C) 2010, 2011 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_method_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 /* If BV_VCALL_INDEX is non-NULL, give up. */
1400 fndecl = TREE_VALUE (v);
1401 node = cgraph_get_node_or_alias (fndecl);
1404 /* Bail out if it is a thunk declaration. Since simple this_adjusting
1405 thunks are represented by a constant in TREE_PURPOSE of items in
1406 BINFO_VIRTUALS, this is a more complicate type which we cannot handle as
1409 FIXME: Remove the following condition once we are able to represent
1410 thunk information on call graph edges. */
1411 || (node->same_body_alias && node->thunk.thunk_p)))
1414 /* When cgraph node is missing and function is not public, we cannot
1415 devirtualize. This can happen in WHOPR when the actual method
1416 ends up in other partition, because we found devirtualization
1417 possibility too late. */
1418 if (!can_refer_decl_in_current_unit_p (TREE_VALUE (v)))
1421 *delta = TREE_PURPOSE (v);
1422 gcc_checking_assert (host_integerp (*delta, 0));
1426 /* Generate code adjusting the first parameter of a call statement determined
1430 gimple_adjust_this_by_delta (gimple_stmt_iterator *gsi, tree delta)
1432 gimple call_stmt = gsi_stmt (*gsi);
1436 delta = fold_convert (sizetype, delta);
1437 gcc_assert (gimple_call_num_args (call_stmt) >= 1);
1438 parm = gimple_call_arg (call_stmt, 0);
1439 gcc_assert (POINTER_TYPE_P (TREE_TYPE (parm)));
1440 tmp = create_tmp_var (TREE_TYPE (parm), NULL);
1441 add_referenced_var (tmp);
1443 tmp = make_ssa_name (tmp, NULL);
1444 new_stmt = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, tmp, parm, delta);
1445 SSA_NAME_DEF_STMT (tmp) = new_stmt;
1446 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1447 gimple_call_set_arg (call_stmt, 0, tmp);
1450 /* Attempt to fold a call statement referenced by the statement iterator GSI.
1451 The statement may be replaced by another statement, e.g., if the call
1452 simplifies to a constant value. Return true if any changes were made.
1453 It is assumed that the operands have been previously folded. */
1456 gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
1458 gimple stmt = gsi_stmt (*gsi);
1460 tree callee = gimple_call_fndecl (stmt);
1462 /* Check for builtins that CCP can handle using information not
1463 available in the generic fold routines. */
1464 if (!inplace && callee && DECL_BUILT_IN (callee))
1466 tree result = gimple_fold_builtin (stmt);
1470 if (!update_call_from_tree (gsi, result))
1471 gimplify_and_update_call_from_tree (gsi, result);
1478 /* Worker for both fold_stmt and fold_stmt_inplace. The INPLACE argument
1479 distinguishes both cases. */
1482 fold_stmt_1 (gimple_stmt_iterator *gsi, bool inplace)
1484 bool changed = false;
1485 gimple stmt = gsi_stmt (*gsi);
1487 gimple_stmt_iterator gsinext = *gsi;
1490 gsi_next (&gsinext);
1491 next_stmt = gsi_end_p (gsinext) ? NULL : gsi_stmt (gsinext);
1493 /* Fold the main computation performed by the statement. */
1494 switch (gimple_code (stmt))
1498 unsigned old_num_ops = gimple_num_ops (stmt);
1499 tree new_rhs = fold_gimple_assign (gsi);
1500 tree lhs = gimple_assign_lhs (stmt);
1502 && !useless_type_conversion_p (TREE_TYPE (lhs),
1503 TREE_TYPE (new_rhs)))
1504 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1507 || get_gimple_rhs_num_ops (TREE_CODE (new_rhs)) < old_num_ops))
1509 gimple_assign_set_rhs_from_tree (gsi, new_rhs);
1516 changed |= fold_gimple_cond (stmt);
1520 /* Fold *& in call arguments. */
1521 for (i = 0; i < gimple_call_num_args (stmt); ++i)
1522 if (REFERENCE_CLASS_P (gimple_call_arg (stmt, i)))
1524 tree tmp = maybe_fold_reference (gimple_call_arg (stmt, i), false);
1527 gimple_call_set_arg (stmt, i, tmp);
1531 changed |= gimple_fold_call (gsi, inplace);
1535 /* Fold *& in asm operands. */
1538 const char **oconstraints;
1539 const char *constraint;
1540 bool allows_mem, allows_reg;
1542 noutputs = gimple_asm_noutputs (stmt);
1543 oconstraints = XALLOCAVEC (const char *, noutputs);
1545 for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
1547 tree link = gimple_asm_output_op (stmt, i);
1548 tree op = TREE_VALUE (link);
1550 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1551 if (REFERENCE_CLASS_P (op)
1552 && (op = maybe_fold_reference (op, true)) != NULL_TREE)
1554 TREE_VALUE (link) = op;
1558 for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
1560 tree link = gimple_asm_input_op (stmt, i);
1561 tree op = TREE_VALUE (link);
1563 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
1564 parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1565 oconstraints, &allows_mem, &allows_reg);
1566 if (REFERENCE_CLASS_P (op)
1567 && (op = maybe_fold_reference (op, !allows_reg && allows_mem))
1570 TREE_VALUE (link) = op;
1578 if (gimple_debug_bind_p (stmt))
1580 tree val = gimple_debug_bind_get_value (stmt);
1582 && REFERENCE_CLASS_P (val))
1584 tree tem = maybe_fold_reference (val, false);
1587 gimple_debug_bind_set_value (stmt, tem);
1597 /* If stmt folds into nothing and it was the last stmt in a bb,
1598 don't call gsi_stmt. */
1599 if (gsi_end_p (*gsi))
1601 gcc_assert (next_stmt == NULL);
1605 stmt = gsi_stmt (*gsi);
1607 /* Fold *& on the lhs. Don't do this if stmt folded into nothing,
1608 as we'd changing the next stmt. */
1609 if (gimple_has_lhs (stmt) && stmt != next_stmt)
1611 tree lhs = gimple_get_lhs (stmt);
1612 if (lhs && REFERENCE_CLASS_P (lhs))
1614 tree new_lhs = maybe_fold_reference (lhs, true);
1617 gimple_set_lhs (stmt, new_lhs);
1626 /* Fold the statement pointed to by GSI. In some cases, this function may
1627 replace the whole statement with a new one. Returns true iff folding
1629 The statement pointed to by GSI should be in valid gimple form but may
1630 be in unfolded state as resulting from for example constant propagation
1631 which can produce *&x = 0. */
1634 fold_stmt (gimple_stmt_iterator *gsi)
1636 return fold_stmt_1 (gsi, false);
1639 /* Perform the minimal folding on statement STMT. Only operations like
1640 *&x created by constant propagation are handled. The statement cannot
1641 be replaced with a new one. Return true if the statement was
1642 changed, false otherwise.
1643 The statement STMT should be in valid gimple form but may
1644 be in unfolded state as resulting from for example constant propagation
1645 which can produce *&x = 0. */
1648 fold_stmt_inplace (gimple stmt)
1650 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1651 bool changed = fold_stmt_1 (&gsi, true);
1652 gcc_assert (gsi_stmt (gsi) == stmt);
1656 /* Canonicalize and possibly invert the boolean EXPR; return NULL_TREE
1657 if EXPR is null or we don't know how.
1658 If non-null, the result always has boolean type. */
1661 canonicalize_bool (tree expr, bool invert)
1667 if (integer_nonzerop (expr))
1668 return boolean_false_node;
1669 else if (integer_zerop (expr))
1670 return boolean_true_node;
1671 else if (TREE_CODE (expr) == SSA_NAME)
1672 return fold_build2 (EQ_EXPR, boolean_type_node, expr,
1673 build_int_cst (TREE_TYPE (expr), 0));
1674 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1675 return fold_build2 (invert_tree_comparison (TREE_CODE (expr), false),
1677 TREE_OPERAND (expr, 0),
1678 TREE_OPERAND (expr, 1));
1684 if (TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1686 if (integer_nonzerop (expr))
1687 return boolean_true_node;
1688 else if (integer_zerop (expr))
1689 return boolean_false_node;
1690 else if (TREE_CODE (expr) == SSA_NAME)
1691 return fold_build2 (NE_EXPR, boolean_type_node, expr,
1692 build_int_cst (TREE_TYPE (expr), 0));
1693 else if (TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison)
1694 return fold_build2 (TREE_CODE (expr),
1696 TREE_OPERAND (expr, 0),
1697 TREE_OPERAND (expr, 1));
1703 /* Check to see if a boolean expression EXPR is logically equivalent to the
1704 comparison (OP1 CODE OP2). Check for various identities involving
1708 same_bool_comparison_p (const_tree expr, enum tree_code code,
1709 const_tree op1, const_tree op2)
1713 /* The obvious case. */
1714 if (TREE_CODE (expr) == code
1715 && operand_equal_p (TREE_OPERAND (expr, 0), op1, 0)
1716 && operand_equal_p (TREE_OPERAND (expr, 1), op2, 0))
1719 /* Check for comparing (name, name != 0) and the case where expr
1720 is an SSA_NAME with a definition matching the comparison. */
1721 if (TREE_CODE (expr) == SSA_NAME
1722 && TREE_CODE (TREE_TYPE (expr)) == BOOLEAN_TYPE)
1724 if (operand_equal_p (expr, op1, 0))
1725 return ((code == NE_EXPR && integer_zerop (op2))
1726 || (code == EQ_EXPR && integer_nonzerop (op2)));
1727 s = SSA_NAME_DEF_STMT (expr);
1728 if (is_gimple_assign (s)
1729 && gimple_assign_rhs_code (s) == code
1730 && operand_equal_p (gimple_assign_rhs1 (s), op1, 0)
1731 && operand_equal_p (gimple_assign_rhs2 (s), op2, 0))
1735 /* If op1 is of the form (name != 0) or (name == 0), and the definition
1736 of name is a comparison, recurse. */
1737 if (TREE_CODE (op1) == SSA_NAME
1738 && TREE_CODE (TREE_TYPE (op1)) == BOOLEAN_TYPE)
1740 s = SSA_NAME_DEF_STMT (op1);
1741 if (is_gimple_assign (s)
1742 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
1744 enum tree_code c = gimple_assign_rhs_code (s);
1745 if ((c == NE_EXPR && integer_zerop (op2))
1746 || (c == EQ_EXPR && integer_nonzerop (op2)))
1747 return same_bool_comparison_p (expr, c,
1748 gimple_assign_rhs1 (s),
1749 gimple_assign_rhs2 (s));
1750 if ((c == EQ_EXPR && integer_zerop (op2))
1751 || (c == NE_EXPR && integer_nonzerop (op2)))
1752 return same_bool_comparison_p (expr,
1753 invert_tree_comparison (c, false),
1754 gimple_assign_rhs1 (s),
1755 gimple_assign_rhs2 (s));
1761 /* Check to see if two boolean expressions OP1 and OP2 are logically
1765 same_bool_result_p (const_tree op1, const_tree op2)
1767 /* Simple cases first. */
1768 if (operand_equal_p (op1, op2, 0))
1771 /* Check the cases where at least one of the operands is a comparison.
1772 These are a bit smarter than operand_equal_p in that they apply some
1773 identifies on SSA_NAMEs. */
1774 if (TREE_CODE_CLASS (TREE_CODE (op2)) == tcc_comparison
1775 && same_bool_comparison_p (op1, TREE_CODE (op2),
1776 TREE_OPERAND (op2, 0),
1777 TREE_OPERAND (op2, 1)))
1779 if (TREE_CODE_CLASS (TREE_CODE (op1)) == tcc_comparison
1780 && same_bool_comparison_p (op2, TREE_CODE (op1),
1781 TREE_OPERAND (op1, 0),
1782 TREE_OPERAND (op1, 1)))
1789 /* Forward declarations for some mutually recursive functions. */
1792 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1793 enum tree_code code2, tree op2a, tree op2b);
1795 and_var_with_comparison (tree var, bool invert,
1796 enum tree_code code2, tree op2a, tree op2b);
1798 and_var_with_comparison_1 (gimple stmt,
1799 enum tree_code code2, tree op2a, tree op2b);
1801 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
1802 enum tree_code code2, tree op2a, tree op2b);
1804 or_var_with_comparison (tree var, bool invert,
1805 enum tree_code code2, tree op2a, tree op2b);
1807 or_var_with_comparison_1 (gimple stmt,
1808 enum tree_code code2, tree op2a, tree op2b);
1810 /* Helper function for and_comparisons_1: try to simplify the AND of the
1811 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
1812 If INVERT is true, invert the value of the VAR before doing the AND.
1813 Return NULL_EXPR if we can't simplify this to a single expression. */
1816 and_var_with_comparison (tree var, bool invert,
1817 enum tree_code code2, tree op2a, tree op2b)
1820 gimple stmt = SSA_NAME_DEF_STMT (var);
1822 /* We can only deal with variables whose definitions are assignments. */
1823 if (!is_gimple_assign (stmt))
1826 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
1827 !var AND (op2a code2 op2b) => !(var OR !(op2a code2 op2b))
1828 Then we only have to consider the simpler non-inverted cases. */
1830 t = or_var_with_comparison_1 (stmt,
1831 invert_tree_comparison (code2, false),
1834 t = and_var_with_comparison_1 (stmt, code2, op2a, op2b);
1835 return canonicalize_bool (t, invert);
1838 /* Try to simplify the AND of the ssa variable defined by the assignment
1839 STMT with the comparison specified by (OP2A CODE2 OP2B).
1840 Return NULL_EXPR if we can't simplify this to a single expression. */
1843 and_var_with_comparison_1 (gimple stmt,
1844 enum tree_code code2, tree op2a, tree op2b)
1846 tree var = gimple_assign_lhs (stmt);
1847 tree true_test_var = NULL_TREE;
1848 tree false_test_var = NULL_TREE;
1849 enum tree_code innercode = gimple_assign_rhs_code (stmt);
1851 /* Check for identities like (var AND (var == 0)) => false. */
1852 if (TREE_CODE (op2a) == SSA_NAME
1853 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
1855 if ((code2 == NE_EXPR && integer_zerop (op2b))
1856 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
1858 true_test_var = op2a;
1859 if (var == true_test_var)
1862 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
1863 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
1865 false_test_var = op2a;
1866 if (var == false_test_var)
1867 return boolean_false_node;
1871 /* If the definition is a comparison, recurse on it. */
1872 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
1874 tree t = and_comparisons_1 (innercode,
1875 gimple_assign_rhs1 (stmt),
1876 gimple_assign_rhs2 (stmt),
1884 /* If the definition is an AND or OR expression, we may be able to
1885 simplify by reassociating. */
1886 if (innercode == TRUTH_AND_EXPR
1887 || innercode == TRUTH_OR_EXPR
1888 || (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
1889 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
1891 tree inner1 = gimple_assign_rhs1 (stmt);
1892 tree inner2 = gimple_assign_rhs2 (stmt);
1895 tree partial = NULL_TREE;
1896 bool is_and = (innercode == TRUTH_AND_EXPR || innercode == BIT_AND_EXPR);
1898 /* Check for boolean identities that don't require recursive examination
1900 inner1 AND (inner1 AND inner2) => inner1 AND inner2 => var
1901 inner1 AND (inner1 OR inner2) => inner1
1902 !inner1 AND (inner1 AND inner2) => false
1903 !inner1 AND (inner1 OR inner2) => !inner1 AND inner2
1904 Likewise for similar cases involving inner2. */
1905 if (inner1 == true_test_var)
1906 return (is_and ? var : inner1);
1907 else if (inner2 == true_test_var)
1908 return (is_and ? var : inner2);
1909 else if (inner1 == false_test_var)
1911 ? boolean_false_node
1912 : and_var_with_comparison (inner2, false, code2, op2a, op2b));
1913 else if (inner2 == false_test_var)
1915 ? boolean_false_node
1916 : and_var_with_comparison (inner1, false, code2, op2a, op2b));
1918 /* Next, redistribute/reassociate the AND across the inner tests.
1919 Compute the first partial result, (inner1 AND (op2a code op2b)) */
1920 if (TREE_CODE (inner1) == SSA_NAME
1921 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
1922 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1923 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1924 gimple_assign_rhs1 (s),
1925 gimple_assign_rhs2 (s),
1926 code2, op2a, op2b)))
1928 /* Handle the AND case, where we are reassociating:
1929 (inner1 AND inner2) AND (op2a code2 op2b)
1931 If the partial result t is a constant, we win. Otherwise
1932 continue on to try reassociating with the other inner test. */
1935 if (integer_onep (t))
1937 else if (integer_zerop (t))
1938 return boolean_false_node;
1941 /* Handle the OR case, where we are redistributing:
1942 (inner1 OR inner2) AND (op2a code2 op2b)
1943 => (t OR (inner2 AND (op2a code2 op2b))) */
1944 else if (integer_onep (t))
1945 return boolean_true_node;
1947 /* Save partial result for later. */
1951 /* Compute the second partial result, (inner2 AND (op2a code op2b)) */
1952 if (TREE_CODE (inner2) == SSA_NAME
1953 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
1954 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
1955 && (t = maybe_fold_and_comparisons (gimple_assign_rhs_code (s),
1956 gimple_assign_rhs1 (s),
1957 gimple_assign_rhs2 (s),
1958 code2, op2a, op2b)))
1960 /* Handle the AND case, where we are reassociating:
1961 (inner1 AND inner2) AND (op2a code2 op2b)
1962 => (inner1 AND t) */
1965 if (integer_onep (t))
1967 else if (integer_zerop (t))
1968 return boolean_false_node;
1969 /* If both are the same, we can apply the identity
1971 else if (partial && same_bool_result_p (t, partial))
1975 /* Handle the OR case. where we are redistributing:
1976 (inner1 OR inner2) AND (op2a code2 op2b)
1977 => (t OR (inner1 AND (op2a code2 op2b)))
1978 => (t OR partial) */
1981 if (integer_onep (t))
1982 return boolean_true_node;
1985 /* We already got a simplification for the other
1986 operand to the redistributed OR expression. The
1987 interesting case is when at least one is false.
1988 Or, if both are the same, we can apply the identity
1990 if (integer_zerop (partial))
1992 else if (integer_zerop (t))
1994 else if (same_bool_result_p (t, partial))
2003 /* Try to simplify the AND of two comparisons defined by
2004 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2005 If this can be done without constructing an intermediate value,
2006 return the resulting tree; otherwise NULL_TREE is returned.
2007 This function is deliberately asymmetric as it recurses on SSA_DEFs
2008 in the first comparison but not the second. */
2011 and_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2012 enum tree_code code2, tree op2a, tree op2b)
2014 /* First check for ((x CODE1 y) AND (x CODE2 y)). */
2015 if (operand_equal_p (op1a, op2a, 0)
2016 && operand_equal_p (op1b, op2b, 0))
2018 tree t = combine_comparisons (UNKNOWN_LOCATION,
2019 TRUTH_ANDIF_EXPR, code1, code2,
2020 boolean_type_node, op1a, op1b);
2025 /* Likewise the swapped case of the above. */
2026 if (operand_equal_p (op1a, op2b, 0)
2027 && operand_equal_p (op1b, op2a, 0))
2029 tree t = combine_comparisons (UNKNOWN_LOCATION,
2030 TRUTH_ANDIF_EXPR, code1,
2031 swap_tree_comparison (code2),
2032 boolean_type_node, op1a, op1b);
2037 /* If both comparisons are of the same value against constants, we might
2038 be able to merge them. */
2039 if (operand_equal_p (op1a, op2a, 0)
2040 && TREE_CODE (op1b) == INTEGER_CST
2041 && TREE_CODE (op2b) == INTEGER_CST)
2043 int cmp = tree_int_cst_compare (op1b, op2b);
2045 /* If we have (op1a == op1b), we should either be able to
2046 return that or FALSE, depending on whether the constant op1b
2047 also satisfies the other comparison against op2b. */
2048 if (code1 == EQ_EXPR)
2054 case EQ_EXPR: val = (cmp == 0); break;
2055 case NE_EXPR: val = (cmp != 0); break;
2056 case LT_EXPR: val = (cmp < 0); break;
2057 case GT_EXPR: val = (cmp > 0); break;
2058 case LE_EXPR: val = (cmp <= 0); break;
2059 case GE_EXPR: val = (cmp >= 0); break;
2060 default: done = false;
2065 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2067 return boolean_false_node;
2070 /* Likewise if the second comparison is an == comparison. */
2071 else if (code2 == EQ_EXPR)
2077 case EQ_EXPR: val = (cmp == 0); break;
2078 case NE_EXPR: val = (cmp != 0); break;
2079 case LT_EXPR: val = (cmp > 0); break;
2080 case GT_EXPR: val = (cmp < 0); break;
2081 case LE_EXPR: val = (cmp >= 0); break;
2082 case GE_EXPR: val = (cmp <= 0); break;
2083 default: done = false;
2088 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2090 return boolean_false_node;
2094 /* Same business with inequality tests. */
2095 else if (code1 == NE_EXPR)
2100 case EQ_EXPR: val = (cmp != 0); break;
2101 case NE_EXPR: val = (cmp == 0); break;
2102 case LT_EXPR: val = (cmp >= 0); break;
2103 case GT_EXPR: val = (cmp <= 0); break;
2104 case LE_EXPR: val = (cmp > 0); break;
2105 case GE_EXPR: val = (cmp < 0); break;
2110 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2112 else if (code2 == NE_EXPR)
2117 case EQ_EXPR: val = (cmp == 0); break;
2118 case NE_EXPR: val = (cmp != 0); break;
2119 case LT_EXPR: val = (cmp <= 0); break;
2120 case GT_EXPR: val = (cmp >= 0); break;
2121 case LE_EXPR: val = (cmp < 0); break;
2122 case GE_EXPR: val = (cmp > 0); break;
2127 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2130 /* Chose the more restrictive of two < or <= comparisons. */
2131 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2132 && (code2 == LT_EXPR || code2 == LE_EXPR))
2134 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2135 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2137 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2140 /* Likewise chose the more restrictive of two > or >= comparisons. */
2141 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2142 && (code2 == GT_EXPR || code2 == GE_EXPR))
2144 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2145 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2147 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2150 /* Check for singleton ranges. */
2152 && ((code1 == LE_EXPR && code2 == GE_EXPR)
2153 || (code1 == GE_EXPR && code2 == LE_EXPR)))
2154 return fold_build2 (EQ_EXPR, boolean_type_node, op1a, op2b);
2156 /* Check for disjoint ranges. */
2158 && (code1 == LT_EXPR || code1 == LE_EXPR)
2159 && (code2 == GT_EXPR || code2 == GE_EXPR))
2160 return boolean_false_node;
2162 && (code1 == GT_EXPR || code1 == GE_EXPR)
2163 && (code2 == LT_EXPR || code2 == LE_EXPR))
2164 return boolean_false_node;
2167 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2168 NAME's definition is a truth value. See if there are any simplifications
2169 that can be done against the NAME's definition. */
2170 if (TREE_CODE (op1a) == SSA_NAME
2171 && (code1 == NE_EXPR || code1 == EQ_EXPR)
2172 && (integer_zerop (op1b) || integer_onep (op1b)))
2174 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2175 || (code1 == NE_EXPR && integer_onep (op1b)));
2176 gimple stmt = SSA_NAME_DEF_STMT (op1a);
2177 switch (gimple_code (stmt))
2180 /* Try to simplify by copy-propagating the definition. */
2181 return and_var_with_comparison (op1a, invert, code2, op2a, op2b);
2184 /* If every argument to the PHI produces the same result when
2185 ANDed with the second comparison, we win.
2186 Do not do this unless the type is bool since we need a bool
2187 result here anyway. */
2188 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2190 tree result = NULL_TREE;
2192 for (i = 0; i < gimple_phi_num_args (stmt); i++)
2194 tree arg = gimple_phi_arg_def (stmt, i);
2196 /* If this PHI has itself as an argument, ignore it.
2197 If all the other args produce the same result,
2199 if (arg == gimple_phi_result (stmt))
2201 else if (TREE_CODE (arg) == INTEGER_CST)
2203 if (invert ? integer_nonzerop (arg) : integer_zerop (arg))
2206 result = boolean_false_node;
2207 else if (!integer_zerop (result))
2211 result = fold_build2 (code2, boolean_type_node,
2213 else if (!same_bool_comparison_p (result,
2217 else if (TREE_CODE (arg) == SSA_NAME
2218 && !SSA_NAME_IS_DEFAULT_DEF (arg))
2221 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
2222 /* In simple cases we can look through PHI nodes,
2223 but we have to be careful with loops.
2225 if (! dom_info_available_p (CDI_DOMINATORS)
2226 || gimple_bb (def_stmt) == gimple_bb (stmt)
2227 || dominated_by_p (CDI_DOMINATORS,
2228 gimple_bb (def_stmt),
2231 temp = and_var_with_comparison (arg, invert, code2,
2237 else if (!same_bool_result_p (result, temp))
2253 /* Try to simplify the AND of two comparisons, specified by
2254 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2255 If this can be simplified to a single expression (without requiring
2256 introducing more SSA variables to hold intermediate values),
2257 return the resulting tree. Otherwise return NULL_TREE.
2258 If the result expression is non-null, it has boolean type. */
2261 maybe_fold_and_comparisons (enum tree_code code1, tree op1a, tree op1b,
2262 enum tree_code code2, tree op2a, tree op2b)
2264 tree t = and_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2268 return and_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);
2271 /* Helper function for or_comparisons_1: try to simplify the OR of the
2272 ssa variable VAR with the comparison specified by (OP2A CODE2 OP2B).
2273 If INVERT is true, invert the value of VAR before doing the OR.
2274 Return NULL_EXPR if we can't simplify this to a single expression. */
2277 or_var_with_comparison (tree var, bool invert,
2278 enum tree_code code2, tree op2a, tree op2b)
2281 gimple stmt = SSA_NAME_DEF_STMT (var);
2283 /* We can only deal with variables whose definitions are assignments. */
2284 if (!is_gimple_assign (stmt))
2287 /* If we have an inverted comparison, apply DeMorgan's law and rewrite
2288 !var OR (op2a code2 op2b) => !(var AND !(op2a code2 op2b))
2289 Then we only have to consider the simpler non-inverted cases. */
2291 t = and_var_with_comparison_1 (stmt,
2292 invert_tree_comparison (code2, false),
2295 t = or_var_with_comparison_1 (stmt, code2, op2a, op2b);
2296 return canonicalize_bool (t, invert);
2299 /* Try to simplify the OR of the ssa variable defined by the assignment
2300 STMT with the comparison specified by (OP2A CODE2 OP2B).
2301 Return NULL_EXPR if we can't simplify this to a single expression. */
2304 or_var_with_comparison_1 (gimple stmt,
2305 enum tree_code code2, tree op2a, tree op2b)
2307 tree var = gimple_assign_lhs (stmt);
2308 tree true_test_var = NULL_TREE;
2309 tree false_test_var = NULL_TREE;
2310 enum tree_code innercode = gimple_assign_rhs_code (stmt);
2312 /* Check for identities like (var OR (var != 0)) => true . */
2313 if (TREE_CODE (op2a) == SSA_NAME
2314 && TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE)
2316 if ((code2 == NE_EXPR && integer_zerop (op2b))
2317 || (code2 == EQ_EXPR && integer_nonzerop (op2b)))
2319 true_test_var = op2a;
2320 if (var == true_test_var)
2323 else if ((code2 == EQ_EXPR && integer_zerop (op2b))
2324 || (code2 == NE_EXPR && integer_nonzerop (op2b)))
2326 false_test_var = op2a;
2327 if (var == false_test_var)
2328 return boolean_true_node;
2332 /* If the definition is a comparison, recurse on it. */
2333 if (TREE_CODE_CLASS (innercode) == tcc_comparison)
2335 tree t = or_comparisons_1 (innercode,
2336 gimple_assign_rhs1 (stmt),
2337 gimple_assign_rhs2 (stmt),
2345 /* If the definition is an AND or OR expression, we may be able to
2346 simplify by reassociating. */
2347 if (innercode == TRUTH_AND_EXPR
2348 || innercode == TRUTH_OR_EXPR
2349 || (TREE_CODE (TREE_TYPE (var)) == BOOLEAN_TYPE
2350 && (innercode == BIT_AND_EXPR || innercode == BIT_IOR_EXPR)))
2352 tree inner1 = gimple_assign_rhs1 (stmt);
2353 tree inner2 = gimple_assign_rhs2 (stmt);
2356 tree partial = NULL_TREE;
2357 bool is_or = (innercode == TRUTH_OR_EXPR || innercode == BIT_IOR_EXPR);
2359 /* Check for boolean identities that don't require recursive examination
2361 inner1 OR (inner1 OR inner2) => inner1 OR inner2 => var
2362 inner1 OR (inner1 AND inner2) => inner1
2363 !inner1 OR (inner1 OR inner2) => true
2364 !inner1 OR (inner1 AND inner2) => !inner1 OR inner2
2366 if (inner1 == true_test_var)
2367 return (is_or ? var : inner1);
2368 else if (inner2 == true_test_var)
2369 return (is_or ? var : inner2);
2370 else if (inner1 == false_test_var)
2373 : or_var_with_comparison (inner2, false, code2, op2a, op2b));
2374 else if (inner2 == false_test_var)
2377 : or_var_with_comparison (inner1, false, code2, op2a, op2b));
2379 /* Next, redistribute/reassociate the OR across the inner tests.
2380 Compute the first partial result, (inner1 OR (op2a code op2b)) */
2381 if (TREE_CODE (inner1) == SSA_NAME
2382 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner1))
2383 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2384 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2385 gimple_assign_rhs1 (s),
2386 gimple_assign_rhs2 (s),
2387 code2, op2a, op2b)))
2389 /* Handle the OR case, where we are reassociating:
2390 (inner1 OR inner2) OR (op2a code2 op2b)
2392 If the partial result t is a constant, we win. Otherwise
2393 continue on to try reassociating with the other inner test. */
2396 if (integer_onep (t))
2397 return boolean_true_node;
2398 else if (integer_zerop (t))
2402 /* Handle the AND case, where we are redistributing:
2403 (inner1 AND inner2) OR (op2a code2 op2b)
2404 => (t AND (inner2 OR (op2a code op2b))) */
2405 else if (integer_zerop (t))
2406 return boolean_false_node;
2408 /* Save partial result for later. */
2412 /* Compute the second partial result, (inner2 OR (op2a code op2b)) */
2413 if (TREE_CODE (inner2) == SSA_NAME
2414 && is_gimple_assign (s = SSA_NAME_DEF_STMT (inner2))
2415 && TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison
2416 && (t = maybe_fold_or_comparisons (gimple_assign_rhs_code (s),
2417 gimple_assign_rhs1 (s),
2418 gimple_assign_rhs2 (s),
2419 code2, op2a, op2b)))
2421 /* Handle the OR case, where we are reassociating:
2422 (inner1 OR inner2) OR (op2a code2 op2b)
2424 => (t OR partial) */
2427 if (integer_zerop (t))
2429 else if (integer_onep (t))
2430 return boolean_true_node;
2431 /* If both are the same, we can apply the identity
2433 else if (partial && same_bool_result_p (t, partial))
2437 /* Handle the AND case, where we are redistributing:
2438 (inner1 AND inner2) OR (op2a code2 op2b)
2439 => (t AND (inner1 OR (op2a code2 op2b)))
2440 => (t AND partial) */
2443 if (integer_zerop (t))
2444 return boolean_false_node;
2447 /* We already got a simplification for the other
2448 operand to the redistributed AND expression. The
2449 interesting case is when at least one is true.
2450 Or, if both are the same, we can apply the identity
2452 if (integer_onep (partial))
2454 else if (integer_onep (t))
2456 else if (same_bool_result_p (t, partial))
2465 /* Try to simplify the OR of two comparisons defined by
2466 (OP1A CODE1 OP1B) and (OP2A CODE2 OP2B), respectively.
2467 If this can be done without constructing an intermediate value,
2468 return the resulting tree; otherwise NULL_TREE is returned.
2469 This function is deliberately asymmetric as it recurses on SSA_DEFs
2470 in the first comparison but not the second. */
2473 or_comparisons_1 (enum tree_code code1, tree op1a, tree op1b,
2474 enum tree_code code2, tree op2a, tree op2b)
2476 /* First check for ((x CODE1 y) OR (x CODE2 y)). */
2477 if (operand_equal_p (op1a, op2a, 0)
2478 && operand_equal_p (op1b, op2b, 0))
2480 tree t = combine_comparisons (UNKNOWN_LOCATION,
2481 TRUTH_ORIF_EXPR, code1, code2,
2482 boolean_type_node, op1a, op1b);
2487 /* Likewise the swapped case of the above. */
2488 if (operand_equal_p (op1a, op2b, 0)
2489 && operand_equal_p (op1b, op2a, 0))
2491 tree t = combine_comparisons (UNKNOWN_LOCATION,
2492 TRUTH_ORIF_EXPR, code1,
2493 swap_tree_comparison (code2),
2494 boolean_type_node, op1a, op1b);
2499 /* If both comparisons are of the same value against constants, we might
2500 be able to merge them. */
2501 if (operand_equal_p (op1a, op2a, 0)
2502 && TREE_CODE (op1b) == INTEGER_CST
2503 && TREE_CODE (op2b) == INTEGER_CST)
2505 int cmp = tree_int_cst_compare (op1b, op2b);
2507 /* If we have (op1a != op1b), we should either be able to
2508 return that or TRUE, depending on whether the constant op1b
2509 also satisfies the other comparison against op2b. */
2510 if (code1 == NE_EXPR)
2516 case EQ_EXPR: val = (cmp == 0); break;
2517 case NE_EXPR: val = (cmp != 0); break;
2518 case LT_EXPR: val = (cmp < 0); break;
2519 case GT_EXPR: val = (cmp > 0); break;
2520 case LE_EXPR: val = (cmp <= 0); break;
2521 case GE_EXPR: val = (cmp >= 0); break;
2522 default: done = false;
2527 return boolean_true_node;
2529 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2532 /* Likewise if the second comparison is a != comparison. */
2533 else if (code2 == NE_EXPR)
2539 case EQ_EXPR: val = (cmp == 0); break;
2540 case NE_EXPR: val = (cmp != 0); break;
2541 case LT_EXPR: val = (cmp > 0); break;
2542 case GT_EXPR: val = (cmp < 0); break;
2543 case LE_EXPR: val = (cmp >= 0); break;
2544 case GE_EXPR: val = (cmp <= 0); break;
2545 default: done = false;
2550 return boolean_true_node;
2552 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2556 /* See if an equality test is redundant with the other comparison. */
2557 else if (code1 == EQ_EXPR)
2562 case EQ_EXPR: val = (cmp == 0); break;
2563 case NE_EXPR: val = (cmp != 0); break;
2564 case LT_EXPR: val = (cmp < 0); break;
2565 case GT_EXPR: val = (cmp > 0); break;
2566 case LE_EXPR: val = (cmp <= 0); break;
2567 case GE_EXPR: val = (cmp >= 0); break;
2572 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2574 else if (code2 == EQ_EXPR)
2579 case EQ_EXPR: val = (cmp == 0); break;
2580 case NE_EXPR: val = (cmp != 0); break;
2581 case LT_EXPR: val = (cmp > 0); break;
2582 case GT_EXPR: val = (cmp < 0); break;
2583 case LE_EXPR: val = (cmp >= 0); break;
2584 case GE_EXPR: val = (cmp <= 0); break;
2589 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2592 /* Chose the less restrictive of two < or <= comparisons. */
2593 else if ((code1 == LT_EXPR || code1 == LE_EXPR)
2594 && (code2 == LT_EXPR || code2 == LE_EXPR))
2596 if ((cmp < 0) || (cmp == 0 && code1 == LT_EXPR))
2597 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2599 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2602 /* Likewise chose the less restrictive of two > or >= comparisons. */
2603 else if ((code1 == GT_EXPR || code1 == GE_EXPR)
2604 && (code2 == GT_EXPR || code2 == GE_EXPR))
2606 if ((cmp > 0) || (cmp == 0 && code1 == GT_EXPR))
2607 return fold_build2 (code2, boolean_type_node, op2a, op2b);
2609 return fold_build2 (code1, boolean_type_node, op1a, op1b);
2612 /* Check for singleton ranges. */
2614 && ((code1 == LT_EXPR && code2 == GT_EXPR)
2615 || (code1 == GT_EXPR && code2 == LT_EXPR)))
2616 return fold_build2 (NE_EXPR, boolean_type_node, op1a, op2b);
2618 /* Check for less/greater pairs that don't restrict the range at all. */
2620 && (code1 == LT_EXPR || code1 == LE_EXPR)
2621 && (code2 == GT_EXPR || code2 == GE_EXPR))
2622 return boolean_true_node;
2624 && (code1 == GT_EXPR || code1 == GE_EXPR)
2625 && (code2 == LT_EXPR || code2 == LE_EXPR))
2626 return boolean_true_node;
2629 /* Perhaps the first comparison is (NAME != 0) or (NAME == 1) where
2630 NAME's definition is a truth value. See if there are any simplifications
2631 that can be done against the NAME's definition. */
2632 if (TREE_CODE (op1a) == SSA_NAME
2633 && (code1 == NE_EXPR || code1 == EQ_EXPR)
2634 && (integer_zerop (op1b) || integer_onep (op1b)))
2636 bool invert = ((code1 == EQ_EXPR && integer_zerop (op1b))
2637 || (code1 == NE_EXPR && integer_onep (op1b)));
2638 gimple stmt = SSA_NAME_DEF_STMT (op1a);
2639 switch (gimple_code (stmt))
2642 /* Try to simplify by copy-propagating the definition. */
2643 return or_var_with_comparison (op1a, invert, code2, op2a, op2b);
2646 /* If every argument to the PHI produces the same result when
2647 ORed with the second comparison, we win.
2648 Do not do this unless the type is bool since we need a bool
2649 result here anyway. */
2650 if (TREE_CODE (TREE_TYPE (op1a)) == BOOLEAN_TYPE)
2652 tree result = NULL_TREE;
2654 for (i = 0; i < gimple_phi_num_args (stmt); i++)
2656 tree arg = gimple_phi_arg_def (stmt, i);
2658 /* If this PHI has itself as an argument, ignore it.
2659 If all the other args produce the same result,
2661 if (arg == gimple_phi_result (stmt))
2663 else if (TREE_CODE (arg) == INTEGER_CST)
2665 if (invert ? integer_zerop (arg) : integer_nonzerop (arg))
2668 result = boolean_true_node;
2669 else if (!integer_onep (result))
2673 result = fold_build2 (code2, boolean_type_node,
2675 else if (!same_bool_comparison_p (result,
2679 else if (TREE_CODE (arg) == SSA_NAME
2680 && !SSA_NAME_IS_DEFAULT_DEF (arg))
2683 gimple def_stmt = SSA_NAME_DEF_STMT (arg);
2684 /* In simple cases we can look through PHI nodes,
2685 but we have to be careful with loops.
2687 if (! dom_info_available_p (CDI_DOMINATORS)
2688 || gimple_bb (def_stmt) == gimple_bb (stmt)
2689 || dominated_by_p (CDI_DOMINATORS,
2690 gimple_bb (def_stmt),
2693 temp = or_var_with_comparison (arg, invert, code2,
2699 else if (!same_bool_result_p (result, temp))
2715 /* Try to simplify the OR of two comparisons, specified by
2716 (OP1A CODE1 OP1B) and (OP2B CODE2 OP2B), respectively.
2717 If this can be simplified to a single expression (without requiring
2718 introducing more SSA variables to hold intermediate values),
2719 return the resulting tree. Otherwise return NULL_TREE.
2720 If the result expression is non-null, it has boolean type. */
2723 maybe_fold_or_comparisons (enum tree_code code1, tree op1a, tree op1b,
2724 enum tree_code code2, tree op2a, tree op2b)
2726 tree t = or_comparisons_1 (code1, op1a, op1b, code2, op2a, op2b);
2730 return or_comparisons_1 (code2, op2a, op2b, code1, op1a, op1b);