gcc/tree.c

   1 /* Language-independent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains the low level primitives for operating on tree nodes,
  23    including allocation, list operations, interning of identifiers,
  24    construction of data type nodes and statement nodes,
  25    and construction of type conversion nodes.  It also contains
  26    tables index by tree code that describe how to take apart
  27    nodes of that code.
  28
  29    It is intended to be language-independent, but occasionally
  30    calls language-dependent routines defined (for C) in typecheck.c.  */
  31
  32 #include "config.h"
  33 #include "system.h"
  34 #include "coretypes.h"
  35 #include "tm.h"
  36 #include "flags.h"
  37 #include "tree.h"
  38 #include "real.h"
  39 #include "tm_p.h"
  40 #include "function.h"
  41 #include "obstack.h"
  42 #include "toplev.h"
  43 #include "ggc.h"
  44 #include "hashtab.h"
  45 #include "output.h"
  46 #include "target.h"
  47 #include "langhooks.h"
  48
  49 /* obstack.[ch] explicitly declined to prototype this.  */
  50 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  51
  52 #ifdef GATHER_STATISTICS
  53 /* Statistics-gathering stuff.  */
  54
  55 int tree_node_counts[(int) all_kinds];
  56 int tree_node_sizes[(int) all_kinds];
  57
  58 /* Keep in sync with tree.h:enum tree_node_kind.  */
  59 static const char * const tree_node_kind_names[] = {
  60   "decls",
  61   "types",
  62   "blocks",
  63   "stmts",
  64   "refs",
  65   "exprs",
  66   "constants",
  67   "identifiers",
  68   "perm_tree_lists",
  69   "temp_tree_lists",
  70   "vecs",
  71   "random kinds",
  72   "lang_decl kinds",
  73   "lang_type kinds"
  74 };
  75 #endif /* GATHER_STATISTICS */
  76
  77 /* Unique id for next decl created.  */
  78 static GTY(()) int next_decl_uid;
  79 /* Unique id for next type created.  */
  80 static GTY(()) int next_type_uid = 1;
  81
  82 /* Since we cannot rehash a type after it is in the table, we have to
  83    keep the hash code.  */
  84
  85 struct type_hash GTY(())
  86 {
  87   unsigned long hash;
  88   tree type;
  89 };
  90
  91 /* Initial size of the hash table (rounded to next prime).  */
  92 #define TYPE_HASH_INITIAL_SIZE 1000
  93
  94 /* Now here is the hash table.  When recording a type, it is added to
  95    the slot whose index is the hash code.  Note that the hash table is
  96    used for several kinds of types (function types, array types and
  97    array index range types, for now).  While all these live in the
  98    same table, they are completely independent, and the hash code is
  99    computed differently for each of these.  */
 100
 101 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 102      htab_t type_hash_table;
 103
 104 static void set_type_quals (tree, int);
 105 static int type_hash_eq (const void *, const void *);
 106 static hashval_t type_hash_hash (const void *);
 107 static void print_type_hash_statistics (void);
 108 static void finish_vector_type (tree);
 109 static tree make_vector (enum machine_mode, tree, int);
 110 static int type_hash_marked_p (const void *);
 111
 112 tree global_trees[TI_MAX];
 113 tree integer_types[itk_none];
 114 \f
 115 /* Init tree.c.  */
 116
 117 void
 118 init_ttree (void)
 119 {
 120   /* Initialize the hash table of types.  */
 121   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 122                                      type_hash_eq, 0);
 123 }
 124
 125 \f
 126 /* The name of the object as the assembler will see it (but before any
 127    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 128    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 129 tree
 130 decl_assembler_name (tree decl)
 131 {
 132   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 133     (*lang_hooks.set_decl_assembler_name) (decl);
 134   return DECL_CHECK (decl)->decl.assembler_name;
 135 }
 136
 137 /* Compute the number of bytes occupied by 'node'.  This routine only
 138    looks at TREE_CODE and, if the code is TREE_VEC, TREE_VEC_LENGTH.  */
 139 size_t
 140 tree_size (tree node)
 141 {
 142   enum tree_code code = TREE_CODE (node);
 143
 144   switch (TREE_CODE_CLASS (code))
 145     {
 146     case 'd':  /* A decl node */
 147       return sizeof (struct tree_decl);
 148
 149     case 't':  /* a type node */
 150       return sizeof (struct tree_type);
 151
 152     case 'b':  /* a lexical block node */
 153       return sizeof (struct tree_block);
 154
 155     case 'r':  /* a reference */
 156     case 'e':  /* an expression */
 157     case 's':  /* an expression with side effects */
 158     case '<':  /* a comparison expression */
 159     case '1':  /* a unary arithmetic expression */
 160     case '2':  /* a binary arithmetic expression */
 161       return (sizeof (struct tree_exp)
 162               + TREE_CODE_LENGTH (code) * sizeof (char *) - sizeof (char *));
 163
 164     case 'c':  /* a constant */
 165       switch (code)
 166         {
 167         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 168         case REAL_CST:          return sizeof (struct tree_real_cst);
 169         case COMPLEX_CST:       return sizeof (struct tree_complex);
 170         case VECTOR_CST:        return sizeof (struct tree_vector);
 171         case STRING_CST:        return sizeof (struct tree_string);
 172         default:
 173           return (*lang_hooks.tree_size) (code);
 174         }
 175
 176     case 'x':  /* something random, like an identifier.  */
 177       switch (code)
 178         {
 179         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 180         case TREE_LIST:         return sizeof (struct tree_list);
 181         case TREE_VEC:          return (sizeof (struct tree_vec)
 182                                         + TREE_VEC_LENGTH(node) * sizeof(char *)
 183                                         - sizeof (char *));
 184
 185         case ERROR_MARK:
 186         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 187
 188         default:
 189           return (*lang_hooks.tree_size) (code);
 190         }
 191
 192     default:
 193       abort ();
 194     }
 195 }
 196
 197 /* Return a newly allocated node of code CODE.
 198    For decl and type nodes, some other fields are initialized.
 199    The rest of the node is initialized to zero.
 200
 201    Achoo!  I got a code in the node.  */
 202
 203 tree
 204 make_node (enum tree_code code)
 205 {
 206   tree t;
 207   int type = TREE_CODE_CLASS (code);
 208   size_t length;
 209 #ifdef GATHER_STATISTICS
 210   tree_node_kind kind;
 211 #endif
 212   struct tree_common ttmp;
 213
 214   /* We can't allocate a TREE_VEC without knowing how many elements
 215      it will have.  */
 216   if (code == TREE_VEC)
 217     abort ();
 218
 219   TREE_SET_CODE ((tree)&ttmp, code);
 220   length = tree_size ((tree)&ttmp);
 221
 222 #ifdef GATHER_STATISTICS
 223   switch (type)
 224     {
 225     case 'd':  /* A decl node */
 226       kind = d_kind;
 227       break;
 228
 229     case 't':  /* a type node */
 230       kind = t_kind;
 231       break;
 232
 233     case 'b':  /* a lexical block */
 234       kind = b_kind;
 235       break;
 236
 237     case 's':  /* an expression with side effects */
 238       kind = s_kind;
 239       break;
 240
 241     case 'r':  /* a reference */
 242       kind = r_kind;
 243       break;
 244
 245     case 'e':  /* an expression */
 246     case '<':  /* a comparison expression */
 247     case '1':  /* a unary arithmetic expression */
 248     case '2':  /* a binary arithmetic expression */
 249       kind = e_kind;
 250       break;
 251
 252     case 'c':  /* a constant */
 253       kind = c_kind;
 254       break;
 255
 256     case 'x':  /* something random, like an identifier.  */
 257       if (code == IDENTIFIER_NODE)
 258         kind = id_kind;
 259       else if (code == TREE_VEC)
 260         kind = vec_kind;
 261       else
 262         kind = x_kind;
 263       break;
 264
 265     default:
 266       abort ();
 267     }
 268
 269   tree_node_counts[(int) kind]++;
 270   tree_node_sizes[(int) kind] += length;
 271 #endif
 272
 273   t = ggc_alloc_tree (length);
 274
 275   memset (t, 0, length);
 276
 277   TREE_SET_CODE (t, code);
 278
 279   switch (type)
 280     {
 281     case 's':
 282       TREE_SIDE_EFFECTS (t) = 1;
 283       break;
 284
 285     case 'd':
 286       if (code != FUNCTION_DECL)
 287         DECL_ALIGN (t) = 1;
 288       DECL_USER_ALIGN (t) = 0;
 289       DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 290       DECL_SOURCE_LOCATION (t) = input_location;
 291       DECL_UID (t) = next_decl_uid++;
 292
 293       /* We have not yet computed the alias set for this declaration.  */
 294       DECL_POINTER_ALIAS_SET (t) = -1;
 295       break;
 296
 297     case 't':
 298       TYPE_UID (t) = next_type_uid++;
 299       TYPE_ALIGN (t) = char_type_node ? TYPE_ALIGN (char_type_node) : 0;
 300       TYPE_USER_ALIGN (t) = 0;
 301       TYPE_MAIN_VARIANT (t) = t;
 302
 303       /* Default to no attributes for type, but let target change that.  */
 304       TYPE_ATTRIBUTES (t) = NULL_TREE;
 305       (*targetm.set_default_type_attributes) (t);
 306
 307       /* We have not yet computed the alias set for this type.  */
 308       TYPE_ALIAS_SET (t) = -1;
 309       break;
 310
 311     case 'c':
 312       TREE_CONSTANT (t) = 1;
 313       break;
 314
 315     case 'e':
 316       switch (code)
 317         {
 318         case INIT_EXPR:
 319         case MODIFY_EXPR:
 320         case VA_ARG_EXPR:
 321         case RTL_EXPR:
 322         case PREDECREMENT_EXPR:
 323         case PREINCREMENT_EXPR:
 324         case POSTDECREMENT_EXPR:
 325         case POSTINCREMENT_EXPR:
 326           /* All of these have side-effects, no matter what their
 327              operands are.  */
 328           TREE_SIDE_EFFECTS (t) = 1;
 329           break;
 330
 331         default:
 332           break;
 333         }
 334       break;
 335     }
 336
 337   return t;
 338 }
 339 \f
 340 /* Return a new node with the same contents as NODE except that its
 341    TREE_CHAIN is zero and it has a fresh uid.  */
 342
 343 tree
 344 copy_node (tree node)
 345 {
 346   tree t;
 347   enum tree_code code = TREE_CODE (node);
 348   size_t length;
 349
 350   length = tree_size (node);
 351   t = ggc_alloc_tree (length);
 352   memcpy (t, node, length);
 353
 354   TREE_CHAIN (t) = 0;
 355   TREE_ASM_WRITTEN (t) = 0;
 356
 357   if (TREE_CODE_CLASS (code) == 'd')
 358     DECL_UID (t) = next_decl_uid++;
 359   else if (TREE_CODE_CLASS (code) == 't')
 360     {
 361       TYPE_UID (t) = next_type_uid++;
 362       /* The following is so that the debug code for
 363          the copy is different from the original type.
 364          The two statements usually duplicate each other
 365          (because they clear fields of the same union),
 366          but the optimizer should catch that.  */
 367       TYPE_SYMTAB_POINTER (t) = 0;
 368       TYPE_SYMTAB_ADDRESS (t) = 0;
 369     }
 370
 371   return t;
 372 }
 373
 374 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 375    For example, this can copy a list made of TREE_LIST nodes.  */
 376
 377 tree
 378 copy_list (tree list)
 379 {
 380   tree head;
 381   tree prev, next;
 382
 383   if (list == 0)
 384     return 0;
 385
 386   head = prev = copy_node (list);
 387   next = TREE_CHAIN (list);
 388   while (next)
 389     {
 390       TREE_CHAIN (prev) = copy_node (next);
 391       prev = TREE_CHAIN (prev);
 392       next = TREE_CHAIN (next);
 393     }
 394   return head;
 395 }
 396
 397 \f
 398 /* Return a newly constructed INTEGER_CST node whose constant value
 399    is specified by the two ints LOW and HI.
 400    The TREE_TYPE is set to `int'.
 401
 402    This function should be used via the `build_int_2' macro.  */
 403
 404 tree
 405 build_int_2_wide (unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 406 {
 407   tree t = make_node (INTEGER_CST);
 408
 409   TREE_INT_CST_LOW (t) = low;
 410   TREE_INT_CST_HIGH (t) = hi;
 411   TREE_TYPE (t) = integer_type_node;
 412   return t;
 413 }
 414
 415 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 416    are in a list pointed by VALS.  */
 417
 418 tree
 419 build_vector (tree type, tree vals)
 420 {
 421   tree v = make_node (VECTOR_CST);
 422   int over1 = 0, over2 = 0;
 423   tree link;
 424
 425   TREE_VECTOR_CST_ELTS (v) = vals;
 426   TREE_TYPE (v) = type;
 427
 428   /* Iterate through elements and check for overflow.  */
 429   for (link = vals; link; link = TREE_CHAIN (link))
 430     {
 431       tree value = TREE_VALUE (link);
 432
 433       over1 |= TREE_OVERFLOW (value);
 434       over2 |= TREE_CONSTANT_OVERFLOW (value);
 435     }
 436
 437   TREE_OVERFLOW (v) = over1;
 438   TREE_CONSTANT_OVERFLOW (v) = over2;
 439
 440   return v;
 441 }
 442
 443 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 444    are in a list pointed to by VALS.  */
 445 tree
 446 build_constructor (tree type, tree vals)
 447 {
 448   tree c = make_node (CONSTRUCTOR);
 449   TREE_TYPE (c) = type;
 450   CONSTRUCTOR_ELTS (c) = vals;
 451
 452   /* ??? May not be necessary.  Mirrors what build does.  */
 453   if (vals)
 454     {
 455       TREE_SIDE_EFFECTS (c) = TREE_SIDE_EFFECTS (vals);
 456       TREE_READONLY (c) = TREE_READONLY (vals);
 457       TREE_CONSTANT (c) = TREE_CONSTANT (vals);
 458     }
 459   else
 460     TREE_CONSTANT (c) = 0;  /* safe side */
 461
 462   return c;
 463 }
 464
 465 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
 466
 467 tree
 468 build_real (tree type, REAL_VALUE_TYPE d)
 469 {
 470   tree v;
 471   REAL_VALUE_TYPE *dp;
 472   int overflow = 0;
 473
 474   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
 475      Consider doing it via real_convert now.  */
 476
 477   v = make_node (REAL_CST);
 478   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
 479   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
 480
 481   TREE_TYPE (v) = type;
 482   TREE_REAL_CST_PTR (v) = dp;
 483   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
 484   return v;
 485 }
 486
 487 /* Return a new REAL_CST node whose type is TYPE
 488    and whose value is the integer value of the INTEGER_CST node I.  */
 489
 490 REAL_VALUE_TYPE
 491 real_value_from_int_cst (tree type ATTRIBUTE_UNUSED, tree i)
 492 {
 493   REAL_VALUE_TYPE d;
 494
 495   /* Clear all bits of the real value type so that we can later do
 496      bitwise comparisons to see if two values are the same.  */
 497   memset (&d, 0, sizeof d);
 498
 499   if (! TREE_UNSIGNED (TREE_TYPE (i)))
 500     REAL_VALUE_FROM_INT (d, TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
 501                          TYPE_MODE (type));
 502   else
 503     REAL_VALUE_FROM_UNSIGNED_INT (d, TREE_INT_CST_LOW (i),
 504                                   TREE_INT_CST_HIGH (i), TYPE_MODE (type));
 505   return d;
 506 }
 507
 508 /* Given a tree representing an integer constant I, return a tree
 509    representing the same value as a floating-point constant of type TYPE.  */
 510
 511 tree
 512 build_real_from_int_cst (tree type, tree i)
 513 {
 514   tree v;
 515   int overflow = TREE_OVERFLOW (i);
 516
 517   v = build_real (type, real_value_from_int_cst (type, i));
 518
 519   TREE_OVERFLOW (v) |= overflow;
 520   TREE_CONSTANT_OVERFLOW (v) |= overflow;
 521   return v;
 522 }
 523
 524 /* Return a newly constructed STRING_CST node whose value is
 525    the LEN characters at STR.
 526    The TREE_TYPE is not initialized.  */
 527
 528 tree
 529 build_string (int len, const char *str)
 530 {
 531   tree s = make_node (STRING_CST);
 532
 533   TREE_STRING_LENGTH (s) = len;
 534   TREE_STRING_POINTER (s) = ggc_alloc_string (str, len);
 535
 536   return s;
 537 }
 538
 539 /* Return a newly constructed COMPLEX_CST node whose value is
 540    specified by the real and imaginary parts REAL and IMAG.
 541    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
 542    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
 543
 544 tree
 545 build_complex (tree type, tree real, tree imag)
 546 {
 547   tree t = make_node (COMPLEX_CST);
 548
 549   TREE_REALPART (t) = real;
 550   TREE_IMAGPART (t) = imag;
 551   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
 552   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
 553   TREE_CONSTANT_OVERFLOW (t)
 554     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
 555   return t;
 556 }
 557
 558 /* Build a newly constructed TREE_VEC node of length LEN.  */
 559
 560 tree
 561 make_tree_vec (int len)
 562 {
 563   tree t;
 564   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
 565
 566 #ifdef GATHER_STATISTICS
 567   tree_node_counts[(int) vec_kind]++;
 568   tree_node_sizes[(int) vec_kind] += length;
 569 #endif
 570
 571   t = ggc_alloc_tree (length);
 572
 573   memset (t, 0, length);
 574   TREE_SET_CODE (t, TREE_VEC);
 575   TREE_VEC_LENGTH (t) = len;
 576
 577   return t;
 578 }
 579 \f
 580 /* Return 1 if EXPR is the integer constant zero or a complex constant
 581    of zero.  */
 582
 583 int
 584 integer_zerop (tree expr)
 585 {
 586   STRIP_NOPS (expr);
 587
 588   return ((TREE_CODE (expr) == INTEGER_CST
 589            && ! TREE_CONSTANT_OVERFLOW (expr)
 590            && TREE_INT_CST_LOW (expr) == 0
 591            && TREE_INT_CST_HIGH (expr) == 0)
 592           || (TREE_CODE (expr) == COMPLEX_CST
 593               && integer_zerop (TREE_REALPART (expr))
 594               && integer_zerop (TREE_IMAGPART (expr))));
 595 }
 596
 597 /* Return 1 if EXPR is the integer constant one or the corresponding
 598    complex constant.  */
 599
 600 int
 601 integer_onep (tree expr)
 602 {
 603   STRIP_NOPS (expr);
 604
 605   return ((TREE_CODE (expr) == INTEGER_CST
 606            && ! TREE_CONSTANT_OVERFLOW (expr)
 607            && TREE_INT_CST_LOW (expr) == 1
 608            && TREE_INT_CST_HIGH (expr) == 0)
 609           || (TREE_CODE (expr) == COMPLEX_CST
 610               && integer_onep (TREE_REALPART (expr))
 611               && integer_zerop (TREE_IMAGPART (expr))));
 612 }
 613
 614 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
 615    it contains.  Likewise for the corresponding complex constant.  */
 616
 617 int
 618 integer_all_onesp (tree expr)
 619 {
 620   int prec;
 621   int uns;
 622
 623   STRIP_NOPS (expr);
 624
 625   if (TREE_CODE (expr) == COMPLEX_CST
 626       && integer_all_onesp (TREE_REALPART (expr))
 627       && integer_zerop (TREE_IMAGPART (expr)))
 628     return 1;
 629
 630   else if (TREE_CODE (expr) != INTEGER_CST
 631            || TREE_CONSTANT_OVERFLOW (expr))
 632     return 0;
 633
 634   uns = TREE_UNSIGNED (TREE_TYPE (expr));
 635   if (!uns)
 636     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 637             && TREE_INT_CST_HIGH (expr) == -1);
 638
 639   /* Note that using TYPE_PRECISION here is wrong.  We care about the
 640      actual bits, not the (arbitrary) range of the type.  */
 641   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
 642   if (prec >= HOST_BITS_PER_WIDE_INT)
 643     {
 644       HOST_WIDE_INT high_value;
 645       int shift_amount;
 646
 647       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
 648
 649       if (shift_amount > HOST_BITS_PER_WIDE_INT)
 650         /* Can not handle precisions greater than twice the host int size.  */
 651         abort ();
 652       else if (shift_amount == HOST_BITS_PER_WIDE_INT)
 653         /* Shifting by the host word size is undefined according to the ANSI
 654            standard, so we must handle this as a special case.  */
 655         high_value = -1;
 656       else
 657         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
 658
 659       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 660               && TREE_INT_CST_HIGH (expr) == high_value);
 661     }
 662   else
 663     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
 664 }
 665
 666 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
 667    one bit on).  */
 668
 669 int
 670 integer_pow2p (tree expr)
 671 {
 672   int prec;
 673   HOST_WIDE_INT high, low;
 674
 675   STRIP_NOPS (expr);
 676
 677   if (TREE_CODE (expr) == COMPLEX_CST
 678       && integer_pow2p (TREE_REALPART (expr))
 679       && integer_zerop (TREE_IMAGPART (expr)))
 680     return 1;
 681
 682   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
 683     return 0;
 684
 685   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 686           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 687   high = TREE_INT_CST_HIGH (expr);
 688   low = TREE_INT_CST_LOW (expr);
 689
 690   /* First clear all bits that are beyond the type's precision in case
 691      we've been sign extended.  */
 692
 693   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 694     ;
 695   else if (prec > HOST_BITS_PER_WIDE_INT)
 696     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 697   else
 698     {
 699       high = 0;
 700       if (prec < HOST_BITS_PER_WIDE_INT)
 701         low &= ~((HOST_WIDE_INT) (-1) << prec);
 702     }
 703
 704   if (high == 0 && low == 0)
 705     return 0;
 706
 707   return ((high == 0 && (low & (low - 1)) == 0)
 708           || (low == 0 && (high & (high - 1)) == 0));
 709 }
 710
 711 /* Return 1 if EXPR is an integer constant other than zero or a
 712    complex constant other than zero.  */
 713
 714 int
 715 integer_nonzerop (tree expr)
 716 {
 717   STRIP_NOPS (expr);
 718
 719   return ((TREE_CODE (expr) == INTEGER_CST
 720            && ! TREE_CONSTANT_OVERFLOW (expr)
 721            && (TREE_INT_CST_LOW (expr) != 0
 722                || TREE_INT_CST_HIGH (expr) != 0))
 723           || (TREE_CODE (expr) == COMPLEX_CST
 724               && (integer_nonzerop (TREE_REALPART (expr))
 725                   || integer_nonzerop (TREE_IMAGPART (expr)))));
 726 }
 727
 728 /* Return the power of two represented by a tree node known to be a
 729    power of two.  */
 730
 731 int
 732 tree_log2 (tree expr)
 733 {
 734   int prec;
 735   HOST_WIDE_INT high, low;
 736
 737   STRIP_NOPS (expr);
 738
 739   if (TREE_CODE (expr) == COMPLEX_CST)
 740     return tree_log2 (TREE_REALPART (expr));
 741
 742   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 743           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 744
 745   high = TREE_INT_CST_HIGH (expr);
 746   low = TREE_INT_CST_LOW (expr);
 747
 748   /* First clear all bits that are beyond the type's precision in case
 749      we've been sign extended.  */
 750
 751   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 752     ;
 753   else if (prec > HOST_BITS_PER_WIDE_INT)
 754     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 755   else
 756     {
 757       high = 0;
 758       if (prec < HOST_BITS_PER_WIDE_INT)
 759         low &= ~((HOST_WIDE_INT) (-1) << prec);
 760     }
 761
 762   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
 763           : exact_log2 (low));
 764 }
 765
 766 /* Similar, but return the largest integer Y such that 2 ** Y is less
 767    than or equal to EXPR.  */
 768
 769 int
 770 tree_floor_log2 (tree expr)
 771 {
 772   int prec;
 773   HOST_WIDE_INT high, low;
 774
 775   STRIP_NOPS (expr);
 776
 777   if (TREE_CODE (expr) == COMPLEX_CST)
 778     return tree_log2 (TREE_REALPART (expr));
 779
 780   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 781           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 782
 783   high = TREE_INT_CST_HIGH (expr);
 784   low = TREE_INT_CST_LOW (expr);
 785
 786   /* First clear all bits that are beyond the type's precision in case
 787      we've been sign extended.  Ignore if type's precision hasn't been set
 788      since what we are doing is setting it.  */
 789
 790   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
 791     ;
 792   else if (prec > HOST_BITS_PER_WIDE_INT)
 793     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 794   else
 795     {
 796       high = 0;
 797       if (prec < HOST_BITS_PER_WIDE_INT)
 798         low &= ~((HOST_WIDE_INT) (-1) << prec);
 799     }
 800
 801   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
 802           : floor_log2 (low));
 803 }
 804
 805 /* Return 1 if EXPR is the real constant zero.  */
 806
 807 int
 808 real_zerop (tree expr)
 809 {
 810   STRIP_NOPS (expr);
 811
 812   return ((TREE_CODE (expr) == REAL_CST
 813            && ! TREE_CONSTANT_OVERFLOW (expr)
 814            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
 815           || (TREE_CODE (expr) == COMPLEX_CST
 816               && real_zerop (TREE_REALPART (expr))
 817               && real_zerop (TREE_IMAGPART (expr))));
 818 }
 819
 820 /* Return 1 if EXPR is the real constant one in real or complex form.  */
 821
 822 int
 823 real_onep (tree expr)
 824 {
 825   STRIP_NOPS (expr);
 826
 827   return ((TREE_CODE (expr) == REAL_CST
 828            && ! TREE_CONSTANT_OVERFLOW (expr)
 829            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
 830           || (TREE_CODE (expr) == COMPLEX_CST
 831               && real_onep (TREE_REALPART (expr))
 832               && real_zerop (TREE_IMAGPART (expr))));
 833 }
 834
 835 /* Return 1 if EXPR is the real constant two.  */
 836
 837 int
 838 real_twop (tree expr)
 839 {
 840   STRIP_NOPS (expr);
 841
 842   return ((TREE_CODE (expr) == REAL_CST
 843            && ! TREE_CONSTANT_OVERFLOW (expr)
 844            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
 845           || (TREE_CODE (expr) == COMPLEX_CST
 846               && real_twop (TREE_REALPART (expr))
 847               && real_zerop (TREE_IMAGPART (expr))));
 848 }
 849
 850 /* Return 1 if EXPR is the real constant minus one.  */
 851
 852 int
 853 real_minus_onep (tree expr)
 854 {
 855   STRIP_NOPS (expr);
 856
 857   return ((TREE_CODE (expr) == REAL_CST
 858            && ! TREE_CONSTANT_OVERFLOW (expr)
 859            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
 860           || (TREE_CODE (expr) == COMPLEX_CST
 861               && real_minus_onep (TREE_REALPART (expr))
 862               && real_zerop (TREE_IMAGPART (expr))));
 863 }
 864
 865 /* Nonzero if EXP is a constant or a cast of a constant.  */
 866
 867 int
 868 really_constant_p (tree exp)
 869 {
 870   /* This is not quite the same as STRIP_NOPS.  It does more.  */
 871   while (TREE_CODE (exp) == NOP_EXPR
 872          || TREE_CODE (exp) == CONVERT_EXPR
 873          || TREE_CODE (exp) == NON_LVALUE_EXPR)
 874     exp = TREE_OPERAND (exp, 0);
 875   return TREE_CONSTANT (exp);
 876 }
 877 \f
 878 /* Return first list element whose TREE_VALUE is ELEM.
 879    Return 0 if ELEM is not in LIST.  */
 880
 881 tree
 882 value_member (tree elem, tree list)
 883 {
 884   while (list)
 885     {
 886       if (elem == TREE_VALUE (list))
 887         return list;
 888       list = TREE_CHAIN (list);
 889     }
 890   return NULL_TREE;
 891 }
 892
 893 /* Return first list element whose TREE_PURPOSE is ELEM.
 894    Return 0 if ELEM is not in LIST.  */
 895
 896 tree
 897 purpose_member (tree elem, tree list)
 898 {
 899   while (list)
 900     {
 901       if (elem == TREE_PURPOSE (list))
 902         return list;
 903       list = TREE_CHAIN (list);
 904     }
 905   return NULL_TREE;
 906 }
 907
 908 /* Return first list element whose BINFO_TYPE is ELEM.
 909    Return 0 if ELEM is not in LIST.  */
 910
 911 tree
 912 binfo_member (tree elem, tree list)
 913 {
 914   while (list)
 915     {
 916       if (elem == BINFO_TYPE (list))
 917         return list;
 918       list = TREE_CHAIN (list);
 919     }
 920   return NULL_TREE;
 921 }
 922
 923 /* Return nonzero if ELEM is part of the chain CHAIN.  */
 924
 925 int
 926 chain_member (tree elem, tree chain)
 927 {
 928   while (chain)
 929     {
 930       if (elem == chain)
 931         return 1;
 932       chain = TREE_CHAIN (chain);
 933     }
 934
 935   return 0;
 936 }
 937
 938 /* Return the length of a chain of nodes chained through TREE_CHAIN.
 939    We expect a null pointer to mark the end of the chain.
 940    This is the Lisp primitive `length'.  */
 941
 942 int
 943 list_length (tree t)
 944 {
 945   tree tail;
 946   int len = 0;
 947
 948   for (tail = t; tail; tail = TREE_CHAIN (tail))
 949     len++;
 950
 951   return len;
 952 }
 953
 954 /* Returns the number of FIELD_DECLs in TYPE.  */
 955
 956 int
 957 fields_length (tree type)
 958 {
 959   tree t = TYPE_FIELDS (type);
 960   int count = 0;
 961
 962   for (; t; t = TREE_CHAIN (t))
 963     if (TREE_CODE (t) == FIELD_DECL)
 964       ++count;
 965
 966   return count;
 967 }
 968
 969 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
 970    by modifying the last node in chain 1 to point to chain 2.
 971    This is the Lisp primitive `nconc'.  */
 972
 973 tree
 974 chainon (tree op1, tree op2)
 975 {
 976   tree t1;
 977
 978   if (!op1)
 979     return op2;
 980   if (!op2)
 981     return op1;
 982
 983   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
 984     continue;
 985   TREE_CHAIN (t1) = op2;
 986
 987 #ifdef ENABLE_TREE_CHECKING
 988   {
 989     tree t2;
 990     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
 991       if (t2 == t1)
 992         abort ();  /* Circularity created.  */
 993   }
 994 #endif
 995
 996   return op1;
 997 }
 998
 999 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1000
1001 tree
1002 tree_last (tree chain)
1003 {
1004   tree next;
1005   if (chain)
1006     while ((next = TREE_CHAIN (chain)))
1007       chain = next;
1008   return chain;
1009 }
1010
1011 /* Reverse the order of elements in the chain T,
1012    and return the new head of the chain (old last element).  */
1013
1014 tree
1015 nreverse (tree t)
1016 {
1017   tree prev = 0, decl, next;
1018   for (decl = t; decl; decl = next)
1019     {
1020       next = TREE_CHAIN (decl);
1021       TREE_CHAIN (decl) = prev;
1022       prev = decl;
1023     }
1024   return prev;
1025 }
1026 \f
1027 /* Return a newly created TREE_LIST node whose
1028    purpose and value fields are PARM and VALUE.  */
1029
1030 tree
1031 build_tree_list (tree parm, tree value)
1032 {
1033   tree t = make_node (TREE_LIST);
1034   TREE_PURPOSE (t) = parm;
1035   TREE_VALUE (t) = value;
1036   return t;
1037 }
1038
1039 /* Return a newly created TREE_LIST node whose
1040    purpose and value fields are PURPOSE and VALUE
1041    and whose TREE_CHAIN is CHAIN.  */
1042
1043 tree
1044 tree_cons (tree purpose, tree value, tree chain)
1045 {
1046   tree node;
1047
1048   node = ggc_alloc_tree (sizeof (struct tree_list));
1049
1050   memset (node, 0, sizeof (struct tree_common));
1051
1052 #ifdef GATHER_STATISTICS
1053   tree_node_counts[(int) x_kind]++;
1054   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1055 #endif
1056
1057   TREE_SET_CODE (node, TREE_LIST);
1058   TREE_CHAIN (node) = chain;
1059   TREE_PURPOSE (node) = purpose;
1060   TREE_VALUE (node) = value;
1061   return node;
1062 }
1063
1064 /* Return the first expression in a sequence of COMPOUND_EXPRs.  */
1065
1066 tree
1067 expr_first (tree expr)
1068 {
1069   if (expr == NULL_TREE)
1070     return expr;
1071   while (TREE_CODE (expr) == COMPOUND_EXPR)
1072     expr = TREE_OPERAND (expr, 0);
1073   return expr;
1074 }
1075
1076 /* Return the last expression in a sequence of COMPOUND_EXPRs.  */
1077
1078 tree
1079 expr_last (tree expr)
1080 {
1081   if (expr == NULL_TREE)
1082     return expr;
1083   while (TREE_CODE (expr) == COMPOUND_EXPR)
1084     expr = TREE_OPERAND (expr, 1);
1085   return expr;
1086 }
1087
1088 /* Return the number of subexpressions in a sequence of COMPOUND_EXPRs.  */
1089
1090 int
1091 expr_length (tree expr)
1092 {
1093   int len = 0;
1094
1095   if (expr == NULL_TREE)
1096     return 0;
1097   for (; TREE_CODE (expr) == COMPOUND_EXPR; expr = TREE_OPERAND (expr, 1))
1098     len += expr_length (TREE_OPERAND (expr, 0));
1099   ++len;
1100   return len;
1101 }
1102 \f
1103 /* Return the size nominally occupied by an object of type TYPE
1104    when it resides in memory.  The value is measured in units of bytes,
1105    and its data type is that normally used for type sizes
1106    (which is the first type created by make_signed_type or
1107    make_unsigned_type).  */
1108
1109 tree
1110 size_in_bytes (tree type)
1111 {
1112   tree t;
1113
1114   if (type == error_mark_node)
1115     return integer_zero_node;
1116
1117   type = TYPE_MAIN_VARIANT (type);
1118   t = TYPE_SIZE_UNIT (type);
1119
1120   if (t == 0)
1121     {
1122       (*lang_hooks.types.incomplete_type_error) (NULL_TREE, type);
1123       return size_zero_node;
1124     }
1125
1126   if (TREE_CODE (t) == INTEGER_CST)
1127     force_fit_type (t, 0);
1128
1129   return t;
1130 }
1131
1132 /* Return the size of TYPE (in bytes) as a wide integer
1133    or return -1 if the size can vary or is larger than an integer.  */
1134
1135 HOST_WIDE_INT
1136 int_size_in_bytes (tree type)
1137 {
1138   tree t;
1139
1140   if (type == error_mark_node)
1141     return 0;
1142
1143   type = TYPE_MAIN_VARIANT (type);
1144   t = TYPE_SIZE_UNIT (type);
1145   if (t == 0
1146       || TREE_CODE (t) != INTEGER_CST
1147       || TREE_OVERFLOW (t)
1148       || TREE_INT_CST_HIGH (t) != 0
1149       /* If the result would appear negative, it's too big to represent.  */
1150       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1151     return -1;
1152
1153   return TREE_INT_CST_LOW (t);
1154 }
1155 \f
1156 /* Return the bit position of FIELD, in bits from the start of the record.
1157    This is a tree of type bitsizetype.  */
1158
1159 tree
1160 bit_position (tree field)
1161 {
1162   return bit_from_pos (DECL_FIELD_OFFSET (field),
1163                        DECL_FIELD_BIT_OFFSET (field));
1164 }
1165
1166 /* Likewise, but return as an integer.  Abort if it cannot be represented
1167    in that way (since it could be a signed value, we don't have the option
1168    of returning -1 like int_size_in_byte can.  */
1169
1170 HOST_WIDE_INT
1171 int_bit_position (tree field)
1172 {
1173   return tree_low_cst (bit_position (field), 0);
1174 }
1175 \f
1176 /* Return the byte position of FIELD, in bytes from the start of the record.
1177    This is a tree of type sizetype.  */
1178
1179 tree
1180 byte_position (tree field)
1181 {
1182   return byte_from_pos (DECL_FIELD_OFFSET (field),
1183                         DECL_FIELD_BIT_OFFSET (field));
1184 }
1185
1186 /* Likewise, but return as an integer.  Abort if it cannot be represented
1187    in that way (since it could be a signed value, we don't have the option
1188    of returning -1 like int_size_in_byte can.  */
1189
1190 HOST_WIDE_INT
1191 int_byte_position (tree field)
1192 {
1193   return tree_low_cst (byte_position (field), 0);
1194 }
1195 \f
1196 /* Return the strictest alignment, in bits, that T is known to have.  */
1197
1198 unsigned int
1199 expr_align (tree t)
1200 {
1201   unsigned int align0, align1;
1202
1203   switch (TREE_CODE (t))
1204     {
1205     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1206       /* If we have conversions, we know that the alignment of the
1207          object must meet each of the alignments of the types.  */
1208       align0 = expr_align (TREE_OPERAND (t, 0));
1209       align1 = TYPE_ALIGN (TREE_TYPE (t));
1210       return MAX (align0, align1);
1211
1212     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1213     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1214     case WITH_RECORD_EXPR:  case CLEANUP_POINT_EXPR:  case UNSAVE_EXPR:
1215       /* These don't change the alignment of an object.  */
1216       return expr_align (TREE_OPERAND (t, 0));
1217
1218     case COND_EXPR:
1219       /* The best we can do is say that the alignment is the least aligned
1220          of the two arms.  */
1221       align0 = expr_align (TREE_OPERAND (t, 1));
1222       align1 = expr_align (TREE_OPERAND (t, 2));
1223       return MIN (align0, align1);
1224
1225     case LABEL_DECL:     case CONST_DECL:
1226     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1227       if (DECL_ALIGN (t) != 0)
1228         return DECL_ALIGN (t);
1229       break;
1230
1231     case FUNCTION_DECL:
1232       return FUNCTION_BOUNDARY;
1233
1234     default:
1235       break;
1236     }
1237
1238   /* Otherwise take the alignment from that of the type.  */
1239   return TYPE_ALIGN (TREE_TYPE (t));
1240 }
1241 \f
1242 /* Return, as a tree node, the number of elements for TYPE (which is an
1243    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1244
1245 tree
1246 array_type_nelts (tree type)
1247 {
1248   tree index_type, min, max;
1249
1250   /* If they did it with unspecified bounds, then we should have already
1251      given an error about it before we got here.  */
1252   if (! TYPE_DOMAIN (type))
1253     return error_mark_node;
1254
1255   index_type = TYPE_DOMAIN (type);
1256   min = TYPE_MIN_VALUE (index_type);
1257   max = TYPE_MAX_VALUE (index_type);
1258
1259   return (integer_zerop (min)
1260           ? max
1261           : fold (build (MINUS_EXPR, TREE_TYPE (max), max, min)));
1262 }
1263 \f
1264 /* Return nonzero if arg is static -- a reference to an object in
1265    static storage.  This is not the same as the C meaning of `static'.  */
1266
1267 int
1268 staticp (tree arg)
1269 {
1270   switch (TREE_CODE (arg))
1271     {
1272     case FUNCTION_DECL:
1273       /* Nested functions aren't static, since taking their address
1274          involves a trampoline.  */
1275       return ((decl_function_context (arg) == 0 || DECL_NO_STATIC_CHAIN (arg))
1276               && ! DECL_NON_ADDR_CONST_P (arg));
1277
1278     case VAR_DECL:
1279       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1280               && ! DECL_THREAD_LOCAL (arg)
1281               && ! DECL_NON_ADDR_CONST_P (arg));
1282
1283     case CONSTRUCTOR:
1284       return TREE_STATIC (arg);
1285
1286     case LABEL_DECL:
1287     case STRING_CST:
1288       return 1;
1289
1290       /* If we are referencing a bitfield, we can't evaluate an
1291          ADDR_EXPR at compile time and so it isn't a constant.  */
1292     case COMPONENT_REF:
1293       return (! DECL_BIT_FIELD (TREE_OPERAND (arg, 1))
1294               && staticp (TREE_OPERAND (arg, 0)));
1295
1296     case BIT_FIELD_REF:
1297       return 0;
1298
1299 #if 0
1300        /* This case is technically correct, but results in setting
1301           TREE_CONSTANT on ADDR_EXPRs that cannot be evaluated at
1302           compile time.  */
1303     case INDIRECT_REF:
1304       return TREE_CONSTANT (TREE_OPERAND (arg, 0));
1305 #endif
1306
1307     case ARRAY_REF:
1308     case ARRAY_RANGE_REF:
1309       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1310           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1311         return staticp (TREE_OPERAND (arg, 0));
1312
1313     default:
1314       if ((unsigned int) TREE_CODE (arg)
1315           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1316         return (*lang_hooks.staticp) (arg);
1317       else
1318         return 0;
1319     }
1320 }
1321 \f
1322 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1323    Do this to any expression which may be used in more than one place,
1324    but must be evaluated only once.
1325
1326    Normally, expand_expr would reevaluate the expression each time.
1327    Calling save_expr produces something that is evaluated and recorded
1328    the first time expand_expr is called on it.  Subsequent calls to
1329    expand_expr just reuse the recorded value.
1330
1331    The call to expand_expr that generates code that actually computes
1332    the value is the first call *at compile time*.  Subsequent calls
1333    *at compile time* generate code to use the saved value.
1334    This produces correct result provided that *at run time* control
1335    always flows through the insns made by the first expand_expr
1336    before reaching the other places where the save_expr was evaluated.
1337    You, the caller of save_expr, must make sure this is so.
1338
1339    Constants, and certain read-only nodes, are returned with no
1340    SAVE_EXPR because that is safe.  Expressions containing placeholders
1341    are not touched; see tree.def for an explanation of what these
1342    are used for.  */
1343
1344 tree
1345 save_expr (tree expr)
1346 {
1347   tree t = fold (expr);
1348   tree inner;
1349
1350   /* If the tree evaluates to a constant, then we don't want to hide that
1351      fact (i.e. this allows further folding, and direct checks for constants).
1352      However, a read-only object that has side effects cannot be bypassed.
1353      Since it is no problem to reevaluate literals, we just return the
1354      literal node.  */
1355   inner = skip_simple_arithmetic (t);
1356   if (TREE_CONSTANT (inner)
1357       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1358       || TREE_CODE (inner) == SAVE_EXPR
1359       || TREE_CODE (inner) == ERROR_MARK)
1360     return t;
1361
1362   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1363      it means that the size or offset of some field of an object depends on
1364      the value within another field.
1365
1366      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1367      and some variable since it would then need to be both evaluated once and
1368      evaluated more than once.  Front-ends must assure this case cannot
1369      happen by surrounding any such subexpressions in their own SAVE_EXPR
1370      and forcing evaluation at the proper time.  */
1371   if (contains_placeholder_p (inner))
1372     return t;
1373
1374   t = build (SAVE_EXPR, TREE_TYPE (expr), t, current_function_decl, NULL_TREE);
1375
1376   /* This expression might be placed ahead of a jump to ensure that the
1377      value was computed on both sides of the jump.  So make sure it isn't
1378      eliminated as dead.  */
1379   TREE_SIDE_EFFECTS (t) = 1;
1380   TREE_READONLY (t) = 1;
1381   return t;
1382 }
1383
1384 /* Look inside EXPR and into any simple arithmetic operations.  Return
1385    the innermost non-arithmetic node.  */
1386
1387 tree
1388 skip_simple_arithmetic (tree expr)
1389 {
1390   tree inner;
1391
1392   /* We don't care about whether this can be used as an lvalue in this
1393      context.  */
1394   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1395     expr = TREE_OPERAND (expr, 0);
1396
1397   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1398      a constant, it will be more efficient to not make another SAVE_EXPR since
1399      it will allow better simplification and GCSE will be able to merge the
1400      computations if they actually occur.  */
1401   inner = expr;
1402   while (1)
1403     {
1404       if (TREE_CODE_CLASS (TREE_CODE (inner)) == '1')
1405         inner = TREE_OPERAND (inner, 0);
1406       else if (TREE_CODE_CLASS (TREE_CODE (inner)) == '2')
1407         {
1408           if (TREE_CONSTANT (TREE_OPERAND (inner, 1)))
1409             inner = TREE_OPERAND (inner, 0);
1410           else if (TREE_CONSTANT (TREE_OPERAND (inner, 0)))
1411             inner = TREE_OPERAND (inner, 1);
1412           else
1413             break;
1414         }
1415       else
1416         break;
1417     }
1418
1419   return inner;
1420 }
1421
1422 /* Return TRUE if EXPR is a SAVE_EXPR or wraps simple arithmetic around a
1423    SAVE_EXPR.  Return FALSE otherwise.  */
1424
1425 bool
1426 saved_expr_p (tree expr)
1427 {
1428   return TREE_CODE (skip_simple_arithmetic (expr)) == SAVE_EXPR;
1429 }
1430
1431 /* Arrange for an expression to be expanded multiple independent
1432    times.  This is useful for cleanup actions, as the backend can
1433    expand them multiple times in different places.  */
1434
1435 tree
1436 unsave_expr (tree expr)
1437 {
1438   tree t;
1439
1440   /* If this is already protected, no sense in protecting it again.  */
1441   if (TREE_CODE (expr) == UNSAVE_EXPR)
1442     return expr;
1443
1444   t = build1 (UNSAVE_EXPR, TREE_TYPE (expr), expr);
1445   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (expr);
1446   return t;
1447 }
1448
1449 /* Returns the index of the first non-tree operand for CODE, or the number
1450    of operands if all are trees.  */
1451
1452 int
1453 first_rtl_op (enum tree_code code)
1454 {
1455   switch (code)
1456     {
1457     case SAVE_EXPR:
1458       return 2;
1459     case GOTO_SUBROUTINE_EXPR:
1460     case RTL_EXPR:
1461       return 0;
1462     case WITH_CLEANUP_EXPR:
1463       return 2;
1464     default:
1465       return TREE_CODE_LENGTH (code);
1466     }
1467 }
1468
1469 /* Return which tree structure is used by T.  */
1470
1471 enum tree_node_structure_enum
1472 tree_node_structure (tree t)
1473 {
1474   enum tree_code code = TREE_CODE (t);
1475
1476   switch (TREE_CODE_CLASS (code))
1477     {
1478     case 'd':   return TS_DECL;
1479     case 't':   return TS_TYPE;
1480     case 'b':   return TS_BLOCK;
1481     case 'r': case '<': case '1': case '2': case 'e': case 's':
1482       return TS_EXP;
1483     default:  /* 'c' and 'x' */
1484       break;
1485     }
1486   switch (code)
1487     {
1488       /* 'c' cases.  */
1489     case INTEGER_CST:           return TS_INT_CST;
1490     case REAL_CST:              return TS_REAL_CST;
1491     case COMPLEX_CST:           return TS_COMPLEX;
1492     case VECTOR_CST:            return TS_VECTOR;
1493     case STRING_CST:            return TS_STRING;
1494       /* 'x' cases.  */
1495     case ERROR_MARK:            return TS_COMMON;
1496     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1497     case TREE_LIST:             return TS_LIST;
1498     case TREE_VEC:              return TS_VEC;
1499     case PLACEHOLDER_EXPR:      return TS_COMMON;
1500
1501     default:
1502       abort ();
1503     }
1504 }
1505
1506 /* Perform any modifications to EXPR required when it is unsaved.  Does
1507    not recurse into EXPR's subtrees.  */
1508
1509 void
1510 unsave_expr_1 (tree expr)
1511 {
1512   switch (TREE_CODE (expr))
1513     {
1514     case SAVE_EXPR:
1515       if (! SAVE_EXPR_PERSISTENT_P (expr))
1516         SAVE_EXPR_RTL (expr) = 0;
1517       break;
1518
1519     case TARGET_EXPR:
1520       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
1521          It's OK for this to happen if it was part of a subtree that
1522          isn't immediately expanded, such as operand 2 of another
1523          TARGET_EXPR.  */
1524       if (TREE_OPERAND (expr, 1))
1525         break;
1526
1527       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
1528       TREE_OPERAND (expr, 3) = NULL_TREE;
1529       break;
1530
1531     case RTL_EXPR:
1532       /* I don't yet know how to emit a sequence multiple times.  */
1533       if (RTL_EXPR_SEQUENCE (expr) != 0)
1534         abort ();
1535       break;
1536
1537     default:
1538       break;
1539     }
1540 }
1541
1542 /* Default lang hook for "unsave_expr_now".  */
1543
1544 tree
1545 lhd_unsave_expr_now (tree expr)
1546 {
1547   enum tree_code code;
1548
1549   /* There's nothing to do for NULL_TREE.  */
1550   if (expr == 0)
1551     return expr;
1552
1553   unsave_expr_1 (expr);
1554
1555   code = TREE_CODE (expr);
1556   switch (TREE_CODE_CLASS (code))
1557     {
1558     case 'c':  /* a constant */
1559     case 't':  /* a type node */
1560     case 'd':  /* A decl node */
1561     case 'b':  /* A block node */
1562       break;
1563
1564     case 'x':  /* miscellaneous: e.g., identifier, TREE_LIST or ERROR_MARK.  */
1565       if (code == TREE_LIST)
1566         {
1567           lhd_unsave_expr_now (TREE_VALUE (expr));
1568           lhd_unsave_expr_now (TREE_CHAIN (expr));
1569         }
1570       break;
1571
1572     case 'e':  /* an expression */
1573     case 'r':  /* a reference */
1574     case 's':  /* an expression with side effects */
1575     case '<':  /* a comparison expression */
1576     case '2':  /* a binary arithmetic expression */
1577     case '1':  /* a unary arithmetic expression */
1578       {
1579         int i;
1580
1581         for (i = first_rtl_op (code) - 1; i >= 0; i--)
1582           lhd_unsave_expr_now (TREE_OPERAND (expr, i));
1583       }
1584       break;
1585
1586     default:
1587       abort ();
1588     }
1589
1590   return expr;
1591 }
1592
1593 /* Return 0 if it is safe to evaluate EXPR multiple times,
1594    return 1 if it is safe if EXPR is unsaved afterward, or
1595    return 2 if it is completely unsafe.
1596
1597    This assumes that CALL_EXPRs and TARGET_EXPRs are never replicated in
1598    an expression tree, so that it safe to unsave them and the surrounding
1599    context will be correct.
1600
1601    SAVE_EXPRs basically *only* appear replicated in an expression tree,
1602    occasionally across the whole of a function.  It is therefore only
1603    safe to unsave a SAVE_EXPR if you know that all occurrences appear
1604    below the UNSAVE_EXPR.
1605
1606    RTL_EXPRs consume their rtl during evaluation.  It is therefore
1607    never possible to unsave them.  */
1608
1609 int
1610 unsafe_for_reeval (tree expr)
1611 {
1612   int unsafeness = 0;
1613   enum tree_code code;
1614   int i, tmp, tmp2;
1615   tree exp;
1616   int first_rtl;
1617
1618   if (expr == NULL_TREE)
1619     return 1;
1620
1621   code = TREE_CODE (expr);
1622   first_rtl = first_rtl_op (code);
1623
1624   switch (code)
1625     {
1626     case SAVE_EXPR:
1627     case RTL_EXPR:
1628       return 2;
1629
1630     case TREE_LIST:
1631       for (exp = expr; exp != 0; exp = TREE_CHAIN (exp))
1632         {
1633           tmp = unsafe_for_reeval (TREE_VALUE (exp));
1634           unsafeness = MAX (tmp, unsafeness);
1635         }
1636
1637       return unsafeness;
1638
1639     case CALL_EXPR:
1640       tmp2 = unsafe_for_reeval (TREE_OPERAND (expr, 0));
1641       tmp = unsafe_for_reeval (TREE_OPERAND (expr, 1));
1642       return MAX (MAX (tmp, 1), tmp2);
1643
1644     case TARGET_EXPR:
1645       unsafeness = 1;
1646       break;
1647
1648     default:
1649       tmp = (*lang_hooks.unsafe_for_reeval) (expr);
1650       if (tmp >= 0)
1651         return tmp;
1652       break;
1653     }
1654
1655   switch (TREE_CODE_CLASS (code))
1656     {
1657     case 'c':  /* a constant */
1658     case 't':  /* a type node */
1659     case 'x':  /* something random, like an identifier or an ERROR_MARK.  */
1660     case 'd':  /* A decl node */
1661     case 'b':  /* A block node */
1662       return 0;
1663
1664     case 'e':  /* an expression */
1665     case 'r':  /* a reference */
1666     case 's':  /* an expression with side effects */
1667     case '<':  /* a comparison expression */
1668     case '2':  /* a binary arithmetic expression */
1669     case '1':  /* a unary arithmetic expression */
1670       for (i = first_rtl - 1; i >= 0; i--)
1671         {
1672           tmp = unsafe_for_reeval (TREE_OPERAND (expr, i));
1673           unsafeness = MAX (tmp, unsafeness);
1674         }
1675
1676       return unsafeness;
1677
1678     default:
1679       return 2;
1680     }
1681 }
1682 \f
1683 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1684    or offset that depends on a field within a record.  */
1685
1686 bool
1687 contains_placeholder_p (tree exp)
1688 {
1689   enum tree_code code;
1690   int result;
1691
1692   if (!exp)
1693     return 0;
1694
1695   /* If we have a WITH_RECORD_EXPR, it "cancels" any PLACEHOLDER_EXPR
1696      in it since it is supplying a value for it.  */
1697   code = TREE_CODE (exp);
1698   if (code == WITH_RECORD_EXPR)
1699     return 0;
1700   else if (code == PLACEHOLDER_EXPR)
1701     return 1;
1702
1703   switch (TREE_CODE_CLASS (code))
1704     {
1705     case 'r':
1706       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1707          position computations since they will be converted into a
1708          WITH_RECORD_EXPR involving the reference, which will assume
1709          here will be valid.  */
1710       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1711
1712     case 'x':
1713       if (code == TREE_LIST)
1714         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1715                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1716       break;
1717
1718     case '1':
1719     case '2':  case '<':
1720     case 'e':
1721       switch (code)
1722         {
1723         case COMPOUND_EXPR:
1724           /* Ignoring the first operand isn't quite right, but works best.  */
1725           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1726
1727         case RTL_EXPR:
1728         case CONSTRUCTOR:
1729           return 0;
1730
1731         case COND_EXPR:
1732           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1733                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1734                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1735
1736         case SAVE_EXPR:
1737           /* If we already know this doesn't have a placeholder, don't
1738              check again.  */
1739           if (SAVE_EXPR_NOPLACEHOLDER (exp) || SAVE_EXPR_RTL (exp) != 0)
1740             return 0;
1741
1742           SAVE_EXPR_NOPLACEHOLDER (exp) = 1;
1743           result = CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1744           if (result)
1745             SAVE_EXPR_NOPLACEHOLDER (exp) = 0;
1746
1747           return result;
1748
1749         case CALL_EXPR:
1750           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1751
1752         default:
1753           break;
1754         }
1755
1756       switch (TREE_CODE_LENGTH (code))
1757         {
1758         case 1:
1759           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1760         case 2:
1761           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1762                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1763         default:
1764           return 0;
1765         }
1766
1767     default:
1768       return 0;
1769     }
1770   return 0;
1771 }
1772
1773 /* Return 1 if any part of the computation of TYPE involves a PLACEHOLDER_EXPR.
1774    This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and field
1775    positions.  */
1776
1777 bool
1778 type_contains_placeholder_p (tree type)
1779 {
1780   /* If the size contains a placeholder or the parent type (component type in
1781      the case of arrays) type involves a placeholder, this type does.  */
1782   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1783       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1784       || (TREE_TYPE (type) != 0
1785           && type_contains_placeholder_p (TREE_TYPE (type))))
1786     return 1;
1787
1788   /* Now do type-specific checks.  Note that the last part of the check above
1789      greatly limits what we have to do below.  */
1790   switch (TREE_CODE (type))
1791     {
1792     case VOID_TYPE:
1793     case COMPLEX_TYPE:
1794     case VECTOR_TYPE:
1795     case ENUMERAL_TYPE:
1796     case BOOLEAN_TYPE:
1797     case CHAR_TYPE:
1798     case POINTER_TYPE:
1799     case OFFSET_TYPE:
1800     case REFERENCE_TYPE:
1801     case METHOD_TYPE:
1802     case FILE_TYPE:
1803     case FUNCTION_TYPE:
1804       return 0;
1805
1806     case INTEGER_TYPE:
1807     case REAL_TYPE:
1808       /* Here we just check the bounds.  */
1809       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1810               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1811
1812     case ARRAY_TYPE:
1813     case SET_TYPE:
1814       /* We're already checked the component type (TREE_TYPE), so just check
1815          the index type.  */
1816       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1817
1818     case RECORD_TYPE:
1819     case UNION_TYPE:
1820     case QUAL_UNION_TYPE:
1821       {
1822         static tree seen_types = 0;
1823         tree field;
1824         bool ret = 0;
1825
1826         /* We have to be careful here that we don't end up in infinite
1827            recursions due to a field of a type being a pointer to that type
1828            or to a mutually-recursive type.  So we store a list of record
1829            types that we've seen and see if this type is in them.  To save
1830            memory, we don't use a list for just one type.  Here we check
1831            whether we've seen this type before and store it if not.  */
1832         if (seen_types == 0)
1833           seen_types = type;
1834         else if (TREE_CODE (seen_types) != TREE_LIST)
1835           {
1836             if (seen_types == type)
1837               return 0;
1838
1839             seen_types = tree_cons (NULL_TREE, type,
1840                                     build_tree_list (NULL_TREE, seen_types));
1841           }
1842         else
1843           {
1844             if (value_member (type, seen_types) != 0)
1845               return 0;
1846
1847             seen_types = tree_cons (NULL_TREE, type, seen_types);
1848           }
1849
1850         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1851           if (TREE_CODE (field) == FIELD_DECL
1852               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1853                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1854                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1855                   || type_contains_placeholder_p (TREE_TYPE (field))))
1856             {
1857               ret = true;
1858               break;
1859             }
1860
1861         /* Now remove us from seen_types and return the result.  */
1862         if (seen_types == type)
1863           seen_types = 0;
1864         else
1865           seen_types = TREE_CHAIN (seen_types);
1866
1867         return ret;
1868       }
1869
1870     default:
1871       abort ();
1872     }
1873 }
1874
1875 /* Return 1 if EXP contains any expressions that produce cleanups for an
1876    outer scope to deal with.  Used by fold.  */
1877
1878 int
1879 has_cleanups (tree exp)
1880 {
1881   int i, nops, cmp;
1882
1883   if (! TREE_SIDE_EFFECTS (exp))
1884     return 0;
1885
1886   switch (TREE_CODE (exp))
1887     {
1888     case TARGET_EXPR:
1889     case GOTO_SUBROUTINE_EXPR:
1890     case WITH_CLEANUP_EXPR:
1891       return 1;
1892
1893     case CLEANUP_POINT_EXPR:
1894       return 0;
1895
1896     case CALL_EXPR:
1897       for (exp = TREE_OPERAND (exp, 1); exp; exp = TREE_CHAIN (exp))
1898         {
1899           cmp = has_cleanups (TREE_VALUE (exp));
1900           if (cmp)
1901             return cmp;
1902         }
1903       return 0;
1904
1905     default:
1906       break;
1907     }
1908
1909   /* This general rule works for most tree codes.  All exceptions should be
1910      handled above.  If this is a language-specific tree code, we can't
1911      trust what might be in the operand, so say we don't know
1912      the situation.  */
1913   if ((int) TREE_CODE (exp) >= (int) LAST_AND_UNUSED_TREE_CODE)
1914     return -1;
1915
1916   nops = first_rtl_op (TREE_CODE (exp));
1917   for (i = 0; i < nops; i++)
1918     if (TREE_OPERAND (exp, i) != 0)
1919       {
1920         int type = TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (exp, i)));
1921         if (type == 'e' || type == '<' || type == '1' || type == '2'
1922             || type == 'r' || type == 's')
1923           {
1924             cmp = has_cleanups (TREE_OPERAND (exp, i));
1925             if (cmp)
1926               return cmp;
1927           }
1928       }
1929
1930   return 0;
1931 }
1932 \f
1933 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1934    return a tree with all occurrences of references to F in a
1935    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1936    contains only arithmetic expressions or a CALL_EXPR with a
1937    PLACEHOLDER_EXPR occurring only in its arglist.  */
1938
1939 tree
1940 substitute_in_expr (tree exp, tree f, tree r)
1941 {
1942   enum tree_code code = TREE_CODE (exp);
1943   tree op0, op1, op2;
1944   tree new;
1945   tree inner;
1946
1947   switch (TREE_CODE_CLASS (code))
1948     {
1949     case 'c':
1950     case 'd':
1951       return exp;
1952
1953     case 'x':
1954       if (code == PLACEHOLDER_EXPR)
1955         return exp;
1956       else if (code == TREE_LIST)
1957         {
1958           op0 = (TREE_CHAIN (exp) == 0
1959                  ? 0 : substitute_in_expr (TREE_CHAIN (exp), f, r));
1960           op1 = substitute_in_expr (TREE_VALUE (exp), f, r);
1961           if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1962             return exp;
1963
1964           return tree_cons (TREE_PURPOSE (exp), op1, op0);
1965         }
1966
1967       abort ();
1968
1969     case '1':
1970     case '2':
1971     case '<':
1972     case 'e':
1973       switch (TREE_CODE_LENGTH (code))
1974         {
1975         case 1:
1976           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1977           if (op0 == TREE_OPERAND (exp, 0))
1978             return exp;
1979
1980           if (code == NON_LVALUE_EXPR)
1981             return op0;
1982
1983           new = fold (build1 (code, TREE_TYPE (exp), op0));
1984           break;
1985
1986         case 2:
1987           /* An RTL_EXPR cannot contain a PLACEHOLDER_EXPR; a CONSTRUCTOR
1988              could, but we don't support it.  */
1989           if (code == RTL_EXPR)
1990             return exp;
1991           else if (code == CONSTRUCTOR)
1992             abort ();
1993
1994           op0 = TREE_OPERAND (exp, 0);
1995           op1 = TREE_OPERAND (exp, 1);
1996           if (CONTAINS_PLACEHOLDER_P (op0))
1997             op0 = substitute_in_expr (op0, f, r);
1998           if (CONTAINS_PLACEHOLDER_P (op1))
1999             op1 = substitute_in_expr (op1, f, r);
2000
2001           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2002             return exp;
2003
2004           new = fold (build (code, TREE_TYPE (exp), op0, op1));
2005           break;
2006
2007         case 3:
2008           /* It cannot be that anything inside a SAVE_EXPR contains a
2009              PLACEHOLDER_EXPR.  */
2010           if (code == SAVE_EXPR)
2011             return exp;
2012
2013           else if (code == CALL_EXPR)
2014             {
2015               op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2016               if (op1 == TREE_OPERAND (exp, 1))
2017                 return exp;
2018
2019               return build (code, TREE_TYPE (exp),
2020                             TREE_OPERAND (exp, 0), op1, NULL_TREE);
2021             }
2022
2023           else if (code != COND_EXPR)
2024             abort ();
2025
2026           op0 = TREE_OPERAND (exp, 0);
2027           op1 = TREE_OPERAND (exp, 1);
2028           op2 = TREE_OPERAND (exp, 2);
2029
2030           if (CONTAINS_PLACEHOLDER_P (op0))
2031             op0 = substitute_in_expr (op0, f, r);
2032           if (CONTAINS_PLACEHOLDER_P (op1))
2033             op1 = substitute_in_expr (op1, f, r);
2034           if (CONTAINS_PLACEHOLDER_P (op2))
2035             op2 = substitute_in_expr (op2, f, r);
2036
2037           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2038               && op2 == TREE_OPERAND (exp, 2))
2039             return exp;
2040
2041           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
2042           break;
2043
2044         default:
2045           abort ();
2046         }
2047
2048       break;
2049
2050     case 'r':
2051       switch (code)
2052         {
2053         case COMPONENT_REF:
2054           /* If this expression is getting a value from a PLACEHOLDER_EXPR
2055              and it is the right field, replace it with R.  */
2056           for (inner = TREE_OPERAND (exp, 0);
2057                TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
2058                inner = TREE_OPERAND (inner, 0))
2059             ;
2060           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2061               && TREE_OPERAND (exp, 1) == f)
2062             return r;
2063
2064           /* If this expression hasn't been completed let, leave it
2065              alone.  */
2066           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2067               && TREE_TYPE (inner) == 0)
2068             return exp;
2069
2070           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2071           if (op0 == TREE_OPERAND (exp, 0))
2072             return exp;
2073
2074           new = fold (build (code, TREE_TYPE (exp), op0,
2075                              TREE_OPERAND (exp, 1)));
2076           break;
2077
2078         case BIT_FIELD_REF:
2079           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2080           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
2081           op2 = substitute_in_expr (TREE_OPERAND (exp, 2), f, r);
2082           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2083               && op2 == TREE_OPERAND (exp, 2))
2084             return exp;
2085
2086           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
2087           break;
2088
2089         case INDIRECT_REF:
2090         case BUFFER_REF:
2091           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
2092           if (op0 == TREE_OPERAND (exp, 0))
2093             return exp;
2094
2095           new = fold (build1 (code, TREE_TYPE (exp), op0));
2096           break;
2097
2098         default:
2099           abort ();
2100         }
2101       break;
2102
2103     default:
2104       abort ();
2105     }
2106
2107   TREE_READONLY (new) = TREE_READONLY (exp);
2108   return new;
2109 }
2110 \f
2111 /* Stabilize a reference so that we can use it any number of times
2112    without causing its operands to be evaluated more than once.
2113    Returns the stabilized reference.  This works by means of save_expr,
2114    so see the caveats in the comments about save_expr.
2115
2116    Also allows conversion expressions whose operands are references.
2117    Any other kind of expression is returned unchanged.  */
2118
2119 tree
2120 stabilize_reference (tree ref)
2121 {
2122   tree result;
2123   enum tree_code code = TREE_CODE (ref);
2124
2125   switch (code)
2126     {
2127     case VAR_DECL:
2128     case PARM_DECL:
2129     case RESULT_DECL:
2130       /* No action is needed in this case.  */
2131       return ref;
2132
2133     case NOP_EXPR:
2134     case CONVERT_EXPR:
2135     case FLOAT_EXPR:
2136     case FIX_TRUNC_EXPR:
2137     case FIX_FLOOR_EXPR:
2138     case FIX_ROUND_EXPR:
2139     case FIX_CEIL_EXPR:
2140       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2141       break;
2142
2143     case INDIRECT_REF:
2144       result = build_nt (INDIRECT_REF,
2145                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2146       break;
2147
2148     case COMPONENT_REF:
2149       result = build_nt (COMPONENT_REF,
2150                          stabilize_reference (TREE_OPERAND (ref, 0)),
2151                          TREE_OPERAND (ref, 1));
2152       break;
2153
2154     case BIT_FIELD_REF:
2155       result = build_nt (BIT_FIELD_REF,
2156                          stabilize_reference (TREE_OPERAND (ref, 0)),
2157                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2158                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2159       break;
2160
2161     case ARRAY_REF:
2162       result = build_nt (ARRAY_REF,
2163                          stabilize_reference (TREE_OPERAND (ref, 0)),
2164                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2165       break;
2166
2167     case ARRAY_RANGE_REF:
2168       result = build_nt (ARRAY_RANGE_REF,
2169                          stabilize_reference (TREE_OPERAND (ref, 0)),
2170                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2171       break;
2172
2173     case COMPOUND_EXPR:
2174       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2175          it wouldn't be ignored.  This matters when dealing with
2176          volatiles.  */
2177       return stabilize_reference_1 (ref);
2178
2179     case RTL_EXPR:
2180       result = build1 (INDIRECT_REF, TREE_TYPE (ref),
2181                        save_expr (build1 (ADDR_EXPR,
2182                                           build_pointer_type (TREE_TYPE (ref)),
2183                                           ref)));
2184       break;
2185
2186       /* If arg isn't a kind of lvalue we recognize, make no change.
2187          Caller should recognize the error for an invalid lvalue.  */
2188     default:
2189       return ref;
2190
2191     case ERROR_MARK:
2192       return error_mark_node;
2193     }
2194
2195   TREE_TYPE (result) = TREE_TYPE (ref);
2196   TREE_READONLY (result) = TREE_READONLY (ref);
2197   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2198   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2199
2200   return result;
2201 }
2202
2203 /* Subroutine of stabilize_reference; this is called for subtrees of
2204    references.  Any expression with side-effects must be put in a SAVE_EXPR
2205    to ensure that it is only evaluated once.
2206
2207    We don't put SAVE_EXPR nodes around everything, because assigning very
2208    simple expressions to temporaries causes us to miss good opportunities
2209    for optimizations.  Among other things, the opportunity to fold in the
2210    addition of a constant into an addressing mode often gets lost, e.g.
2211    "y[i+1] += x;".  In general, we take the approach that we should not make
2212    an assignment unless we are forced into it - i.e., that any non-side effect
2213    operator should be allowed, and that cse should take care of coalescing
2214    multiple utterances of the same expression should that prove fruitful.  */
2215
2216 tree
2217 stabilize_reference_1 (tree e)
2218 {
2219   tree result;
2220   enum tree_code code = TREE_CODE (e);
2221
2222   /* We cannot ignore const expressions because it might be a reference
2223      to a const array but whose index contains side-effects.  But we can
2224      ignore things that are actual constant or that already have been
2225      handled by this function.  */
2226
2227   if (TREE_CONSTANT (e) || code == SAVE_EXPR)
2228     return e;
2229
2230   switch (TREE_CODE_CLASS (code))
2231     {
2232     case 'x':
2233     case 't':
2234     case 'd':
2235     case 'b':
2236     case '<':
2237     case 's':
2238     case 'e':
2239     case 'r':
2240       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2241          so that it will only be evaluated once.  */
2242       /* The reference (r) and comparison (<) classes could be handled as
2243          below, but it is generally faster to only evaluate them once.  */
2244       if (TREE_SIDE_EFFECTS (e))
2245         return save_expr (e);
2246       return e;
2247
2248     case 'c':
2249       /* Constants need no processing.  In fact, we should never reach
2250          here.  */
2251       return e;
2252
2253     case '2':
2254       /* Division is slow and tends to be compiled with jumps,
2255          especially the division by powers of 2 that is often
2256          found inside of an array reference.  So do it just once.  */
2257       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2258           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2259           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2260           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2261         return save_expr (e);
2262       /* Recursively stabilize each operand.  */
2263       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2264                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2265       break;
2266
2267     case '1':
2268       /* Recursively stabilize each operand.  */
2269       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2270       break;
2271
2272     default:
2273       abort ();
2274     }
2275
2276   TREE_TYPE (result) = TREE_TYPE (e);
2277   TREE_READONLY (result) = TREE_READONLY (e);
2278   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2279   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2280
2281   return result;
2282 }
2283 \f
2284 /* Low-level constructors for expressions.  */
2285
2286 /* Build an expression of code CODE, data type TYPE,
2287    and operands as specified by the arguments ARG1 and following arguments.
2288    Expressions and reference nodes can be created this way.
2289    Constants, decls, types and misc nodes cannot be.  */
2290
2291 tree
2292 build (enum tree_code code, tree tt, ...)
2293 {
2294   tree t;
2295   int length;
2296   int i;
2297   int fro;
2298   int constant;
2299   va_list p;
2300
2301   va_start (p, tt);
2302
2303   t = make_node (code);
2304   length = TREE_CODE_LENGTH (code);
2305   TREE_TYPE (t) = tt;
2306
2307   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2308      result based on those same flags for the arguments.  But if the
2309      arguments aren't really even `tree' expressions, we shouldn't be trying
2310      to do this.  */
2311   fro = first_rtl_op (code);
2312
2313   /* Expressions without side effects may be constant if their
2314      arguments are as well.  */
2315   constant = (TREE_CODE_CLASS (code) == '<'
2316               || TREE_CODE_CLASS (code) == '1'
2317               || TREE_CODE_CLASS (code) == '2'
2318               || TREE_CODE_CLASS (code) == 'c');
2319
2320   if (length == 2)
2321     {
2322       /* This is equivalent to the loop below, but faster.  */
2323       tree arg0 = va_arg (p, tree);
2324       tree arg1 = va_arg (p, tree);
2325
2326       TREE_OPERAND (t, 0) = arg0;
2327       TREE_OPERAND (t, 1) = arg1;
2328       TREE_READONLY (t) = 1;
2329       if (arg0 && fro > 0)
2330         {
2331           if (TREE_SIDE_EFFECTS (arg0))
2332             TREE_SIDE_EFFECTS (t) = 1;
2333           if (!TREE_READONLY (arg0))
2334             TREE_READONLY (t) = 0;
2335           if (!TREE_CONSTANT (arg0))
2336             constant = 0;
2337         }
2338
2339       if (arg1 && fro > 1)
2340         {
2341           if (TREE_SIDE_EFFECTS (arg1))
2342             TREE_SIDE_EFFECTS (t) = 1;
2343           if (!TREE_READONLY (arg1))
2344             TREE_READONLY (t) = 0;
2345           if (!TREE_CONSTANT (arg1))
2346             constant = 0;
2347         }
2348     }
2349   else if (length == 1)
2350     {
2351       tree arg0 = va_arg (p, tree);
2352
2353       /* The only one-operand cases we handle here are those with side-effects.
2354          Others are handled with build1.  So don't bother checked if the
2355          arg has side-effects since we'll already have set it.
2356
2357          ??? This really should use build1 too.  */
2358       if (TREE_CODE_CLASS (code) != 's')
2359         abort ();
2360       TREE_OPERAND (t, 0) = arg0;
2361     }
2362   else
2363     {
2364       for (i = 0; i < length; i++)
2365         {
2366           tree operand = va_arg (p, tree);
2367
2368           TREE_OPERAND (t, i) = operand;
2369           if (operand && fro > i)
2370             {
2371               if (TREE_SIDE_EFFECTS (operand))
2372                 TREE_SIDE_EFFECTS (t) = 1;
2373               if (!TREE_CONSTANT (operand))
2374                 constant = 0;
2375             }
2376         }
2377     }
2378   va_end (p);
2379
2380   TREE_CONSTANT (t) = constant;
2381
2382   if (code == CALL_EXPR && !TREE_SIDE_EFFECTS (t))
2383     {
2384       /* Calls have side-effects, except those to const or
2385          pure functions.  */
2386       tree fn = get_callee_fndecl (t);
2387
2388       if (!fn || (!DECL_IS_PURE (fn) && !TREE_READONLY (fn)))
2389         TREE_SIDE_EFFECTS (t) = 1;
2390     }
2391
2392   return t;
2393 }
2394
2395 /* Same as above, but only builds for unary operators.
2396    Saves lions share of calls to `build'; cuts down use
2397    of varargs, which is expensive for RISC machines.  */
2398
2399 tree
2400 build1 (enum tree_code code, tree type, tree node)
2401 {
2402   int length = sizeof (struct tree_exp);
2403 #ifdef GATHER_STATISTICS
2404   tree_node_kind kind;
2405 #endif
2406   tree t;
2407
2408 #ifdef GATHER_STATISTICS
2409   switch (TREE_CODE_CLASS (code))
2410     {
2411     case 's':  /* an expression with side effects */
2412       kind = s_kind;
2413       break;
2414     case 'r':  /* a reference */
2415       kind = r_kind;
2416       break;
2417     default:
2418       kind = e_kind;
2419       break;
2420     }
2421
2422   tree_node_counts[(int) kind]++;
2423   tree_node_sizes[(int) kind] += length;
2424 #endif
2425
2426 #ifdef ENABLE_CHECKING
2427   if (TREE_CODE_CLASS (code) == '2'
2428       || TREE_CODE_CLASS (code) == '<'
2429       || TREE_CODE_LENGTH (code) != 1)
2430     abort ();
2431 #endif /* ENABLE_CHECKING */
2432
2433   t = ggc_alloc_tree (length);
2434
2435   memset (t, 0, sizeof (struct tree_common));
2436
2437   TREE_SET_CODE (t, code);
2438
2439   TREE_TYPE (t) = type;
2440   TREE_COMPLEXITY (t) = 0;
2441   TREE_OPERAND (t, 0) = node;
2442   if (node && first_rtl_op (code) != 0)
2443     {
2444       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2445       TREE_READONLY (t) = TREE_READONLY (node);
2446     }
2447
2448   if (TREE_CODE_CLASS (code) == 's')
2449     TREE_SIDE_EFFECTS (t) = 1;
2450   else switch (code)
2451     {
2452     case INIT_EXPR:
2453     case MODIFY_EXPR:
2454     case VA_ARG_EXPR:
2455     case RTL_EXPR:
2456     case PREDECREMENT_EXPR:
2457     case PREINCREMENT_EXPR:
2458     case POSTDECREMENT_EXPR:
2459     case POSTINCREMENT_EXPR:
2460       /* All of these have side-effects, no matter what their
2461          operands are.  */
2462       TREE_SIDE_EFFECTS (t) = 1;
2463       TREE_READONLY (t) = 0;
2464       break;
2465
2466     case INDIRECT_REF:
2467       /* Whether a dereference is readonly has nothing to do with whether
2468          its operand is readonly.  */
2469       TREE_READONLY (t) = 0;
2470       break;
2471
2472     default:
2473       if (TREE_CODE_CLASS (code) == '1' && node && TREE_CONSTANT (node))
2474         TREE_CONSTANT (t) = 1;
2475       break;
2476     }
2477
2478   return t;
2479 }
2480
2481 /* Similar except don't specify the TREE_TYPE
2482    and leave the TREE_SIDE_EFFECTS as 0.
2483    It is permissible for arguments to be null,
2484    or even garbage if their values do not matter.  */
2485
2486 tree
2487 build_nt (enum tree_code code, ...)
2488 {
2489   tree t;
2490   int length;
2491   int i;
2492   va_list p;
2493
2494   va_start (p, code);
2495
2496   t = make_node (code);
2497   length = TREE_CODE_LENGTH (code);
2498
2499   for (i = 0; i < length; i++)
2500     TREE_OPERAND (t, i) = va_arg (p, tree);
2501
2502   va_end (p);
2503   return t;
2504 }
2505 \f
2506 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2507    We do NOT enter this node in any sort of symbol table.
2508
2509    layout_decl is used to set up the decl's storage layout.
2510    Other slots are initialized to 0 or null pointers.  */
2511
2512 tree
2513 build_decl (enum tree_code code, tree name, tree type)
2514 {
2515   tree t;
2516
2517   t = make_node (code);
2518
2519 /*  if (type == error_mark_node)
2520     type = integer_type_node; */
2521 /* That is not done, deliberately, so that having error_mark_node
2522    as the type can suppress useless errors in the use of this variable.  */
2523
2524   DECL_NAME (t) = name;
2525   TREE_TYPE (t) = type;
2526
2527   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2528     layout_decl (t, 0);
2529   else if (code == FUNCTION_DECL)
2530     DECL_MODE (t) = FUNCTION_MODE;
2531
2532   return t;
2533 }
2534 \f
2535 /* BLOCK nodes are used to represent the structure of binding contours
2536    and declarations, once those contours have been exited and their contents
2537    compiled.  This information is used for outputting debugging info.  */
2538
2539 tree
2540 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2541              tree supercontext, tree chain)
2542 {
2543   tree block = make_node (BLOCK);
2544
2545   BLOCK_VARS (block) = vars;
2546   BLOCK_SUBBLOCKS (block) = subblocks;
2547   BLOCK_SUPERCONTEXT (block) = supercontext;
2548   BLOCK_CHAIN (block) = chain;
2549   return block;
2550 }
2551
2552 /* EXPR_WITH_FILE_LOCATION are used to keep track of the exact
2553    location where an expression or an identifier were encountered. It
2554    is necessary for languages where the frontend parser will handle
2555    recursively more than one file (Java is one of them).  */
2556
2557 tree
2558 build_expr_wfl (tree node, const char *file, int line, int col)
2559 {
2560   static const char *last_file = 0;
2561   static tree last_filenode = NULL_TREE;
2562   tree wfl = make_node (EXPR_WITH_FILE_LOCATION);
2563
2564   EXPR_WFL_NODE (wfl) = node;
2565   EXPR_WFL_SET_LINECOL (wfl, line, col);
2566   if (file != last_file)
2567     {
2568       last_file = file;
2569       last_filenode = file ? get_identifier (file) : NULL_TREE;
2570     }
2571
2572   EXPR_WFL_FILENAME_NODE (wfl) = last_filenode;
2573   if (node)
2574     {
2575       TREE_SIDE_EFFECTS (wfl) = TREE_SIDE_EFFECTS (node);
2576       TREE_TYPE (wfl) = TREE_TYPE (node);
2577     }
2578
2579   return wfl;
2580 }
2581 \f
2582 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2583    is ATTRIBUTE.  */
2584
2585 tree
2586 build_decl_attribute_variant (tree ddecl, tree attribute)
2587 {
2588   DECL_ATTRIBUTES (ddecl) = attribute;
2589   return ddecl;
2590 }
2591
2592 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2593    is ATTRIBUTE.
2594
2595    Record such modified types already made so we don't make duplicates.  */
2596
2597 tree
2598 build_type_attribute_variant (tree ttype, tree attribute)
2599 {
2600   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2601     {
2602       unsigned int hashcode;
2603       tree ntype;
2604
2605       ntype = copy_node (ttype);
2606
2607       TYPE_POINTER_TO (ntype) = 0;
2608       TYPE_REFERENCE_TO (ntype) = 0;
2609       TYPE_ATTRIBUTES (ntype) = attribute;
2610
2611       /* Create a new main variant of TYPE.  */
2612       TYPE_MAIN_VARIANT (ntype) = ntype;
2613       TYPE_NEXT_VARIANT (ntype) = 0;
2614       set_type_quals (ntype, TYPE_UNQUALIFIED);
2615
2616       hashcode = (TYPE_HASH (TREE_CODE (ntype))
2617                   + TYPE_HASH (TREE_TYPE (ntype))
2618                   + attribute_hash_list (attribute));
2619
2620       switch (TREE_CODE (ntype))
2621         {
2622         case FUNCTION_TYPE:
2623           hashcode += TYPE_HASH (TYPE_ARG_TYPES (ntype));
2624           break;
2625         case ARRAY_TYPE:
2626           hashcode += TYPE_HASH (TYPE_DOMAIN (ntype));
2627           break;
2628         case INTEGER_TYPE:
2629           hashcode += TYPE_HASH (TYPE_MAX_VALUE (ntype));
2630           break;
2631         case REAL_TYPE:
2632           hashcode += TYPE_HASH (TYPE_PRECISION (ntype));
2633           break;
2634         default:
2635           break;
2636         }
2637
2638       ntype = type_hash_canon (hashcode, ntype);
2639       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2640     }
2641
2642   return ttype;
2643 }
2644
2645 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2646    or zero if not.
2647
2648    We try both `text' and `__text__', ATTR may be either one.  */
2649 /* ??? It might be a reasonable simplification to require ATTR to be only
2650    `text'.  One might then also require attribute lists to be stored in
2651    their canonicalized form.  */
2652
2653 int
2654 is_attribute_p (const char *attr, tree ident)
2655 {
2656   int ident_len, attr_len;
2657   const char *p;
2658
2659   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2660     return 0;
2661
2662   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2663     return 1;
2664
2665   p = IDENTIFIER_POINTER (ident);
2666   ident_len = strlen (p);
2667   attr_len = strlen (attr);
2668
2669   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2670   if (attr[0] == '_')
2671     {
2672       if (attr[1] != '_'
2673           || attr[attr_len - 2] != '_'
2674           || attr[attr_len - 1] != '_')
2675         abort ();
2676       if (ident_len == attr_len - 4
2677           && strncmp (attr + 2, p, attr_len - 4) == 0)
2678         return 1;
2679     }
2680   else
2681     {
2682       if (ident_len == attr_len + 4
2683           && p[0] == '_' && p[1] == '_'
2684           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2685           && strncmp (attr, p + 2, attr_len) == 0)
2686         return 1;
2687     }
2688
2689   return 0;
2690 }
2691
2692 /* Given an attribute name and a list of attributes, return a pointer to the
2693    attribute's list element if the attribute is part of the list, or NULL_TREE
2694    if not found.  If the attribute appears more than once, this only
2695    returns the first occurrence; the TREE_CHAIN of the return value should
2696    be passed back in if further occurrences are wanted.  */
2697
2698 tree
2699 lookup_attribute (const char *attr_name, tree list)
2700 {
2701   tree l;
2702
2703   for (l = list; l; l = TREE_CHAIN (l))
2704     {
2705       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2706         abort ();
2707       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2708         return l;
2709     }
2710
2711   return NULL_TREE;
2712 }
2713
2714 /* Return an attribute list that is the union of a1 and a2.  */
2715
2716 tree
2717 merge_attributes (tree a1, tree a2)
2718 {
2719   tree attributes;
2720
2721   /* Either one unset?  Take the set one.  */
2722
2723   if ((attributes = a1) == 0)
2724     attributes = a2;
2725
2726   /* One that completely contains the other?  Take it.  */
2727
2728   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2729     {
2730       if (attribute_list_contained (a2, a1))
2731         attributes = a2;
2732       else
2733         {
2734           /* Pick the longest list, and hang on the other list.  */
2735
2736           if (list_length (a1) < list_length (a2))
2737             attributes = a2, a2 = a1;
2738
2739           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2740             {
2741               tree a;
2742               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2743                                          attributes);
2744                    a != NULL_TREE;
2745                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2746                                          TREE_CHAIN (a)))
2747                 {
2748                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2749                     break;
2750                 }
2751               if (a == NULL_TREE)
2752                 {
2753                   a1 = copy_node (a2);
2754                   TREE_CHAIN (a1) = attributes;
2755                   attributes = a1;
2756                 }
2757             }
2758         }
2759     }
2760   return attributes;
2761 }
2762
2763 /* Given types T1 and T2, merge their attributes and return
2764   the result.  */
2765
2766 tree
2767 merge_type_attributes (tree t1, tree t2)
2768 {
2769   return merge_attributes (TYPE_ATTRIBUTES (t1),
2770                            TYPE_ATTRIBUTES (t2));
2771 }
2772
2773 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
2774    the result.  */
2775
2776 tree
2777 merge_decl_attributes (tree olddecl, tree newdecl)
2778 {
2779   return merge_attributes (DECL_ATTRIBUTES (olddecl),
2780                            DECL_ATTRIBUTES (newdecl));
2781 }
2782
2783 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
2784
2785 /* Specialization of merge_decl_attributes for various Windows targets.
2786
2787    This handles the following situation:
2788
2789      __declspec (dllimport) int foo;
2790      int foo;
2791
2792    The second instance of `foo' nullifies the dllimport.  */
2793
2794 tree
2795 merge_dllimport_decl_attributes (tree old, tree new)
2796 {
2797   tree a;
2798   int delete_dllimport_p;
2799
2800   old = DECL_ATTRIBUTES (old);
2801   new = DECL_ATTRIBUTES (new);
2802
2803   /* What we need to do here is remove from `old' dllimport if it doesn't
2804      appear in `new'.  dllimport behaves like extern: if a declaration is
2805      marked dllimport and a definition appears later, then the object
2806      is not dllimport'd.  */
2807   if (lookup_attribute ("dllimport", old) != NULL_TREE
2808       && lookup_attribute ("dllimport", new) == NULL_TREE)
2809     delete_dllimport_p = 1;
2810   else
2811     delete_dllimport_p = 0;
2812
2813   a = merge_attributes (old, new);
2814
2815   if (delete_dllimport_p)
2816     {
2817       tree prev, t;
2818
2819       /* Scan the list for dllimport and delete it.  */
2820       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
2821         {
2822           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
2823             {
2824               if (prev == NULL_TREE)
2825                 a = TREE_CHAIN (a);
2826               else
2827                 TREE_CHAIN (prev) = TREE_CHAIN (t);
2828               break;
2829             }
2830         }
2831     }
2832
2833   return a;
2834 }
2835
2836 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
2837 \f
2838 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
2839    of the various TYPE_QUAL values.  */
2840
2841 static void
2842 set_type_quals (tree type, int type_quals)
2843 {
2844   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
2845   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
2846   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
2847 }
2848
2849 /* Return a version of the TYPE, qualified as indicated by the
2850    TYPE_QUALS, if one exists.  If no qualified version exists yet,
2851    return NULL_TREE.  */
2852
2853 tree
2854 get_qualified_type (tree type, int type_quals)
2855 {
2856   tree t;
2857
2858   /* Search the chain of variants to see if there is already one there just
2859      like the one we need to have.  If so, use that existing one.  We must
2860      preserve the TYPE_NAME, since there is code that depends on this.  */
2861   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
2862     if (TYPE_QUALS (t) == type_quals && TYPE_NAME (t) == TYPE_NAME (type)
2863         && TYPE_CONTEXT (t) == TYPE_CONTEXT (type)
2864         && attribute_list_equal (TYPE_ATTRIBUTES (t), TYPE_ATTRIBUTES (type)))
2865       return t;
2866
2867   return NULL_TREE;
2868 }
2869
2870 /* Like get_qualified_type, but creates the type if it does not
2871    exist.  This function never returns NULL_TREE.  */
2872
2873 tree
2874 build_qualified_type (tree type, int type_quals)
2875 {
2876   tree t;
2877
2878   /* See if we already have the appropriate qualified variant.  */
2879   t = get_qualified_type (type, type_quals);
2880
2881   /* If not, build it.  */
2882   if (!t)
2883     {
2884       t = build_type_copy (type);
2885       set_type_quals (t, type_quals);
2886     }
2887
2888   return t;
2889 }
2890
2891 /* Create a new variant of TYPE, equivalent but distinct.
2892    This is so the caller can modify it.  */
2893
2894 tree
2895 build_type_copy (tree type)
2896 {
2897   tree t, m = TYPE_MAIN_VARIANT (type);
2898
2899   t = copy_node (type);
2900
2901   TYPE_POINTER_TO (t) = 0;
2902   TYPE_REFERENCE_TO (t) = 0;
2903
2904   /* Add this type to the chain of variants of TYPE.  */
2905   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
2906   TYPE_NEXT_VARIANT (m) = t;
2907
2908   return t;
2909 }
2910 \f
2911 /* Hashing of types so that we don't make duplicates.
2912    The entry point is `type_hash_canon'.  */
2913
2914 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
2915    with types in the TREE_VALUE slots), by adding the hash codes
2916    of the individual types.  */
2917
2918 unsigned int
2919 type_hash_list (tree list)
2920 {
2921   unsigned int hashcode;
2922   tree tail;
2923
2924   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
2925     hashcode += TYPE_HASH (TREE_VALUE (tail));
2926
2927   return hashcode;
2928 }
2929
2930 /* These are the Hashtable callback functions.  */
2931
2932 /* Returns true if the types are equal.  */
2933
2934 static int
2935 type_hash_eq (const void *va, const void *vb)
2936 {
2937   const struct type_hash *a = va, *b = vb;
2938   if (a->hash == b->hash
2939       && TREE_CODE (a->type) == TREE_CODE (b->type)
2940       && TREE_TYPE (a->type) == TREE_TYPE (b->type)
2941       && attribute_list_equal (TYPE_ATTRIBUTES (a->type),
2942                                TYPE_ATTRIBUTES (b->type))
2943       && TYPE_ALIGN (a->type) == TYPE_ALIGN (b->type)
2944       && (TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
2945           || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
2946                                  TYPE_MAX_VALUE (b->type)))
2947       && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
2948           || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
2949                                  TYPE_MIN_VALUE (b->type)))
2950       /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE.  */
2951       && (TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type)
2952           || (TYPE_DOMAIN (a->type)
2953               && TREE_CODE (TYPE_DOMAIN (a->type)) == TREE_LIST
2954               && TYPE_DOMAIN (b->type)
2955               && TREE_CODE (TYPE_DOMAIN (b->type)) == TREE_LIST
2956               && type_list_equal (TYPE_DOMAIN (a->type),
2957                                   TYPE_DOMAIN (b->type)))))
2958     return 1;
2959   return 0;
2960 }
2961
2962 /* Return the cached hash value.  */
2963
2964 static hashval_t
2965 type_hash_hash (const void *item)
2966 {
2967   return ((const struct type_hash *) item)->hash;
2968 }
2969
2970 /* Look in the type hash table for a type isomorphic to TYPE.
2971    If one is found, return it.  Otherwise return 0.  */
2972
2973 tree
2974 type_hash_lookup (unsigned int hashcode, tree type)
2975 {
2976   struct type_hash *h, in;
2977
2978   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
2979      must call that routine before comparing TYPE_ALIGNs.  */
2980   layout_type (type);
2981
2982   in.hash = hashcode;
2983   in.type = type;
2984
2985   h = htab_find_with_hash (type_hash_table, &in, hashcode);
2986   if (h)
2987     return h->type;
2988   return NULL_TREE;
2989 }
2990
2991 /* Add an entry to the type-hash-table
2992    for a type TYPE whose hash code is HASHCODE.  */
2993
2994 void
2995 type_hash_add (unsigned int hashcode, tree type)
2996 {
2997   struct type_hash *h;
2998   void **loc;
2999
3000   h = ggc_alloc (sizeof (struct type_hash));
3001   h->hash = hashcode;
3002   h->type = type;
3003   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3004   *(struct type_hash **) loc = h;
3005 }
3006
3007 /* Given TYPE, and HASHCODE its hash code, return the canonical
3008    object for an identical type if one already exists.
3009    Otherwise, return TYPE, and record it as the canonical object
3010    if it is a permanent object.
3011
3012    To use this function, first create a type of the sort you want.
3013    Then compute its hash code from the fields of the type that
3014    make it different from other similar types.
3015    Then call this function and use the value.
3016    This function frees the type you pass in if it is a duplicate.  */
3017
3018 /* Set to 1 to debug without canonicalization.  Never set by program.  */
3019 int debug_no_type_hash = 0;
3020
3021 tree
3022 type_hash_canon (unsigned int hashcode, tree type)
3023 {
3024   tree t1;
3025
3026   if (debug_no_type_hash)
3027     return type;
3028
3029   /* See if the type is in the hash table already.  If so, return it.
3030      Otherwise, add the type.  */
3031   t1 = type_hash_lookup (hashcode, type);
3032   if (t1 != 0)
3033     {
3034 #ifdef GATHER_STATISTICS
3035       tree_node_counts[(int) t_kind]--;
3036       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3037 #endif
3038       return t1;
3039     }
3040   else
3041     {
3042       type_hash_add (hashcode, type);
3043       return type;
3044     }
3045 }
3046
3047 /* See if the data pointed to by the type hash table is marked.  We consider
3048    it marked if the type is marked or if a debug type number or symbol
3049    table entry has been made for the type.  This reduces the amount of
3050    debugging output and eliminates that dependency of the debug output on
3051    the number of garbage collections.  */
3052
3053 static int
3054 type_hash_marked_p (const void *p)
3055 {
3056   tree type = ((struct type_hash *) p)->type;
3057
3058   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3059 }
3060
3061 static void
3062 print_type_hash_statistics (void)
3063 {
3064   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3065            (long) htab_size (type_hash_table),
3066            (long) htab_elements (type_hash_table),
3067            htab_collisions (type_hash_table));
3068 }
3069
3070 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3071    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3072    by adding the hash codes of the individual attributes.  */
3073
3074 unsigned int
3075 attribute_hash_list (tree list)
3076 {
3077   unsigned int hashcode;
3078   tree tail;
3079
3080   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
3081     /* ??? Do we want to add in TREE_VALUE too? */
3082     hashcode += TYPE_HASH (TREE_PURPOSE (tail));
3083   return hashcode;
3084 }
3085
3086 /* Given two lists of attributes, return true if list l2 is
3087    equivalent to l1.  */
3088
3089 int
3090 attribute_list_equal (tree l1, tree l2)
3091 {
3092   return attribute_list_contained (l1, l2)
3093          && attribute_list_contained (l2, l1);
3094 }
3095
3096 /* Given two lists of attributes, return true if list L2 is
3097    completely contained within L1.  */
3098 /* ??? This would be faster if attribute names were stored in a canonicalized
3099    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3100    must be used to show these elements are equivalent (which they are).  */
3101 /* ??? It's not clear that attributes with arguments will always be handled
3102    correctly.  */
3103
3104 int
3105 attribute_list_contained (tree l1, tree l2)
3106 {
3107   tree t1, t2;
3108
3109   /* First check the obvious, maybe the lists are identical.  */
3110   if (l1 == l2)
3111     return 1;
3112
3113   /* Maybe the lists are similar.  */
3114   for (t1 = l1, t2 = l2;
3115        t1 != 0 && t2 != 0
3116         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3117         && TREE_VALUE (t1) == TREE_VALUE (t2);
3118        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3119
3120   /* Maybe the lists are equal.  */
3121   if (t1 == 0 && t2 == 0)
3122     return 1;
3123
3124   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3125     {
3126       tree attr;
3127       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3128            attr != NULL_TREE;
3129            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3130                                     TREE_CHAIN (attr)))
3131         {
3132           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3133             break;
3134         }
3135
3136       if (attr == 0)
3137         return 0;
3138
3139       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3140         return 0;
3141     }
3142
3143   return 1;
3144 }
3145
3146 /* Given two lists of types
3147    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3148    return 1 if the lists contain the same types in the same order.
3149    Also, the TREE_PURPOSEs must match.  */
3150
3151 int
3152 type_list_equal (tree l1, tree l2)
3153 {
3154   tree t1, t2;
3155
3156   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3157     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3158         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3159             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3160                   && (TREE_TYPE (TREE_PURPOSE (t1))
3161                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3162       return 0;
3163
3164   return t1 == t2;
3165 }
3166
3167 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3168    given by TYPE.  If the argument list accepts variable arguments,
3169    then this function counts only the ordinary arguments.  */
3170
3171 int
3172 type_num_arguments (tree type)
3173 {
3174   int i = 0;
3175   tree t;
3176
3177   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3178     /* If the function does not take a variable number of arguments,
3179        the last element in the list will have type `void'.  */
3180     if (VOID_TYPE_P (TREE_VALUE (t)))
3181       break;
3182     else
3183       ++i;
3184
3185   return i;
3186 }
3187
3188 /* Nonzero if integer constants T1 and T2
3189    represent the same constant value.  */
3190
3191 int
3192 tree_int_cst_equal (tree t1, tree t2)
3193 {
3194   if (t1 == t2)
3195     return 1;
3196
3197   if (t1 == 0 || t2 == 0)
3198     return 0;
3199
3200   if (TREE_CODE (t1) == INTEGER_CST
3201       && TREE_CODE (t2) == INTEGER_CST
3202       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3203       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3204     return 1;
3205
3206   return 0;
3207 }
3208
3209 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3210    The precise way of comparison depends on their data type.  */
3211
3212 int
3213 tree_int_cst_lt (tree t1, tree t2)
3214 {
3215   if (t1 == t2)
3216     return 0;
3217
3218   if (TREE_UNSIGNED (TREE_TYPE (t1)) != TREE_UNSIGNED (TREE_TYPE (t2)))
3219     {
3220       int t1_sgn = tree_int_cst_sgn (t1);
3221       int t2_sgn = tree_int_cst_sgn (t2);
3222
3223       if (t1_sgn < t2_sgn)
3224         return 1;
3225       else if (t1_sgn > t2_sgn)
3226         return 0;
3227       /* Otherwise, both are non-negative, so we compare them as
3228          unsigned just in case one of them would overflow a signed
3229          type.  */
3230     }
3231   else if (! TREE_UNSIGNED (TREE_TYPE (t1)))
3232     return INT_CST_LT (t1, t2);
3233
3234   return INT_CST_LT_UNSIGNED (t1, t2);
3235 }
3236
3237 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3238
3239 int
3240 tree_int_cst_compare (tree t1, tree t2)
3241 {
3242   if (tree_int_cst_lt (t1, t2))
3243     return -1;
3244   else if (tree_int_cst_lt (t2, t1))
3245     return 1;
3246   else
3247     return 0;
3248 }
3249
3250 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3251    the host.  If POS is zero, the value can be represented in a single
3252    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3253    be represented in a single unsigned HOST_WIDE_INT.  */
3254
3255 int
3256 host_integerp (tree t, int pos)
3257 {
3258   return (TREE_CODE (t) == INTEGER_CST
3259           && ! TREE_OVERFLOW (t)
3260           && ((TREE_INT_CST_HIGH (t) == 0
3261                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3262               || (! pos && TREE_INT_CST_HIGH (t) == -1
3263                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3264                   && ! TREE_UNSIGNED (TREE_TYPE (t)))
3265               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3266 }
3267
3268 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3269    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3270    be positive.  Abort if we cannot satisfy the above conditions.  */
3271
3272 HOST_WIDE_INT
3273 tree_low_cst (tree t, int pos)
3274 {
3275   if (host_integerp (t, pos))
3276     return TREE_INT_CST_LOW (t);
3277   else
3278     abort ();
3279 }
3280
3281 /* Return the most significant bit of the integer constant T.  */
3282
3283 int
3284 tree_int_cst_msb (tree t)
3285 {
3286   int prec;
3287   HOST_WIDE_INT h;
3288   unsigned HOST_WIDE_INT l;
3289
3290   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3291      actual bits, not the (arbitrary) range of the type.  */
3292   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3293   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3294                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3295   return (l & 1) == 1;
3296 }
3297
3298 /* Return an indication of the sign of the integer constant T.
3299    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3300    Note that -1 will never be returned it T's type is unsigned.  */
3301
3302 int
3303 tree_int_cst_sgn (tree t)
3304 {
3305   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3306     return 0;
3307   else if (TREE_UNSIGNED (TREE_TYPE (t)))
3308     return 1;
3309   else if (TREE_INT_CST_HIGH (t) < 0)
3310     return -1;
3311   else
3312     return 1;
3313 }
3314
3315 /* Compare two constructor-element-type constants.  Return 1 if the lists
3316    are known to be equal; otherwise return 0.  */
3317
3318 int
3319 simple_cst_list_equal (tree l1, tree l2)
3320 {
3321   while (l1 != NULL_TREE && l2 != NULL_TREE)
3322     {
3323       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3324         return 0;
3325
3326       l1 = TREE_CHAIN (l1);
3327       l2 = TREE_CHAIN (l2);
3328     }
3329
3330   return l1 == l2;
3331 }
3332
3333 /* Return truthvalue of whether T1 is the same tree structure as T2.
3334    Return 1 if they are the same.
3335    Return 0 if they are understandably different.
3336    Return -1 if either contains tree structure not understood by
3337    this function.  */
3338
3339 int
3340 simple_cst_equal (tree t1, tree t2)
3341 {
3342   enum tree_code code1, code2;
3343   int cmp;
3344   int i;
3345
3346   if (t1 == t2)
3347     return 1;
3348   if (t1 == 0 || t2 == 0)
3349     return 0;
3350
3351   code1 = TREE_CODE (t1);
3352   code2 = TREE_CODE (t2);
3353
3354   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3355     {
3356       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3357           || code2 == NON_LVALUE_EXPR)
3358         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3359       else
3360         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3361     }
3362
3363   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3364            || code2 == NON_LVALUE_EXPR)
3365     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3366
3367   if (code1 != code2)
3368     return 0;
3369
3370   switch (code1)
3371     {
3372     case INTEGER_CST:
3373       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3374               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3375
3376     case REAL_CST:
3377       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3378
3379     case STRING_CST:
3380       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3381               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3382                          TREE_STRING_LENGTH (t1)));
3383
3384     case CONSTRUCTOR:
3385       if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
3386         return 1;
3387       else
3388         abort ();
3389
3390     case SAVE_EXPR:
3391       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3392
3393     case CALL_EXPR:
3394       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3395       if (cmp <= 0)
3396         return cmp;
3397       return
3398         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3399
3400     case TARGET_EXPR:
3401       /* Special case: if either target is an unallocated VAR_DECL,
3402          it means that it's going to be unified with whatever the
3403          TARGET_EXPR is really supposed to initialize, so treat it
3404          as being equivalent to anything.  */
3405       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3406            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3407            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3408           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3409               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3410               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3411         cmp = 1;
3412       else
3413         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3414
3415       if (cmp <= 0)
3416         return cmp;
3417
3418       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3419
3420     case WITH_CLEANUP_EXPR:
3421       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3422       if (cmp <= 0)
3423         return cmp;
3424
3425       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3426
3427     case COMPONENT_REF:
3428       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3429         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3430
3431       return 0;
3432
3433     case VAR_DECL:
3434     case PARM_DECL:
3435     case CONST_DECL:
3436     case FUNCTION_DECL:
3437       return 0;
3438
3439     default:
3440       break;
3441     }
3442
3443   /* This general rule works for most tree codes.  All exceptions should be
3444      handled above.  If this is a language-specific tree code, we can't
3445      trust what might be in the operand, so say we don't know
3446      the situation.  */
3447   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3448     return -1;
3449
3450   switch (TREE_CODE_CLASS (code1))
3451     {
3452     case '1':
3453     case '2':
3454     case '<':
3455     case 'e':
3456     case 'r':
3457     case 's':
3458       cmp = 1;
3459       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3460         {
3461           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3462           if (cmp <= 0)
3463             return cmp;
3464         }
3465
3466       return cmp;
3467
3468     default:
3469       return -1;
3470     }
3471 }
3472
3473 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3474    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3475    than U, respectively.  */
3476
3477 int
3478 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3479 {
3480   if (tree_int_cst_sgn (t) < 0)
3481     return -1;
3482   else if (TREE_INT_CST_HIGH (t) != 0)
3483     return 1;
3484   else if (TREE_INT_CST_LOW (t) == u)
3485     return 0;
3486   else if (TREE_INT_CST_LOW (t) < u)
3487     return -1;
3488   else
3489     return 1;
3490 }
3491
3492 /* Generate a hash value for an expression.  This can be used iteratively
3493    by passing a previous result as the "val" argument.
3494
3495    This function is intended to produce the same hash for expressions which
3496    would compare equal using operand_equal_p.  */
3497
3498 hashval_t
3499 iterative_hash_expr (tree t, hashval_t val)
3500 {
3501   int i;
3502   enum tree_code code;
3503   char class;
3504
3505   if (t == NULL_TREE)
3506     return iterative_hash_object (t, val);
3507
3508   code = TREE_CODE (t);
3509   class = TREE_CODE_CLASS (code);
3510
3511   if (class == 'd')
3512     {
3513       /* Decls we can just compare by pointer.  */
3514       val = iterative_hash_object (t, val);
3515     }
3516   else if (class == 'c')
3517     {
3518       /* Alas, constants aren't shared, so we can't rely on pointer
3519          identity.  */
3520       if (code == INTEGER_CST)
3521         {
3522           val = iterative_hash_object (TREE_INT_CST_LOW (t), val);
3523           val = iterative_hash_object (TREE_INT_CST_HIGH (t), val);
3524         }
3525       else if (code == REAL_CST)
3526         val = iterative_hash (TREE_REAL_CST_PTR (t),
3527                               sizeof (REAL_VALUE_TYPE), val);
3528       else if (code == STRING_CST)
3529         val = iterative_hash (TREE_STRING_POINTER (t),
3530                               TREE_STRING_LENGTH (t), val);
3531       else if (code == COMPLEX_CST)
3532         {
3533           val = iterative_hash_expr (TREE_REALPART (t), val);
3534           val = iterative_hash_expr (TREE_IMAGPART (t), val);
3535         }
3536       else if (code == VECTOR_CST)
3537         val = iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
3538       else
3539         abort ();
3540     }
3541   else if (IS_EXPR_CODE_CLASS (class))
3542     {
3543       val = iterative_hash_object (code, val);
3544
3545       if (code == NOP_EXPR || code == CONVERT_EXPR
3546           || code == NON_LVALUE_EXPR)
3547         val = iterative_hash_object (TREE_TYPE (t), val);
3548
3549       if (code == PLUS_EXPR || code == MULT_EXPR || code == MIN_EXPR
3550           || code == MAX_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR
3551           || code == BIT_AND_EXPR || code == NE_EXPR || code == EQ_EXPR)
3552         {
3553           /* It's a commutative expression.  We want to hash it the same
3554              however it appears.  We do this by first hashing both operands
3555              and then rehashing based on the order of their independent
3556              hashes.  */
3557           hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
3558           hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
3559           hashval_t t;
3560
3561           if (one > two)
3562             t = one, one = two, two = t;
3563
3564           val = iterative_hash_object (one, val);
3565           val = iterative_hash_object (two, val);
3566         }
3567       else
3568         for (i = first_rtl_op (code) - 1; i >= 0; --i)
3569           val = iterative_hash_expr (TREE_OPERAND (t, i), val);
3570     }
3571   else if (code == TREE_LIST)
3572     {
3573       /* A list of expressions, for a CALL_EXPR or as the elements of a
3574          VECTOR_CST.  */
3575       for (; t; t = TREE_CHAIN (t))
3576         val = iterative_hash_expr (TREE_VALUE (t), val);
3577     }
3578   else
3579     abort ();
3580
3581   return val;
3582 }
3583 \f
3584 /* Constructors for pointer, array and function types.
3585    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3586    constructed by language-dependent code, not here.)  */
3587
3588 /* Construct, lay out and return the type of pointers to TO_TYPE
3589    with mode MODE. If such a type has already been constructed,
3590    reuse it.  */
3591
3592 tree
3593 build_pointer_type_for_mode (tree to_type, enum machine_mode mode)
3594 {
3595   tree t = TYPE_POINTER_TO (to_type);
3596
3597   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3598   if (t != 0 && mode == ptr_mode)
3599     return t;
3600
3601   t = make_node (POINTER_TYPE);
3602
3603   TREE_TYPE (t) = to_type;
3604   TYPE_MODE (t) = mode;
3605
3606   /* Record this type as the pointer to TO_TYPE.  */
3607   if (mode == ptr_mode)
3608   TYPE_POINTER_TO (to_type) = t;
3609
3610   /* Lay out the type.  This function has many callers that are concerned
3611      with expression-construction, and this simplifies them all.
3612      Also, it guarantees the TYPE_SIZE is in the same obstack as the type.  */
3613   layout_type (t);
3614
3615   return t;
3616 }
3617
3618 /* By default build pointers in ptr_mode.  */
3619
3620 tree
3621 build_pointer_type (tree to_type)
3622 {
3623   return build_pointer_type_for_mode (to_type, ptr_mode);
3624 }
3625
3626 /* Construct, lay out and return the type of references to TO_TYPE
3627    with mode MODE. If such a type has already been constructed,
3628    reuse it.  */
3629
3630 tree
3631 build_reference_type_for_mode (tree to_type, enum machine_mode mode)
3632 {
3633   tree t = TYPE_REFERENCE_TO (to_type);
3634
3635   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3636   if (t != 0 && mode == ptr_mode)
3637     return t;
3638
3639   t = make_node (REFERENCE_TYPE);
3640
3641   TREE_TYPE (t) = to_type;
3642   TYPE_MODE (t) = mode;
3643
3644   /* Record this type as the pointer to TO_TYPE.  */
3645   if (mode == ptr_mode)
3646   TYPE_REFERENCE_TO (to_type) = t;
3647
3648   layout_type (t);
3649
3650   return t;
3651 }
3652
3653
3654 /* Build the node for the type of references-to-TO_TYPE by default
3655    in ptr_mode.  */
3656
3657 tree
3658 build_reference_type (tree to_type)
3659 {
3660   return build_reference_type_for_mode (to_type, ptr_mode);
3661 }
3662
3663 /* Build a type that is compatible with t but has no cv quals anywhere
3664    in its type, thus
3665
3666    const char *const *const *  ->  char ***.  */
3667
3668 tree
3669 build_type_no_quals (tree t)
3670 {
3671   switch (TREE_CODE (t))
3672     {
3673     case POINTER_TYPE:
3674       return build_pointer_type (build_type_no_quals (TREE_TYPE (t)));
3675     case REFERENCE_TYPE:
3676       return build_reference_type (build_type_no_quals (TREE_TYPE (t)));
3677     default:
3678       return TYPE_MAIN_VARIANT (t);
3679     }
3680 }
3681
3682 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
3683    MAXVAL should be the maximum value in the domain
3684    (one less than the length of the array).
3685
3686    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
3687    We don't enforce this limit, that is up to caller (e.g. language front end).
3688    The limit exists because the result is a signed type and we don't handle
3689    sizes that use more than one HOST_WIDE_INT.  */
3690
3691 tree
3692 build_index_type (tree maxval)
3693 {
3694   tree itype = make_node (INTEGER_TYPE);
3695
3696   TREE_TYPE (itype) = sizetype;
3697   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
3698   TYPE_MIN_VALUE (itype) = size_zero_node;
3699   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
3700   TYPE_MODE (itype) = TYPE_MODE (sizetype);
3701   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
3702   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
3703   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
3704   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
3705
3706   if (host_integerp (maxval, 1))
3707     return type_hash_canon (tree_low_cst (maxval, 1), itype);
3708   else
3709     return itype;
3710 }
3711
3712 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
3713    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
3714    low bound LOWVAL and high bound HIGHVAL.
3715    if TYPE==NULL_TREE, sizetype is used.  */
3716
3717 tree
3718 build_range_type (tree type, tree lowval, tree highval)
3719 {
3720   tree itype = make_node (INTEGER_TYPE);
3721
3722   TREE_TYPE (itype) = type;
3723   if (type == NULL_TREE)
3724     type = sizetype;
3725
3726   TYPE_MIN_VALUE (itype) = convert (type, lowval);
3727   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
3728
3729   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
3730   TYPE_MODE (itype) = TYPE_MODE (type);
3731   TYPE_SIZE (itype) = TYPE_SIZE (type);
3732   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
3733   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
3734   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
3735
3736   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
3737     return type_hash_canon (tree_low_cst (highval, 0)
3738                             - tree_low_cst (lowval, 0),
3739                             itype);
3740   else
3741     return itype;
3742 }
3743
3744 /* Just like build_index_type, but takes lowval and highval instead
3745    of just highval (maxval).  */
3746
3747 tree
3748 build_index_2_type (tree lowval, tree highval)
3749 {
3750   return build_range_type (sizetype, lowval, highval);
3751 }
3752
3753 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
3754    and number of elements specified by the range of values of INDEX_TYPE.
3755    If such a type has already been constructed, reuse it.  */
3756
3757 tree
3758 build_array_type (tree elt_type, tree index_type)
3759 {
3760   tree t;
3761   unsigned int hashcode;
3762
3763   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
3764     {
3765       error ("arrays of functions are not meaningful");
3766       elt_type = integer_type_node;
3767     }
3768
3769   /* Make sure TYPE_POINTER_TO (elt_type) is filled in.  */
3770   build_pointer_type (elt_type);
3771
3772   /* Allocate the array after the pointer type,
3773      in case we free it in type_hash_canon.  */
3774   t = make_node (ARRAY_TYPE);
3775   TREE_TYPE (t) = elt_type;
3776   TYPE_DOMAIN (t) = index_type;
3777
3778   if (index_type == 0)
3779     {
3780       return t;
3781     }
3782
3783   hashcode = TYPE_HASH (elt_type) + TYPE_HASH (index_type);
3784   t = type_hash_canon (hashcode, t);
3785
3786   if (!COMPLETE_TYPE_P (t))
3787     layout_type (t);
3788   return t;
3789 }
3790
3791 /* Return the TYPE of the elements comprising
3792    the innermost dimension of ARRAY.  */
3793
3794 tree
3795 get_inner_array_type (tree array)
3796 {
3797   tree type = TREE_TYPE (array);
3798
3799   while (TREE_CODE (type) == ARRAY_TYPE)
3800     type = TREE_TYPE (type);
3801
3802   return type;
3803 }
3804
3805 /* Construct, lay out and return
3806    the type of functions returning type VALUE_TYPE
3807    given arguments of types ARG_TYPES.
3808    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
3809    are data type nodes for the arguments of the function.
3810    If such a type has already been constructed, reuse it.  */
3811
3812 tree
3813 build_function_type (tree value_type, tree arg_types)
3814 {
3815   tree t;
3816   unsigned int hashcode;
3817
3818   if (TREE_CODE (value_type) == FUNCTION_TYPE)
3819     {
3820       error ("function return type cannot be function");
3821       value_type = integer_type_node;
3822     }
3823
3824   /* Make a node of the sort we want.  */
3825   t = make_node (FUNCTION_TYPE);
3826   TREE_TYPE (t) = value_type;
3827   TYPE_ARG_TYPES (t) = arg_types;
3828
3829   /* If we already have such a type, use the old one and free this one.  */
3830   hashcode = TYPE_HASH (value_type) + type_hash_list (arg_types);
3831   t = type_hash_canon (hashcode, t);
3832
3833   if (!COMPLETE_TYPE_P (t))
3834     layout_type (t);
3835   return t;
3836 }
3837
3838 /* Build a function type.  The RETURN_TYPE is the type returned by the
3839    function.  If additional arguments are provided, they are
3840    additional argument types.  The list of argument types must always
3841    be terminated by NULL_TREE.  */
3842
3843 tree
3844 build_function_type_list (tree return_type, ...)
3845 {
3846   tree t, args, last;
3847   va_list p;
3848
3849   va_start (p, return_type);
3850
3851   t = va_arg (p, tree);
3852   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
3853     args = tree_cons (NULL_TREE, t, args);
3854
3855   last = args;
3856   args = nreverse (args);
3857   TREE_CHAIN (last) = void_list_node;
3858   args = build_function_type (return_type, args);
3859
3860   va_end (p);
3861   return args;
3862 }
3863
3864 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
3865    and ARGTYPES (a TREE_LIST) are the return type and arguments types
3866    for the method.  An implicit additional parameter (of type
3867    pointer-to-BASETYPE) is added to the ARGTYPES.  */
3868
3869 tree
3870 build_method_type_directly (tree basetype,
3871                             tree rettype,
3872                             tree argtypes)
3873 {
3874   tree t;
3875   tree ptype;
3876   int hashcode;
3877
3878   /* Make a node of the sort we want.  */
3879   t = make_node (METHOD_TYPE);
3880
3881   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3882   TREE_TYPE (t) = rettype;
3883   ptype = build_pointer_type (basetype);
3884
3885   /* The actual arglist for this function includes a "hidden" argument
3886      which is "this".  Put it into the list of argument types.  */
3887   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
3888   TYPE_ARG_TYPES (t) = argtypes;
3889
3890   /* If we already have such a type, use the old one and free this one.
3891      Note that it also frees up the above cons cell if found.  */
3892   hashcode = TYPE_HASH (basetype) + TYPE_HASH (rettype) +
3893     type_hash_list (argtypes);
3894
3895   t = type_hash_canon (hashcode, t);
3896
3897   if (!COMPLETE_TYPE_P (t))
3898     layout_type (t);
3899
3900   return t;
3901 }
3902
3903 /* Construct, lay out and return the type of methods belonging to class
3904    BASETYPE and whose arguments and values are described by TYPE.
3905    If that type exists already, reuse it.
3906    TYPE must be a FUNCTION_TYPE node.  */
3907
3908 tree
3909 build_method_type (tree basetype, tree type)
3910 {
3911   if (TREE_CODE (type) != FUNCTION_TYPE)
3912     abort ();
3913
3914   return build_method_type_directly (basetype,
3915                                      TREE_TYPE (type),
3916                                      TYPE_ARG_TYPES (type));
3917 }
3918
3919 /* Construct, lay out and return the type of offsets to a value
3920    of type TYPE, within an object of type BASETYPE.
3921    If a suitable offset type exists already, reuse it.  */
3922
3923 tree
3924 build_offset_type (tree basetype, tree type)
3925 {
3926   tree t;
3927   unsigned int hashcode;
3928
3929   /* Make a node of the sort we want.  */
3930   t = make_node (OFFSET_TYPE);
3931
3932   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3933   TREE_TYPE (t) = type;
3934
3935   /* If we already have such a type, use the old one and free this one.  */
3936   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
3937   t = type_hash_canon (hashcode, t);
3938
3939   if (!COMPLETE_TYPE_P (t))
3940     layout_type (t);
3941
3942   return t;
3943 }
3944
3945 /* Create a complex type whose components are COMPONENT_TYPE.  */
3946
3947 tree
3948 build_complex_type (tree component_type)
3949 {
3950   tree t;
3951   unsigned int hashcode;
3952
3953   /* Make a node of the sort we want.  */
3954   t = make_node (COMPLEX_TYPE);
3955
3956   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
3957   set_type_quals (t, TYPE_QUALS (component_type));
3958
3959   /* If we already have such a type, use the old one and free this one.  */
3960   hashcode = TYPE_HASH (component_type);
3961   t = type_hash_canon (hashcode, t);
3962
3963   if (!COMPLETE_TYPE_P (t))
3964     layout_type (t);
3965
3966   /* If we are writing Dwarf2 output we need to create a name,
3967      since complex is a fundamental type.  */
3968   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
3969       && ! TYPE_NAME (t))
3970     {
3971       const char *name;
3972       if (component_type == char_type_node)
3973         name = "complex char";
3974       else if (component_type == signed_char_type_node)
3975         name = "complex signed char";
3976       else if (component_type == unsigned_char_type_node)
3977         name = "complex unsigned char";
3978       else if (component_type == short_integer_type_node)
3979         name = "complex short int";
3980       else if (component_type == short_unsigned_type_node)
3981         name = "complex short unsigned int";
3982       else if (component_type == integer_type_node)
3983         name = "complex int";
3984       else if (component_type == unsigned_type_node)
3985         name = "complex unsigned int";
3986       else if (component_type == long_integer_type_node)
3987         name = "complex long int";
3988       else if (component_type == long_unsigned_type_node)
3989         name = "complex long unsigned int";
3990       else if (component_type == long_long_integer_type_node)
3991         name = "complex long long int";
3992       else if (component_type == long_long_unsigned_type_node)
3993         name = "complex long long unsigned int";
3994       else
3995         name = 0;
3996
3997       if (name != 0)
3998         TYPE_NAME (t) = get_identifier (name);
3999     }
4000
4001   return t;
4002 }
4003 \f
4004 /* Return OP, stripped of any conversions to wider types as much as is safe.
4005    Converting the value back to OP's type makes a value equivalent to OP.
4006
4007    If FOR_TYPE is nonzero, we return a value which, if converted to
4008    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4009
4010    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4011    narrowest type that can hold the value, even if they don't exactly fit.
4012    Otherwise, bit-field references are changed to a narrower type
4013    only if they can be fetched directly from memory in that type.
4014
4015    OP must have integer, real or enumeral type.  Pointers are not allowed!
4016
4017    There are some cases where the obvious value we could return
4018    would regenerate to OP if converted to OP's type,
4019    but would not extend like OP to wider types.
4020    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4021    For example, if OP is (unsigned short)(signed char)-1,
4022    we avoid returning (signed char)-1 if FOR_TYPE is int,
4023    even though extending that to an unsigned short would regenerate OP,
4024    since the result of extending (signed char)-1 to (int)
4025    is different from (int) OP.  */
4026
4027 tree
4028 get_unwidened (tree op, tree for_type)
4029 {
4030   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4031   tree type = TREE_TYPE (op);
4032   unsigned final_prec
4033     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4034   int uns
4035     = (for_type != 0 && for_type != type
4036        && final_prec > TYPE_PRECISION (type)
4037        && TREE_UNSIGNED (type));
4038   tree win = op;
4039
4040   while (TREE_CODE (op) == NOP_EXPR)
4041     {
4042       int bitschange
4043         = TYPE_PRECISION (TREE_TYPE (op))
4044           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4045
4046       /* Truncations are many-one so cannot be removed.
4047          Unless we are later going to truncate down even farther.  */
4048       if (bitschange < 0
4049           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4050         break;
4051
4052       /* See what's inside this conversion.  If we decide to strip it,
4053          we will set WIN.  */
4054       op = TREE_OPERAND (op, 0);
4055
4056       /* If we have not stripped any zero-extensions (uns is 0),
4057          we can strip any kind of extension.
4058          If we have previously stripped a zero-extension,
4059          only zero-extensions can safely be stripped.
4060          Any extension can be stripped if the bits it would produce
4061          are all going to be discarded later by truncating to FOR_TYPE.  */
4062
4063       if (bitschange > 0)
4064         {
4065           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4066             win = op;
4067           /* TREE_UNSIGNED says whether this is a zero-extension.
4068              Let's avoid computing it if it does not affect WIN
4069              and if UNS will not be needed again.  */
4070           if ((uns || TREE_CODE (op) == NOP_EXPR)
4071               && TREE_UNSIGNED (TREE_TYPE (op)))
4072             {
4073               uns = 1;
4074               win = op;
4075             }
4076         }
4077     }
4078
4079   if (TREE_CODE (op) == COMPONENT_REF
4080       /* Since type_for_size always gives an integer type.  */
4081       && TREE_CODE (type) != REAL_TYPE
4082       /* Don't crash if field not laid out yet.  */
4083       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4084       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4085     {
4086       unsigned int innerprec
4087         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4088       int unsignedp = TREE_UNSIGNED (TREE_OPERAND (op, 1));
4089       type = (*lang_hooks.types.type_for_size) (innerprec, unsignedp);
4090
4091       /* We can get this structure field in the narrowest type it fits in.
4092          If FOR_TYPE is 0, do this only for a field that matches the
4093          narrower type exactly and is aligned for it
4094          The resulting extension to its nominal type (a fullword type)
4095          must fit the same conditions as for other extensions.  */
4096
4097       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4098           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4099           && (! uns || final_prec <= innerprec || unsignedp)
4100           && type != 0)
4101         {
4102           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4103                        TREE_OPERAND (op, 1));
4104           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4105           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4106         }
4107     }
4108
4109   return win;
4110 }
4111 \f
4112 /* Return OP or a simpler expression for a narrower value
4113    which can be sign-extended or zero-extended to give back OP.
4114    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4115    or 0 if the value should be sign-extended.  */
4116
4117 tree
4118 get_narrower (tree op, int *unsignedp_ptr)
4119 {
4120   int uns = 0;
4121   int first = 1;
4122   tree win = op;
4123
4124   while (TREE_CODE (op) == NOP_EXPR)
4125     {
4126       int bitschange
4127         = (TYPE_PRECISION (TREE_TYPE (op))
4128            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4129
4130       /* Truncations are many-one so cannot be removed.  */
4131       if (bitschange < 0)
4132         break;
4133
4134       /* See what's inside this conversion.  If we decide to strip it,
4135          we will set WIN.  */
4136
4137       if (bitschange > 0)
4138         {
4139           op = TREE_OPERAND (op, 0);
4140           /* An extension: the outermost one can be stripped,
4141              but remember whether it is zero or sign extension.  */
4142           if (first)
4143             uns = TREE_UNSIGNED (TREE_TYPE (op));
4144           /* Otherwise, if a sign extension has been stripped,
4145              only sign extensions can now be stripped;
4146              if a zero extension has been stripped, only zero-extensions.  */
4147           else if (uns != TREE_UNSIGNED (TREE_TYPE (op)))
4148             break;
4149           first = 0;
4150         }
4151       else /* bitschange == 0 */
4152         {
4153           /* A change in nominal type can always be stripped, but we must
4154              preserve the unsignedness.  */
4155           if (first)
4156             uns = TREE_UNSIGNED (TREE_TYPE (op));
4157           first = 0;
4158           op = TREE_OPERAND (op, 0);
4159         }
4160
4161       win = op;
4162     }
4163
4164   if (TREE_CODE (op) == COMPONENT_REF
4165       /* Since type_for_size always gives an integer type.  */
4166       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4167       /* Ensure field is laid out already.  */
4168       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0)
4169     {
4170       unsigned HOST_WIDE_INT innerprec
4171         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4172       tree type = (*lang_hooks.types.type_for_size) (innerprec,
4173                                                      TREE_UNSIGNED (op));
4174
4175       /* We can get this structure field in a narrower type that fits it,
4176          but the resulting extension to its nominal type (a fullword type)
4177          must satisfy the same conditions as for other extensions.
4178
4179          Do this only for fields that are aligned (not bit-fields),
4180          because when bit-field insns will be used there is no
4181          advantage in doing this.  */
4182
4183       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4184           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4185           && (first || uns == TREE_UNSIGNED (TREE_OPERAND (op, 1)))
4186           && type != 0)
4187         {
4188           if (first)
4189             uns = TREE_UNSIGNED (TREE_OPERAND (op, 1));
4190           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4191                        TREE_OPERAND (op, 1));
4192           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4193           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4194         }
4195     }
4196   *unsignedp_ptr = uns;
4197   return win;
4198 }
4199 \f
4200 /* Nonzero if integer constant C has a value that is permissible
4201    for type TYPE (an INTEGER_TYPE).  */
4202
4203 int
4204 int_fits_type_p (tree c, tree type)
4205 {
4206   tree type_low_bound = TYPE_MIN_VALUE (type);
4207   tree type_high_bound = TYPE_MAX_VALUE (type);
4208   int ok_for_low_bound, ok_for_high_bound;
4209
4210   /* Perform some generic filtering first, which may allow making a decision
4211      even if the bounds are not constant.  First, negative integers never fit
4212      in unsigned types, */
4213   if ((TREE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4214       /* Also, unsigned integers with top bit set never fit signed types.  */
4215       || (! TREE_UNSIGNED (type)
4216           && TREE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4217     return 0;
4218
4219   /* If at least one bound of the type is a constant integer, we can check
4220      ourselves and maybe make a decision. If no such decision is possible, but
4221      this type is a subtype, try checking against that.  Otherwise, use
4222      force_fit_type, which checks against the precision.
4223
4224      Compute the status for each possibly constant bound, and return if we see
4225      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4226      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4227      for "constant known to fit".  */
4228
4229   ok_for_low_bound = -1;
4230   ok_for_high_bound = -1;
4231
4232   /* Check if C >= type_low_bound.  */
4233   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4234     {
4235       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4236       if (! ok_for_low_bound)
4237         return 0;
4238     }
4239
4240   /* Check if c <= type_high_bound.  */
4241   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4242     {
4243       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4244       if (! ok_for_high_bound)
4245         return 0;
4246     }
4247
4248   /* If the constant fits both bounds, the result is known.  */
4249   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4250     return 1;
4251
4252   /* If we haven't been able to decide at this point, there nothing more we
4253      can check ourselves here. Look at the base type if we have one.  */
4254   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4255     return int_fits_type_p (c, TREE_TYPE (type));
4256
4257   /* Or to force_fit_type, if nothing else.  */
4258   else
4259     {
4260       c = copy_node (c);
4261       TREE_TYPE (c) = type;
4262       return !force_fit_type (c, 0);
4263     }
4264 }
4265
4266 /* Returns true if T is, contains, or refers to a type with variable
4267    size.  This concept is more general than that of C99 'variably
4268    modified types': in C99, a struct type is never variably modified
4269    because a VLA may not appear as a structure member.  However, in
4270    GNU C code like:
4271
4272      struct S { int i[f()]; };
4273
4274    is valid, and other languages may define similar constructs.  */
4275
4276 bool
4277 variably_modified_type_p (tree type)
4278 {
4279   if (type == error_mark_node)
4280     return false;
4281
4282   /* If TYPE itself has variable size, it is variably modified.
4283
4284      We do not yet have a representation of the C99 '[*]' syntax.
4285      When a representation is chosen, this function should be modified
4286      to test for that case as well.  */
4287   if (TYPE_SIZE (type)
4288       && TYPE_SIZE (type) != error_mark_node
4289       && TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST)
4290     return true;
4291
4292   /* If TYPE is a pointer or reference, it is variably modified if
4293      the type pointed to is variably modified.  */
4294   if ((TREE_CODE (type) == POINTER_TYPE
4295        || TREE_CODE (type) == REFERENCE_TYPE)
4296       && variably_modified_type_p (TREE_TYPE (type)))
4297     return true;
4298
4299   /* If TYPE is an array, it is variably modified if the array
4300      elements are.  (Note that the VLA case has already been checked
4301      above.)  */
4302   if (TREE_CODE (type) == ARRAY_TYPE
4303       && variably_modified_type_p (TREE_TYPE (type)))
4304     return true;
4305
4306   /* If TYPE is a function type, it is variably modified if any of the
4307      parameters or the return type are variably modified.  */
4308   if (TREE_CODE (type) == FUNCTION_TYPE
4309       || TREE_CODE (type) == METHOD_TYPE)
4310     {
4311       tree parm;
4312
4313       if (variably_modified_type_p (TREE_TYPE (type)))
4314         return true;
4315       for (parm = TYPE_ARG_TYPES (type);
4316            parm && parm != void_list_node;
4317            parm = TREE_CHAIN (parm))
4318         if (variably_modified_type_p (TREE_VALUE (parm)))
4319           return true;
4320     }
4321
4322   /* The current language may have other cases to check, but in general,
4323      all other types are not variably modified.  */
4324   return (*lang_hooks.tree_inlining.var_mod_type_p) (type);
4325 }
4326
4327 /* Given a DECL or TYPE, return the scope in which it was declared, or
4328    NULL_TREE if there is no containing scope.  */
4329
4330 tree
4331 get_containing_scope (tree t)
4332 {
4333   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4334 }
4335
4336 /* Return the innermost context enclosing DECL that is
4337    a FUNCTION_DECL, or zero if none.  */
4338
4339 tree
4340 decl_function_context (tree decl)
4341 {
4342   tree context;
4343
4344   if (TREE_CODE (decl) == ERROR_MARK)
4345     return 0;
4346
4347   if (TREE_CODE (decl) == SAVE_EXPR)
4348     context = SAVE_EXPR_CONTEXT (decl);
4349
4350   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4351      where we look up the function at runtime.  Such functions always take
4352      a first argument of type 'pointer to real context'.
4353
4354      C++ should really be fixed to use DECL_CONTEXT for the real context,
4355      and use something else for the "virtual context".  */
4356   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4357     context
4358       = TYPE_MAIN_VARIANT
4359         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4360   else
4361     context = DECL_CONTEXT (decl);
4362
4363   while (context && TREE_CODE (context) != FUNCTION_DECL)
4364     {
4365       if (TREE_CODE (context) == BLOCK)
4366         context = BLOCK_SUPERCONTEXT (context);
4367       else
4368         context = get_containing_scope (context);
4369     }
4370
4371   return context;
4372 }
4373
4374 /* Return the innermost context enclosing DECL that is
4375    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4376    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4377
4378 tree
4379 decl_type_context (tree decl)
4380 {
4381   tree context = DECL_CONTEXT (decl);
4382
4383   while (context)
4384     switch (TREE_CODE (context))
4385       {
4386       case NAMESPACE_DECL:
4387       case TRANSLATION_UNIT_DECL:
4388         return NULL_TREE;
4389
4390       case RECORD_TYPE:
4391       case UNION_TYPE:
4392       case QUAL_UNION_TYPE:
4393         return context;
4394
4395       case TYPE_DECL:
4396       case FUNCTION_DECL:
4397         context = DECL_CONTEXT (context);
4398         break;
4399
4400       case BLOCK:
4401         context = BLOCK_SUPERCONTEXT (context);
4402         break;
4403
4404       default:
4405         abort ();
4406       }
4407
4408   return NULL_TREE;
4409 }
4410
4411 /* CALL is a CALL_EXPR.  Return the declaration for the function
4412    called, or NULL_TREE if the called function cannot be
4413    determined.  */
4414
4415 tree
4416 get_callee_fndecl (tree call)
4417 {
4418   tree addr;
4419
4420   /* It's invalid to call this function with anything but a
4421      CALL_EXPR.  */
4422   if (TREE_CODE (call) != CALL_EXPR)
4423     abort ();
4424
4425   /* The first operand to the CALL is the address of the function
4426      called.  */
4427   addr = TREE_OPERAND (call, 0);
4428
4429   STRIP_NOPS (addr);
4430
4431   /* If this is a readonly function pointer, extract its initial value.  */
4432   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4433       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4434       && DECL_INITIAL (addr))
4435     addr = DECL_INITIAL (addr);
4436
4437   /* If the address is just `&f' for some function `f', then we know
4438      that `f' is being called.  */
4439   if (TREE_CODE (addr) == ADDR_EXPR
4440       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4441     return TREE_OPERAND (addr, 0);
4442
4443   /* We couldn't figure out what was being called.  */
4444   return NULL_TREE;
4445 }
4446
4447 /* Print debugging information about tree nodes generated during the compile,
4448    and any language-specific information.  */
4449
4450 void
4451 dump_tree_statistics (void)
4452 {
4453 #ifdef GATHER_STATISTICS
4454   int i;
4455   int total_nodes, total_bytes;
4456 #endif
4457
4458   fprintf (stderr, "\n??? tree nodes created\n\n");
4459 #ifdef GATHER_STATISTICS
4460   fprintf (stderr, "Kind                   Nodes      Bytes\n");
4461   fprintf (stderr, "---------------------------------------\n");
4462   total_nodes = total_bytes = 0;
4463   for (i = 0; i < (int) all_kinds; i++)
4464     {
4465       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
4466                tree_node_counts[i], tree_node_sizes[i]);
4467       total_nodes += tree_node_counts[i];
4468       total_bytes += tree_node_sizes[i];
4469     }
4470   fprintf (stderr, "---------------------------------------\n");
4471   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
4472   fprintf (stderr, "---------------------------------------\n");
4473 #else
4474   fprintf (stderr, "(No per-node statistics)\n");
4475 #endif
4476   print_type_hash_statistics ();
4477   (*lang_hooks.print_statistics) ();
4478 }
4479 \f
4480 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4481
4482 /* Generate a crc32 of a string.  */
4483
4484 unsigned
4485 crc32_string (unsigned chksum, const char *string)
4486 {
4487   do
4488     {
4489       unsigned value = *string << 24;
4490       unsigned ix;
4491
4492       for (ix = 8; ix--; value <<= 1)
4493         {
4494           unsigned feedback;
4495
4496           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
4497           chksum <<= 1;
4498           chksum ^= feedback;
4499         }
4500     }
4501   while (*string++);
4502   return chksum;
4503 }
4504
4505 /* P is a string that will be used in a symbol.  Mask out any characters
4506    that are not valid in that context.  */
4507
4508 void
4509 clean_symbol_name (char *p)
4510 {
4511   for (; *p; p++)
4512     if (! (ISALNUM (*p)
4513 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4514             || *p == '$'
4515 #endif
4516 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4517             || *p == '.'
4518 #endif
4519            ))
4520       *p = '_';
4521 }
4522
4523 /* Generate a name for a function unique to this translation unit.
4524    TYPE is some string to identify the purpose of this function to the
4525    linker or collect2.  */
4526
4527 tree
4528 get_file_function_name_long (const char *type)
4529 {
4530   char *buf;
4531   const char *p;
4532   char *q;
4533
4534   if (first_global_object_name)
4535     p = first_global_object_name;
4536   else
4537     {
4538       /* We don't have anything that we know to be unique to this translation
4539          unit, so use what we do have and throw in some randomness.  */
4540       unsigned len;
4541       const char *name = weak_global_object_name;
4542       const char *file = main_input_filename;
4543
4544       if (! name)
4545         name = "";
4546       if (! file)
4547         file = input_filename;
4548
4549       len = strlen (file);
4550       q = alloca (9 * 2 + len + 1);
4551       memcpy (q, file, len + 1);
4552       clean_symbol_name (q);
4553
4554       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
4555                crc32_string (0, flag_random_seed));
4556
4557       p = q;
4558     }
4559
4560   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
4561
4562   /* Set up the name of the file-level functions we may need.
4563      Use a global object (which is already required to be unique over
4564      the program) rather than the file name (which imposes extra
4565      constraints).  */
4566   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
4567
4568   return get_identifier (buf);
4569 }
4570
4571 /* If KIND=='I', return a suitable global initializer (constructor) name.
4572    If KIND=='D', return a suitable global clean-up (destructor) name.  */
4573
4574 tree
4575 get_file_function_name (int kind)
4576 {
4577   char p[2];
4578
4579   p[0] = kind;
4580   p[1] = 0;
4581
4582   return get_file_function_name_long (p);
4583 }
4584 \f
4585 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4586    The result is placed in BUFFER (which has length BIT_SIZE),
4587    with one bit in each char ('\000' or '\001').
4588
4589    If the constructor is constant, NULL_TREE is returned.
4590    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4591
4592 tree
4593 get_set_constructor_bits (tree init, char *buffer, int bit_size)
4594 {
4595   int i;
4596   tree vals;
4597   HOST_WIDE_INT domain_min
4598     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
4599   tree non_const_bits = NULL_TREE;
4600
4601   for (i = 0; i < bit_size; i++)
4602     buffer[i] = 0;
4603
4604   for (vals = TREE_OPERAND (init, 1);
4605        vals != NULL_TREE; vals = TREE_CHAIN (vals))
4606     {
4607       if (!host_integerp (TREE_VALUE (vals), 0)
4608           || (TREE_PURPOSE (vals) != NULL_TREE
4609               && !host_integerp (TREE_PURPOSE (vals), 0)))
4610         non_const_bits
4611           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
4612       else if (TREE_PURPOSE (vals) != NULL_TREE)
4613         {
4614           /* Set a range of bits to ones.  */
4615           HOST_WIDE_INT lo_index
4616             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
4617           HOST_WIDE_INT hi_index
4618             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4619
4620           if (lo_index < 0 || lo_index >= bit_size
4621               || hi_index < 0 || hi_index >= bit_size)
4622             abort ();
4623           for (; lo_index <= hi_index; lo_index++)
4624             buffer[lo_index] = 1;
4625         }
4626       else
4627         {
4628           /* Set a single bit to one.  */
4629           HOST_WIDE_INT index
4630             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4631           if (index < 0 || index >= bit_size)
4632             {
4633               error ("invalid initializer for bit string");
4634               return NULL_TREE;
4635             }
4636           buffer[index] = 1;
4637         }
4638     }
4639   return non_const_bits;
4640 }
4641
4642 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4643    The result is placed in BUFFER (which is an array of bytes).
4644    If the constructor is constant, NULL_TREE is returned.
4645    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4646
4647 tree
4648 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
4649 {
4650   int i;
4651   int set_word_size = BITS_PER_UNIT;
4652   int bit_size = wd_size * set_word_size;
4653   int bit_pos = 0;
4654   unsigned char *bytep = buffer;
4655   char *bit_buffer = alloca (bit_size);
4656   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
4657
4658   for (i = 0; i < wd_size; i++)
4659     buffer[i] = 0;
4660
4661   for (i = 0; i < bit_size; i++)
4662     {
4663       if (bit_buffer[i])
4664         {
4665           if (BYTES_BIG_ENDIAN)
4666             *bytep |= (1 << (set_word_size - 1 - bit_pos));
4667           else
4668             *bytep |= 1 << bit_pos;
4669         }
4670       bit_pos++;
4671       if (bit_pos >= set_word_size)
4672         bit_pos = 0, bytep++;
4673     }
4674   return non_const_bits;
4675 }
4676 \f
4677 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4678 /* Complain that the tree code of NODE does not match the expected CODE.
4679    FILE, LINE, and FUNCTION are of the caller.  */
4680
4681 void
4682 tree_check_failed (const tree node, enum tree_code code, const char *file,
4683                    int line, const char *function)
4684 {
4685   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
4686                   tree_code_name[code], tree_code_name[TREE_CODE (node)],
4687                   function, trim_filename (file), line);
4688 }
4689
4690 /* Similar to above, except that we check for a class of tree
4691    code, given in CL.  */
4692
4693 void
4694 tree_class_check_failed (const tree node, int cl, const char *file,
4695                          int line, const char *function)
4696 {
4697   internal_error
4698     ("tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
4699      cl, TREE_CODE_CLASS (TREE_CODE (node)),
4700      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
4701 }
4702
4703 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
4704    (dynamically sized) vector.  */
4705
4706 void
4707 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
4708                            const char *function)
4709 {
4710   internal_error
4711     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
4712      idx + 1, len, function, trim_filename (file), line);
4713 }
4714
4715 /* Similar to above, except that the check is for the bounds of the operand
4716    vector of an expression node.  */
4717
4718 void
4719 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
4720                            int line, const char *function)
4721 {
4722   internal_error
4723     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
4724      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
4725      function, trim_filename (file), line);
4726 }
4727 #endif /* ENABLE_TREE_CHECKING */
4728 \f
4729 /* For a new vector type node T, build the information necessary for
4730    debugging output.  */
4731
4732 static void
4733 finish_vector_type (tree t)
4734 {
4735   layout_type (t);
4736
4737   {
4738     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
4739     tree array = build_array_type (TREE_TYPE (t),
4740                                    build_index_type (index));
4741     tree rt = make_node (RECORD_TYPE);
4742
4743     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
4744     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
4745     layout_type (rt);
4746     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
4747     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
4748        the representation type, and we want to find that die when looking up
4749        the vector type.  This is most easily achieved by making the TYPE_UID
4750        numbers equal.  */
4751     TYPE_UID (rt) = TYPE_UID (t);
4752   }
4753 }
4754
4755 /* Create nodes for all integer types (and error_mark_node) using the sizes
4756    of C datatypes.  The caller should call set_sizetype soon after calling
4757    this function to select one of the types as sizetype.  */
4758
4759 void
4760 build_common_tree_nodes (int signed_char)
4761 {
4762   error_mark_node = make_node (ERROR_MARK);
4763   TREE_TYPE (error_mark_node) = error_mark_node;
4764
4765   initialize_sizetypes ();
4766
4767   /* Define both `signed char' and `unsigned char'.  */
4768   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
4769   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
4770
4771   /* Define `char', which is like either `signed char' or `unsigned char'
4772      but not the same as either.  */
4773   char_type_node
4774     = (signed_char
4775        ? make_signed_type (CHAR_TYPE_SIZE)
4776        : make_unsigned_type (CHAR_TYPE_SIZE));
4777
4778   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
4779   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
4780   integer_type_node = make_signed_type (INT_TYPE_SIZE);
4781   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
4782   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
4783   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
4784   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
4785   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
4786
4787   /* Define a boolean type.  This type only represents boolean values but
4788      may be larger than char depending on the value of BOOL_TYPE_SIZE.
4789      Front ends which want to override this size (i.e. Java) can redefine
4790      boolean_type_node before calling build_common_tree_nodes_2.  */
4791   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
4792   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
4793   TYPE_MAX_VALUE (boolean_type_node) = build_int_2 (1, 0);
4794   TREE_TYPE (TYPE_MAX_VALUE (boolean_type_node)) = boolean_type_node;
4795   TYPE_PRECISION (boolean_type_node) = 1;
4796
4797   intQI_type_node = make_signed_type (GET_MODE_BITSIZE (QImode));
4798   intHI_type_node = make_signed_type (GET_MODE_BITSIZE (HImode));
4799   intSI_type_node = make_signed_type (GET_MODE_BITSIZE (SImode));
4800   intDI_type_node = make_signed_type (GET_MODE_BITSIZE (DImode));
4801   intTI_type_node = make_signed_type (GET_MODE_BITSIZE (TImode));
4802
4803   unsigned_intQI_type_node = make_unsigned_type (GET_MODE_BITSIZE (QImode));
4804   unsigned_intHI_type_node = make_unsigned_type (GET_MODE_BITSIZE (HImode));
4805   unsigned_intSI_type_node = make_unsigned_type (GET_MODE_BITSIZE (SImode));
4806   unsigned_intDI_type_node = make_unsigned_type (GET_MODE_BITSIZE (DImode));
4807   unsigned_intTI_type_node = make_unsigned_type (GET_MODE_BITSIZE (TImode));
4808 }
4809
4810 /* Call this function after calling build_common_tree_nodes and set_sizetype.
4811    It will create several other common tree nodes.  */
4812
4813 void
4814 build_common_tree_nodes_2 (int short_double)
4815 {
4816   /* Define these next since types below may used them.  */
4817   integer_zero_node = build_int_2 (0, 0);
4818   integer_one_node = build_int_2 (1, 0);
4819   integer_minus_one_node = build_int_2 (-1, -1);
4820
4821   size_zero_node = size_int (0);
4822   size_one_node = size_int (1);
4823   bitsize_zero_node = bitsize_int (0);
4824   bitsize_one_node = bitsize_int (1);
4825   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
4826
4827   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
4828   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
4829
4830   void_type_node = make_node (VOID_TYPE);
4831   layout_type (void_type_node);
4832
4833   /* We are not going to have real types in C with less than byte alignment,
4834      so we might as well not have any types that claim to have it.  */
4835   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
4836   TYPE_USER_ALIGN (void_type_node) = 0;
4837
4838   null_pointer_node = build_int_2 (0, 0);
4839   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
4840   layout_type (TREE_TYPE (null_pointer_node));
4841
4842   ptr_type_node = build_pointer_type (void_type_node);
4843   const_ptr_type_node
4844     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
4845
4846   float_type_node = make_node (REAL_TYPE);
4847   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
4848   layout_type (float_type_node);
4849
4850   double_type_node = make_node (REAL_TYPE);
4851   if (short_double)
4852     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
4853   else
4854     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
4855   layout_type (double_type_node);
4856
4857   long_double_type_node = make_node (REAL_TYPE);
4858   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
4859   layout_type (long_double_type_node);
4860
4861   float_ptr_type_node = build_pointer_type (float_type_node);
4862   double_ptr_type_node = build_pointer_type (double_type_node);
4863   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
4864   integer_ptr_type_node = build_pointer_type (integer_type_node);
4865
4866   complex_integer_type_node = make_node (COMPLEX_TYPE);
4867   TREE_TYPE (complex_integer_type_node) = integer_type_node;
4868   layout_type (complex_integer_type_node);
4869
4870   complex_float_type_node = make_node (COMPLEX_TYPE);
4871   TREE_TYPE (complex_float_type_node) = float_type_node;
4872   layout_type (complex_float_type_node);
4873
4874   complex_double_type_node = make_node (COMPLEX_TYPE);
4875   TREE_TYPE (complex_double_type_node) = double_type_node;
4876   layout_type (complex_double_type_node);
4877
4878   complex_long_double_type_node = make_node (COMPLEX_TYPE);
4879   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
4880   layout_type (complex_long_double_type_node);
4881
4882   {
4883     tree t;
4884     BUILD_VA_LIST_TYPE (t);
4885
4886     /* Many back-ends define record types without setting TYPE_NAME.
4887        If we copied the record type here, we'd keep the original
4888        record type without a name.  This breaks name mangling.  So,
4889        don't copy record types and let c_common_nodes_and_builtins()
4890        declare the type to be __builtin_va_list.  */
4891     if (TREE_CODE (t) != RECORD_TYPE)
4892       t = build_type_copy (t);
4893
4894     va_list_type_node = t;
4895   }
4896
4897   unsigned_V4SI_type_node
4898     = make_vector (V4SImode, unsigned_intSI_type_node, 1);
4899   unsigned_V2HI_type_node
4900     = make_vector (V2HImode, unsigned_intHI_type_node, 1);
4901   unsigned_V2SI_type_node
4902     = make_vector (V2SImode, unsigned_intSI_type_node, 1);
4903   unsigned_V2DI_type_node
4904     = make_vector (V2DImode, unsigned_intDI_type_node, 1);
4905   unsigned_V4HI_type_node
4906     = make_vector (V4HImode, unsigned_intHI_type_node, 1);
4907   unsigned_V8QI_type_node
4908     = make_vector (V8QImode, unsigned_intQI_type_node, 1);
4909   unsigned_V8HI_type_node
4910     = make_vector (V8HImode, unsigned_intHI_type_node, 1);
4911   unsigned_V16QI_type_node
4912     = make_vector (V16QImode, unsigned_intQI_type_node, 1);
4913   unsigned_V1DI_type_node
4914     = make_vector (V1DImode, unsigned_intDI_type_node, 1);
4915
4916   V16SF_type_node = make_vector (V16SFmode, float_type_node, 0);
4917   V4SF_type_node = make_vector (V4SFmode, float_type_node, 0);
4918   V4SI_type_node = make_vector (V4SImode, intSI_type_node, 0);
4919   V2HI_type_node = make_vector (V2HImode, intHI_type_node, 0);
4920   V2SI_type_node = make_vector (V2SImode, intSI_type_node, 0);
4921   V2DI_type_node = make_vector (V2DImode, intDI_type_node, 0);
4922   V4HI_type_node = make_vector (V4HImode, intHI_type_node, 0);
4923   V8QI_type_node = make_vector (V8QImode, intQI_type_node, 0);
4924   V8HI_type_node = make_vector (V8HImode, intHI_type_node, 0);
4925   V2SF_type_node = make_vector (V2SFmode, float_type_node, 0);
4926   V2DF_type_node = make_vector (V2DFmode, double_type_node, 0);
4927   V16QI_type_node = make_vector (V16QImode, intQI_type_node, 0);
4928   V1DI_type_node = make_vector (V1DImode, intDI_type_node, 0);
4929   V4DF_type_node = make_vector (V4DFmode, double_type_node, 0);
4930 }
4931
4932 /* Returns a vector tree node given a vector mode, the inner type, and
4933    the signness.  */
4934
4935 static tree
4936 make_vector (enum machine_mode mode, tree innertype, int unsignedp)
4937 {
4938   tree t;
4939
4940   t = make_node (VECTOR_TYPE);
4941   TREE_TYPE (t) = innertype;
4942   TYPE_MODE (t) = mode;
4943   TREE_UNSIGNED (TREE_TYPE (t)) = unsignedp;
4944   finish_vector_type (t);
4945
4946   return t;
4947 }
4948
4949 /* Given an initializer INIT, return TRUE if INIT is zero or some
4950    aggregate of zeros.  Otherwise return FALSE.  */
4951
4952 bool
4953 initializer_zerop (tree init)
4954 {
4955   STRIP_NOPS (init);
4956
4957   switch (TREE_CODE (init))
4958     {
4959     case INTEGER_CST:
4960       return integer_zerop (init);
4961     case REAL_CST:
4962       return real_zerop (init)
4963         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
4964     case COMPLEX_CST:
4965       return integer_zerop (init)
4966         || (real_zerop (init)
4967             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
4968             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
4969     case CONSTRUCTOR:
4970       {
4971         if (AGGREGATE_TYPE_P (TREE_TYPE (init)))
4972           {
4973             tree aggr_init = CONSTRUCTOR_ELTS (init);
4974
4975             while (aggr_init)
4976               {
4977                 if (! initializer_zerop (TREE_VALUE (aggr_init)))
4978                   return false;
4979                 aggr_init = TREE_CHAIN (aggr_init);
4980               }
4981             return true;
4982           }
4983         return false;
4984       }
4985     default:
4986       return false;
4987     }
4988 }
4989
4990 #include "gt-tree.h"