OSDN Git Service

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