OSDN Git Service

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