OSDN Git Service

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