OSDN Git Service

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