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