OSDN Git Service

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