OSDN Git Service

d83f084dd0387a4a492f19b1976f2988011cab4a
[pf3gnuchains/gcc-fork.git] / gcc / fold-const.c
1 /* Fold a constant sub-tree into a single node for C-compiler
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
3    2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
4    2012 Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /*@@ This file should be rewritten to use an arbitrary precision
23   @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
24   @@ Perhaps the routines could also be used for bc/dc, and made a lib.
25   @@ The routines that translate from the ap rep should
26   @@ warn if precision et. al. is lost.
27   @@ This would also make life easier when this technology is used
28   @@ for cross-compilers.  */
29
30 /* The entry points in this file are fold, size_int_wide and size_binop.
31
32    fold takes a tree as argument and returns a simplified tree.
33
34    size_binop takes a tree code for an arithmetic operation
35    and two operands that are trees, and produces a tree for the
36    result, assuming the type comes from `sizetype'.
37
38    size_int takes an integer value, and creates a tree constant
39    with type from `sizetype'.
40
41    Note: Since the folders get called on non-gimple code as well as
42    gimple code, we need to handle GIMPLE tuples as well as their
43    corresponding tree equivalents.  */
44
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "tm.h"
49 #include "flags.h"
50 #include "tree.h"
51 #include "realmpfr.h"
52 #include "rtl.h"
53 #include "expr.h"
54 #include "tm_p.h"
55 #include "target.h"
56 #include "diagnostic-core.h"
57 #include "intl.h"
58 #include "ggc.h"
59 #include "hashtab.h"
60 #include "langhooks.h"
61 #include "md5.h"
62 #include "gimple.h"
63 #include "tree-flow.h"
64
65 /* Nonzero if we are folding constants inside an initializer; zero
66    otherwise.  */
67 int folding_initializer = 0;
68
69 /* The following constants represent a bit based encoding of GCC's
70    comparison operators.  This encoding simplifies transformations
71    on relational comparison operators, such as AND and OR.  */
72 enum comparison_code {
73   COMPCODE_FALSE = 0,
74   COMPCODE_LT = 1,
75   COMPCODE_EQ = 2,
76   COMPCODE_LE = 3,
77   COMPCODE_GT = 4,
78   COMPCODE_LTGT = 5,
79   COMPCODE_GE = 6,
80   COMPCODE_ORD = 7,
81   COMPCODE_UNORD = 8,
82   COMPCODE_UNLT = 9,
83   COMPCODE_UNEQ = 10,
84   COMPCODE_UNLE = 11,
85   COMPCODE_UNGT = 12,
86   COMPCODE_NE = 13,
87   COMPCODE_UNGE = 14,
88   COMPCODE_TRUE = 15
89 };
90
91 static bool negate_mathfn_p (enum built_in_function);
92 static bool negate_expr_p (tree);
93 static tree negate_expr (tree);
94 static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int);
95 static tree associate_trees (location_t, tree, tree, enum tree_code, tree);
96 static tree const_binop (enum tree_code, tree, tree);
97 static enum comparison_code comparison_to_compcode (enum tree_code);
98 static enum tree_code compcode_to_comparison (enum comparison_code);
99 static int operand_equal_for_comparison_p (tree, tree, tree);
100 static int twoval_comparison_p (tree, tree *, tree *, int *);
101 static tree eval_subst (location_t, tree, tree, tree, tree, tree);
102 static tree pedantic_omit_one_operand_loc (location_t, tree, tree, tree);
103 static tree distribute_bit_expr (location_t, enum tree_code, tree, tree, tree);
104 static tree make_bit_field_ref (location_t, tree, tree,
105                                 HOST_WIDE_INT, HOST_WIDE_INT, int);
106 static tree optimize_bit_field_compare (location_t, enum tree_code,
107                                         tree, tree, tree);
108 static tree decode_field_reference (location_t, tree, HOST_WIDE_INT *,
109                                     HOST_WIDE_INT *,
110                                     enum machine_mode *, int *, int *,
111                                     tree *, tree *);
112 static int all_ones_mask_p (const_tree, int);
113 static tree sign_bit_p (tree, const_tree);
114 static int simple_operand_p (const_tree);
115 static bool simple_operand_p_2 (tree);
116 static tree range_binop (enum tree_code, tree, tree, int, tree, int);
117 static tree range_predecessor (tree);
118 static tree range_successor (tree);
119 static tree fold_range_test (location_t, enum tree_code, tree, tree, tree);
120 static tree fold_cond_expr_with_comparison (location_t, tree, tree, tree, tree);
121 static tree unextend (tree, int, int, tree);
122 static tree optimize_minmax_comparison (location_t, enum tree_code,
123                                         tree, tree, tree);
124 static tree extract_muldiv (tree, tree, enum tree_code, tree, bool *);
125 static tree extract_muldiv_1 (tree, tree, enum tree_code, tree, bool *);
126 static tree fold_binary_op_with_conditional_arg (location_t,
127                                                  enum tree_code, tree,
128                                                  tree, tree,
129                                                  tree, tree, int);
130 static tree fold_mathfn_compare (location_t,
131                                  enum built_in_function, enum tree_code,
132                                  tree, tree, tree);
133 static tree fold_inf_compare (location_t, enum tree_code, tree, tree, tree);
134 static tree fold_div_compare (location_t, enum tree_code, tree, tree, tree);
135 static bool reorder_operands_p (const_tree, const_tree);
136 static tree fold_negate_const (tree, tree);
137 static tree fold_not_const (const_tree, tree);
138 static tree fold_relational_const (enum tree_code, tree, tree, tree);
139 static tree fold_convert_const (enum tree_code, tree, tree);
140
141 /* Return EXPR_LOCATION of T if it is not UNKNOWN_LOCATION.
142    Otherwise, return LOC.  */
143
144 static location_t
145 expr_location_or (tree t, location_t loc)
146 {
147   location_t tloc = EXPR_LOCATION (t);
148   return tloc != UNKNOWN_LOCATION ? tloc : loc;
149 }
150
151 /* Similar to protected_set_expr_location, but never modify x in place,
152    if location can and needs to be set, unshare it.  */
153
154 static inline tree
155 protected_set_expr_location_unshare (tree x, location_t loc)
156 {
157   if (CAN_HAVE_LOCATION_P (x)
158       && EXPR_LOCATION (x) != loc
159       && !(TREE_CODE (x) == SAVE_EXPR
160            || TREE_CODE (x) == TARGET_EXPR
161            || TREE_CODE (x) == BIND_EXPR))
162     {
163       x = copy_node (x);
164       SET_EXPR_LOCATION (x, loc);
165     }
166   return x;
167 }
168
169
170 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
171    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
172    and SUM1.  Then this yields nonzero if overflow occurred during the
173    addition.
174
175    Overflow occurs if A and B have the same sign, but A and SUM differ in
176    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
177    sign.  */
178 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
179 \f
180 /* If ARG2 divides ARG1 with zero remainder, carries out the division
181    of type CODE and returns the quotient.
182    Otherwise returns NULL_TREE.  */
183
184 tree
185 div_if_zero_remainder (enum tree_code code, const_tree arg1, const_tree arg2)
186 {
187   double_int quo, rem;
188   int uns;
189
190   /* The sign of the division is according to operand two, that
191      does the correct thing for POINTER_PLUS_EXPR where we want
192      a signed division.  */
193   uns = TYPE_UNSIGNED (TREE_TYPE (arg2));
194   if (TREE_CODE (TREE_TYPE (arg2)) == INTEGER_TYPE
195       && TYPE_IS_SIZETYPE (TREE_TYPE (arg2)))
196     uns = false;
197
198   quo = double_int_divmod (tree_to_double_int (arg1),
199                            tree_to_double_int (arg2),
200                            uns, code, &rem);
201
202   if (double_int_zero_p (rem))
203     return build_int_cst_wide (TREE_TYPE (arg1), quo.low, quo.high);
204
205   return NULL_TREE; 
206 }
207 \f
208 /* This is nonzero if we should defer warnings about undefined
209    overflow.  This facility exists because these warnings are a
210    special case.  The code to estimate loop iterations does not want
211    to issue any warnings, since it works with expressions which do not
212    occur in user code.  Various bits of cleanup code call fold(), but
213    only use the result if it has certain characteristics (e.g., is a
214    constant); that code only wants to issue a warning if the result is
215    used.  */
216
217 static int fold_deferring_overflow_warnings;
218
219 /* If a warning about undefined overflow is deferred, this is the
220    warning.  Note that this may cause us to turn two warnings into
221    one, but that is fine since it is sufficient to only give one
222    warning per expression.  */
223
224 static const char* fold_deferred_overflow_warning;
225
226 /* If a warning about undefined overflow is deferred, this is the
227    level at which the warning should be emitted.  */
228
229 static enum warn_strict_overflow_code fold_deferred_overflow_code;
230
231 /* Start deferring overflow warnings.  We could use a stack here to
232    permit nested calls, but at present it is not necessary.  */
233
234 void
235 fold_defer_overflow_warnings (void)
236 {
237   ++fold_deferring_overflow_warnings;
238 }
239
240 /* Stop deferring overflow warnings.  If there is a pending warning,
241    and ISSUE is true, then issue the warning if appropriate.  STMT is
242    the statement with which the warning should be associated (used for
243    location information); STMT may be NULL.  CODE is the level of the
244    warning--a warn_strict_overflow_code value.  This function will use
245    the smaller of CODE and the deferred code when deciding whether to
246    issue the warning.  CODE may be zero to mean to always use the
247    deferred code.  */
248
249 void
250 fold_undefer_overflow_warnings (bool issue, const_gimple stmt, int code)
251 {
252   const char *warnmsg;
253   location_t locus;
254
255   gcc_assert (fold_deferring_overflow_warnings > 0);
256   --fold_deferring_overflow_warnings;
257   if (fold_deferring_overflow_warnings > 0)
258     {
259       if (fold_deferred_overflow_warning != NULL
260           && code != 0
261           && code < (int) fold_deferred_overflow_code)
262         fold_deferred_overflow_code = (enum warn_strict_overflow_code) code;
263       return;
264     }
265
266   warnmsg = fold_deferred_overflow_warning;
267   fold_deferred_overflow_warning = NULL;
268
269   if (!issue || warnmsg == NULL)
270     return;
271
272   if (gimple_no_warning_p (stmt))
273     return;
274
275   /* Use the smallest code level when deciding to issue the
276      warning.  */
277   if (code == 0 || code > (int) fold_deferred_overflow_code)
278     code = fold_deferred_overflow_code;
279
280   if (!issue_strict_overflow_warning (code))
281     return;
282
283   if (stmt == NULL)
284     locus = input_location;
285   else
286     locus = gimple_location (stmt);
287   warning_at (locus, OPT_Wstrict_overflow, "%s", warnmsg);
288 }
289
290 /* Stop deferring overflow warnings, ignoring any deferred
291    warnings.  */
292
293 void
294 fold_undefer_and_ignore_overflow_warnings (void)
295 {
296   fold_undefer_overflow_warnings (false, NULL, 0);
297 }
298
299 /* Whether we are deferring overflow warnings.  */
300
301 bool
302 fold_deferring_overflow_warnings_p (void)
303 {
304   return fold_deferring_overflow_warnings > 0;
305 }
306
307 /* This is called when we fold something based on the fact that signed
308    overflow is undefined.  */
309
310 static void
311 fold_overflow_warning (const char* gmsgid, enum warn_strict_overflow_code wc)
312 {
313   if (fold_deferring_overflow_warnings > 0)
314     {
315       if (fold_deferred_overflow_warning == NULL
316           || wc < fold_deferred_overflow_code)
317         {
318           fold_deferred_overflow_warning = gmsgid;
319           fold_deferred_overflow_code = wc;
320         }
321     }
322   else if (issue_strict_overflow_warning (wc))
323     warning (OPT_Wstrict_overflow, gmsgid);
324 }
325 \f
326 /* Return true if the built-in mathematical function specified by CODE
327    is odd, i.e. -f(x) == f(-x).  */
328
329 static bool
330 negate_mathfn_p (enum built_in_function code)
331 {
332   switch (code)
333     {
334     CASE_FLT_FN (BUILT_IN_ASIN):
335     CASE_FLT_FN (BUILT_IN_ASINH):
336     CASE_FLT_FN (BUILT_IN_ATAN):
337     CASE_FLT_FN (BUILT_IN_ATANH):
338     CASE_FLT_FN (BUILT_IN_CASIN):
339     CASE_FLT_FN (BUILT_IN_CASINH):
340     CASE_FLT_FN (BUILT_IN_CATAN):
341     CASE_FLT_FN (BUILT_IN_CATANH):
342     CASE_FLT_FN (BUILT_IN_CBRT):
343     CASE_FLT_FN (BUILT_IN_CPROJ):
344     CASE_FLT_FN (BUILT_IN_CSIN):
345     CASE_FLT_FN (BUILT_IN_CSINH):
346     CASE_FLT_FN (BUILT_IN_CTAN):
347     CASE_FLT_FN (BUILT_IN_CTANH):
348     CASE_FLT_FN (BUILT_IN_ERF):
349     CASE_FLT_FN (BUILT_IN_LLROUND):
350     CASE_FLT_FN (BUILT_IN_LROUND):
351     CASE_FLT_FN (BUILT_IN_ROUND):
352     CASE_FLT_FN (BUILT_IN_SIN):
353     CASE_FLT_FN (BUILT_IN_SINH):
354     CASE_FLT_FN (BUILT_IN_TAN):
355     CASE_FLT_FN (BUILT_IN_TANH):
356     CASE_FLT_FN (BUILT_IN_TRUNC):
357       return true;
358
359     CASE_FLT_FN (BUILT_IN_LLRINT):
360     CASE_FLT_FN (BUILT_IN_LRINT):
361     CASE_FLT_FN (BUILT_IN_NEARBYINT):
362     CASE_FLT_FN (BUILT_IN_RINT):
363       return !flag_rounding_math;
364
365     default:
366       break;
367     }
368   return false;
369 }
370
371 /* Check whether we may negate an integer constant T without causing
372    overflow.  */
373
374 bool
375 may_negate_without_overflow_p (const_tree t)
376 {
377   unsigned HOST_WIDE_INT val;
378   unsigned int prec;
379   tree type;
380
381   gcc_assert (TREE_CODE (t) == INTEGER_CST);
382
383   type = TREE_TYPE (t);
384   if (TYPE_UNSIGNED (type))
385     return false;
386
387   prec = TYPE_PRECISION (type);
388   if (prec > HOST_BITS_PER_WIDE_INT)
389     {
390       if (TREE_INT_CST_LOW (t) != 0)
391         return true;
392       prec -= HOST_BITS_PER_WIDE_INT;
393       val = TREE_INT_CST_HIGH (t);
394     }
395   else
396     val = TREE_INT_CST_LOW (t);
397   if (prec < HOST_BITS_PER_WIDE_INT)
398     val &= ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
399   return val != ((unsigned HOST_WIDE_INT) 1 << (prec - 1));
400 }
401
402 /* Determine whether an expression T can be cheaply negated using
403    the function negate_expr without introducing undefined overflow.  */
404
405 static bool
406 negate_expr_p (tree t)
407 {
408   tree type;
409
410   if (t == 0)
411     return false;
412
413   type = TREE_TYPE (t);
414
415   STRIP_SIGN_NOPS (t);
416   switch (TREE_CODE (t))
417     {
418     case INTEGER_CST:
419       if (TYPE_OVERFLOW_WRAPS (type))
420         return true;
421
422       /* Check that -CST will not overflow type.  */
423       return may_negate_without_overflow_p (t);
424     case BIT_NOT_EXPR:
425       return (INTEGRAL_TYPE_P (type)
426               && TYPE_OVERFLOW_WRAPS (type));
427
428     case FIXED_CST:
429     case NEGATE_EXPR:
430       return true;
431
432     case REAL_CST:
433       /* We want to canonicalize to positive real constants.  Pretend
434          that only negative ones can be easily negated.  */
435       return REAL_VALUE_NEGATIVE (TREE_REAL_CST (t));
436
437     case COMPLEX_CST:
438       return negate_expr_p (TREE_REALPART (t))
439              && negate_expr_p (TREE_IMAGPART (t));
440
441     case COMPLEX_EXPR:
442       return negate_expr_p (TREE_OPERAND (t, 0))
443              && negate_expr_p (TREE_OPERAND (t, 1));
444
445     case CONJ_EXPR:
446       return negate_expr_p (TREE_OPERAND (t, 0));
447
448     case PLUS_EXPR:
449       if (HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
450           || HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
451         return false;
452       /* -(A + B) -> (-B) - A.  */
453       if (negate_expr_p (TREE_OPERAND (t, 1))
454           && reorder_operands_p (TREE_OPERAND (t, 0),
455                                  TREE_OPERAND (t, 1)))
456         return true;
457       /* -(A + B) -> (-A) - B.  */
458       return negate_expr_p (TREE_OPERAND (t, 0));
459
460     case MINUS_EXPR:
461       /* We can't turn -(A-B) into B-A when we honor signed zeros.  */
462       return !HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
463              && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
464              && reorder_operands_p (TREE_OPERAND (t, 0),
465                                     TREE_OPERAND (t, 1));
466
467     case MULT_EXPR:
468       if (TYPE_UNSIGNED (TREE_TYPE (t)))
469         break;
470
471       /* Fall through.  */
472
473     case RDIV_EXPR:
474       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (TREE_TYPE (t))))
475         return negate_expr_p (TREE_OPERAND (t, 1))
476                || negate_expr_p (TREE_OPERAND (t, 0));
477       break;
478
479     case TRUNC_DIV_EXPR:
480     case ROUND_DIV_EXPR:
481     case FLOOR_DIV_EXPR:
482     case CEIL_DIV_EXPR:
483     case EXACT_DIV_EXPR:
484       /* In general we can't negate A / B, because if A is INT_MIN and
485          B is 1, we may turn this into INT_MIN / -1 which is undefined
486          and actually traps on some architectures.  But if overflow is
487          undefined, we can negate, because - (INT_MIN / 1) is an
488          overflow.  */
489       if (INTEGRAL_TYPE_P (TREE_TYPE (t)))
490         {
491           if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (t)))
492             break;
493           /* If overflow is undefined then we have to be careful because
494              we ask whether it's ok to associate the negate with the
495              division which is not ok for example for
496              -((a - b) / c) where (-(a - b)) / c may invoke undefined
497              overflow because of negating INT_MIN.  So do not use
498              negate_expr_p here but open-code the two important cases.  */
499           if (TREE_CODE (TREE_OPERAND (t, 0)) == NEGATE_EXPR
500               || (TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
501                   && may_negate_without_overflow_p (TREE_OPERAND (t, 0))))
502             return true;
503         }
504       else if (negate_expr_p (TREE_OPERAND (t, 0)))
505         return true;
506       return negate_expr_p (TREE_OPERAND (t, 1));
507
508     case NOP_EXPR:
509       /* Negate -((double)float) as (double)(-float).  */
510       if (TREE_CODE (type) == REAL_TYPE)
511         {
512           tree tem = strip_float_extensions (t);
513           if (tem != t)
514             return negate_expr_p (tem);
515         }
516       break;
517
518     case CALL_EXPR:
519       /* Negate -f(x) as f(-x).  */
520       if (negate_mathfn_p (builtin_mathfn_code (t)))
521         return negate_expr_p (CALL_EXPR_ARG (t, 0));
522       break;
523
524     case RSHIFT_EXPR:
525       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
526       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
527         {
528           tree op1 = TREE_OPERAND (t, 1);
529           if (TREE_INT_CST_HIGH (op1) == 0
530               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
531                  == TREE_INT_CST_LOW (op1))
532             return true;
533         }
534       break;
535
536     default:
537       break;
538     }
539   return false;
540 }
541
542 /* Given T, an expression, return a folded tree for -T or NULL_TREE, if no
543    simplification is possible.
544    If negate_expr_p would return true for T, NULL_TREE will never be
545    returned.  */
546
547 static tree
548 fold_negate_expr (location_t loc, tree t)
549 {
550   tree type = TREE_TYPE (t);
551   tree tem;
552
553   switch (TREE_CODE (t))
554     {
555     /* Convert - (~A) to A + 1.  */
556     case BIT_NOT_EXPR:
557       if (INTEGRAL_TYPE_P (type))
558         return fold_build2_loc (loc, PLUS_EXPR, type, TREE_OPERAND (t, 0),
559                             build_int_cst (type, 1));
560       break;
561
562     case INTEGER_CST:
563       tem = fold_negate_const (t, type);
564       if (TREE_OVERFLOW (tem) == TREE_OVERFLOW (t)
565           || !TYPE_OVERFLOW_TRAPS (type))
566         return tem;
567       break;
568
569     case REAL_CST:
570       tem = fold_negate_const (t, type);
571       /* Two's complement FP formats, such as c4x, may overflow.  */
572       if (!TREE_OVERFLOW (tem) || !flag_trapping_math)
573         return tem;
574       break;
575
576     case FIXED_CST:
577       tem = fold_negate_const (t, type);
578       return tem;
579
580     case COMPLEX_CST:
581       {
582         tree rpart = negate_expr (TREE_REALPART (t));
583         tree ipart = negate_expr (TREE_IMAGPART (t));
584
585         if ((TREE_CODE (rpart) == REAL_CST
586              && TREE_CODE (ipart) == REAL_CST)
587             || (TREE_CODE (rpart) == INTEGER_CST
588                 && TREE_CODE (ipart) == INTEGER_CST))
589           return build_complex (type, rpart, ipart);
590       }
591       break;
592
593     case COMPLEX_EXPR:
594       if (negate_expr_p (t))
595         return fold_build2_loc (loc, COMPLEX_EXPR, type,
596                             fold_negate_expr (loc, TREE_OPERAND (t, 0)),
597                             fold_negate_expr (loc, TREE_OPERAND (t, 1)));
598       break;
599
600     case CONJ_EXPR:
601       if (negate_expr_p (t))
602         return fold_build1_loc (loc, CONJ_EXPR, type,
603                             fold_negate_expr (loc, TREE_OPERAND (t, 0)));
604       break;
605
606     case NEGATE_EXPR:
607       return TREE_OPERAND (t, 0);
608
609     case PLUS_EXPR:
610       if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
611           && !HONOR_SIGNED_ZEROS (TYPE_MODE (type)))
612         {
613           /* -(A + B) -> (-B) - A.  */
614           if (negate_expr_p (TREE_OPERAND (t, 1))
615               && reorder_operands_p (TREE_OPERAND (t, 0),
616                                      TREE_OPERAND (t, 1)))
617             {
618               tem = negate_expr (TREE_OPERAND (t, 1));
619               return fold_build2_loc (loc, MINUS_EXPR, type,
620                                   tem, TREE_OPERAND (t, 0));
621             }
622
623           /* -(A + B) -> (-A) - B.  */
624           if (negate_expr_p (TREE_OPERAND (t, 0)))
625             {
626               tem = negate_expr (TREE_OPERAND (t, 0));
627               return fold_build2_loc (loc, MINUS_EXPR, type,
628                                   tem, TREE_OPERAND (t, 1));
629             }
630         }
631       break;
632
633     case MINUS_EXPR:
634       /* - (A - B) -> B - A  */
635       if (!HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type))
636           && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
637           && reorder_operands_p (TREE_OPERAND (t, 0), TREE_OPERAND (t, 1)))
638         return fold_build2_loc (loc, MINUS_EXPR, type,
639                             TREE_OPERAND (t, 1), TREE_OPERAND (t, 0));
640       break;
641
642     case MULT_EXPR:
643       if (TYPE_UNSIGNED (type))
644         break;
645
646       /* Fall through.  */
647
648     case RDIV_EXPR:
649       if (! HONOR_SIGN_DEPENDENT_ROUNDING (TYPE_MODE (type)))
650         {
651           tem = TREE_OPERAND (t, 1);
652           if (negate_expr_p (tem))
653             return fold_build2_loc (loc, TREE_CODE (t), type,
654                                 TREE_OPERAND (t, 0), negate_expr (tem));
655           tem = TREE_OPERAND (t, 0);
656           if (negate_expr_p (tem))
657             return fold_build2_loc (loc, TREE_CODE (t), type,
658                                 negate_expr (tem), TREE_OPERAND (t, 1));
659         }
660       break;
661
662     case TRUNC_DIV_EXPR:
663     case ROUND_DIV_EXPR:
664     case FLOOR_DIV_EXPR:
665     case CEIL_DIV_EXPR:
666     case EXACT_DIV_EXPR:
667       /* In general we can't negate A / B, because if A is INT_MIN and
668          B is 1, we may turn this into INT_MIN / -1 which is undefined
669          and actually traps on some architectures.  But if overflow is
670          undefined, we can negate, because - (INT_MIN / 1) is an
671          overflow.  */
672       if (!INTEGRAL_TYPE_P (type) || TYPE_OVERFLOW_UNDEFINED (type))
673         {
674           const char * const warnmsg = G_("assuming signed overflow does not "
675                                           "occur when negating a division");
676           tem = TREE_OPERAND (t, 1);
677           if (negate_expr_p (tem))
678             {
679               if (INTEGRAL_TYPE_P (type)
680                   && (TREE_CODE (tem) != INTEGER_CST
681                       || integer_onep (tem)))
682                 fold_overflow_warning (warnmsg, WARN_STRICT_OVERFLOW_MISC);
683               return fold_build2_loc (loc, TREE_CODE (t), type,
684                                   TREE_OPERAND (t, 0), negate_expr (tem));
685             }
686           /* If overflow is undefined then we have to be careful because
687              we ask whether it's ok to associate the negate with the
688              division which is not ok for example for
689              -((a - b) / c) where (-(a - b)) / c may invoke undefined
690              overflow because of negating INT_MIN.  So do not use
691              negate_expr_p here but open-code the two important cases.  */
692           tem = TREE_OPERAND (t, 0);
693           if ((INTEGRAL_TYPE_P (type)
694                && (TREE_CODE (tem) == NEGATE_EXPR
695                    || (TREE_CODE (tem) == INTEGER_CST
696                        && may_negate_without_overflow_p (tem))))
697               || !INTEGRAL_TYPE_P (type))
698             return fold_build2_loc (loc, TREE_CODE (t), type,
699                                     negate_expr (tem), TREE_OPERAND (t, 1));
700         }
701       break;
702
703     case NOP_EXPR:
704       /* Convert -((double)float) into (double)(-float).  */
705       if (TREE_CODE (type) == REAL_TYPE)
706         {
707           tem = strip_float_extensions (t);
708           if (tem != t && negate_expr_p (tem))
709             return fold_convert_loc (loc, type, negate_expr (tem));
710         }
711       break;
712
713     case CALL_EXPR:
714       /* Negate -f(x) as f(-x).  */
715       if (negate_mathfn_p (builtin_mathfn_code (t))
716           && negate_expr_p (CALL_EXPR_ARG (t, 0)))
717         {
718           tree fndecl, arg;
719
720           fndecl = get_callee_fndecl (t);
721           arg = negate_expr (CALL_EXPR_ARG (t, 0));
722           return build_call_expr_loc (loc, fndecl, 1, arg);
723         }
724       break;
725
726     case RSHIFT_EXPR:
727       /* Optimize -((int)x >> 31) into (unsigned)x >> 31.  */
728       if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST)
729         {
730           tree op1 = TREE_OPERAND (t, 1);
731           if (TREE_INT_CST_HIGH (op1) == 0
732               && (unsigned HOST_WIDE_INT) (TYPE_PRECISION (type) - 1)
733                  == TREE_INT_CST_LOW (op1))
734             {
735               tree ntype = TYPE_UNSIGNED (type)
736                            ? signed_type_for (type)
737                            : unsigned_type_for (type);
738               tree temp = fold_convert_loc (loc, ntype, TREE_OPERAND (t, 0));
739               temp = fold_build2_loc (loc, RSHIFT_EXPR, ntype, temp, op1);
740               return fold_convert_loc (loc, type, temp);
741             }
742         }
743       break;
744
745     default:
746       break;
747     }
748
749   return NULL_TREE;
750 }
751
752 /* Like fold_negate_expr, but return a NEGATE_EXPR tree, if T can not be
753    negated in a simpler way.  Also allow for T to be NULL_TREE, in which case
754    return NULL_TREE. */
755
756 static tree
757 negate_expr (tree t)
758 {
759   tree type, tem;
760   location_t loc;
761
762   if (t == NULL_TREE)
763     return NULL_TREE;
764
765   loc = EXPR_LOCATION (t);
766   type = TREE_TYPE (t);
767   STRIP_SIGN_NOPS (t);
768
769   tem = fold_negate_expr (loc, t);
770   if (!tem)
771     tem = build1_loc (loc, NEGATE_EXPR, TREE_TYPE (t), t);
772   return fold_convert_loc (loc, type, tem);
773 }
774 \f
775 /* Split a tree IN into a constant, literal and variable parts that could be
776    combined with CODE to make IN.  "constant" means an expression with
777    TREE_CONSTANT but that isn't an actual constant.  CODE must be a
778    commutative arithmetic operation.  Store the constant part into *CONP,
779    the literal in *LITP and return the variable part.  If a part isn't
780    present, set it to null.  If the tree does not decompose in this way,
781    return the entire tree as the variable part and the other parts as null.
782
783    If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.  In that
784    case, we negate an operand that was subtracted.  Except if it is a
785    literal for which we use *MINUS_LITP instead.
786
787    If NEGATE_P is true, we are negating all of IN, again except a literal
788    for which we use *MINUS_LITP instead.
789
790    If IN is itself a literal or constant, return it as appropriate.
791
792    Note that we do not guarantee that any of the three values will be the
793    same type as IN, but they will have the same signedness and mode.  */
794
795 static tree
796 split_tree (tree in, enum tree_code code, tree *conp, tree *litp,
797             tree *minus_litp, int negate_p)
798 {
799   tree var = 0;
800
801   *conp = 0;
802   *litp = 0;
803   *minus_litp = 0;
804
805   /* Strip any conversions that don't change the machine mode or signedness.  */
806   STRIP_SIGN_NOPS (in);
807
808   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST
809       || TREE_CODE (in) == FIXED_CST)
810     *litp = in;
811   else if (TREE_CODE (in) == code
812            || ((! FLOAT_TYPE_P (TREE_TYPE (in)) || flag_associative_math)
813                && ! SAT_FIXED_POINT_TYPE_P (TREE_TYPE (in))
814                /* We can associate addition and subtraction together (even
815                   though the C standard doesn't say so) for integers because
816                   the value is not affected.  For reals, the value might be
817                   affected, so we can't.  */
818                && ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
819                    || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
820     {
821       tree op0 = TREE_OPERAND (in, 0);
822       tree op1 = TREE_OPERAND (in, 1);
823       int neg1_p = TREE_CODE (in) == MINUS_EXPR;
824       int neg_litp_p = 0, neg_conp_p = 0, neg_var_p = 0;
825
826       /* First see if either of the operands is a literal, then a constant.  */
827       if (TREE_CODE (op0) == INTEGER_CST || TREE_CODE (op0) == REAL_CST
828           || TREE_CODE (op0) == FIXED_CST)
829         *litp = op0, op0 = 0;
830       else if (TREE_CODE (op1) == INTEGER_CST || TREE_CODE (op1) == REAL_CST
831                || TREE_CODE (op1) == FIXED_CST)
832         *litp = op1, neg_litp_p = neg1_p, op1 = 0;
833
834       if (op0 != 0 && TREE_CONSTANT (op0))
835         *conp = op0, op0 = 0;
836       else if (op1 != 0 && TREE_CONSTANT (op1))
837         *conp = op1, neg_conp_p = neg1_p, op1 = 0;
838
839       /* If we haven't dealt with either operand, this is not a case we can
840          decompose.  Otherwise, VAR is either of the ones remaining, if any.  */
841       if (op0 != 0 && op1 != 0)
842         var = in;
843       else if (op0 != 0)
844         var = op0;
845       else
846         var = op1, neg_var_p = neg1_p;
847
848       /* Now do any needed negations.  */
849       if (neg_litp_p)
850         *minus_litp = *litp, *litp = 0;
851       if (neg_conp_p)
852         *conp = negate_expr (*conp);
853       if (neg_var_p)
854         var = negate_expr (var);
855     }
856   else if (TREE_CONSTANT (in))
857     *conp = in;
858   else
859     var = in;
860
861   if (negate_p)
862     {
863       if (*litp)
864         *minus_litp = *litp, *litp = 0;
865       else if (*minus_litp)
866         *litp = *minus_litp, *minus_litp = 0;
867       *conp = negate_expr (*conp);
868       var = negate_expr (var);
869     }
870
871   return var;
872 }
873
874 /* Re-associate trees split by the above function.  T1 and T2 are
875    either expressions to associate or null.  Return the new
876    expression, if any.  LOC is the location of the new expression.  If
877    we build an operation, do it in TYPE and with CODE.  */
878
879 static tree
880 associate_trees (location_t loc, tree t1, tree t2, enum tree_code code, tree type)
881 {
882   if (t1 == 0)
883     return t2;
884   else if (t2 == 0)
885     return t1;
886
887   /* If either input is CODE, a PLUS_EXPR, or a MINUS_EXPR, don't
888      try to fold this since we will have infinite recursion.  But do
889      deal with any NEGATE_EXPRs.  */
890   if (TREE_CODE (t1) == code || TREE_CODE (t2) == code
891       || TREE_CODE (t1) == MINUS_EXPR || TREE_CODE (t2) == MINUS_EXPR)
892     {
893       if (code == PLUS_EXPR)
894         {
895           if (TREE_CODE (t1) == NEGATE_EXPR)
896             return build2_loc (loc, MINUS_EXPR, type,
897                                fold_convert_loc (loc, type, t2),
898                                fold_convert_loc (loc, type,
899                                                  TREE_OPERAND (t1, 0)));
900           else if (TREE_CODE (t2) == NEGATE_EXPR)
901             return build2_loc (loc, MINUS_EXPR, type,
902                                fold_convert_loc (loc, type, t1),
903                                fold_convert_loc (loc, type,
904                                                  TREE_OPERAND (t2, 0)));
905           else if (integer_zerop (t2))
906             return fold_convert_loc (loc, type, t1);
907         }
908       else if (code == MINUS_EXPR)
909         {
910           if (integer_zerop (t2))
911             return fold_convert_loc (loc, type, t1);
912         }
913
914       return build2_loc (loc, code, type, fold_convert_loc (loc, type, t1),
915                          fold_convert_loc (loc, type, t2));
916     }
917
918   return fold_build2_loc (loc, code, type, fold_convert_loc (loc, type, t1),
919                           fold_convert_loc (loc, type, t2));
920 }
921 \f
922 /* Check whether TYPE1 and TYPE2 are equivalent integer types, suitable
923    for use in int_const_binop, size_binop and size_diffop.  */
924
925 static bool
926 int_binop_types_match_p (enum tree_code code, const_tree type1, const_tree type2)
927 {
928   if (TREE_CODE (type1) != INTEGER_TYPE && !POINTER_TYPE_P (type1))
929     return false;
930   if (TREE_CODE (type2) != INTEGER_TYPE && !POINTER_TYPE_P (type2))
931     return false;
932
933   switch (code)
934     {
935     case LSHIFT_EXPR:
936     case RSHIFT_EXPR:
937     case LROTATE_EXPR:
938     case RROTATE_EXPR:
939       return true;
940
941     default:
942       break;
943     }
944
945   return TYPE_UNSIGNED (type1) == TYPE_UNSIGNED (type2)
946          && TYPE_PRECISION (type1) == TYPE_PRECISION (type2)
947          && TYPE_MODE (type1) == TYPE_MODE (type2);
948 }
949
950
951 /* Combine two integer constants ARG1 and ARG2 under operation CODE
952    to produce a new constant.  Return NULL_TREE if we don't know how
953    to evaluate CODE at compile-time.  */
954
955 tree
956 int_const_binop (enum tree_code code, const_tree arg1, const_tree arg2)
957 {
958   double_int op1, op2, res, tmp;
959   tree t;
960   tree type = TREE_TYPE (arg1);
961   bool uns = TYPE_UNSIGNED (type);
962   bool is_sizetype
963     = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
964   bool overflow = false;
965
966   op1 = tree_to_double_int (arg1);
967   op2 = tree_to_double_int (arg2);
968
969   switch (code)
970     {
971     case BIT_IOR_EXPR:
972       res = double_int_ior (op1, op2);
973       break;
974
975     case BIT_XOR_EXPR:
976       res = double_int_xor (op1, op2);
977       break;
978
979     case BIT_AND_EXPR:
980       res = double_int_and (op1, op2);
981       break;
982
983     case RSHIFT_EXPR:
984       res = double_int_rshift (op1, double_int_to_shwi (op2),
985                                TYPE_PRECISION (type), !uns);
986       break;
987
988     case LSHIFT_EXPR:
989       /* It's unclear from the C standard whether shifts can overflow.
990          The following code ignores overflow; perhaps a C standard
991          interpretation ruling is needed.  */
992       res = double_int_lshift (op1, double_int_to_shwi (op2),
993                                TYPE_PRECISION (type), !uns);
994       break;
995
996     case RROTATE_EXPR:
997       res = double_int_rrotate (op1, double_int_to_shwi (op2),
998                                 TYPE_PRECISION (type));
999       break;
1000
1001     case LROTATE_EXPR:
1002       res = double_int_lrotate (op1, double_int_to_shwi (op2),
1003                                 TYPE_PRECISION (type));
1004       break;
1005
1006     case PLUS_EXPR:
1007       overflow = add_double (op1.low, op1.high, op2.low, op2.high,
1008                              &res.low, &res.high);
1009       break;
1010
1011     case MINUS_EXPR:
1012       neg_double (op2.low, op2.high, &res.low, &res.high);
1013       add_double (op1.low, op1.high, res.low, res.high,
1014                   &res.low, &res.high);
1015       overflow = OVERFLOW_SUM_SIGN (res.high, op2.high, op1.high);
1016       break;
1017
1018     case MULT_EXPR:
1019       overflow = mul_double (op1.low, op1.high, op2.low, op2.high,
1020                              &res.low, &res.high);
1021       break;
1022
1023     case TRUNC_DIV_EXPR:
1024     case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
1025     case EXACT_DIV_EXPR:
1026       /* This is a shortcut for a common special case.  */
1027       if (op2.high == 0 && (HOST_WIDE_INT) op2.low > 0
1028           && !TREE_OVERFLOW (arg1)
1029           && !TREE_OVERFLOW (arg2)
1030           && op1.high == 0 && (HOST_WIDE_INT) op1.low >= 0)
1031         {
1032           if (code == CEIL_DIV_EXPR)
1033             op1.low += op2.low - 1;
1034
1035           res.low = op1.low / op2.low, res.high = 0;
1036           break;
1037         }
1038
1039       /* ... fall through ...  */
1040
1041     case ROUND_DIV_EXPR:
1042       if (double_int_zero_p (op2))
1043         return NULL_TREE;
1044       if (double_int_one_p (op2))
1045         {
1046           res = op1;
1047           break;
1048         }
1049       if (double_int_equal_p (op1, op2)
1050           && ! double_int_zero_p (op1))
1051         {
1052           res = double_int_one;
1053           break;
1054         }
1055       overflow = div_and_round_double (code, uns,
1056                                        op1.low, op1.high, op2.low, op2.high,
1057                                        &res.low, &res.high,
1058                                        &tmp.low, &tmp.high);
1059       break;
1060
1061     case TRUNC_MOD_EXPR:
1062     case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
1063       /* This is a shortcut for a common special case.  */
1064       if (op2.high == 0 && (HOST_WIDE_INT) op2.low > 0
1065           && !TREE_OVERFLOW (arg1)
1066           && !TREE_OVERFLOW (arg2)
1067           && op1.high == 0 && (HOST_WIDE_INT) op1.low >= 0)
1068         {
1069           if (code == CEIL_MOD_EXPR)
1070             op1.low += op2.low - 1;
1071           res.low = op1.low % op2.low, res.high = 0;
1072           break;
1073         }
1074
1075       /* ... fall through ...  */
1076
1077     case ROUND_MOD_EXPR:
1078       if (double_int_zero_p (op2))
1079         return NULL_TREE;
1080       overflow = div_and_round_double (code, uns,
1081                                        op1.low, op1.high, op2.low, op2.high,
1082                                        &tmp.low, &tmp.high,
1083                                        &res.low, &res.high);
1084       break;
1085
1086     case MIN_EXPR:
1087       res = double_int_min (op1, op2, uns);
1088       break;
1089
1090     case MAX_EXPR:
1091       res = double_int_max (op1, op2, uns);
1092       break;
1093
1094     default:
1095       return NULL_TREE;
1096     }
1097
1098   t = force_fit_type_double (TREE_TYPE (arg1), res, 1,
1099                              ((!uns || is_sizetype) && overflow)
1100                              | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2));
1101
1102   return t;
1103 }
1104
1105 /* Combine two constants ARG1 and ARG2 under operation CODE to produce a new
1106    constant.  We assume ARG1 and ARG2 have the same data type, or at least
1107    are the same kind of constant and the same machine mode.  Return zero if
1108    combining the constants is not allowed in the current operating mode.  */
1109
1110 static tree
1111 const_binop (enum tree_code code, tree arg1, tree arg2)
1112 {
1113   /* Sanity check for the recursive cases.  */
1114   if (!arg1 || !arg2)
1115     return NULL_TREE;
1116
1117   STRIP_NOPS (arg1);
1118   STRIP_NOPS (arg2);
1119
1120   if (TREE_CODE (arg1) == INTEGER_CST)
1121     return int_const_binop (code, arg1, arg2);
1122
1123   if (TREE_CODE (arg1) == REAL_CST)
1124     {
1125       enum machine_mode mode;
1126       REAL_VALUE_TYPE d1;
1127       REAL_VALUE_TYPE d2;
1128       REAL_VALUE_TYPE value;
1129       REAL_VALUE_TYPE result;
1130       bool inexact;
1131       tree t, type;
1132
1133       /* The following codes are handled by real_arithmetic.  */
1134       switch (code)
1135         {
1136         case PLUS_EXPR:
1137         case MINUS_EXPR:
1138         case MULT_EXPR:
1139         case RDIV_EXPR:
1140         case MIN_EXPR:
1141         case MAX_EXPR:
1142           break;
1143
1144         default:
1145           return NULL_TREE;
1146         }
1147
1148       d1 = TREE_REAL_CST (arg1);
1149       d2 = TREE_REAL_CST (arg2);
1150
1151       type = TREE_TYPE (arg1);
1152       mode = TYPE_MODE (type);
1153
1154       /* Don't perform operation if we honor signaling NaNs and
1155          either operand is a NaN.  */
1156       if (HONOR_SNANS (mode)
1157           && (REAL_VALUE_ISNAN (d1) || REAL_VALUE_ISNAN (d2)))
1158         return NULL_TREE;
1159
1160       /* Don't perform operation if it would raise a division
1161          by zero exception.  */
1162       if (code == RDIV_EXPR
1163           && REAL_VALUES_EQUAL (d2, dconst0)
1164           && (flag_trapping_math || ! MODE_HAS_INFINITIES (mode)))
1165         return NULL_TREE;
1166
1167       /* If either operand is a NaN, just return it.  Otherwise, set up
1168          for floating-point trap; we return an overflow.  */
1169       if (REAL_VALUE_ISNAN (d1))
1170         return arg1;
1171       else if (REAL_VALUE_ISNAN (d2))
1172         return arg2;
1173
1174       inexact = real_arithmetic (&value, code, &d1, &d2);
1175       real_convert (&result, mode, &value);
1176
1177       /* Don't constant fold this floating point operation if
1178          the result has overflowed and flag_trapping_math.  */
1179       if (flag_trapping_math
1180           && MODE_HAS_INFINITIES (mode)
1181           && REAL_VALUE_ISINF (result)
1182           && !REAL_VALUE_ISINF (d1)
1183           && !REAL_VALUE_ISINF (d2))
1184         return NULL_TREE;
1185
1186       /* Don't constant fold this floating point operation if the
1187          result may dependent upon the run-time rounding mode and
1188          flag_rounding_math is set, or if GCC's software emulation
1189          is unable to accurately represent the result.  */
1190       if ((flag_rounding_math
1191            || (MODE_COMPOSITE_P (mode) && !flag_unsafe_math_optimizations))
1192           && (inexact || !real_identical (&result, &value)))
1193         return NULL_TREE;
1194
1195       t = build_real (type, result);
1196
1197       TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2);
1198       return t;
1199     }
1200
1201   if (TREE_CODE (arg1) == FIXED_CST)
1202     {
1203       FIXED_VALUE_TYPE f1;
1204       FIXED_VALUE_TYPE f2;
1205       FIXED_VALUE_TYPE result;
1206       tree t, type;
1207       int sat_p;
1208       bool overflow_p;
1209
1210       /* The following codes are handled by fixed_arithmetic.  */
1211       switch (code)
1212         {
1213         case PLUS_EXPR:
1214         case MINUS_EXPR:
1215         case MULT_EXPR:
1216         case TRUNC_DIV_EXPR:
1217           f2 = TREE_FIXED_CST (arg2);
1218           break;
1219
1220         case LSHIFT_EXPR:
1221         case RSHIFT_EXPR:
1222           f2.data.high = TREE_INT_CST_HIGH (arg2);
1223           f2.data.low = TREE_INT_CST_LOW (arg2);
1224           f2.mode = SImode;
1225           break;
1226
1227         default:
1228           return NULL_TREE;
1229         }
1230
1231       f1 = TREE_FIXED_CST (arg1);
1232       type = TREE_TYPE (arg1);
1233       sat_p = TYPE_SATURATING (type);
1234       overflow_p = fixed_arithmetic (&result, code, &f1, &f2, sat_p);
1235       t = build_fixed (type, result);
1236       /* Propagate overflow flags.  */
1237       if (overflow_p | TREE_OVERFLOW (arg1) | TREE_OVERFLOW (arg2))
1238         TREE_OVERFLOW (t) = 1;
1239       return t;
1240     }
1241
1242   if (TREE_CODE (arg1) == COMPLEX_CST)
1243     {
1244       tree type = TREE_TYPE (arg1);
1245       tree r1 = TREE_REALPART (arg1);
1246       tree i1 = TREE_IMAGPART (arg1);
1247       tree r2 = TREE_REALPART (arg2);
1248       tree i2 = TREE_IMAGPART (arg2);
1249       tree real, imag;
1250
1251       switch (code)
1252         {
1253         case PLUS_EXPR:
1254         case MINUS_EXPR:
1255           real = const_binop (code, r1, r2);
1256           imag = const_binop (code, i1, i2);
1257           break;
1258
1259         case MULT_EXPR:
1260           if (COMPLEX_FLOAT_TYPE_P (type))
1261             return do_mpc_arg2 (arg1, arg2, type,
1262                                 /* do_nonfinite= */ folding_initializer,
1263                                 mpc_mul);
1264
1265           real = const_binop (MINUS_EXPR,
1266                               const_binop (MULT_EXPR, r1, r2),
1267                               const_binop (MULT_EXPR, i1, i2));
1268           imag = const_binop (PLUS_EXPR,
1269                               const_binop (MULT_EXPR, r1, i2),
1270                               const_binop (MULT_EXPR, i1, r2));
1271           break;
1272
1273         case RDIV_EXPR:
1274           if (COMPLEX_FLOAT_TYPE_P (type))
1275             return do_mpc_arg2 (arg1, arg2, type,
1276                                 /* do_nonfinite= */ folding_initializer,
1277                                 mpc_div);
1278           /* Fallthru ... */
1279         case TRUNC_DIV_EXPR:
1280         case CEIL_DIV_EXPR:
1281         case FLOOR_DIV_EXPR:
1282         case ROUND_DIV_EXPR:
1283           if (flag_complex_method == 0)
1284           {
1285             /* Keep this algorithm in sync with
1286                tree-complex.c:expand_complex_div_straight().
1287
1288                Expand complex division to scalars, straightforward algorithm.
1289                a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
1290                t = br*br + bi*bi
1291             */
1292             tree magsquared
1293               = const_binop (PLUS_EXPR,
1294                              const_binop (MULT_EXPR, r2, r2),
1295                              const_binop (MULT_EXPR, i2, i2));
1296             tree t1
1297               = const_binop (PLUS_EXPR,
1298                              const_binop (MULT_EXPR, r1, r2),
1299                              const_binop (MULT_EXPR, i1, i2));
1300             tree t2
1301               = const_binop (MINUS_EXPR,
1302                              const_binop (MULT_EXPR, i1, r2),
1303                              const_binop (MULT_EXPR, r1, i2));
1304
1305             real = const_binop (code, t1, magsquared);
1306             imag = const_binop (code, t2, magsquared);
1307           }
1308           else
1309           {
1310             /* Keep this algorithm in sync with
1311                tree-complex.c:expand_complex_div_wide().
1312
1313                Expand complex division to scalars, modified algorithm to minimize
1314                overflow with wide input ranges.  */
1315             tree compare = fold_build2 (LT_EXPR, boolean_type_node,
1316                                         fold_abs_const (r2, TREE_TYPE (type)),
1317                                         fold_abs_const (i2, TREE_TYPE (type)));
1318
1319             if (integer_nonzerop (compare))
1320               {
1321                 /* In the TRUE branch, we compute
1322                    ratio = br/bi;
1323                    div = (br * ratio) + bi;
1324                    tr = (ar * ratio) + ai;
1325                    ti = (ai * ratio) - ar;
1326                    tr = tr / div;
1327                    ti = ti / div;  */
1328                 tree ratio = const_binop (code, r2, i2);
1329                 tree div = const_binop (PLUS_EXPR, i2,
1330                                         const_binop (MULT_EXPR, r2, ratio));
1331                 real = const_binop (MULT_EXPR, r1, ratio);
1332                 real = const_binop (PLUS_EXPR, real, i1);
1333                 real = const_binop (code, real, div);
1334
1335                 imag = const_binop (MULT_EXPR, i1, ratio);
1336                 imag = const_binop (MINUS_EXPR, imag, r1);
1337                 imag = const_binop (code, imag, div);
1338               }
1339             else
1340               {
1341                 /* In the FALSE branch, we compute
1342                    ratio = d/c;
1343                    divisor = (d * ratio) + c;
1344                    tr = (b * ratio) + a;
1345                    ti = b - (a * ratio);
1346                    tr = tr / div;
1347                    ti = ti / div;  */
1348                 tree ratio = const_binop (code, i2, r2);
1349                 tree div = const_binop (PLUS_EXPR, r2,
1350                                         const_binop (MULT_EXPR, i2, ratio));
1351
1352                 real = const_binop (MULT_EXPR, i1, ratio);
1353                 real = const_binop (PLUS_EXPR, real, r1);
1354                 real = const_binop (code, real, div);
1355
1356                 imag = const_binop (MULT_EXPR, r1, ratio);
1357                 imag = const_binop (MINUS_EXPR, i1, imag);
1358                 imag = const_binop (code, imag, div);
1359               }
1360           }
1361           break;
1362
1363         default:
1364           return NULL_TREE;
1365         }
1366
1367       if (real && imag)
1368         return build_complex (type, real, imag);
1369     }
1370
1371   if (TREE_CODE (arg1) == VECTOR_CST)
1372     {
1373       tree type = TREE_TYPE(arg1);
1374       int count = TYPE_VECTOR_SUBPARTS (type), i;
1375       tree elements1, elements2, list = NULL_TREE;
1376
1377       if(TREE_CODE(arg2) != VECTOR_CST)
1378         return NULL_TREE;
1379
1380       elements1 = TREE_VECTOR_CST_ELTS (arg1);
1381       elements2 = TREE_VECTOR_CST_ELTS (arg2);
1382
1383       for (i = 0; i < count; i++)
1384         {
1385           tree elem1, elem2, elem;
1386
1387           /* The trailing elements can be empty and should be treated as 0 */
1388           if(!elements1)
1389             elem1 = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1390           else
1391             {
1392               elem1 = TREE_VALUE(elements1);
1393               elements1 = TREE_CHAIN (elements1);
1394             }
1395
1396           if(!elements2)
1397             elem2 = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1398           else
1399             {
1400               elem2 = TREE_VALUE(elements2);
1401               elements2 = TREE_CHAIN (elements2);
1402             }
1403
1404           elem = const_binop (code, elem1, elem2);
1405
1406           /* It is possible that const_binop cannot handle the given
1407             code and return NULL_TREE */
1408           if(elem == NULL_TREE)
1409             return NULL_TREE;
1410
1411           list = tree_cons (NULL_TREE, elem, list);
1412         }
1413       return build_vector(type, nreverse(list));
1414     }
1415   return NULL_TREE;
1416 }
1417
1418 /* Create a size type INT_CST node with NUMBER sign extended.  KIND
1419    indicates which particular sizetype to create.  */
1420
1421 tree
1422 size_int_kind (HOST_WIDE_INT number, enum size_type_kind kind)
1423 {
1424   return build_int_cst (sizetype_tab[(int) kind], number);
1425 }
1426 \f
1427 /* Combine operands OP1 and OP2 with arithmetic operation CODE.  CODE
1428    is a tree code.  The type of the result is taken from the operands.
1429    Both must be equivalent integer types, ala int_binop_types_match_p.
1430    If the operands are constant, so is the result.  */
1431
1432 tree
1433 size_binop_loc (location_t loc, enum tree_code code, tree arg0, tree arg1)
1434 {
1435   tree type = TREE_TYPE (arg0);
1436
1437   if (arg0 == error_mark_node || arg1 == error_mark_node)
1438     return error_mark_node;
1439
1440   gcc_assert (int_binop_types_match_p (code, TREE_TYPE (arg0),
1441                                        TREE_TYPE (arg1)));
1442
1443   /* Handle the special case of two integer constants faster.  */
1444   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1445     {
1446       /* And some specific cases even faster than that.  */
1447       if (code == PLUS_EXPR)
1448         {
1449           if (integer_zerop (arg0) && !TREE_OVERFLOW (arg0))
1450             return arg1;
1451           if (integer_zerop (arg1) && !TREE_OVERFLOW (arg1))
1452             return arg0;
1453         }
1454       else if (code == MINUS_EXPR)
1455         {
1456           if (integer_zerop (arg1) && !TREE_OVERFLOW (arg1))
1457             return arg0;
1458         }
1459       else if (code == MULT_EXPR)
1460         {
1461           if (integer_onep (arg0) && !TREE_OVERFLOW (arg0))
1462             return arg1;
1463         }
1464
1465       /* Handle general case of two integer constants.  */
1466       return int_const_binop (code, arg0, arg1);
1467     }
1468
1469   return fold_build2_loc (loc, code, type, arg0, arg1);
1470 }
1471
1472 /* Given two values, either both of sizetype or both of bitsizetype,
1473    compute the difference between the two values.  Return the value
1474    in signed type corresponding to the type of the operands.  */
1475
1476 tree
1477 size_diffop_loc (location_t loc, tree arg0, tree arg1)
1478 {
1479   tree type = TREE_TYPE (arg0);
1480   tree ctype;
1481
1482   gcc_assert (int_binop_types_match_p (MINUS_EXPR, TREE_TYPE (arg0),
1483                                        TREE_TYPE (arg1)));
1484
1485   /* If the type is already signed, just do the simple thing.  */
1486   if (!TYPE_UNSIGNED (type))
1487     return size_binop_loc (loc, MINUS_EXPR, arg0, arg1);
1488
1489   if (type == sizetype)
1490     ctype = ssizetype;
1491   else if (type == bitsizetype)
1492     ctype = sbitsizetype;
1493   else
1494     ctype = signed_type_for (type);
1495
1496   /* If either operand is not a constant, do the conversions to the signed
1497      type and subtract.  The hardware will do the right thing with any
1498      overflow in the subtraction.  */
1499   if (TREE_CODE (arg0) != INTEGER_CST || TREE_CODE (arg1) != INTEGER_CST)
1500     return size_binop_loc (loc, MINUS_EXPR,
1501                            fold_convert_loc (loc, ctype, arg0),
1502                            fold_convert_loc (loc, ctype, arg1));
1503
1504   /* If ARG0 is larger than ARG1, subtract and return the result in CTYPE.
1505      Otherwise, subtract the other way, convert to CTYPE (we know that can't
1506      overflow) and negate (which can't either).  Special-case a result
1507      of zero while we're here.  */
1508   if (tree_int_cst_equal (arg0, arg1))
1509     return build_int_cst (ctype, 0);
1510   else if (tree_int_cst_lt (arg1, arg0))
1511     return fold_convert_loc (loc, ctype,
1512                              size_binop_loc (loc, MINUS_EXPR, arg0, arg1));
1513   else
1514     return size_binop_loc (loc, MINUS_EXPR, build_int_cst (ctype, 0),
1515                            fold_convert_loc (loc, ctype,
1516                                              size_binop_loc (loc,
1517                                                              MINUS_EXPR,
1518                                                              arg1, arg0)));
1519 }
1520 \f
1521 /* A subroutine of fold_convert_const handling conversions of an
1522    INTEGER_CST to another integer type.  */
1523
1524 static tree
1525 fold_convert_const_int_from_int (tree type, const_tree arg1)
1526 {
1527   tree t;
1528
1529   /* Given an integer constant, make new constant with new type,
1530      appropriately sign-extended or truncated.  */
1531   t = force_fit_type_double (type, tree_to_double_int (arg1),
1532                              !POINTER_TYPE_P (TREE_TYPE (arg1)),
1533                              (TREE_INT_CST_HIGH (arg1) < 0
1534                               && (TYPE_UNSIGNED (type)
1535                                   < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1536                              | TREE_OVERFLOW (arg1));
1537
1538   return t;
1539 }
1540
1541 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1542    to an integer type.  */
1543
1544 static tree
1545 fold_convert_const_int_from_real (enum tree_code code, tree type, const_tree arg1)
1546 {
1547   int overflow = 0;
1548   tree t;
1549
1550   /* The following code implements the floating point to integer
1551      conversion rules required by the Java Language Specification,
1552      that IEEE NaNs are mapped to zero and values that overflow
1553      the target precision saturate, i.e. values greater than
1554      INT_MAX are mapped to INT_MAX, and values less than INT_MIN
1555      are mapped to INT_MIN.  These semantics are allowed by the
1556      C and C++ standards that simply state that the behavior of
1557      FP-to-integer conversion is unspecified upon overflow.  */
1558
1559   double_int val;
1560   REAL_VALUE_TYPE r;
1561   REAL_VALUE_TYPE x = TREE_REAL_CST (arg1);
1562
1563   switch (code)
1564     {
1565     case FIX_TRUNC_EXPR:
1566       real_trunc (&r, VOIDmode, &x);
1567       break;
1568
1569     default:
1570       gcc_unreachable ();
1571     }
1572
1573   /* If R is NaN, return zero and show we have an overflow.  */
1574   if (REAL_VALUE_ISNAN (r))
1575     {
1576       overflow = 1;
1577       val = double_int_zero;
1578     }
1579
1580   /* See if R is less than the lower bound or greater than the
1581      upper bound.  */
1582
1583   if (! overflow)
1584     {
1585       tree lt = TYPE_MIN_VALUE (type);
1586       REAL_VALUE_TYPE l = real_value_from_int_cst (NULL_TREE, lt);
1587       if (REAL_VALUES_LESS (r, l))
1588         {
1589           overflow = 1;
1590           val = tree_to_double_int (lt);
1591         }
1592     }
1593
1594   if (! overflow)
1595     {
1596       tree ut = TYPE_MAX_VALUE (type);
1597       if (ut)
1598         {
1599           REAL_VALUE_TYPE u = real_value_from_int_cst (NULL_TREE, ut);
1600           if (REAL_VALUES_LESS (u, r))
1601             {
1602               overflow = 1;
1603               val = tree_to_double_int (ut);
1604             }
1605         }
1606     }
1607
1608   if (! overflow)
1609     real_to_integer2 ((HOST_WIDE_INT *) &val.low, &val.high, &r);
1610
1611   t = force_fit_type_double (type, val, -1, overflow | TREE_OVERFLOW (arg1));
1612   return t;
1613 }
1614
1615 /* A subroutine of fold_convert_const handling conversions of a
1616    FIXED_CST to an integer type.  */
1617
1618 static tree
1619 fold_convert_const_int_from_fixed (tree type, const_tree arg1)
1620 {
1621   tree t;
1622   double_int temp, temp_trunc;
1623   unsigned int mode;
1624
1625   /* Right shift FIXED_CST to temp by fbit.  */
1626   temp = TREE_FIXED_CST (arg1).data;
1627   mode = TREE_FIXED_CST (arg1).mode;
1628   if (GET_MODE_FBIT (mode) < 2 * HOST_BITS_PER_WIDE_INT)
1629     {
1630       temp = double_int_rshift (temp, GET_MODE_FBIT (mode),
1631                                 HOST_BITS_PER_DOUBLE_INT,
1632                                 SIGNED_FIXED_POINT_MODE_P (mode));
1633
1634       /* Left shift temp to temp_trunc by fbit.  */
1635       temp_trunc = double_int_lshift (temp, GET_MODE_FBIT (mode),
1636                                       HOST_BITS_PER_DOUBLE_INT,
1637                                       SIGNED_FIXED_POINT_MODE_P (mode));
1638     }
1639   else
1640     {
1641       temp = double_int_zero;
1642       temp_trunc = double_int_zero;
1643     }
1644
1645   /* If FIXED_CST is negative, we need to round the value toward 0.
1646      By checking if the fractional bits are not zero to add 1 to temp.  */
1647   if (SIGNED_FIXED_POINT_MODE_P (mode)
1648       && double_int_negative_p (temp_trunc)
1649       && !double_int_equal_p (TREE_FIXED_CST (arg1).data, temp_trunc))
1650     temp = double_int_add (temp, double_int_one);
1651
1652   /* Given a fixed-point constant, make new constant with new type,
1653      appropriately sign-extended or truncated.  */
1654   t = force_fit_type_double (type, temp, -1,
1655                              (double_int_negative_p (temp)
1656                               && (TYPE_UNSIGNED (type)
1657                                   < TYPE_UNSIGNED (TREE_TYPE (arg1))))
1658                              | TREE_OVERFLOW (arg1));
1659
1660   return t;
1661 }
1662
1663 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1664    to another floating point type.  */
1665
1666 static tree
1667 fold_convert_const_real_from_real (tree type, const_tree arg1)
1668 {
1669   REAL_VALUE_TYPE value;
1670   tree t;
1671
1672   real_convert (&value, TYPE_MODE (type), &TREE_REAL_CST (arg1));
1673   t = build_real (type, value);
1674
1675   /* If converting an infinity or NAN to a representation that doesn't
1676      have one, set the overflow bit so that we can produce some kind of
1677      error message at the appropriate point if necessary.  It's not the
1678      most user-friendly message, but it's better than nothing.  */
1679   if (REAL_VALUE_ISINF (TREE_REAL_CST (arg1))
1680       && !MODE_HAS_INFINITIES (TYPE_MODE (type)))
1681     TREE_OVERFLOW (t) = 1;
1682   else if (REAL_VALUE_ISNAN (TREE_REAL_CST (arg1))
1683            && !MODE_HAS_NANS (TYPE_MODE (type)))
1684     TREE_OVERFLOW (t) = 1;
1685   /* Regular overflow, conversion produced an infinity in a mode that
1686      can't represent them.  */
1687   else if (!MODE_HAS_INFINITIES (TYPE_MODE (type))
1688            && REAL_VALUE_ISINF (value)
1689            && !REAL_VALUE_ISINF (TREE_REAL_CST (arg1)))
1690     TREE_OVERFLOW (t) = 1;
1691   else
1692     TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1693   return t;
1694 }
1695
1696 /* A subroutine of fold_convert_const handling conversions a FIXED_CST
1697    to a floating point type.  */
1698
1699 static tree
1700 fold_convert_const_real_from_fixed (tree type, const_tree arg1)
1701 {
1702   REAL_VALUE_TYPE value;
1703   tree t;
1704
1705   real_convert_from_fixed (&value, TYPE_MODE (type), &TREE_FIXED_CST (arg1));
1706   t = build_real (type, value);
1707
1708   TREE_OVERFLOW (t) = TREE_OVERFLOW (arg1);
1709   return t;
1710 }
1711
1712 /* A subroutine of fold_convert_const handling conversions a FIXED_CST
1713    to another fixed-point type.  */
1714
1715 static tree
1716 fold_convert_const_fixed_from_fixed (tree type, const_tree arg1)
1717 {
1718   FIXED_VALUE_TYPE value;
1719   tree t;
1720   bool overflow_p;
1721
1722   overflow_p = fixed_convert (&value, TYPE_MODE (type), &TREE_FIXED_CST (arg1),
1723                               TYPE_SATURATING (type));
1724   t = build_fixed (type, value);
1725
1726   /* Propagate overflow flags.  */
1727   if (overflow_p | TREE_OVERFLOW (arg1))
1728     TREE_OVERFLOW (t) = 1;
1729   return t;
1730 }
1731
1732 /* A subroutine of fold_convert_const handling conversions an INTEGER_CST
1733    to a fixed-point type.  */
1734
1735 static tree
1736 fold_convert_const_fixed_from_int (tree type, const_tree arg1)
1737 {
1738   FIXED_VALUE_TYPE value;
1739   tree t;
1740   bool overflow_p;
1741
1742   overflow_p = fixed_convert_from_int (&value, TYPE_MODE (type),
1743                                        TREE_INT_CST (arg1),
1744                                        TYPE_UNSIGNED (TREE_TYPE (arg1)),
1745                                        TYPE_SATURATING (type));
1746   t = build_fixed (type, value);
1747
1748   /* Propagate overflow flags.  */
1749   if (overflow_p | TREE_OVERFLOW (arg1))
1750     TREE_OVERFLOW (t) = 1;
1751   return t;
1752 }
1753
1754 /* A subroutine of fold_convert_const handling conversions a REAL_CST
1755    to a fixed-point type.  */
1756
1757 static tree
1758 fold_convert_const_fixed_from_real (tree type, const_tree arg1)
1759 {
1760   FIXED_VALUE_TYPE value;
1761   tree t;
1762   bool overflow_p;
1763
1764   overflow_p = fixed_convert_from_real (&value, TYPE_MODE (type),
1765                                         &TREE_REAL_CST (arg1),
1766                                         TYPE_SATURATING (type));
1767   t = build_fixed (type, value);
1768
1769   /* Propagate overflow flags.  */
1770   if (overflow_p | TREE_OVERFLOW (arg1))
1771     TREE_OVERFLOW (t) = 1;
1772   return t;
1773 }
1774
1775 /* Attempt to fold type conversion operation CODE of expression ARG1 to
1776    type TYPE.  If no simplification can be done return NULL_TREE.  */
1777
1778 static tree
1779 fold_convert_const (enum tree_code code, tree type, tree arg1)
1780 {
1781   if (TREE_TYPE (arg1) == type)
1782     return arg1;
1783
1784   if (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)
1785       || TREE_CODE (type) == OFFSET_TYPE)
1786     {
1787       if (TREE_CODE (arg1) == INTEGER_CST)
1788         return fold_convert_const_int_from_int (type, arg1);
1789       else if (TREE_CODE (arg1) == REAL_CST)
1790         return fold_convert_const_int_from_real (code, type, arg1);
1791       else if (TREE_CODE (arg1) == FIXED_CST)
1792         return fold_convert_const_int_from_fixed (type, arg1);
1793     }
1794   else if (TREE_CODE (type) == REAL_TYPE)
1795     {
1796       if (TREE_CODE (arg1) == INTEGER_CST)
1797         return build_real_from_int_cst (type, arg1);
1798       else if (TREE_CODE (arg1) == REAL_CST)
1799         return fold_convert_const_real_from_real (type, arg1);
1800       else if (TREE_CODE (arg1) == FIXED_CST)
1801         return fold_convert_const_real_from_fixed (type, arg1);
1802     }
1803   else if (TREE_CODE (type) == FIXED_POINT_TYPE)
1804     {
1805       if (TREE_CODE (arg1) == FIXED_CST)
1806         return fold_convert_const_fixed_from_fixed (type, arg1);
1807       else if (TREE_CODE (arg1) == INTEGER_CST)
1808         return fold_convert_const_fixed_from_int (type, arg1);
1809       else if (TREE_CODE (arg1) == REAL_CST)
1810         return fold_convert_const_fixed_from_real (type, arg1);
1811     }
1812   return NULL_TREE;
1813 }
1814
1815 /* Construct a vector of zero elements of vector type TYPE.  */
1816
1817 static tree
1818 build_zero_vector (tree type)
1819 {
1820   tree t;
1821
1822   t = fold_convert_const (NOP_EXPR, TREE_TYPE (type), integer_zero_node);
1823   return build_vector_from_val (type, t);
1824 }
1825
1826 /* Returns true, if ARG is convertible to TYPE using a NOP_EXPR.  */
1827
1828 bool
1829 fold_convertible_p (const_tree type, const_tree arg)
1830 {
1831   tree orig = TREE_TYPE (arg);
1832
1833   if (type == orig)
1834     return true;
1835
1836   if (TREE_CODE (arg) == ERROR_MARK
1837       || TREE_CODE (type) == ERROR_MARK
1838       || TREE_CODE (orig) == ERROR_MARK)
1839     return false;
1840
1841   if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig))
1842     return true;
1843
1844   switch (TREE_CODE (type))
1845     {
1846     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1847     case POINTER_TYPE: case REFERENCE_TYPE:
1848     case OFFSET_TYPE:
1849       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1850           || TREE_CODE (orig) == OFFSET_TYPE)
1851         return true;
1852       return (TREE_CODE (orig) == VECTOR_TYPE
1853               && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1854
1855     case REAL_TYPE:
1856     case FIXED_POINT_TYPE:
1857     case COMPLEX_TYPE:
1858     case VECTOR_TYPE:
1859     case VOID_TYPE:
1860       return TREE_CODE (type) == TREE_CODE (orig);
1861
1862     default:
1863       return false;
1864     }
1865 }
1866
1867 /* Convert expression ARG to type TYPE.  Used by the middle-end for
1868    simple conversions in preference to calling the front-end's convert.  */
1869
1870 tree
1871 fold_convert_loc (location_t loc, tree type, tree arg)
1872 {
1873   tree orig = TREE_TYPE (arg);
1874   tree tem;
1875
1876   if (type == orig)
1877     return arg;
1878
1879   if (TREE_CODE (arg) == ERROR_MARK
1880       || TREE_CODE (type) == ERROR_MARK
1881       || TREE_CODE (orig) == ERROR_MARK)
1882     return error_mark_node;
1883
1884   switch (TREE_CODE (type))
1885     {
1886     case POINTER_TYPE:
1887     case REFERENCE_TYPE:
1888       /* Handle conversions between pointers to different address spaces.  */
1889       if (POINTER_TYPE_P (orig)
1890           && (TYPE_ADDR_SPACE (TREE_TYPE (type))
1891               != TYPE_ADDR_SPACE (TREE_TYPE (orig))))
1892         return fold_build1_loc (loc, ADDR_SPACE_CONVERT_EXPR, type, arg);
1893       /* fall through */
1894
1895     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1896     case OFFSET_TYPE:
1897       if (TREE_CODE (arg) == INTEGER_CST)
1898         {
1899           tem = fold_convert_const (NOP_EXPR, type, arg);
1900           if (tem != NULL_TREE)
1901             return tem;
1902         }
1903       if (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
1904           || TREE_CODE (orig) == OFFSET_TYPE)
1905         return fold_build1_loc (loc, NOP_EXPR, type, arg);
1906       if (TREE_CODE (orig) == COMPLEX_TYPE)
1907         return fold_convert_loc (loc, type,
1908                              fold_build1_loc (loc, REALPART_EXPR,
1909                                           TREE_TYPE (orig), arg));
1910       gcc_assert (TREE_CODE (orig) == VECTOR_TYPE
1911                   && tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
1912       return fold_build1_loc (loc, NOP_EXPR, type, arg);
1913
1914     case REAL_TYPE:
1915       if (TREE_CODE (arg) == INTEGER_CST)
1916         {
1917           tem = fold_convert_const (FLOAT_EXPR, type, arg);
1918           if (tem != NULL_TREE)
1919             return tem;
1920         }
1921       else if (TREE_CODE (arg) == REAL_CST)
1922         {
1923           tem = fold_convert_const (NOP_EXPR, type, arg);
1924           if (tem != NULL_TREE)
1925             return tem;
1926         }
1927       else if (TREE_CODE (arg) == FIXED_CST)
1928         {
1929           tem = fold_convert_const (FIXED_CONVERT_EXPR, type, arg);
1930           if (tem != NULL_TREE)
1931             return tem;
1932         }
1933
1934       switch (TREE_CODE (orig))
1935         {
1936         case INTEGER_TYPE:
1937         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1938         case POINTER_TYPE: case REFERENCE_TYPE:
1939           return fold_build1_loc (loc, FLOAT_EXPR, type, arg);
1940
1941         case REAL_TYPE:
1942           return fold_build1_loc (loc, NOP_EXPR, type, arg);
1943
1944         case FIXED_POINT_TYPE:
1945           return fold_build1_loc (loc, FIXED_CONVERT_EXPR, type, arg);
1946
1947         case COMPLEX_TYPE:
1948           tem = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
1949           return fold_convert_loc (loc, type, tem);
1950
1951         default:
1952           gcc_unreachable ();
1953         }
1954
1955     case FIXED_POINT_TYPE:
1956       if (TREE_CODE (arg) == FIXED_CST || TREE_CODE (arg) == INTEGER_CST
1957           || TREE_CODE (arg) == REAL_CST)
1958         {
1959           tem = fold_convert_const (FIXED_CONVERT_EXPR, type, arg);
1960           if (tem != NULL_TREE)
1961             goto fold_convert_exit;
1962         }
1963
1964       switch (TREE_CODE (orig))
1965         {
1966         case FIXED_POINT_TYPE:
1967         case INTEGER_TYPE:
1968         case ENUMERAL_TYPE:
1969         case BOOLEAN_TYPE:
1970         case REAL_TYPE:
1971           return fold_build1_loc (loc, FIXED_CONVERT_EXPR, type, arg);
1972
1973         case COMPLEX_TYPE:
1974           tem = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
1975           return fold_convert_loc (loc, type, tem);
1976
1977         default:
1978           gcc_unreachable ();
1979         }
1980
1981     case COMPLEX_TYPE:
1982       switch (TREE_CODE (orig))
1983         {
1984         case INTEGER_TYPE:
1985         case BOOLEAN_TYPE: case ENUMERAL_TYPE:
1986         case POINTER_TYPE: case REFERENCE_TYPE:
1987         case REAL_TYPE:
1988         case FIXED_POINT_TYPE:
1989           return fold_build2_loc (loc, COMPLEX_EXPR, type,
1990                               fold_convert_loc (loc, TREE_TYPE (type), arg),
1991                               fold_convert_loc (loc, TREE_TYPE (type),
1992                                             integer_zero_node));
1993         case COMPLEX_TYPE:
1994           {
1995             tree rpart, ipart;
1996
1997             if (TREE_CODE (arg) == COMPLEX_EXPR)
1998               {
1999                 rpart = fold_convert_loc (loc, TREE_TYPE (type),
2000                                       TREE_OPERAND (arg, 0));
2001                 ipart = fold_convert_loc (loc, TREE_TYPE (type),
2002                                       TREE_OPERAND (arg, 1));
2003                 return fold_build2_loc (loc, COMPLEX_EXPR, type, rpart, ipart);
2004               }
2005
2006             arg = save_expr (arg);
2007             rpart = fold_build1_loc (loc, REALPART_EXPR, TREE_TYPE (orig), arg);
2008             ipart = fold_build1_loc (loc, IMAGPART_EXPR, TREE_TYPE (orig), arg);
2009             rpart = fold_convert_loc (loc, TREE_TYPE (type), rpart);
2010             ipart = fold_convert_loc (loc, TREE_TYPE (type), ipart);
2011             return fold_build2_loc (loc, COMPLEX_EXPR, type, rpart, ipart);
2012           }
2013
2014         default:
2015           gcc_unreachable ();
2016         }
2017
2018     case VECTOR_TYPE:
2019       if (integer_zerop (arg))
2020         return build_zero_vector (type);
2021       gcc_assert (tree_int_cst_equal (TYPE_SIZE (type), TYPE_SIZE (orig)));
2022       gcc_assert (INTEGRAL_TYPE_P (orig) || POINTER_TYPE_P (orig)
2023                   || TREE_CODE (orig) == VECTOR_TYPE);
2024       return fold_build1_loc (loc, VIEW_CONVERT_EXPR, type, arg);
2025
2026     case VOID_TYPE:
2027       tem = fold_ignored_result (arg);
2028       return fold_build1_loc (loc, NOP_EXPR, type, tem);
2029
2030     default:
2031       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (orig))
2032         return fold_build1_loc (loc, NOP_EXPR, type, arg);
2033       gcc_unreachable ();
2034     }
2035  fold_convert_exit:
2036   protected_set_expr_location_unshare (tem, loc);
2037   return tem;
2038 }
2039 \f
2040 /* Return false if expr can be assumed not to be an lvalue, true
2041    otherwise.  */
2042
2043 static bool
2044 maybe_lvalue_p (const_tree x)
2045 {
2046   /* We only need to wrap lvalue tree codes.  */
2047   switch (TREE_CODE (x))
2048   {
2049   case VAR_DECL:
2050   case PARM_DECL:
2051   case RESULT_DECL:
2052   case LABEL_DECL:
2053   case FUNCTION_DECL:
2054   case SSA_NAME:
2055
2056   case COMPONENT_REF:
2057   case MEM_REF:
2058   case INDIRECT_REF:
2059   case ARRAY_REF:
2060   case ARRAY_RANGE_REF:
2061   case BIT_FIELD_REF:
2062   case OBJ_TYPE_REF:
2063
2064   case REALPART_EXPR:
2065   case IMAGPART_EXPR:
2066   case PREINCREMENT_EXPR:
2067   case PREDECREMENT_EXPR:
2068   case SAVE_EXPR:
2069   case TRY_CATCH_EXPR:
2070   case WITH_CLEANUP_EXPR:
2071   case COMPOUND_EXPR:
2072   case MODIFY_EXPR:
2073   case TARGET_EXPR:
2074   case COND_EXPR:
2075   case BIND_EXPR:
2076     break;
2077
2078   default:
2079     /* Assume the worst for front-end tree codes.  */
2080     if ((int)TREE_CODE (x) >= NUM_TREE_CODES)
2081       break;
2082     return false;
2083   }
2084
2085   return true;
2086 }
2087
2088 /* Return an expr equal to X but certainly not valid as an lvalue.  */
2089
2090 tree
2091 non_lvalue_loc (location_t loc, tree x)
2092 {
2093   /* While we are in GIMPLE, NON_LVALUE_EXPR doesn't mean anything to
2094      us.  */
2095   if (in_gimple_form)
2096     return x;
2097
2098   if (! maybe_lvalue_p (x))
2099     return x;
2100   return build1_loc (loc, NON_LVALUE_EXPR, TREE_TYPE (x), x);
2101 }
2102
2103 /* Nonzero means lvalues are limited to those valid in pedantic ANSI C.
2104    Zero means allow extended lvalues.  */
2105
2106 int pedantic_lvalues;
2107
2108 /* When pedantic, return an expr equal to X but certainly not valid as a
2109    pedantic lvalue.  Otherwise, return X.  */
2110
2111 static tree
2112 pedantic_non_lvalue_loc (location_t loc, tree x)
2113 {
2114   if (pedantic_lvalues)
2115     return non_lvalue_loc (loc, x);
2116
2117   return protected_set_expr_location_unshare (x, loc);
2118 }
2119 \f
2120 /* Given a tree comparison code, return the code that is the logical inverse.
2121    It is generally not safe to do this for floating-point comparisons, except
2122    for EQ_EXPR and NE_EXPR, so we return ERROR_MARK in this case.  */
2123
2124 enum tree_code
2125 invert_tree_comparison (enum tree_code code, bool honor_nans)
2126 {
2127   if (honor_nans && flag_trapping_math && code != EQ_EXPR && code != NE_EXPR)
2128     return ERROR_MARK;
2129
2130   switch (code)
2131     {
2132     case EQ_EXPR:
2133       return NE_EXPR;
2134     case NE_EXPR:
2135       return EQ_EXPR;
2136     case GT_EXPR:
2137       return honor_nans ? UNLE_EXPR : LE_EXPR;
2138     case GE_EXPR:
2139       return honor_nans ? UNLT_EXPR : LT_EXPR;
2140     case LT_EXPR:
2141       return honor_nans ? UNGE_EXPR : GE_EXPR;
2142     case LE_EXPR:
2143       return honor_nans ? UNGT_EXPR : GT_EXPR;
2144     case LTGT_EXPR:
2145       return UNEQ_EXPR;
2146     case UNEQ_EXPR:
2147       return LTGT_EXPR;
2148     case UNGT_EXPR:
2149       return LE_EXPR;
2150     case UNGE_EXPR:
2151       return LT_EXPR;
2152     case UNLT_EXPR:
2153       return GE_EXPR;
2154     case UNLE_EXPR:
2155       return GT_EXPR;
2156     case ORDERED_EXPR:
2157       return UNORDERED_EXPR;
2158     case UNORDERED_EXPR:
2159       return ORDERED_EXPR;
2160     default:
2161       gcc_unreachable ();
2162     }
2163 }
2164
2165 /* Similar, but return the comparison that results if the operands are
2166    swapped.  This is safe for floating-point.  */
2167
2168 enum tree_code
2169 swap_tree_comparison (enum tree_code code)
2170 {
2171   switch (code)
2172     {
2173     case EQ_EXPR:
2174     case NE_EXPR:
2175     case ORDERED_EXPR:
2176     case UNORDERED_EXPR:
2177     case LTGT_EXPR:
2178     case UNEQ_EXPR:
2179       return code;
2180     case GT_EXPR:
2181       return LT_EXPR;
2182     case GE_EXPR:
2183       return LE_EXPR;
2184     case LT_EXPR:
2185       return GT_EXPR;
2186     case LE_EXPR:
2187       return GE_EXPR;
2188     case UNGT_EXPR:
2189       return UNLT_EXPR;
2190     case UNGE_EXPR:
2191       return UNLE_EXPR;
2192     case UNLT_EXPR:
2193       return UNGT_EXPR;
2194     case UNLE_EXPR:
2195       return UNGE_EXPR;
2196     default:
2197       gcc_unreachable ();
2198     }
2199 }
2200
2201
2202 /* Convert a comparison tree code from an enum tree_code representation
2203    into a compcode bit-based encoding.  This function is the inverse of
2204    compcode_to_comparison.  */
2205
2206 static enum comparison_code
2207 comparison_to_compcode (enum tree_code code)
2208 {
2209   switch (code)
2210     {
2211     case LT_EXPR:
2212       return COMPCODE_LT;
2213     case EQ_EXPR:
2214       return COMPCODE_EQ;
2215     case LE_EXPR:
2216       return COMPCODE_LE;
2217     case GT_EXPR:
2218       return COMPCODE_GT;
2219     case NE_EXPR:
2220       return COMPCODE_NE;
2221     case GE_EXPR:
2222       return COMPCODE_GE;
2223     case ORDERED_EXPR:
2224       return COMPCODE_ORD;
2225     case UNORDERED_EXPR:
2226       return COMPCODE_UNORD;
2227     case UNLT_EXPR:
2228       return COMPCODE_UNLT;
2229     case UNEQ_EXPR:
2230       return COMPCODE_UNEQ;
2231     case UNLE_EXPR:
2232       return COMPCODE_UNLE;
2233     case UNGT_EXPR:
2234       return COMPCODE_UNGT;
2235     case LTGT_EXPR:
2236       return COMPCODE_LTGT;
2237     case UNGE_EXPR:
2238       return COMPCODE_UNGE;
2239     default:
2240       gcc_unreachable ();
2241     }
2242 }
2243
2244 /* Convert a compcode bit-based encoding of a comparison operator back
2245    to GCC's enum tree_code representation.  This function is the
2246    inverse of comparison_to_compcode.  */
2247
2248 static enum tree_code
2249 compcode_to_comparison (enum comparison_code code)
2250 {
2251   switch (code)
2252     {
2253     case COMPCODE_LT:
2254       return LT_EXPR;
2255     case COMPCODE_EQ:
2256       return EQ_EXPR;
2257     case COMPCODE_LE:
2258       return LE_EXPR;
2259     case COMPCODE_GT:
2260       return GT_EXPR;
2261     case COMPCODE_NE:
2262       return NE_EXPR;
2263     case COMPCODE_GE:
2264       return GE_EXPR;
2265     case COMPCODE_ORD:
2266       return ORDERED_EXPR;
2267     case COMPCODE_UNORD:
2268       return UNORDERED_EXPR;
2269     case COMPCODE_UNLT:
2270       return UNLT_EXPR;
2271     case COMPCODE_UNEQ:
2272       return UNEQ_EXPR;
2273     case COMPCODE_UNLE:
2274       return UNLE_EXPR;
2275     case COMPCODE_UNGT:
2276       return UNGT_EXPR;
2277     case COMPCODE_LTGT:
2278       return LTGT_EXPR;
2279     case COMPCODE_UNGE:
2280       return UNGE_EXPR;
2281     default:
2282       gcc_unreachable ();
2283     }
2284 }
2285
2286 /* Return a tree for the comparison which is the combination of
2287    doing the AND or OR (depending on CODE) of the two operations LCODE
2288    and RCODE on the identical operands LL_ARG and LR_ARG.  Take into account
2289    the possibility of trapping if the mode has NaNs, and return NULL_TREE
2290    if this makes the transformation invalid.  */
2291
2292 tree
2293 combine_comparisons (location_t loc,
2294                      enum tree_code code, enum tree_code lcode,
2295                      enum tree_code rcode, tree truth_type,
2296                      tree ll_arg, tree lr_arg)
2297 {
2298   bool honor_nans = HONOR_NANS (TYPE_MODE (TREE_TYPE (ll_arg)));
2299   enum comparison_code lcompcode = comparison_to_compcode (lcode);
2300   enum comparison_code rcompcode = comparison_to_compcode (rcode);
2301   int compcode;
2302
2303   switch (code)
2304     {
2305     case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR:
2306       compcode = lcompcode & rcompcode;
2307       break;
2308
2309     case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR:
2310       compcode = lcompcode | rcompcode;
2311       break;
2312
2313     default:
2314       return NULL_TREE;
2315     }
2316
2317   if (!honor_nans)
2318     {
2319       /* Eliminate unordered comparisons, as well as LTGT and ORD
2320          which are not used unless the mode has NaNs.  */
2321       compcode &= ~COMPCODE_UNORD;
2322       if (compcode == COMPCODE_LTGT)
2323         compcode = COMPCODE_NE;
2324       else if (compcode == COMPCODE_ORD)
2325         compcode = COMPCODE_TRUE;
2326     }
2327    else if (flag_trapping_math)
2328      {
2329         /* Check that the original operation and the optimized ones will trap
2330            under the same condition.  */
2331         bool ltrap = (lcompcode & COMPCODE_UNORD) == 0
2332                      && (lcompcode != COMPCODE_EQ)
2333                      && (lcompcode != COMPCODE_ORD);
2334         bool rtrap = (rcompcode & COMPCODE_UNORD) == 0
2335                      && (rcompcode != COMPCODE_EQ)
2336                      && (rcompcode != COMPCODE_ORD);
2337         bool trap = (compcode & COMPCODE_UNORD) == 0
2338                     && (compcode != COMPCODE_EQ)
2339                     && (compcode != COMPCODE_ORD);
2340
2341         /* In a short-circuited boolean expression the LHS might be
2342            such that the RHS, if evaluated, will never trap.  For
2343            example, in ORD (x, y) && (x < y), we evaluate the RHS only
2344            if neither x nor y is NaN.  (This is a mixed blessing: for
2345            example, the expression above will never trap, hence
2346            optimizing it to x < y would be invalid).  */
2347         if ((code == TRUTH_ORIF_EXPR && (lcompcode & COMPCODE_UNORD))
2348             || (code == TRUTH_ANDIF_EXPR && !(lcompcode & COMPCODE_UNORD)))
2349           rtrap = false;
2350
2351         /* If the comparison was short-circuited, and only the RHS
2352            trapped, we may now generate a spurious trap.  */
2353         if (rtrap && !ltrap
2354             && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2355           return NULL_TREE;
2356
2357         /* If we changed the conditions that cause a trap, we lose.  */
2358         if ((ltrap || rtrap) != trap)
2359           return NULL_TREE;
2360       }
2361
2362   if (compcode == COMPCODE_TRUE)
2363     return constant_boolean_node (true, truth_type);
2364   else if (compcode == COMPCODE_FALSE)
2365     return constant_boolean_node (false, truth_type);
2366   else
2367     {
2368       enum tree_code tcode;
2369
2370       tcode = compcode_to_comparison ((enum comparison_code) compcode);
2371       return fold_build2_loc (loc, tcode, truth_type, ll_arg, lr_arg);
2372     }
2373 }
2374 \f
2375 /* Return nonzero if two operands (typically of the same tree node)
2376    are necessarily equal.  If either argument has side-effects this
2377    function returns zero.  FLAGS modifies behavior as follows:
2378
2379    If OEP_ONLY_CONST is set, only return nonzero for constants.
2380    This function tests whether the operands are indistinguishable;
2381    it does not test whether they are equal using C's == operation.
2382    The distinction is important for IEEE floating point, because
2383    (1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
2384    (2) two NaNs may be indistinguishable, but NaN!=NaN.
2385
2386    If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
2387    even though it may hold multiple values during a function.
2388    This is because a GCC tree node guarantees that nothing else is
2389    executed between the evaluation of its "operands" (which may often
2390    be evaluated in arbitrary order).  Hence if the operands themselves
2391    don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
2392    same value in each operand/subexpression.  Hence leaving OEP_ONLY_CONST
2393    unset means assuming isochronic (or instantaneous) tree equivalence.
2394    Unless comparing arbitrary expression trees, such as from different
2395    statements, this flag can usually be left unset.
2396
2397    If OEP_PURE_SAME is set, then pure functions with identical arguments
2398    are considered the same.  It is used when the caller has other ways
2399    to ensure that global memory is unchanged in between.  */
2400
2401 int
2402 operand_equal_p (const_tree arg0, const_tree arg1, unsigned int flags)
2403 {
2404   /* If either is ERROR_MARK, they aren't equal.  */
2405   if (TREE_CODE (arg0) == ERROR_MARK || TREE_CODE (arg1) == ERROR_MARK
2406       || TREE_TYPE (arg0) == error_mark_node
2407       || TREE_TYPE (arg1) == error_mark_node)
2408     return 0;
2409
2410   /* Similar, if either does not have a type (like a released SSA name), 
2411      they aren't equal.  */
2412   if (!TREE_TYPE (arg0) || !TREE_TYPE (arg1))
2413     return 0;
2414
2415   /* Check equality of integer constants before bailing out due to
2416      precision differences.  */
2417   if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
2418     return tree_int_cst_equal (arg0, arg1);
2419
2420   /* If both types don't have the same signedness, then we can't consider
2421      them equal.  We must check this before the STRIP_NOPS calls
2422      because they may change the signedness of the arguments.  As pointers
2423      strictly don't have a signedness, require either two pointers or
2424      two non-pointers as well.  */
2425   if (TYPE_UNSIGNED (TREE_TYPE (arg0)) != TYPE_UNSIGNED (TREE_TYPE (arg1))
2426       || POINTER_TYPE_P (TREE_TYPE (arg0)) != POINTER_TYPE_P (TREE_TYPE (arg1)))
2427     return 0;
2428
2429   /* We cannot consider pointers to different address space equal.  */
2430   if (POINTER_TYPE_P (TREE_TYPE (arg0)) && POINTER_TYPE_P (TREE_TYPE (arg1))
2431       && (TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (arg0)))
2432           != TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (arg1)))))
2433     return 0;
2434
2435   /* If both types don't have the same precision, then it is not safe
2436      to strip NOPs.  */
2437   if (TYPE_PRECISION (TREE_TYPE (arg0)) != TYPE_PRECISION (TREE_TYPE (arg1)))
2438     return 0;
2439
2440   STRIP_NOPS (arg0);
2441   STRIP_NOPS (arg1);
2442
2443   /* In case both args are comparisons but with different comparison
2444      code, try to swap the comparison operands of one arg to produce
2445      a match and compare that variant.  */
2446   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2447       && COMPARISON_CLASS_P (arg0)
2448       && COMPARISON_CLASS_P (arg1))
2449     {
2450       enum tree_code swap_code = swap_tree_comparison (TREE_CODE (arg1));
2451
2452       if (TREE_CODE (arg0) == swap_code)
2453         return operand_equal_p (TREE_OPERAND (arg0, 0),
2454                                 TREE_OPERAND (arg1, 1), flags)
2455                && operand_equal_p (TREE_OPERAND (arg0, 1),
2456                                    TREE_OPERAND (arg1, 0), flags);
2457     }
2458
2459   if (TREE_CODE (arg0) != TREE_CODE (arg1)
2460       /* This is needed for conversions and for COMPONENT_REF.
2461          Might as well play it safe and always test this.  */
2462       || TREE_CODE (TREE_TYPE (arg0)) == ERROR_MARK
2463       || TREE_CODE (TREE_TYPE (arg1)) == ERROR_MARK
2464       || TYPE_MODE (TREE_TYPE (arg0)) != TYPE_MODE (TREE_TYPE (arg1)))
2465     return 0;
2466
2467   /* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
2468      We don't care about side effects in that case because the SAVE_EXPR
2469      takes care of that for us. In all other cases, two expressions are
2470      equal if they have no side effects.  If we have two identical
2471      expressions with side effects that should be treated the same due
2472      to the only side effects being identical SAVE_EXPR's, that will
2473      be detected in the recursive calls below.
2474      If we are taking an invariant address of two identical objects
2475      they are necessarily equal as well.  */
2476   if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
2477       && (TREE_CODE (arg0) == SAVE_EXPR
2478           || (flags & OEP_CONSTANT_ADDRESS_OF)
2479           || (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
2480     return 1;
2481
2482   /* Next handle constant cases, those for which we can return 1 even
2483      if ONLY_CONST is set.  */
2484   if (TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1))
2485     switch (TREE_CODE (arg0))
2486       {
2487       case INTEGER_CST:
2488         return tree_int_cst_equal (arg0, arg1);
2489
2490       case FIXED_CST:
2491         return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (arg0),
2492                                        TREE_FIXED_CST (arg1));
2493
2494       case REAL_CST:
2495         if (REAL_VALUES_IDENTICAL (TREE_REAL_CST (arg0),
2496                                    TREE_REAL_CST (arg1)))
2497           return 1;
2498
2499
2500         if (!HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg0))))
2501           {
2502             /* If we do not distinguish between signed and unsigned zero,
2503                consider them equal.  */
2504             if (real_zerop (arg0) && real_zerop (arg1))
2505               return 1;
2506           }
2507         return 0;
2508
2509       case VECTOR_CST:
2510         {
2511           tree v1, v2;
2512
2513           v1 = TREE_VECTOR_CST_ELTS (arg0);
2514           v2 = TREE_VECTOR_CST_ELTS (arg1);
2515           while (v1 && v2)
2516             {
2517               if (!operand_equal_p (TREE_VALUE (v1), TREE_VALUE (v2),
2518                                     flags))
2519                 return 0;
2520               v1 = TREE_CHAIN (v1);
2521               v2 = TREE_CHAIN (v2);
2522             }
2523
2524           return v1 == v2;
2525         }
2526
2527       case COMPLEX_CST:
2528         return (operand_equal_p (TREE_REALPART (arg0), TREE_REALPART (arg1),
2529                                  flags)
2530                 && operand_equal_p (TREE_IMAGPART (arg0), TREE_IMAGPART (arg1),
2531                                     flags));
2532
2533       case STRING_CST:
2534         return (TREE_STRING_LENGTH (arg0) == TREE_STRING_LENGTH (arg1)
2535                 && ! memcmp (TREE_STRING_POINTER (arg0),
2536                               TREE_STRING_POINTER (arg1),
2537                               TREE_STRING_LENGTH (arg0)));
2538
2539       case ADDR_EXPR:
2540         return operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0),
2541                                 TREE_CONSTANT (arg0) && TREE_CONSTANT (arg1)
2542                                 ? OEP_CONSTANT_ADDRESS_OF : 0);
2543       default:
2544         break;
2545       }
2546
2547   if (flags & OEP_ONLY_CONST)
2548     return 0;
2549
2550 /* Define macros to test an operand from arg0 and arg1 for equality and a
2551    variant that allows null and views null as being different from any
2552    non-null value.  In the latter case, if either is null, the both
2553    must be; otherwise, do the normal comparison.  */
2554 #define OP_SAME(N) operand_equal_p (TREE_OPERAND (arg0, N),     \
2555                                     TREE_OPERAND (arg1, N), flags)
2556
2557 #define OP_SAME_WITH_NULL(N)                            \
2558   ((!TREE_OPERAND (arg0, N) || !TREE_OPERAND (arg1, N)) \
2559    ? TREE_OPERAND (arg0, N) == TREE_OPERAND (arg1, N) : OP_SAME (N))
2560
2561   switch (TREE_CODE_CLASS (TREE_CODE (arg0)))
2562     {
2563     case tcc_unary:
2564       /* Two conversions are equal only if signedness and modes match.  */
2565       switch (TREE_CODE (arg0))
2566         {
2567         CASE_CONVERT:
2568         case FIX_TRUNC_EXPR:
2569           if (TYPE_UNSIGNED (TREE_TYPE (arg0))
2570               != TYPE_UNSIGNED (TREE_TYPE (arg1)))
2571             return 0;
2572           break;
2573         default:
2574           break;
2575         }
2576
2577       return OP_SAME (0);
2578
2579
2580     case tcc_comparison:
2581     case tcc_binary:
2582       if (OP_SAME (0) && OP_SAME (1))
2583         return 1;
2584
2585       /* For commutative ops, allow the other order.  */
2586       return (commutative_tree_code (TREE_CODE (arg0))
2587               && operand_equal_p (TREE_OPERAND (arg0, 0),
2588                                   TREE_OPERAND (arg1, 1), flags)
2589               && operand_equal_p (TREE_OPERAND (arg0, 1),
2590                                   TREE_OPERAND (arg1, 0), flags));
2591
2592     case tcc_reference:
2593       /* If either of the pointer (or reference) expressions we are
2594          dereferencing contain a side effect, these cannot be equal.  */
2595       if (TREE_SIDE_EFFECTS (arg0)
2596           || TREE_SIDE_EFFECTS (arg1))
2597         return 0;
2598
2599       switch (TREE_CODE (arg0))
2600         {
2601         case INDIRECT_REF:
2602         case REALPART_EXPR:
2603         case IMAGPART_EXPR:
2604           return OP_SAME (0);
2605
2606         case MEM_REF:
2607           /* Require equal access sizes, and similar pointer types.
2608              We can have incomplete types for array references of
2609              variable-sized arrays from the Fortran frontent
2610              though.  */
2611           return ((TYPE_SIZE (TREE_TYPE (arg0)) == TYPE_SIZE (TREE_TYPE (arg1))
2612                    || (TYPE_SIZE (TREE_TYPE (arg0))
2613                        && TYPE_SIZE (TREE_TYPE (arg1))
2614                        && operand_equal_p (TYPE_SIZE (TREE_TYPE (arg0)),
2615                                            TYPE_SIZE (TREE_TYPE (arg1)), flags)))
2616                   && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (arg0, 1)))
2617                       == TYPE_MAIN_VARIANT (TREE_TYPE (TREE_OPERAND (arg1, 1))))
2618                   && OP_SAME (0) && OP_SAME (1));
2619
2620         case ARRAY_REF:
2621         case ARRAY_RANGE_REF:
2622           /* Operands 2 and 3 may be null.
2623              Compare the array index by value if it is constant first as we
2624              may have different types but same value here.  */
2625           return (OP_SAME (0)
2626                   && (tree_int_cst_equal (TREE_OPERAND (arg0, 1),
2627                                           TREE_OPERAND (arg1, 1))
2628                       || OP_SAME (1))
2629                   && OP_SAME_WITH_NULL (2)
2630                   && OP_SAME_WITH_NULL (3));
2631
2632         case COMPONENT_REF:
2633           /* Handle operand 2 the same as for ARRAY_REF.  Operand 0
2634              may be NULL when we're called to compare MEM_EXPRs.  */
2635           return OP_SAME_WITH_NULL (0)
2636                  && OP_SAME (1)
2637                  && OP_SAME_WITH_NULL (2);
2638
2639         case BIT_FIELD_REF:
2640           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2641
2642         default:
2643           return 0;
2644         }
2645
2646     case tcc_expression:
2647       switch (TREE_CODE (arg0))
2648         {
2649         case ADDR_EXPR:
2650         case TRUTH_NOT_EXPR:
2651           return OP_SAME (0);
2652
2653         case TRUTH_ANDIF_EXPR:
2654         case TRUTH_ORIF_EXPR:
2655           return OP_SAME (0) && OP_SAME (1);
2656
2657         case FMA_EXPR:
2658         case WIDEN_MULT_PLUS_EXPR:
2659         case WIDEN_MULT_MINUS_EXPR:
2660           if (!OP_SAME (2))
2661             return 0;
2662           /* The multiplcation operands are commutative.  */
2663           /* FALLTHRU */
2664
2665         case TRUTH_AND_EXPR:
2666         case TRUTH_OR_EXPR:
2667         case TRUTH_XOR_EXPR:
2668           if (OP_SAME (0) && OP_SAME (1))
2669             return 1;
2670
2671           /* Otherwise take into account this is a commutative operation.  */
2672           return (operand_equal_p (TREE_OPERAND (arg0, 0),
2673                                    TREE_OPERAND (arg1, 1), flags)
2674                   && operand_equal_p (TREE_OPERAND (arg0, 1),
2675                                       TREE_OPERAND (arg1, 0), flags));
2676
2677         case COND_EXPR:
2678         case VEC_COND_EXPR:
2679         case DOT_PROD_EXPR:
2680           return OP_SAME (0) && OP_SAME (1) && OP_SAME (2);
2681
2682         default:
2683           return 0;
2684         }
2685
2686     case tcc_vl_exp:
2687       switch (TREE_CODE (arg0))
2688         {
2689         case CALL_EXPR:
2690           /* If the CALL_EXPRs call different functions, then they
2691              clearly can not be equal.  */
2692           if (! operand_equal_p (CALL_EXPR_FN (arg0), CALL_EXPR_FN (arg1),
2693                                  flags))
2694             return 0;
2695
2696           {
2697             unsigned int cef = call_expr_flags (arg0);
2698             if (flags & OEP_PURE_SAME)
2699               cef &= ECF_CONST | ECF_PURE;
2700             else
2701               cef &= ECF_CONST;
2702             if (!cef)
2703               return 0;
2704           }
2705
2706           /* Now see if all the arguments are the same.  */
2707           {
2708             const_call_expr_arg_iterator iter0, iter1;
2709             const_tree a0, a1;
2710             for (a0 = first_const_call_expr_arg (arg0, &iter0),
2711                    a1 = first_const_call_expr_arg (arg1, &iter1);
2712                  a0 && a1;
2713                  a0 = next_const_call_expr_arg (&iter0),
2714                    a1 = next_const_call_expr_arg (&iter1))
2715               if (! operand_equal_p (a0, a1, flags))
2716                 return 0;
2717
2718             /* If we get here and both argument lists are exhausted
2719                then the CALL_EXPRs are equal.  */
2720             return ! (a0 || a1);
2721           }
2722         default:
2723           return 0;
2724         }
2725
2726     case tcc_declaration:
2727       /* Consider __builtin_sqrt equal to sqrt.  */
2728       return (TREE_CODE (arg0) == FUNCTION_DECL
2729               && DECL_BUILT_IN (arg0) && DECL_BUILT_IN (arg1)
2730               && DECL_BUILT_IN_CLASS (arg0) == DECL_BUILT_IN_CLASS (arg1)
2731               && DECL_FUNCTION_CODE (arg0) == DECL_FUNCTION_CODE (arg1));
2732
2733     default:
2734       return 0;
2735     }
2736
2737 #undef OP_SAME
2738 #undef OP_SAME_WITH_NULL
2739 }
2740 \f
2741 /* Similar to operand_equal_p, but see if ARG0 might have been made by
2742    shorten_compare from ARG1 when ARG1 was being compared with OTHER.
2743
2744    When in doubt, return 0.  */
2745
2746 static int
2747 operand_equal_for_comparison_p (tree arg0, tree arg1, tree other)
2748 {
2749   int unsignedp1, unsignedpo;
2750   tree primarg0, primarg1, primother;
2751   unsigned int correct_width;
2752
2753   if (operand_equal_p (arg0, arg1, 0))
2754     return 1;
2755
2756   if (! INTEGRAL_TYPE_P (TREE_TYPE (arg0))
2757       || ! INTEGRAL_TYPE_P (TREE_TYPE (arg1)))
2758     return 0;
2759
2760   /* Discard any conversions that don't change the modes of ARG0 and ARG1
2761      and see if the inner values are the same.  This removes any
2762      signedness comparison, which doesn't matter here.  */
2763   primarg0 = arg0, primarg1 = arg1;
2764   STRIP_NOPS (primarg0);
2765   STRIP_NOPS (primarg1);
2766   if (operand_equal_p (primarg0, primarg1, 0))
2767     return 1;
2768
2769   /* Duplicate what shorten_compare does to ARG1 and see if that gives the
2770      actual comparison operand, ARG0.
2771
2772      First throw away any conversions to wider types
2773      already present in the operands.  */
2774
2775   primarg1 = get_narrower (arg1, &unsignedp1);
2776   primother = get_narrower (other, &unsignedpo);
2777
2778   correct_width = TYPE_PRECISION (TREE_TYPE (arg1));
2779   if (unsignedp1 == unsignedpo
2780       && TYPE_PRECISION (TREE_TYPE (primarg1)) < correct_width
2781       && TYPE_PRECISION (TREE_TYPE (primother)) < correct_width)
2782     {
2783       tree type = TREE_TYPE (arg0);
2784
2785       /* Make sure shorter operand is extended the right way
2786          to match the longer operand.  */
2787       primarg1 = fold_convert (signed_or_unsigned_type_for
2788                                (unsignedp1, TREE_TYPE (primarg1)), primarg1);
2789
2790       if (operand_equal_p (arg0, fold_convert (type, primarg1), 0))
2791         return 1;
2792     }
2793
2794   return 0;
2795 }
2796 \f
2797 /* See if ARG is an expression that is either a comparison or is performing
2798    arithmetic on comparisons.  The comparisons must only be comparing
2799    two different values, which will be stored in *CVAL1 and *CVAL2; if
2800    they are nonzero it means that some operands have already been found.
2801    No variables may be used anywhere else in the expression except in the
2802    comparisons.  If SAVE_P is true it means we removed a SAVE_EXPR around
2803    the expression and save_expr needs to be called with CVAL1 and CVAL2.
2804
2805    If this is true, return 1.  Otherwise, return zero.  */
2806
2807 static int
2808 twoval_comparison_p (tree arg, tree *cval1, tree *cval2, int *save_p)
2809 {
2810   enum tree_code code = TREE_CODE (arg);
2811   enum tree_code_class tclass = TREE_CODE_CLASS (code);
2812
2813   /* We can handle some of the tcc_expression cases here.  */
2814   if (tclass == tcc_expression && code == TRUTH_NOT_EXPR)
2815     tclass = tcc_unary;
2816   else if (tclass == tcc_expression
2817            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR
2818                || code == COMPOUND_EXPR))
2819     tclass = tcc_binary;
2820
2821   else if (tclass == tcc_expression && code == SAVE_EXPR
2822            && ! TREE_SIDE_EFFECTS (TREE_OPERAND (arg, 0)))
2823     {
2824       /* If we've already found a CVAL1 or CVAL2, this expression is
2825          two complex to handle.  */
2826       if (*cval1 || *cval2)
2827         return 0;
2828
2829       tclass = tcc_unary;
2830       *save_p = 1;
2831     }
2832
2833   switch (tclass)
2834     {
2835     case tcc_unary:
2836       return twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p);
2837
2838     case tcc_binary:
2839       return (twoval_comparison_p (TREE_OPERAND (arg, 0), cval1, cval2, save_p)
2840               && twoval_comparison_p (TREE_OPERAND (arg, 1),
2841                                       cval1, cval2, save_p));
2842
2843     case tcc_constant:
2844       return 1;
2845
2846     case tcc_expression:
2847       if (code == COND_EXPR)
2848         return (twoval_comparison_p (TREE_OPERAND (arg, 0),
2849                                      cval1, cval2, save_p)
2850                 && twoval_comparison_p (TREE_OPERAND (arg, 1),
2851                                         cval1, cval2, save_p)
2852                 && twoval_comparison_p (TREE_OPERAND (arg, 2),
2853                                         cval1, cval2, save_p));
2854       return 0;
2855
2856     case tcc_comparison:
2857       /* First see if we can handle the first operand, then the second.  For
2858          the second operand, we know *CVAL1 can't be zero.  It must be that
2859          one side of the comparison is each of the values; test for the
2860          case where this isn't true by failing if the two operands
2861          are the same.  */
2862
2863       if (operand_equal_p (TREE_OPERAND (arg, 0),
2864                            TREE_OPERAND (arg, 1), 0))
2865         return 0;
2866
2867       if (*cval1 == 0)
2868         *cval1 = TREE_OPERAND (arg, 0);
2869       else if (operand_equal_p (*cval1, TREE_OPERAND (arg, 0), 0))
2870         ;
2871       else if (*cval2 == 0)
2872         *cval2 = TREE_OPERAND (arg, 0);
2873       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 0), 0))
2874         ;
2875       else
2876         return 0;
2877
2878       if (operand_equal_p (*cval1, TREE_OPERAND (arg, 1), 0))
2879         ;
2880       else if (*cval2 == 0)
2881         *cval2 = TREE_OPERAND (arg, 1);
2882       else if (operand_equal_p (*cval2, TREE_OPERAND (arg, 1), 0))
2883         ;
2884       else
2885         return 0;
2886
2887       return 1;
2888
2889     default:
2890       return 0;
2891     }
2892 }
2893 \f
2894 /* ARG is a tree that is known to contain just arithmetic operations and
2895    comparisons.  Evaluate the operations in the tree substituting NEW0 for
2896    any occurrence of OLD0 as an operand of a comparison and likewise for
2897    NEW1 and OLD1.  */
2898
2899 static tree
2900 eval_subst (location_t loc, tree arg, tree old0, tree new0,
2901             tree old1, tree new1)
2902 {
2903   tree type = TREE_TYPE (arg);
2904   enum tree_code code = TREE_CODE (arg);
2905   enum tree_code_class tclass = TREE_CODE_CLASS (code);
2906
2907   /* We can handle some of the tcc_expression cases here.  */
2908   if (tclass == tcc_expression && code == TRUTH_NOT_EXPR)
2909     tclass = tcc_unary;
2910   else if (tclass == tcc_expression
2911            && (code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR))
2912     tclass = tcc_binary;
2913
2914   switch (tclass)
2915     {
2916     case tcc_unary:
2917       return fold_build1_loc (loc, code, type,
2918                           eval_subst (loc, TREE_OPERAND (arg, 0),
2919                                       old0, new0, old1, new1));
2920
2921     case tcc_binary:
2922       return fold_build2_loc (loc, code, type,
2923                           eval_subst (loc, TREE_OPERAND (arg, 0),
2924                                       old0, new0, old1, new1),
2925                           eval_subst (loc, TREE_OPERAND (arg, 1),
2926                                       old0, new0, old1, new1));
2927
2928     case tcc_expression:
2929       switch (code)
2930         {
2931         case SAVE_EXPR:
2932           return eval_subst (loc, TREE_OPERAND (arg, 0), old0, new0,
2933                              old1, new1);
2934
2935         case COMPOUND_EXPR:
2936           return eval_subst (loc, TREE_OPERAND (arg, 1), old0, new0,
2937                              old1, new1);
2938
2939         case COND_EXPR:
2940           return fold_build3_loc (loc, code, type,
2941                               eval_subst (loc, TREE_OPERAND (arg, 0),
2942                                           old0, new0, old1, new1),
2943                               eval_subst (loc, TREE_OPERAND (arg, 1),
2944                                           old0, new0, old1, new1),
2945                               eval_subst (loc, TREE_OPERAND (arg, 2),
2946                                           old0, new0, old1, new1));
2947         default:
2948           break;
2949         }
2950       /* Fall through - ???  */
2951
2952     case tcc_comparison:
2953       {
2954         tree arg0 = TREE_OPERAND (arg, 0);
2955         tree arg1 = TREE_OPERAND (arg, 1);
2956
2957         /* We need to check both for exact equality and tree equality.  The
2958            former will be true if the operand has a side-effect.  In that
2959            case, we know the operand occurred exactly once.  */
2960
2961         if (arg0 == old0 || operand_equal_p (arg0, old0, 0))
2962           arg0 = new0;
2963         else if (arg0 == old1 || operand_equal_p (arg0, old1, 0))
2964           arg0 = new1;
2965
2966         if (arg1 == old0 || operand_equal_p (arg1, old0, 0))
2967           arg1 = new0;
2968         else if (arg1 == old1 || operand_equal_p (arg1, old1, 0))
2969           arg1 = new1;
2970
2971         return fold_build2_loc (loc, code, type, arg0, arg1);
2972       }
2973
2974     default:
2975       return arg;
2976     }
2977 }
2978 \f
2979 /* Return a tree for the case when the result of an expression is RESULT
2980    converted to TYPE and OMITTED was previously an operand of the expression
2981    but is now not needed (e.g., we folded OMITTED * 0).
2982
2983    If OMITTED has side effects, we must evaluate it.  Otherwise, just do
2984    the conversion of RESULT to TYPE.  */
2985
2986 tree
2987 omit_one_operand_loc (location_t loc, tree type, tree result, tree omitted)
2988 {
2989   tree t = fold_convert_loc (loc, type, result);
2990
2991   /* If the resulting operand is an empty statement, just return the omitted
2992      statement casted to void. */
2993   if (IS_EMPTY_STMT (t) && TREE_SIDE_EFFECTS (omitted))
2994     return build1_loc (loc, NOP_EXPR, void_type_node,
2995                        fold_ignored_result (omitted));
2996
2997   if (TREE_SIDE_EFFECTS (omitted))
2998     return build2_loc (loc, COMPOUND_EXPR, type,
2999                        fold_ignored_result (omitted), t);
3000
3001   return non_lvalue_loc (loc, t);
3002 }
3003
3004 /* Similar, but call pedantic_non_lvalue instead of non_lvalue.  */
3005
3006 static tree
3007 pedantic_omit_one_operand_loc (location_t loc, tree type, tree result,
3008                                tree omitted)
3009 {
3010   tree t = fold_convert_loc (loc, type, result);
3011
3012   /* If the resulting operand is an empty statement, just return the omitted
3013      statement casted to void. */
3014   if (IS_EMPTY_STMT (t) && TREE_SIDE_EFFECTS (omitted))
3015     return build1_loc (loc, NOP_EXPR, void_type_node,
3016                        fold_ignored_result (omitted));
3017
3018   if (TREE_SIDE_EFFECTS (omitted))
3019     return build2_loc (loc, COMPOUND_EXPR, type,
3020                        fold_ignored_result (omitted), t);
3021
3022   return pedantic_non_lvalue_loc (loc, t);
3023 }
3024
3025 /* Return a tree for the case when the result of an expression is RESULT
3026    converted to TYPE and OMITTED1 and OMITTED2 were previously operands
3027    of the expression but are now not needed.
3028
3029    If OMITTED1 or OMITTED2 has side effects, they must be evaluated.
3030    If both OMITTED1 and OMITTED2 have side effects, OMITTED1 is
3031    evaluated before OMITTED2.  Otherwise, if neither has side effects,
3032    just do the conversion of RESULT to TYPE.  */
3033
3034 tree
3035 omit_two_operands_loc (location_t loc, tree type, tree result,
3036                        tree omitted1, tree omitted2)
3037 {
3038   tree t = fold_convert_loc (loc, type, result);
3039
3040   if (TREE_SIDE_EFFECTS (omitted2))
3041     t = build2_loc (loc, COMPOUND_EXPR, type, omitted2, t);
3042   if (TREE_SIDE_EFFECTS (omitted1))
3043     t = build2_loc (loc, COMPOUND_EXPR, type, omitted1, t);
3044
3045   return TREE_CODE (t) != COMPOUND_EXPR ? non_lvalue_loc (loc, t) : t;
3046 }
3047
3048 \f
3049 /* Return a simplified tree node for the truth-negation of ARG.  This
3050    never alters ARG itself.  We assume that ARG is an operation that
3051    returns a truth value (0 or 1).
3052
3053    FIXME: one would think we would fold the result, but it causes
3054    problems with the dominator optimizer.  */
3055
3056 tree
3057 fold_truth_not_expr (location_t loc, tree arg)
3058 {
3059   tree type = TREE_TYPE (arg);
3060   enum tree_code code = TREE_CODE (arg);
3061   location_t loc1, loc2;
3062
3063   /* If this is a comparison, we can simply invert it, except for
3064      floating-point non-equality comparisons, in which case we just
3065      enclose a TRUTH_NOT_EXPR around what we have.  */
3066
3067   if (TREE_CODE_CLASS (code) == tcc_comparison)
3068     {
3069       tree op_type = TREE_TYPE (TREE_OPERAND (arg, 0));
3070       if (FLOAT_TYPE_P (op_type)
3071           && flag_trapping_math
3072           && code != ORDERED_EXPR && code != UNORDERED_EXPR
3073           && code != NE_EXPR && code != EQ_EXPR)
3074         return NULL_TREE;
3075
3076       code = invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (op_type)));
3077       if (code == ERROR_MARK)
3078         return NULL_TREE;
3079
3080       return build2_loc (loc, code, type, TREE_OPERAND (arg, 0),
3081                          TREE_OPERAND (arg, 1));
3082     }
3083
3084   switch (code)
3085     {
3086     case INTEGER_CST:
3087       return constant_boolean_node (integer_zerop (arg), type);
3088
3089     case TRUTH_AND_EXPR:
3090       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3091       loc2 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3092       return build2_loc (loc, TRUTH_OR_EXPR, type,
3093                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3094                          invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3095
3096     case TRUTH_OR_EXPR:
3097       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3098       loc2 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3099       return build2_loc (loc, TRUTH_AND_EXPR, type,
3100                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3101                          invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3102
3103     case TRUTH_XOR_EXPR:
3104       /* Here we can invert either operand.  We invert the first operand
3105          unless the second operand is a TRUTH_NOT_EXPR in which case our
3106          result is the XOR of the first operand with the inside of the
3107          negation of the second operand.  */
3108
3109       if (TREE_CODE (TREE_OPERAND (arg, 1)) == TRUTH_NOT_EXPR)
3110         return build2_loc (loc, TRUTH_XOR_EXPR, type, TREE_OPERAND (arg, 0),
3111                            TREE_OPERAND (TREE_OPERAND (arg, 1), 0));
3112       else
3113         return build2_loc (loc, TRUTH_XOR_EXPR, type,
3114                            invert_truthvalue_loc (loc, TREE_OPERAND (arg, 0)),
3115                            TREE_OPERAND (arg, 1));
3116
3117     case TRUTH_ANDIF_EXPR:
3118       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3119       loc2 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3120       return build2_loc (loc, TRUTH_ORIF_EXPR, type,
3121                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3122                          invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3123
3124     case TRUTH_ORIF_EXPR:
3125       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3126       loc2 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3127       return build2_loc (loc, TRUTH_ANDIF_EXPR, type,
3128                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)),
3129                          invert_truthvalue_loc (loc2, TREE_OPERAND (arg, 1)));
3130
3131     case TRUTH_NOT_EXPR:
3132       return TREE_OPERAND (arg, 0);
3133
3134     case COND_EXPR:
3135       {
3136         tree arg1 = TREE_OPERAND (arg, 1);
3137         tree arg2 = TREE_OPERAND (arg, 2);
3138
3139         loc1 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3140         loc2 = expr_location_or (TREE_OPERAND (arg, 2), loc);
3141
3142         /* A COND_EXPR may have a throw as one operand, which
3143            then has void type.  Just leave void operands
3144            as they are.  */
3145         return build3_loc (loc, COND_EXPR, type, TREE_OPERAND (arg, 0),
3146                            VOID_TYPE_P (TREE_TYPE (arg1))
3147                            ? arg1 : invert_truthvalue_loc (loc1, arg1),
3148                            VOID_TYPE_P (TREE_TYPE (arg2))
3149                            ? arg2 : invert_truthvalue_loc (loc2, arg2));
3150       }
3151
3152     case COMPOUND_EXPR:
3153       loc1 = expr_location_or (TREE_OPERAND (arg, 1), loc);
3154       return build2_loc (loc, COMPOUND_EXPR, type,
3155                          TREE_OPERAND (arg, 0),
3156                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 1)));
3157
3158     case NON_LVALUE_EXPR:
3159       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3160       return invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0));
3161
3162     CASE_CONVERT:
3163       if (TREE_CODE (TREE_TYPE (arg)) == BOOLEAN_TYPE)
3164         return build1_loc (loc, TRUTH_NOT_EXPR, type, arg);
3165
3166       /* ... fall through ...  */
3167
3168     case FLOAT_EXPR:
3169       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3170       return build1_loc (loc, TREE_CODE (arg), type,
3171                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)));
3172
3173     case BIT_AND_EXPR:
3174       if (!integer_onep (TREE_OPERAND (arg, 1)))
3175         return NULL_TREE;
3176       return build2_loc (loc, EQ_EXPR, type, arg, build_int_cst (type, 0));
3177
3178     case SAVE_EXPR:
3179       return build1_loc (loc, TRUTH_NOT_EXPR, type, arg);
3180
3181     case CLEANUP_POINT_EXPR:
3182       loc1 = expr_location_or (TREE_OPERAND (arg, 0), loc);
3183       return build1_loc (loc, CLEANUP_POINT_EXPR, type,
3184                          invert_truthvalue_loc (loc1, TREE_OPERAND (arg, 0)));
3185
3186     default:
3187       return NULL_TREE;
3188     }
3189 }
3190
3191 /* Return a simplified tree node for the truth-negation of ARG.  This
3192    never alters ARG itself.  We assume that ARG is an operation that
3193    returns a truth value (0 or 1).
3194
3195    FIXME: one would think we would fold the result, but it causes
3196    problems with the dominator optimizer.  */
3197
3198 tree
3199 invert_truthvalue_loc (location_t loc, tree arg)
3200 {
3201   tree tem;
3202
3203   if (TREE_CODE (arg) == ERROR_MARK)
3204     return arg;
3205
3206   tem = fold_truth_not_expr (loc, arg);
3207   if (!tem)
3208     tem = build1_loc (loc, TRUTH_NOT_EXPR, TREE_TYPE (arg), arg);
3209
3210   return tem;
3211 }
3212
3213 /* Given a bit-wise operation CODE applied to ARG0 and ARG1, see if both
3214    operands are another bit-wise operation with a common input.  If so,
3215    distribute the bit operations to save an operation and possibly two if
3216    constants are involved.  For example, convert
3217         (A | B) & (A | C) into A | (B & C)
3218    Further simplification will occur if B and C are constants.
3219
3220    If this optimization cannot be done, 0 will be returned.  */
3221
3222 static tree
3223 distribute_bit_expr (location_t loc, enum tree_code code, tree type,
3224                      tree arg0, tree arg1)
3225 {
3226   tree common;
3227   tree left, right;
3228
3229   if (TREE_CODE (arg0) != TREE_CODE (arg1)
3230       || TREE_CODE (arg0) == code
3231       || (TREE_CODE (arg0) != BIT_AND_EXPR
3232           && TREE_CODE (arg0) != BIT_IOR_EXPR))
3233     return 0;
3234
3235   if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 0), 0))
3236     {
3237       common = TREE_OPERAND (arg0, 0);
3238       left = TREE_OPERAND (arg0, 1);
3239       right = TREE_OPERAND (arg1, 1);
3240     }
3241   else if (operand_equal_p (TREE_OPERAND (arg0, 0), TREE_OPERAND (arg1, 1), 0))
3242     {
3243       common = TREE_OPERAND (arg0, 0);
3244       left = TREE_OPERAND (arg0, 1);
3245       right = TREE_OPERAND (arg1, 0);
3246     }
3247   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 0), 0))
3248     {
3249       common = TREE_OPERAND (arg0, 1);
3250       left = TREE_OPERAND (arg0, 0);
3251       right = TREE_OPERAND (arg1, 1);
3252     }
3253   else if (operand_equal_p (TREE_OPERAND (arg0, 1), TREE_OPERAND (arg1, 1), 0))
3254     {
3255       common = TREE_OPERAND (arg0, 1);
3256       left = TREE_OPERAND (arg0, 0);
3257       right = TREE_OPERAND (arg1, 0);
3258     }
3259   else
3260     return 0;
3261
3262   common = fold_convert_loc (loc, type, common);
3263   left = fold_convert_loc (loc, type, left);
3264   right = fold_convert_loc (loc, type, right);
3265   return fold_build2_loc (loc, TREE_CODE (arg0), type, common,
3266                       fold_build2_loc (loc, code, type, left, right));
3267 }
3268
3269 /* Knowing that ARG0 and ARG1 are both RDIV_EXPRs, simplify a binary operation
3270    with code CODE.  This optimization is unsafe.  */
3271 static tree
3272 distribute_real_division (location_t loc, enum tree_code code, tree type,
3273                           tree arg0, tree arg1)
3274 {
3275   bool mul0 = TREE_CODE (arg0) == MULT_EXPR;
3276   bool mul1 = TREE_CODE (arg1) == MULT_EXPR;
3277
3278   /* (A / C) +- (B / C) -> (A +- B) / C.  */
3279   if (mul0 == mul1
3280       && operand_equal_p (TREE_OPERAND (arg0, 1),
3281                        TREE_OPERAND (arg1, 1), 0))
3282     return fold_build2_loc (loc, mul0 ? MULT_EXPR : RDIV_EXPR, type,
3283                         fold_build2_loc (loc, code, type,
3284                                      TREE_OPERAND (arg0, 0),
3285                                      TREE_OPERAND (arg1, 0)),
3286                         TREE_OPERAND (arg0, 1));
3287
3288   /* (A / C1) +- (A / C2) -> A * (1 / C1 +- 1 / C2).  */
3289   if (operand_equal_p (TREE_OPERAND (arg0, 0),
3290                        TREE_OPERAND (arg1, 0), 0)
3291       && TREE_CODE (TREE_OPERAND (arg0, 1)) == REAL_CST
3292       && TREE_CODE (TREE_OPERAND (arg1, 1)) == REAL_CST)
3293     {
3294       REAL_VALUE_TYPE r0, r1;
3295       r0 = TREE_REAL_CST (TREE_OPERAND (arg0, 1));
3296       r1 = TREE_REAL_CST (TREE_OPERAND (arg1, 1));
3297       if (!mul0)
3298         real_arithmetic (&r0, RDIV_EXPR, &dconst1, &r0);
3299       if (!mul1)
3300         real_arithmetic (&r1, RDIV_EXPR, &dconst1, &r1);
3301       real_arithmetic (&r0, code, &r0, &r1);
3302       return fold_build2_loc (loc, MULT_EXPR, type,
3303                           TREE_OPERAND (arg0, 0),
3304                           build_real (type, r0));
3305     }
3306
3307   return NULL_TREE;
3308 }
3309 \f
3310 /* Return a BIT_FIELD_REF of type TYPE to refer to BITSIZE bits of INNER
3311    starting at BITPOS.  The field is unsigned if UNSIGNEDP is nonzero.  */
3312
3313 static tree
3314 make_bit_field_ref (location_t loc, tree inner, tree type,
3315                     HOST_WIDE_INT bitsize, HOST_WIDE_INT bitpos, int unsignedp)
3316 {
3317   tree result, bftype;
3318
3319   if (bitpos == 0)
3320     {
3321       tree size = TYPE_SIZE (TREE_TYPE (inner));
3322       if ((INTEGRAL_TYPE_P (TREE_TYPE (inner))
3323            || POINTER_TYPE_P (TREE_TYPE (inner)))
3324           && host_integerp (size, 0)
3325           && tree_low_cst (size, 0) == bitsize)
3326         return fold_convert_loc (loc, type, inner);
3327     }
3328
3329   bftype = type;
3330   if (TYPE_PRECISION (bftype) != bitsize
3331       || TYPE_UNSIGNED (bftype) == !unsignedp)
3332     bftype = build_nonstandard_integer_type (bitsize, 0);
3333
3334   result = build3_loc (loc, BIT_FIELD_REF, bftype, inner,
3335                        size_int (bitsize), bitsize_int (bitpos));
3336
3337   if (bftype != type)
3338     result = fold_convert_loc (loc, type, result);
3339
3340   return result;
3341 }
3342
3343 /* Optimize a bit-field compare.
3344
3345    There are two cases:  First is a compare against a constant and the
3346    second is a comparison of two items where the fields are at the same
3347    bit position relative to the start of a chunk (byte, halfword, word)
3348    large enough to contain it.  In these cases we can avoid the shift
3349    implicit in bitfield extractions.
3350
3351    For constants, we emit a compare of the shifted constant with the
3352    BIT_AND_EXPR of a mask and a byte, halfword, or word of the operand being
3353    compared.  For two fields at the same position, we do the ANDs with the
3354    similar mask and compare the result of the ANDs.
3355
3356    CODE is the comparison code, known to be either NE_EXPR or EQ_EXPR.
3357    COMPARE_TYPE is the type of the comparison, and LHS and RHS
3358    are the left and right operands of the comparison, respectively.
3359
3360    If the optimization described above can be done, we return the resulting
3361    tree.  Otherwise we return zero.  */
3362
3363 static tree
3364 optimize_bit_field_compare (location_t loc, enum tree_code code,
3365                             tree compare_type, tree lhs, tree rhs)
3366 {
3367   HOST_WIDE_INT lbitpos, lbitsize, rbitpos, rbitsize, nbitpos, nbitsize;
3368   tree type = TREE_TYPE (lhs);
3369   tree signed_type, unsigned_type;
3370   int const_p = TREE_CODE (rhs) == INTEGER_CST;
3371   enum machine_mode lmode, rmode, nmode;
3372   int lunsignedp, runsignedp;
3373   int lvolatilep = 0, rvolatilep = 0;
3374   tree linner, rinner = NULL_TREE;
3375   tree mask;
3376   tree offset;
3377
3378   /* Get all the information about the extractions being done.  If the bit size
3379      if the same as the size of the underlying object, we aren't doing an
3380      extraction at all and so can do nothing.  We also don't want to
3381      do anything if the inner expression is a PLACEHOLDER_EXPR since we
3382      then will no longer be able to replace it.  */
3383   linner = get_inner_reference (lhs, &lbitsize, &lbitpos, &offset, &lmode,
3384                                 &lunsignedp, &lvolatilep, false);
3385   if (linner == lhs || lbitsize == GET_MODE_BITSIZE (lmode) || lbitsize < 0
3386       || offset != 0 || TREE_CODE (linner) == PLACEHOLDER_EXPR)
3387     return 0;
3388
3389  if (!const_p)
3390    {
3391      /* If this is not a constant, we can only do something if bit positions,
3392         sizes, and signedness are the same.  */
3393      rinner = get_inner_reference (rhs, &rbitsize, &rbitpos, &offset, &rmode,
3394                                    &runsignedp, &rvolatilep, false);
3395
3396      if (rinner == rhs || lbitpos != rbitpos || lbitsize != rbitsize
3397          || lunsignedp != runsignedp || offset != 0
3398          || TREE_CODE (rinner) == PLACEHOLDER_EXPR)
3399        return 0;
3400    }
3401
3402   /* See if we can find a mode to refer to this field.  We should be able to,
3403      but fail if we can't.  */
3404   if (lvolatilep
3405       && GET_MODE_BITSIZE (lmode) > 0
3406       && flag_strict_volatile_bitfields > 0)
3407     nmode = lmode;
3408   else
3409     nmode = get_best_mode (lbitsize, lbitpos, 0, 0,
3410                            const_p ? TYPE_ALIGN (TREE_TYPE (linner))
3411                            : MIN (TYPE_ALIGN (TREE_TYPE (linner)),
3412                                   TYPE_ALIGN (TREE_TYPE (rinner))),
3413                            word_mode, lvolatilep || rvolatilep);
3414   if (nmode == VOIDmode)
3415     return 0;
3416
3417   /* Set signed and unsigned types of the precision of this mode for the
3418      shifts below.  */
3419   signed_type = lang_hooks.types.type_for_mode (nmode, 0);
3420   unsigned_type = lang_hooks.types.type_for_mode (nmode, 1);
3421
3422   /* Compute the bit position and size for the new reference and our offset
3423      within it. If the new reference is the same size as the original, we
3424      won't optimize anything, so return zero.  */
3425   nbitsize = GET_MODE_BITSIZE (nmode);
3426   nbitpos = lbitpos & ~ (nbitsize - 1);
3427   lbitpos -= nbitpos;
3428   if (nbitsize == lbitsize)
3429     return 0;
3430
3431   if (BYTES_BIG_ENDIAN)
3432     lbitpos = nbitsize - lbitsize - lbitpos;
3433
3434   /* Make the mask to be used against the extracted field.  */
3435   mask = build_int_cst_type (unsigned_type, -1);
3436   mask = const_binop (LSHIFT_EXPR, mask, size_int (nbitsize - lbitsize));
3437   mask = const_binop (RSHIFT_EXPR, mask,
3438                       size_int (nbitsize - lbitsize - lbitpos));
3439
3440   if (! const_p)
3441     /* If not comparing with constant, just rework the comparison
3442        and return.  */
3443     return fold_build2_loc (loc, code, compare_type,
3444                         fold_build2_loc (loc, BIT_AND_EXPR, unsigned_type,
3445                                      make_bit_field_ref (loc, linner,
3446                                                          unsigned_type,
3447                                                          nbitsize, nbitpos,
3448                                                          1),
3449                                      mask),
3450                         fold_build2_loc (loc, BIT_AND_EXPR, unsigned_type,
3451                                      make_bit_field_ref (loc, rinner,
3452                                                          unsigned_type,
3453                                                          nbitsize, nbitpos,
3454                                                          1),
3455                                      mask));
3456
3457   /* Otherwise, we are handling the constant case. See if the constant is too
3458      big for the field.  Warn and return a tree of for 0 (false) if so.  We do
3459      this not only for its own sake, but to avoid having to test for this
3460      error case below.  If we didn't, we might generate wrong code.
3461
3462      For unsigned fields, the constant shifted right by the field length should
3463      be all zero.  For signed fields, the high-order bits should agree with
3464      the sign bit.  */
3465
3466   if (lunsignedp)
3467     {
3468       if (! integer_zerop (const_binop (RSHIFT_EXPR,
3469                                         fold_convert_loc (loc,
3470                                                           unsigned_type, rhs),
3471                                         size_int (lbitsize))))
3472         {
3473           warning (0, "comparison is always %d due to width of bit-field",
3474                    code == NE_EXPR);
3475           return constant_boolean_node (code == NE_EXPR, compare_type);
3476         }
3477     }
3478   else
3479     {
3480       tree tem = const_binop (RSHIFT_EXPR,
3481                               fold_convert_loc (loc, signed_type, rhs),
3482                               size_int (lbitsize - 1));
3483       if (! integer_zerop (tem) && ! integer_all_onesp (tem))
3484         {
3485           warning (0, "comparison is always %d due to width of bit-field",
3486                    code == NE_EXPR);
3487           return constant_boolean_node (code == NE_EXPR, compare_type);
3488         }
3489     }
3490
3491   /* Single-bit compares should always be against zero.  */
3492   if (lbitsize == 1 && ! integer_zerop (rhs))
3493     {
3494       code = code == EQ_EXPR ? NE_EXPR : EQ_EXPR;
3495       rhs = build_int_cst (type, 0);
3496     }
3497
3498   /* Make a new bitfield reference, shift the constant over the
3499      appropriate number of bits and mask it with the computed mask
3500      (in case this was a signed field).  If we changed it, make a new one.  */
3501   lhs = make_bit_field_ref (loc, linner, unsigned_type, nbitsize, nbitpos, 1);
3502   if (lvolatilep)
3503     {
3504       TREE_SIDE_EFFECTS (lhs) = 1;
3505       TREE_THIS_VOLATILE (lhs) = 1;
3506     }
3507
3508   rhs = const_binop (BIT_AND_EXPR,
3509                      const_binop (LSHIFT_EXPR,
3510                                   fold_convert_loc (loc, unsigned_type, rhs),
3511                                   size_int (lbitpos)),
3512                      mask);
3513
3514   lhs = build2_loc (loc, code, compare_type,
3515                     build2 (BIT_AND_EXPR, unsigned_type, lhs, mask), rhs);
3516   return lhs;
3517 }
3518 \f
3519 /* Subroutine for fold_truth_andor_1: decode a field reference.
3520
3521    If EXP is a comparison reference, we return the innermost reference.
3522
3523    *PBITSIZE is set to the number of bits in the reference, *PBITPOS is
3524    set to the starting bit number.
3525
3526    If the innermost field can be completely contained in a mode-sized
3527    unit, *PMODE is set to that mode.  Otherwise, it is set to VOIDmode.
3528
3529    *PVOLATILEP is set to 1 if the any expression encountered is volatile;
3530    otherwise it is not changed.
3531
3532    *PUNSIGNEDP is set to the signedness of the field.
3533
3534    *PMASK is set to the mask used.  This is either contained in a
3535    BIT_AND_EXPR or derived from the width of the field.
3536
3537    *PAND_MASK is set to the mask found in a BIT_AND_EXPR, if any.
3538
3539    Return 0 if this is not a component reference or is one that we can't
3540    do anything with.  */
3541
3542 static tree
3543 decode_field_reference (location_t loc, tree exp, HOST_WIDE_INT *pbitsize,
3544                         HOST_WIDE_INT *pbitpos, enum machine_mode *pmode,
3545                         int *punsignedp, int *pvolatilep,
3546                         tree *pmask, tree *pand_mask)
3547 {
3548   tree outer_type = 0;
3549   tree and_mask = 0;
3550   tree mask, inner, offset;
3551   tree unsigned_type;
3552   unsigned int precision;
3553
3554   /* All the optimizations using this function assume integer fields.
3555      There are problems with FP fields since the type_for_size call
3556      below can fail for, e.g., XFmode.  */
3557   if (! INTEGRAL_TYPE_P (TREE_TYPE (exp)))
3558     return 0;
3559
3560   /* We are interested in the bare arrangement of bits, so strip everything
3561      that doesn't affect the machine mode.  However, record the type of the
3562      outermost expression if it may matter below.  */
3563   if (CONVERT_EXPR_P (exp)
3564       || TREE_CODE (exp) == NON_LVALUE_EXPR)
3565     outer_type = TREE_TYPE (exp);
3566   STRIP_NOPS (exp);
3567
3568   if (TREE_CODE (exp) == BIT_AND_EXPR)
3569     {
3570       and_mask = TREE_OPERAND (exp, 1);
3571       exp = TREE_OPERAND (exp, 0);
3572       STRIP_NOPS (exp); STRIP_NOPS (and_mask);
3573       if (TREE_CODE (and_mask) != INTEGER_CST)
3574         return 0;
3575     }
3576
3577   inner = get_inner_reference (exp, pbitsize, pbitpos, &offset, pmode,
3578                                punsignedp, pvolatilep, false);
3579   if ((inner == exp && and_mask == 0)
3580       || *pbitsize < 0 || offset != 0
3581       || TREE_CODE (inner) == PLACEHOLDER_EXPR)
3582     return 0;
3583
3584   /* If the number of bits in the reference is the same as the bitsize of
3585      the outer type, then the outer type gives the signedness. Otherwise
3586      (in case of a small bitfield) the signedness is unchanged.  */
3587   if (outer_type && *pbitsize == TYPE_PRECISION (outer_type))
3588     *punsignedp = TYPE_UNSIGNED (outer_type);
3589
3590   /* Compute the mask to access the bitfield.  */
3591   unsigned_type = lang_hooks.types.type_for_size (*pbitsize, 1);
3592   precision = TYPE_PRECISION (unsigned_type);
3593
3594   mask = build_int_cst_type (unsigned_type, -1);
3595
3596   mask = const_binop (LSHIFT_EXPR, mask, size_int (precision - *pbitsize));
3597   mask = const_binop (RSHIFT_EXPR, mask, size_int (precision - *pbitsize));
3598
3599   /* Merge it with the mask we found in the BIT_AND_EXPR, if any.  */
3600   if (and_mask != 0)
3601     mask = fold_build2_loc (loc, BIT_AND_EXPR, unsigned_type,
3602                         fold_convert_loc (loc, unsigned_type, and_mask), mask);
3603
3604   *pmask = mask;
3605   *pand_mask = and_mask;
3606   return inner;
3607 }
3608
3609 /* Return nonzero if MASK represents a mask of SIZE ones in the low-order
3610    bit positions.  */
3611
3612 static int
3613 all_ones_mask_p (const_tree mask, int size)
3614 {
3615   tree type = TREE_TYPE (mask);
3616   unsigned int precision = TYPE_PRECISION (type);
3617   tree tmask;
3618
3619   tmask = build_int_cst_type (signed_type_for (type), -1);
3620
3621   return
3622     tree_int_cst_equal (mask,
3623                         const_binop (RSHIFT_EXPR,
3624                                      const_binop (LSHIFT_EXPR, tmask,
3625                                                   size_int (precision - size)),
3626                                      size_int (precision - size)));
3627 }
3628
3629 /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
3630    represents the sign bit of EXP's type.  If EXP represents a sign
3631    or zero extension, also test VAL against the unextended type.
3632    The return value is the (sub)expression whose sign bit is VAL,
3633    or NULL_TREE otherwise.  */
3634
3635 static tree
3636 sign_bit_p (tree exp, const_tree val)
3637 {
3638   unsigned HOST_WIDE_INT mask_lo, lo;
3639   HOST_WIDE_INT mask_hi, hi;
3640   int width;
3641   tree t;
3642
3643   /* Tree EXP must have an integral type.  */
3644   t = TREE_TYPE (exp);
3645   if (! INTEGRAL_TYPE_P (t))
3646     return NULL_TREE;
3647
3648   /* Tree VAL must be an integer constant.  */
3649   if (TREE_CODE (val) != INTEGER_CST
3650       || TREE_OVERFLOW (val))
3651     return NULL_TREE;
3652
3653   width = TYPE_PRECISION (t);
3654   if (width > HOST_BITS_PER_WIDE_INT)
3655     {
3656       hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
3657       lo = 0;
3658
3659       mask_hi = ((unsigned HOST_WIDE_INT) -1
3660                  >> (2 * HOST_BITS_PER_WIDE_INT - width));
3661       mask_lo = -1;
3662     }
3663   else
3664     {
3665       hi = 0;
3666       lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
3667
3668       mask_hi = 0;
3669       mask_lo = ((unsigned HOST_WIDE_INT) -1
3670                  >> (HOST_BITS_PER_WIDE_INT - width));
3671     }
3672
3673   /* We mask off those bits beyond TREE_TYPE (exp) so that we can
3674      treat VAL as if it were unsigned.  */
3675   if ((TREE_INT_CST_HIGH (val) & mask_hi) == hi
3676       && (TREE_INT_CST_LOW (val) & mask_lo) == lo)
3677     return exp;
3678
3679   /* Handle extension from a narrower type.  */
3680   if (TREE_CODE (exp) == NOP_EXPR
3681       && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
3682     return sign_bit_p (TREE_OPERAND (exp, 0), val);
3683
3684   return NULL_TREE;
3685 }
3686
3687 /* Subroutine for fold_truth_andor_1: determine if an operand is simple enough
3688    to be evaluated unconditionally.  */
3689
3690 static int
3691 simple_operand_p (const_tree exp)
3692 {
3693   /* Strip any conversions that don't change the machine mode.  */
3694   STRIP_NOPS (exp);
3695
3696   return (CONSTANT_CLASS_P (exp)
3697           || TREE_CODE (exp) == SSA_NAME
3698           || (DECL_P (exp)
3699               && ! TREE_ADDRESSABLE (exp)
3700               && ! TREE_THIS_VOLATILE (exp)
3701               && ! DECL_NONLOCAL (exp)
3702               /* Don't regard global variables as simple.  They may be
3703                  allocated in ways unknown to the compiler (shared memory,
3704                  #pragma weak, etc).  */
3705               && ! TREE_PUBLIC (exp)
3706               && ! DECL_EXTERNAL (exp)
3707               /* Loading a static variable is unduly expensive, but global
3708                  registers aren't expensive.  */
3709               && (! TREE_STATIC (exp) || DECL_REGISTER (exp))));
3710 }
3711
3712 /* Subroutine for fold_truth_andor: determine if an operand is simple enough
3713    to be evaluated unconditionally.
3714    I addition to simple_operand_p, we assume that comparisons, conversions,
3715    and logic-not operations are simple, if their operands are simple, too.  */
3716
3717 static bool
3718 simple_operand_p_2 (tree exp)
3719 {
3720   enum tree_code code;
3721
3722   if (TREE_SIDE_EFFECTS (exp)
3723       || tree_could_trap_p (exp))
3724     return false;
3725
3726   while (CONVERT_EXPR_P (exp))
3727     exp = TREE_OPERAND (exp, 0);
3728
3729   code = TREE_CODE (exp);
3730
3731   if (TREE_CODE_CLASS (code) == tcc_comparison)
3732     return (simple_operand_p (TREE_OPERAND (exp, 0))
3733             && simple_operand_p (TREE_OPERAND (exp, 1)));
3734
3735   if (code == TRUTH_NOT_EXPR)
3736       return simple_operand_p_2 (TREE_OPERAND (exp, 0));
3737
3738   return simple_operand_p (exp);
3739 }
3740
3741 \f
3742 /* The following functions are subroutines to fold_range_test and allow it to
3743    try to change a logical combination of comparisons into a range test.
3744
3745    For example, both
3746         X == 2 || X == 3 || X == 4 || X == 5
3747    and
3748         X >= 2 && X <= 5
3749    are converted to
3750         (unsigned) (X - 2) <= 3
3751
3752    We describe each set of comparisons as being either inside or outside
3753    a range, using a variable named like IN_P, and then describe the
3754    range with a lower and upper bound.  If one of the bounds is omitted,
3755    it represents either the highest or lowest value of the type.
3756
3757    In the comments below, we represent a range by two numbers in brackets
3758    preceded by a "+" to designate being inside that range, or a "-" to
3759    designate being outside that range, so the condition can be inverted by
3760    flipping the prefix.  An omitted bound is represented by a "-".  For
3761    example, "- [-, 10]" means being outside the range starting at the lowest
3762    possible value and ending at 10, in other words, being greater than 10.
3763    The range "+ [-, -]" is always true and hence the range "- [-, -]" is
3764    always false.
3765
3766    We set up things so that the missing bounds are handled in a consistent
3767    manner so neither a missing bound nor "true" and "false" need to be
3768    handled using a special case.  */
3769
3770 /* Return the result of applying CODE to ARG0 and ARG1, but handle the case
3771    of ARG0 and/or ARG1 being omitted, meaning an unlimited range. UPPER0_P
3772    and UPPER1_P are nonzero if the respective argument is an upper bound
3773    and zero for a lower.  TYPE, if nonzero, is the type of the result; it
3774    must be specified for a comparison.  ARG1 will be converted to ARG0's
3775    type if both are specified.  */
3776
3777 static tree
3778 range_binop (enum tree_code code, tree type, tree arg0, int upper0_p,
3779              tree arg1, int upper1_p)
3780 {
3781   tree tem;
3782   int result;
3783   int sgn0, sgn1;
3784
3785   /* If neither arg represents infinity, do the normal operation.
3786      Else, if not a comparison, return infinity.  Else handle the special
3787      comparison rules. Note that most of the cases below won't occur, but
3788      are handled for consistency.  */
3789
3790   if (arg0 != 0 && arg1 != 0)
3791     {
3792       tem = fold_build2 (code, type != 0 ? type : TREE_TYPE (arg0),
3793                          arg0, fold_convert (TREE_TYPE (arg0), arg1));
3794       STRIP_NOPS (tem);
3795       return TREE_CODE (tem) == INTEGER_CST ? tem : 0;
3796     }
3797
3798   if (TREE_CODE_CLASS (code) != tcc_comparison)
3799     return 0;
3800
3801   /* Set SGN[01] to -1 if ARG[01] is a lower bound, 1 for upper, and 0
3802      for neither.  In real maths, we cannot assume open ended ranges are
3803      the same. But, this is computer arithmetic, where numbers are finite.
3804      We can therefore make the transformation of any unbounded range with
3805      the value Z, Z being greater than any representable number. This permits
3806      us to treat unbounded ranges as equal.  */
3807   sgn0 = arg0 != 0 ? 0 : (upper0_p ? 1 : -1);
3808   sgn1 = arg1 != 0 ? 0 : (upper1_p ? 1 : -1);
3809   switch (code)
3810     {
3811     case EQ_EXPR:
3812       result = sgn0 == sgn1;
3813       break;
3814     case NE_EXPR:
3815       result = sgn0 != sgn1;
3816       break;
3817     case LT_EXPR:
3818       result = sgn0 < sgn1;
3819       break;
3820     case LE_EXPR:
3821       result = sgn0 <= sgn1;
3822       break;
3823     case GT_EXPR:
3824       result = sgn0 > sgn1;
3825       break;
3826     case GE_EXPR:
3827       result = sgn0 >= sgn1;
3828       break;
3829     default:
3830       gcc_unreachable ();
3831     }
3832
3833   return constant_boolean_node (result, type);
3834 }
3835 \f
3836 /* Helper routine for make_range.  Perform one step for it, return
3837    new expression if the loop should continue or NULL_TREE if it should
3838    stop.  */
3839
3840 tree
3841 make_range_step (location_t loc, enum tree_code code, tree arg0, tree arg1,
3842                  tree exp_type, tree *p_low, tree *p_high, int *p_in_p,
3843                  bool *strict_overflow_p)
3844 {
3845   tree arg0_type = TREE_TYPE (arg0);
3846   tree n_low, n_high, low = *p_low, high = *p_high;
3847   int in_p = *p_in_p, n_in_p;
3848
3849   switch (code)
3850     {
3851     case TRUTH_NOT_EXPR:
3852       /* We can only do something if the range is testing for zero.  */
3853       if (low == NULL_TREE || high == NULL_TREE
3854           || ! integer_zerop (low) || ! integer_zerop (high))
3855         return NULL_TREE;
3856       *p_in_p = ! in_p;
3857       return arg0;
3858
3859     case EQ_EXPR: case NE_EXPR:
3860     case LT_EXPR: case LE_EXPR: case GE_EXPR: case GT_EXPR:
3861       /* We can only do something if the range is testing for zero
3862          and if the second operand is an integer constant.  Note that
3863          saying something is "in" the range we make is done by
3864          complementing IN_P since it will set in the initial case of
3865          being not equal to zero; "out" is leaving it alone.  */
3866       if (low == NULL_TREE || high == NULL_TREE
3867           || ! integer_zerop (low) || ! integer_zerop (high)
3868           || TREE_CODE (arg1) != INTEGER_CST)
3869         return NULL_TREE;
3870
3871       switch (code)
3872         {
3873         case NE_EXPR:  /* - [c, c]  */
3874           low = high = arg1;
3875           break;
3876         case EQ_EXPR:  /* + [c, c]  */
3877           in_p = ! in_p, low = high = arg1;
3878           break;
3879         case GT_EXPR:  /* - [-, c] */
3880           low = 0, high = arg1;
3881           break;
3882         case GE_EXPR:  /* + [c, -] */
3883           in_p = ! in_p, low = arg1, high = 0;
3884           break;
3885         case LT_EXPR:  /* - [c, -] */
3886           low = arg1, high = 0;
3887           break;
3888         case LE_EXPR:  /* + [-, c] */
3889           in_p = ! in_p, low = 0, high = arg1;
3890           break;
3891         default:
3892           gcc_unreachable ();
3893         }
3894
3895       /* If this is an unsigned comparison, we also know that EXP is
3896          greater than or equal to zero.  We base the range tests we make
3897          on that fact, so we record it here so we can parse existing
3898          range tests.  We test arg0_type since often the return type
3899          of, e.g. EQ_EXPR, is boolean.  */
3900       if (TYPE_UNSIGNED (arg0_type) && (low == 0 || high == 0))
3901         {
3902           if (! merge_ranges (&n_in_p, &n_low, &n_high,
3903                               in_p, low, high, 1,
3904                               build_int_cst (arg0_type, 0),
3905                               NULL_TREE))
3906             return NULL_TREE;
3907
3908           in_p = n_in_p, low = n_low, high = n_high;
3909
3910           /* If the high bound is missing, but we have a nonzero low
3911              bound, reverse the range so it goes from zero to the low bound
3912              minus 1.  */
3913           if (high == 0 && low && ! integer_zerop (low))
3914             {
3915               in_p = ! in_p;
3916               high = range_binop (MINUS_EXPR, NULL_TREE, low, 0,
3917                                   integer_one_node, 0);
3918               low = build_int_cst (arg0_type, 0);
3919             }
3920         }
3921
3922       *p_low = low;
3923       *p_high = high;
3924       *p_in_p = in_p;
3925       return arg0;
3926
3927     case NEGATE_EXPR:
3928       /* If flag_wrapv and ARG0_TYPE is signed, make sure
3929          low and high are non-NULL, then normalize will DTRT.  */
3930       if (!TYPE_UNSIGNED (arg0_type)
3931           && !TYPE_OVERFLOW_UNDEFINED (arg0_type))
3932         {
3933           if (low == NULL_TREE)
3934             low = TYPE_MIN_VALUE (arg0_type);
3935           if (high == NULL_TREE)
3936             high = TYPE_MAX_VALUE (arg0_type);
3937         }
3938
3939       /* (-x) IN [a,b] -> x in [-b, -a]  */
3940       n_low = range_binop (MINUS_EXPR, exp_type,
3941                            build_int_cst (exp_type, 0),
3942                            0, high, 1);
3943       n_high = range_binop (MINUS_EXPR, exp_type,
3944                             build_int_cst (exp_type, 0),
3945                             0, low, 0);
3946       if (n_high != 0 && TREE_OVERFLOW (n_high))
3947         return NULL_TREE;
3948       goto normalize;
3949
3950     case BIT_NOT_EXPR:
3951       /* ~ X -> -X - 1  */
3952       return build2_loc (loc, MINUS_EXPR, exp_type, negate_expr (arg0),
3953                          build_int_cst (exp_type, 1));
3954
3955     case PLUS_EXPR:
3956     case MINUS_EXPR:
3957       if (TREE_CODE (arg1) != INTEGER_CST)
3958         return NULL_TREE;
3959
3960       /* If flag_wrapv and ARG0_TYPE is signed, then we cannot
3961          move a constant to the other side.  */
3962       if (!TYPE_UNSIGNED (arg0_type)
3963           && !TYPE_OVERFLOW_UNDEFINED (arg0_type))
3964         return NULL_TREE;
3965
3966       /* If EXP is signed, any overflow in the computation is undefined,
3967          so we don't worry about it so long as our computations on
3968          the bounds don't overflow.  For unsigned, overflow is defined
3969          and this is exactly the right thing.  */
3970       n_low = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3971                            arg0_type, low, 0, arg1, 0);
3972       n_high = range_binop (code == MINUS_EXPR ? PLUS_EXPR : MINUS_EXPR,
3973                             arg0_type, high, 1, arg1, 0);
3974       if ((n_low != 0 && TREE_OVERFLOW (n_low))
3975           || (n_high != 0 && TREE_OVERFLOW (n_high)))
3976         return NULL_TREE;
3977
3978       if (TYPE_OVERFLOW_UNDEFINED (arg0_type))
3979         *strict_overflow_p = true;
3980
3981       normalize:
3982         /* Check for an unsigned range which has wrapped around the maximum
3983            value thus making n_high < n_low, and normalize it.  */
3984         if (n_low && n_high && tree_int_cst_lt (n_high, n_low))
3985           {
3986             low = range_binop (PLUS_EXPR, arg0_type, n_high, 0,
3987                                integer_one_node, 0);
3988             high = range_binop (MINUS_EXPR, arg0_type, n_low, 0,
3989                                 integer_one_node, 0);
3990
3991             /* If the range is of the form +/- [ x+1, x ], we won't
3992                be able to normalize it.  But then, it represents the
3993                whole range or the empty set, so make it
3994                +/- [ -, - ].  */
3995             if (tree_int_cst_equal (n_low, low)
3996                 && tree_int_cst_equal (n_high, high))
3997               low = high = 0;
3998             else
3999               in_p = ! in_p;
4000           }
4001         else
4002           low = n_low, high = n_high;
4003
4004         *p_low = low;
4005         *p_high = high;
4006         *p_in_p = in_p;
4007         return arg0;
4008
4009     CASE_CONVERT:
4010     case NON_LVALUE_EXPR:
4011       if (TYPE_PRECISION (arg0_type) > TYPE_PRECISION (exp_type))
4012         return NULL_TREE;
4013
4014       if (! INTEGRAL_TYPE_P (arg0_type)
4015           || (low != 0 && ! int_fits_type_p (low, arg0_type))
4016           || (high != 0 && ! int_fits_type_p (high, arg0_type)))
4017         return NULL_TREE;
4018
4019       n_low = low, n_high = high;
4020
4021       if (n_low != 0)
4022         n_low = fold_convert_loc (loc, arg0_type, n_low);
4023
4024       if (n_high != 0)
4025         n_high = fold_convert_loc (loc, arg0_type, n_high);
4026
4027       /* If we're converting arg0 from an unsigned type, to exp,
4028          a signed type,  we will be doing the comparison as unsigned.
4029          The tests above have already verified that LOW and HIGH
4030          are both positive.
4031
4032          So we have to ensure that we will handle large unsigned
4033          values the same way that the current signed bounds treat
4034          negative values.  */
4035
4036       if (!TYPE_UNSIGNED (exp_type) && TYPE_UNSIGNED (arg0_type))
4037         {
4038           tree high_positive;
4039           tree equiv_type;
4040           /* For fixed-point modes, we need to pass the saturating flag
4041              as the 2nd parameter.  */
4042           if (ALL_FIXED_POINT_MODE_P (TYPE_MODE (arg0_type)))
4043             equiv_type