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