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 && !TYPE_P (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 && !TYPE_P (node)
2460           && TREE_CONSTANT (node))
2461         TREE_CONSTANT (t) = 1;
2462       break;
2463     }
2464
2465   return t;
2466 }
2467
2468 #define PROCESS_ARG(N)                  \
2469   do {                                  \
2470     TREE_OPERAND (t, N) = arg##N;       \
2471     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2472       {                                 \
2473         if (TREE_SIDE_EFFECTS (arg##N)) \
2474           side_effects = 1;             \
2475         if (!TREE_READONLY (arg##N))    \
2476           read_only = 0;                \
2477         if (!TREE_CONSTANT (arg##N))    \
2478           constant = 0;                 \
2479       }                                 \
2480   } while (0)
2481
2482 tree
2483 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2484 {
2485   bool constant, read_only, side_effects;
2486   tree t;
2487   int fro;
2488
2489 #ifdef ENABLE_CHECKING
2490   if (TREE_CODE_LENGTH (code) != 2)
2491     abort ();
2492 #endif
2493
2494   t = make_node_stat (code PASS_MEM_STAT);
2495   TREE_TYPE (t) = tt;
2496
2497   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2498      result based on those same flags for the arguments.  But if the
2499      arguments aren't really even `tree' expressions, we shouldn't be trying
2500      to do this.  */
2501   fro = first_rtl_op (code);
2502
2503   /* Expressions without side effects may be constant if their
2504      arguments are as well.  */
2505   constant = (TREE_CODE_CLASS (code) == '<'
2506               || TREE_CODE_CLASS (code) == '2');
2507   read_only = 1;
2508   side_effects = TREE_SIDE_EFFECTS (t);
2509
2510   PROCESS_ARG(0);
2511   PROCESS_ARG(1);
2512
2513   if (code == CALL_EXPR && !side_effects)
2514     {
2515       tree node;
2516       int i;
2517
2518       /* Calls have side-effects, except those to const or
2519          pure functions.  */
2520       i = call_expr_flags (t);
2521       if (!(i & (ECF_CONST | ECF_PURE)))
2522         side_effects = 1;
2523
2524       /* And even those have side-effects if their arguments do.  */
2525       else for (node = TREE_OPERAND (t, 1); node; node = TREE_CHAIN (node))
2526         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2527           {
2528             side_effects = 1;
2529             break;
2530           }
2531     }
2532
2533   TREE_READONLY (t) = read_only;
2534   TREE_CONSTANT (t) = constant;
2535   TREE_SIDE_EFFECTS (t) = side_effects;
2536
2537   return t;
2538 }
2539
2540 tree
2541 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2542              tree arg2 MEM_STAT_DECL)
2543 {
2544   bool constant, read_only, side_effects;
2545   tree t;
2546   int fro;
2547
2548   /* ??? Quite a lot of existing code passes one too many arguments to
2549      CALL_EXPR.  Not going to fix them, because CALL_EXPR is about to
2550      grow a new argument, so it would just mean changing them back.  */
2551   if (code == CALL_EXPR)
2552     {
2553       if (arg2 != NULL_TREE)
2554         abort ();
2555       return build2 (code, tt, arg0, arg1);
2556     }
2557
2558 #ifdef ENABLE_CHECKING
2559   if (TREE_CODE_LENGTH (code) != 3)
2560     abort ();
2561 #endif
2562
2563   t = make_node_stat (code PASS_MEM_STAT);
2564   TREE_TYPE (t) = tt;
2565
2566   fro = first_rtl_op (code);
2567
2568   side_effects = TREE_SIDE_EFFECTS (t);
2569
2570   PROCESS_ARG(0);
2571   PROCESS_ARG(1);
2572   PROCESS_ARG(2);
2573
2574   TREE_SIDE_EFFECTS (t) = side_effects;
2575
2576   return t;
2577 }
2578
2579 tree
2580 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2581              tree arg2, tree arg3 MEM_STAT_DECL)
2582 {
2583   bool constant, read_only, side_effects;
2584   tree t;
2585   int fro;
2586
2587 #ifdef ENABLE_CHECKING
2588   if (TREE_CODE_LENGTH (code) != 4)
2589     abort ();
2590 #endif
2591
2592   t = make_node_stat (code PASS_MEM_STAT);
2593   TREE_TYPE (t) = tt;
2594
2595   fro = first_rtl_op (code);
2596
2597   side_effects = TREE_SIDE_EFFECTS (t);
2598
2599   PROCESS_ARG(0);
2600   PROCESS_ARG(1);
2601   PROCESS_ARG(2);
2602   PROCESS_ARG(3);
2603
2604   TREE_SIDE_EFFECTS (t) = side_effects;
2605
2606   return t;
2607 }
2608
2609 /* Backup definition for non-gcc build compilers.  */
2610
2611 tree
2612 (build) (enum tree_code code, tree tt, ...)
2613 {
2614   tree t, arg0, arg1, arg2, arg3;
2615   int length = TREE_CODE_LENGTH (code);
2616   va_list p;
2617
2618   va_start (p, tt);
2619   switch (length)
2620     {
2621     case 0:
2622       t = build0 (code, tt);
2623       break;
2624     case 1:
2625       arg0 = va_arg (p, tree);
2626       t = build1 (code, tt, arg0);
2627       break;
2628     case 2:
2629       arg0 = va_arg (p, tree);
2630       arg1 = va_arg (p, tree);
2631       t = build2 (code, tt, arg0, arg1);
2632       break;
2633     case 3:
2634       arg0 = va_arg (p, tree);
2635       arg1 = va_arg (p, tree);
2636       arg2 = va_arg (p, tree);
2637       t = build3 (code, tt, arg0, arg1, arg2);
2638       break;
2639     case 4:
2640       arg0 = va_arg (p, tree);
2641       arg1 = va_arg (p, tree);
2642       arg2 = va_arg (p, tree);
2643       arg3 = va_arg (p, tree);
2644       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2645       break;
2646     default:
2647       abort ();
2648     }
2649   va_end (p);
2650
2651   return t;
2652 }
2653
2654 /* Similar except don't specify the TREE_TYPE
2655    and leave the TREE_SIDE_EFFECTS as 0.
2656    It is permissible for arguments to be null,
2657    or even garbage if their values do not matter.  */
2658
2659 tree
2660 build_nt (enum tree_code code, ...)
2661 {
2662   tree t;
2663   int length;
2664   int i;
2665   va_list p;
2666
2667   va_start (p, code);
2668
2669   t = make_node (code);
2670   length = TREE_CODE_LENGTH (code);
2671
2672   for (i = 0; i < length; i++)
2673     TREE_OPERAND (t, i) = va_arg (p, tree);
2674
2675   va_end (p);
2676   return t;
2677 }
2678 \f
2679 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2680    We do NOT enter this node in any sort of symbol table.
2681
2682    layout_decl is used to set up the decl's storage layout.
2683    Other slots are initialized to 0 or null pointers.  */
2684
2685 tree
2686 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2687 {
2688   tree t;
2689
2690   t = make_node_stat (code PASS_MEM_STAT);
2691
2692 /*  if (type == error_mark_node)
2693     type = integer_type_node; */
2694 /* That is not done, deliberately, so that having error_mark_node
2695    as the type can suppress useless errors in the use of this variable.  */
2696
2697   DECL_NAME (t) = name;
2698   TREE_TYPE (t) = type;
2699
2700   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2701     layout_decl (t, 0);
2702   else if (code == FUNCTION_DECL)
2703     DECL_MODE (t) = FUNCTION_MODE;
2704
2705   return t;
2706 }
2707 \f
2708 /* BLOCK nodes are used to represent the structure of binding contours
2709    and declarations, once those contours have been exited and their contents
2710    compiled.  This information is used for outputting debugging info.  */
2711
2712 tree
2713 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2714              tree supercontext, tree chain)
2715 {
2716   tree block = make_node (BLOCK);
2717
2718   BLOCK_VARS (block) = vars;
2719   BLOCK_SUBBLOCKS (block) = subblocks;
2720   BLOCK_SUPERCONTEXT (block) = supercontext;
2721   BLOCK_CHAIN (block) = chain;
2722   return block;
2723 }
2724
2725 /* EXPR_WITH_FILE_LOCATION are used to keep track of the exact
2726    location where an expression or an identifier were encountered. It
2727    is necessary for languages where the frontend parser will handle
2728    recursively more than one file (Java is one of them).  */
2729
2730 tree
2731 build_expr_wfl (tree node, const char *file, int line, int col)
2732 {
2733   static const char *last_file = 0;
2734   static tree last_filenode = NULL_TREE;
2735   tree wfl = make_node (EXPR_WITH_FILE_LOCATION);
2736
2737   EXPR_WFL_NODE (wfl) = node;
2738   EXPR_WFL_SET_LINECOL (wfl, line, col);
2739   if (file != last_file)
2740     {
2741       last_file = file;
2742       last_filenode = file ? get_identifier (file) : NULL_TREE;
2743     }
2744
2745   EXPR_WFL_FILENAME_NODE (wfl) = last_filenode;
2746
2747   if (node && !TYPE_P (node))
2748     {
2749       TREE_SIDE_EFFECTS (wfl) = TREE_SIDE_EFFECTS (node);
2750       TREE_TYPE (wfl) = TREE_TYPE (node);
2751     }
2752
2753   return wfl;
2754 }
2755 \f
2756 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2757    is ATTRIBUTE.  */
2758
2759 tree
2760 build_decl_attribute_variant (tree ddecl, tree attribute)
2761 {
2762   DECL_ATTRIBUTES (ddecl) = attribute;
2763   return ddecl;
2764 }
2765
2766 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2767    is ATTRIBUTE.
2768
2769    Record such modified types already made so we don't make duplicates.  */
2770
2771 tree
2772 build_type_attribute_variant (tree ttype, tree attribute)
2773 {
2774   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2775     {
2776       hashval_t hashcode = 0;
2777       tree ntype;
2778       enum tree_code code = TREE_CODE (ttype);
2779
2780       ntype = copy_node (ttype);
2781
2782       TYPE_POINTER_TO (ntype) = 0;
2783       TYPE_REFERENCE_TO (ntype) = 0;
2784       TYPE_ATTRIBUTES (ntype) = attribute;
2785
2786       /* Create a new main variant of TYPE.  */
2787       TYPE_MAIN_VARIANT (ntype) = ntype;
2788       TYPE_NEXT_VARIANT (ntype) = 0;
2789       set_type_quals (ntype, TYPE_UNQUALIFIED);
2790
2791       hashcode = iterative_hash_object (code, hashcode);
2792       if (TREE_TYPE (ntype))
2793         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2794                                           hashcode);
2795       hashcode = attribute_hash_list (attribute, hashcode);
2796
2797       switch (TREE_CODE (ntype))
2798         {
2799         case FUNCTION_TYPE:
2800           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2801           break;
2802         case ARRAY_TYPE:
2803           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2804                                             hashcode);
2805           break;
2806         case INTEGER_TYPE:
2807           hashcode = iterative_hash_object
2808             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2809           hashcode = iterative_hash_object
2810             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2811           break;
2812         case REAL_TYPE:
2813           {
2814             unsigned int precision = TYPE_PRECISION (ntype);
2815             hashcode = iterative_hash_object (precision, hashcode);
2816           }
2817           break;
2818         default:
2819           break;
2820         }
2821
2822       ntype = type_hash_canon (hashcode, ntype);
2823       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2824     }
2825
2826   return ttype;
2827 }
2828
2829 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2830    or zero if not.
2831
2832    We try both `text' and `__text__', ATTR may be either one.  */
2833 /* ??? It might be a reasonable simplification to require ATTR to be only
2834    `text'.  One might then also require attribute lists to be stored in
2835    their canonicalized form.  */
2836
2837 int
2838 is_attribute_p (const char *attr, tree ident)
2839 {
2840   int ident_len, attr_len;
2841   const char *p;
2842
2843   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2844     return 0;
2845
2846   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2847     return 1;
2848
2849   p = IDENTIFIER_POINTER (ident);
2850   ident_len = strlen (p);
2851   attr_len = strlen (attr);
2852
2853   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2854   if (attr[0] == '_')
2855     {
2856       if (attr[1] != '_'
2857           || attr[attr_len - 2] != '_'
2858           || attr[attr_len - 1] != '_')
2859         abort ();
2860       if (ident_len == attr_len - 4
2861           && strncmp (attr + 2, p, attr_len - 4) == 0)
2862         return 1;
2863     }
2864   else
2865     {
2866       if (ident_len == attr_len + 4
2867           && p[0] == '_' && p[1] == '_'
2868           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2869           && strncmp (attr, p + 2, attr_len) == 0)
2870         return 1;
2871     }
2872
2873   return 0;
2874 }
2875
2876 /* Given an attribute name and a list of attributes, return a pointer to the
2877    attribute's list element if the attribute is part of the list, or NULL_TREE
2878    if not found.  If the attribute appears more than once, this only
2879    returns the first occurrence; the TREE_CHAIN of the return value should
2880    be passed back in if further occurrences are wanted.  */
2881
2882 tree
2883 lookup_attribute (const char *attr_name, tree list)
2884 {
2885   tree l;
2886
2887   for (l = list; l; l = TREE_CHAIN (l))
2888     {
2889       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2890         abort ();
2891       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2892         return l;
2893     }
2894
2895   return NULL_TREE;
2896 }
2897
2898 /* Return an attribute list that is the union of a1 and a2.  */
2899
2900 tree
2901 merge_attributes (tree a1, tree a2)
2902 {
2903   tree attributes;
2904
2905   /* Either one unset?  Take the set one.  */
2906
2907   if ((attributes = a1) == 0)
2908     attributes = a2;
2909
2910   /* One that completely contains the other?  Take it.  */
2911
2912   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2913     {
2914       if (attribute_list_contained (a2, a1))
2915         attributes = a2;
2916       else
2917         {
2918           /* Pick the longest list, and hang on the other list.  */
2919
2920           if (list_length (a1) < list_length (a2))
2921             attributes = a2, a2 = a1;
2922
2923           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2924             {
2925               tree a;
2926               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2927                                          attributes);
2928                    a != NULL_TREE;
2929                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2930                                          TREE_CHAIN (a)))
2931                 {
2932                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2933                     break;
2934                 }
2935               if (a == NULL_TREE)
2936                 {
2937                   a1 = copy_node (a2);
2938                   TREE_CHAIN (a1) = attributes;
2939                   attributes = a1;
2940                 }
2941             }
2942         }
2943     }
2944   return attributes;
2945 }
2946
2947 /* Given types T1 and T2, merge their attributes and return
2948   the result.  */
2949
2950 tree
2951 merge_type_attributes (tree t1, tree t2)
2952 {
2953   return merge_attributes (TYPE_ATTRIBUTES (t1),
2954                            TYPE_ATTRIBUTES (t2));
2955 }
2956
2957 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
2958    the result.  */
2959
2960 tree
2961 merge_decl_attributes (tree olddecl, tree newdecl)
2962 {
2963   return merge_attributes (DECL_ATTRIBUTES (olddecl),
2964                            DECL_ATTRIBUTES (newdecl));
2965 }
2966
2967 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
2968
2969 /* Specialization of merge_decl_attributes for various Windows targets.
2970
2971    This handles the following situation:
2972
2973      __declspec (dllimport) int foo;
2974      int foo;
2975
2976    The second instance of `foo' nullifies the dllimport.  */
2977
2978 tree
2979 merge_dllimport_decl_attributes (tree old, tree new)
2980 {
2981   tree a;
2982   int delete_dllimport_p;
2983
2984   old = DECL_ATTRIBUTES (old);
2985   new = DECL_ATTRIBUTES (new);
2986
2987   /* What we need to do here is remove from `old' dllimport if it doesn't
2988      appear in `new'.  dllimport behaves like extern: if a declaration is
2989      marked dllimport and a definition appears later, then the object
2990      is not dllimport'd.  */
2991   if (lookup_attribute ("dllimport", old) != NULL_TREE
2992       && lookup_attribute ("dllimport", new) == NULL_TREE)
2993     delete_dllimport_p = 1;
2994   else
2995     delete_dllimport_p = 0;
2996
2997   a = merge_attributes (old, new);
2998
2999   if (delete_dllimport_p)
3000     {
3001       tree prev, t;
3002
3003       /* Scan the list for dllimport and delete it.  */
3004       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3005         {
3006           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3007             {
3008               if (prev == NULL_TREE)
3009                 a = TREE_CHAIN (a);
3010               else
3011                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3012               break;
3013             }
3014         }
3015     }
3016
3017   return a;
3018 }
3019
3020 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3021 \f
3022 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3023    of the various TYPE_QUAL values.  */
3024
3025 static void
3026 set_type_quals (tree type, int type_quals)
3027 {
3028   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3029   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3030   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3031 }
3032
3033 /* Returns true iff cand is equivalent to base with type_quals.  */
3034
3035 bool
3036 check_qualified_type (tree cand, tree base, int type_quals)
3037 {
3038   return (TYPE_QUALS (cand) == type_quals
3039           && TYPE_NAME (cand) == TYPE_NAME (base)
3040           /* Apparently this is needed for Objective-C.  */
3041           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3042           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3043                                    TYPE_ATTRIBUTES (base)));
3044 }
3045
3046 /* Return a version of the TYPE, qualified as indicated by the
3047    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3048    return NULL_TREE.  */
3049
3050 tree
3051 get_qualified_type (tree type, int type_quals)
3052 {
3053   tree t;
3054
3055   if (TYPE_QUALS (type) == type_quals)
3056     return type;
3057
3058   /* Search the chain of variants to see if there is already one there just
3059      like the one we need to have.  If so, use that existing one.  We must
3060      preserve the TYPE_NAME, since there is code that depends on this.  */
3061   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3062     if (check_qualified_type (t, type, type_quals))
3063       return t;
3064
3065   return NULL_TREE;
3066 }
3067
3068 /* Like get_qualified_type, but creates the type if it does not
3069    exist.  This function never returns NULL_TREE.  */
3070
3071 tree
3072 build_qualified_type (tree type, int type_quals)
3073 {
3074   tree t;
3075
3076   /* See if we already have the appropriate qualified variant.  */
3077   t = get_qualified_type (type, type_quals);
3078
3079   /* If not, build it.  */
3080   if (!t)
3081     {
3082       t = build_type_copy (type);
3083       set_type_quals (t, type_quals);
3084     }
3085
3086   return t;
3087 }
3088
3089 /* Create a new variant of TYPE, equivalent but distinct.
3090    This is so the caller can modify it.  */
3091
3092 tree
3093 build_type_copy (tree type)
3094 {
3095   tree t, m = TYPE_MAIN_VARIANT (type);
3096
3097   t = copy_node (type);
3098
3099   TYPE_POINTER_TO (t) = 0;
3100   TYPE_REFERENCE_TO (t) = 0;
3101
3102   /* Add this type to the chain of variants of TYPE.  */
3103   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3104   TYPE_NEXT_VARIANT (m) = t;
3105
3106   return t;
3107 }
3108 \f
3109 /* Hashing of types so that we don't make duplicates.
3110    The entry point is `type_hash_canon'.  */
3111
3112 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3113    with types in the TREE_VALUE slots), by adding the hash codes
3114    of the individual types.  */
3115
3116 unsigned int
3117 type_hash_list (tree list, hashval_t hashcode)
3118 {
3119   tree tail;
3120
3121   for (tail = list; tail; tail = TREE_CHAIN (tail))
3122     if (TREE_VALUE (tail) != error_mark_node)
3123       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3124                                         hashcode);
3125
3126   return hashcode;
3127 }
3128
3129 /* These are the Hashtable callback functions.  */
3130
3131 /* Returns true iff the types are equivalent.  */
3132
3133 static int
3134 type_hash_eq (const void *va, const void *vb)
3135 {
3136   const struct type_hash *a = va, *b = vb;
3137
3138   /* First test the things that are the same for all types.  */
3139   if (a->hash != b->hash
3140       || TREE_CODE (a->type) != TREE_CODE (b->type)
3141       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3142       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3143                                  TYPE_ATTRIBUTES (b->type))
3144       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3145       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3146     return 0;
3147
3148   switch (TREE_CODE (a->type))
3149     {
3150     case VOID_TYPE:
3151     case COMPLEX_TYPE:
3152     case VECTOR_TYPE:
3153     case POINTER_TYPE:
3154     case REFERENCE_TYPE:
3155       return 1;
3156
3157     case ENUMERAL_TYPE:
3158       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3159           && !(TYPE_VALUES (a->type)
3160                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3161                && TYPE_VALUES (b->type)
3162                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3163                && type_list_equal (TYPE_VALUES (a->type),
3164                                    TYPE_VALUES (b->type))))
3165         return 0;
3166
3167       /* ... fall through ... */
3168
3169     case INTEGER_TYPE:
3170     case REAL_TYPE:
3171     case BOOLEAN_TYPE:
3172     case CHAR_TYPE:
3173       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3174                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3175                                       TYPE_MAX_VALUE (b->type)))
3176               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3177                   && tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3178                                          TYPE_MIN_VALUE (b->type))));
3179
3180     case OFFSET_TYPE:
3181       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3182
3183     case METHOD_TYPE:
3184       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3185               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3186                   || (TYPE_ARG_TYPES (a->type)
3187                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3188                       && TYPE_ARG_TYPES (b->type)
3189                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3190                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3191                                           TYPE_ARG_TYPES (b->type)))));
3192
3193     case ARRAY_TYPE:
3194     case SET_TYPE:
3195       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3196
3197     case RECORD_TYPE:
3198     case UNION_TYPE:
3199     case QUAL_UNION_TYPE:
3200       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3201               || (TYPE_FIELDS (a->type)
3202                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3203                   && TYPE_FIELDS (b->type)
3204                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3205                   && type_list_equal (TYPE_FIELDS (a->type),
3206                                       TYPE_FIELDS (b->type))));
3207
3208     case FUNCTION_TYPE:
3209       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3210               || (TYPE_ARG_TYPES (a->type)
3211                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3212                   && TYPE_ARG_TYPES (b->type)
3213                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3214                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3215                                       TYPE_ARG_TYPES (b->type))));
3216
3217     default:
3218       return 0;
3219     }
3220 }
3221
3222 /* Return the cached hash value.  */
3223
3224 static hashval_t
3225 type_hash_hash (const void *item)
3226 {
3227   return ((const struct type_hash *) item)->hash;
3228 }
3229
3230 /* Look in the type hash table for a type isomorphic to TYPE.
3231    If one is found, return it.  Otherwise return 0.  */
3232
3233 tree
3234 type_hash_lookup (hashval_t hashcode, tree type)
3235 {
3236   struct type_hash *h, in;
3237
3238   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3239      must call that routine before comparing TYPE_ALIGNs.  */
3240   layout_type (type);
3241
3242   in.hash = hashcode;
3243   in.type = type;
3244
3245   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3246   if (h)
3247     return h->type;
3248   return NULL_TREE;
3249 }
3250
3251 /* Add an entry to the type-hash-table
3252    for a type TYPE whose hash code is HASHCODE.  */
3253
3254 void
3255 type_hash_add (hashval_t hashcode, tree type)
3256 {
3257   struct type_hash *h;
3258   void **loc;
3259
3260   h = ggc_alloc (sizeof (struct type_hash));
3261   h->hash = hashcode;
3262   h->type = type;
3263   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3264   *(struct type_hash **) loc = h;
3265 }
3266
3267 /* Given TYPE, and HASHCODE its hash code, return the canonical
3268    object for an identical type if one already exists.
3269    Otherwise, return TYPE, and record it as the canonical object.
3270
3271    To use this function, first create a type of the sort you want.
3272    Then compute its hash code from the fields of the type that
3273    make it different from other similar types.
3274    Then call this function and use the value.  */
3275
3276 tree
3277 type_hash_canon (unsigned int hashcode, tree type)
3278 {
3279   tree t1;
3280
3281   /* The hash table only contains main variants, so ensure that's what we're
3282      being passed.  */
3283   if (TYPE_MAIN_VARIANT (type) != type)
3284     abort ();
3285
3286   if (!lang_hooks.types.hash_types)
3287     return type;
3288
3289   /* See if the type is in the hash table already.  If so, return it.
3290      Otherwise, add the type.  */
3291   t1 = type_hash_lookup (hashcode, type);
3292   if (t1 != 0)
3293     {
3294 #ifdef GATHER_STATISTICS
3295       tree_node_counts[(int) t_kind]--;
3296       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3297 #endif
3298       return t1;
3299     }
3300   else
3301     {
3302       type_hash_add (hashcode, type);
3303       return type;
3304     }
3305 }
3306
3307 /* See if the data pointed to by the type hash table is marked.  We consider
3308    it marked if the type is marked or if a debug type number or symbol
3309    table entry has been made for the type.  This reduces the amount of
3310    debugging output and eliminates that dependency of the debug output on
3311    the number of garbage collections.  */
3312
3313 static int
3314 type_hash_marked_p (const void *p)
3315 {
3316   tree type = ((struct type_hash *) p)->type;
3317
3318   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3319 }
3320
3321 static void
3322 print_type_hash_statistics (void)
3323 {
3324   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3325            (long) htab_size (type_hash_table),
3326            (long) htab_elements (type_hash_table),
3327            htab_collisions (type_hash_table));
3328 }
3329
3330 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3331    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3332    by adding the hash codes of the individual attributes.  */
3333
3334 unsigned int
3335 attribute_hash_list (tree list, hashval_t hashcode)
3336 {
3337   tree tail;
3338
3339   for (tail = list; tail; tail = TREE_CHAIN (tail))
3340     /* ??? Do we want to add in TREE_VALUE too? */
3341     hashcode = iterative_hash_object
3342       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3343   return hashcode;
3344 }
3345
3346 /* Given two lists of attributes, return true if list l2 is
3347    equivalent to l1.  */
3348
3349 int
3350 attribute_list_equal (tree l1, tree l2)
3351 {
3352   return attribute_list_contained (l1, l2)
3353          && attribute_list_contained (l2, l1);
3354 }
3355
3356 /* Given two lists of attributes, return true if list L2 is
3357    completely contained within L1.  */
3358 /* ??? This would be faster if attribute names were stored in a canonicalized
3359    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3360    must be used to show these elements are equivalent (which they are).  */
3361 /* ??? It's not clear that attributes with arguments will always be handled
3362    correctly.  */
3363
3364 int
3365 attribute_list_contained (tree l1, tree l2)
3366 {
3367   tree t1, t2;
3368
3369   /* First check the obvious, maybe the lists are identical.  */
3370   if (l1 == l2)
3371     return 1;
3372
3373   /* Maybe the lists are similar.  */
3374   for (t1 = l1, t2 = l2;
3375        t1 != 0 && t2 != 0
3376         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3377         && TREE_VALUE (t1) == TREE_VALUE (t2);
3378        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3379
3380   /* Maybe the lists are equal.  */
3381   if (t1 == 0 && t2 == 0)
3382     return 1;
3383
3384   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3385     {
3386       tree attr;
3387       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3388            attr != NULL_TREE;
3389            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3390                                     TREE_CHAIN (attr)))
3391         {
3392           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3393             break;
3394         }
3395
3396       if (attr == 0)
3397         return 0;
3398
3399       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3400         return 0;
3401     }
3402
3403   return 1;
3404 }
3405
3406 /* Given two lists of types
3407    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3408    return 1 if the lists contain the same types in the same order.
3409    Also, the TREE_PURPOSEs must match.  */
3410
3411 int
3412 type_list_equal (tree l1, tree l2)
3413 {
3414   tree t1, t2;
3415
3416   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3417     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3418         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3419             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3420                   && (TREE_TYPE (TREE_PURPOSE (t1))
3421                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3422       return 0;
3423
3424   return t1 == t2;
3425 }
3426
3427 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3428    given by TYPE.  If the argument list accepts variable arguments,
3429    then this function counts only the ordinary arguments.  */
3430
3431 int
3432 type_num_arguments (tree type)
3433 {
3434   int i = 0;
3435   tree t;
3436
3437   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3438     /* If the function does not take a variable number of arguments,
3439        the last element in the list will have type `void'.  */
3440     if (VOID_TYPE_P (TREE_VALUE (t)))
3441       break;
3442     else
3443       ++i;
3444
3445   return i;
3446 }
3447
3448 /* Nonzero if integer constants T1 and T2
3449    represent the same constant value.  */
3450
3451 int
3452 tree_int_cst_equal (tree t1, tree t2)
3453 {
3454   if (t1 == t2)
3455     return 1;
3456
3457   if (t1 == 0 || t2 == 0)
3458     return 0;
3459
3460   if (TREE_CODE (t1) == INTEGER_CST
3461       && TREE_CODE (t2) == INTEGER_CST
3462       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3463       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3464     return 1;
3465
3466   return 0;
3467 }
3468
3469 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3470    The precise way of comparison depends on their data type.  */
3471
3472 int
3473 tree_int_cst_lt (tree t1, tree t2)
3474 {
3475   if (t1 == t2)
3476     return 0;
3477
3478   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3479     {
3480       int t1_sgn = tree_int_cst_sgn (t1);
3481       int t2_sgn = tree_int_cst_sgn (t2);
3482
3483       if (t1_sgn < t2_sgn)
3484         return 1;
3485       else if (t1_sgn > t2_sgn)
3486         return 0;
3487       /* Otherwise, both are non-negative, so we compare them as
3488          unsigned just in case one of them would overflow a signed
3489          type.  */
3490     }
3491   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3492     return INT_CST_LT (t1, t2);
3493
3494   return INT_CST_LT_UNSIGNED (t1, t2);
3495 }
3496
3497 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3498
3499 int
3500 tree_int_cst_compare (tree t1, tree t2)
3501 {
3502   if (tree_int_cst_lt (t1, t2))
3503     return -1;
3504   else if (tree_int_cst_lt (t2, t1))
3505     return 1;
3506   else
3507     return 0;
3508 }
3509
3510 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3511    the host.  If POS is zero, the value can be represented in a single
3512    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3513    be represented in a single unsigned HOST_WIDE_INT.  */
3514
3515 int
3516 host_integerp (tree t, int pos)
3517 {
3518   return (TREE_CODE (t) == INTEGER_CST
3519           && ! TREE_OVERFLOW (t)
3520           && ((TREE_INT_CST_HIGH (t) == 0
3521                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3522               || (! pos && TREE_INT_CST_HIGH (t) == -1
3523                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3524                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3525               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3526 }
3527
3528 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3529    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3530    be positive.  Abort if we cannot satisfy the above conditions.  */
3531
3532 HOST_WIDE_INT
3533 tree_low_cst (tree t, int pos)
3534 {
3535   if (host_integerp (t, pos))
3536     return TREE_INT_CST_LOW (t);
3537   else
3538     abort ();
3539 }
3540
3541 /* Return the most significant bit of the integer constant T.  */
3542
3543 int
3544 tree_int_cst_msb (tree t)
3545 {
3546   int prec;
3547   HOST_WIDE_INT h;
3548   unsigned HOST_WIDE_INT l;
3549
3550   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3551      actual bits, not the (arbitrary) range of the type.  */
3552   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3553   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3554                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3555   return (l & 1) == 1;
3556 }
3557
3558 /* Return an indication of the sign of the integer constant T.
3559    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3560    Note that -1 will never be returned it T's type is unsigned.  */
3561
3562 int
3563 tree_int_cst_sgn (tree t)
3564 {
3565   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3566     return 0;
3567   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3568     return 1;
3569   else if (TREE_INT_CST_HIGH (t) < 0)
3570     return -1;
3571   else
3572     return 1;
3573 }
3574
3575 /* Compare two constructor-element-type constants.  Return 1 if the lists
3576    are known to be equal; otherwise return 0.  */
3577
3578 int
3579 simple_cst_list_equal (tree l1, tree l2)
3580 {
3581   while (l1 != NULL_TREE && l2 != NULL_TREE)
3582     {
3583       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3584         return 0;
3585
3586       l1 = TREE_CHAIN (l1);
3587       l2 = TREE_CHAIN (l2);
3588     }
3589
3590   return l1 == l2;
3591 }
3592
3593 /* Return truthvalue of whether T1 is the same tree structure as T2.
3594    Return 1 if they are the same.
3595    Return 0 if they are understandably different.
3596    Return -1 if either contains tree structure not understood by
3597    this function.  */
3598
3599 int
3600 simple_cst_equal (tree t1, tree t2)
3601 {
3602   enum tree_code code1, code2;
3603   int cmp;
3604   int i;
3605
3606   if (t1 == t2)
3607     return 1;
3608   if (t1 == 0 || t2 == 0)
3609     return 0;
3610
3611   code1 = TREE_CODE (t1);
3612   code2 = TREE_CODE (t2);
3613
3614   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3615     {
3616       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3617           || code2 == NON_LVALUE_EXPR)
3618         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3619       else
3620         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3621     }
3622
3623   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3624            || code2 == NON_LVALUE_EXPR)
3625     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3626
3627   if (code1 != code2)
3628     return 0;
3629
3630   switch (code1)
3631     {
3632     case INTEGER_CST:
3633       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3634               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3635
3636     case REAL_CST:
3637       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3638
3639     case STRING_CST:
3640       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3641               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3642                          TREE_STRING_LENGTH (t1)));
3643
3644     case CONSTRUCTOR:
3645       if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
3646         return 1;
3647       else
3648         abort ();
3649
3650     case SAVE_EXPR:
3651       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3652
3653     case CALL_EXPR:
3654       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3655       if (cmp <= 0)
3656         return cmp;
3657       return
3658         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3659
3660     case TARGET_EXPR:
3661       /* Special case: if either target is an unallocated VAR_DECL,
3662          it means that it's going to be unified with whatever the
3663          TARGET_EXPR is really supposed to initialize, so treat it
3664          as being equivalent to anything.  */
3665       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3666            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3667            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3668           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3669               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3670               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3671         cmp = 1;
3672       else
3673         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3674
3675       if (cmp <= 0)
3676         return cmp;
3677
3678       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3679
3680     case WITH_CLEANUP_EXPR:
3681       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3682       if (cmp <= 0)
3683         return cmp;
3684
3685       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3686
3687     case COMPONENT_REF:
3688       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3689         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3690
3691       return 0;
3692
3693     case VAR_DECL:
3694     case PARM_DECL:
3695     case CONST_DECL:
3696     case FUNCTION_DECL:
3697       return 0;
3698
3699     default:
3700       break;
3701     }
3702
3703   /* This general rule works for most tree codes.  All exceptions should be
3704      handled above.  If this is a language-specific tree code, we can't
3705      trust what might be in the operand, so say we don't know
3706      the situation.  */
3707   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3708     return -1;
3709
3710   switch (TREE_CODE_CLASS (code1))
3711     {
3712     case '1':
3713     case '2':
3714     case '<':
3715     case 'e':
3716     case 'r':
3717     case 's':
3718       cmp = 1;
3719       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3720         {
3721           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3722           if (cmp <= 0)
3723             return cmp;
3724         }
3725
3726       return cmp;
3727
3728     default:
3729       return -1;
3730     }
3731 }
3732
3733 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3734    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3735    than U, respectively.  */
3736
3737 int
3738 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3739 {
3740   if (tree_int_cst_sgn (t) < 0)
3741     return -1;
3742   else if (TREE_INT_CST_HIGH (t) != 0)
3743     return 1;
3744   else if (TREE_INT_CST_LOW (t) == u)
3745     return 0;
3746   else if (TREE_INT_CST_LOW (t) < u)
3747     return -1;
3748   else
3749     return 1;
3750 }
3751
3752 /* Return true if CODE represents an associative tree code.  Otherwise
3753    return false.  */
3754 bool
3755 associative_tree_code (enum tree_code code)
3756 {
3757   switch (code)
3758     {
3759     case BIT_IOR_EXPR:
3760     case BIT_AND_EXPR:
3761     case BIT_XOR_EXPR:
3762     case PLUS_EXPR:
3763     case MINUS_EXPR:
3764     case MULT_EXPR:
3765     case LSHIFT_EXPR:
3766     case RSHIFT_EXPR:
3767     case MIN_EXPR:
3768     case MAX_EXPR:
3769       return true;
3770
3771     default:
3772       break;
3773     }
3774   return false;
3775 }
3776
3777 /* Return true if CODE represents an commutative tree code.  Otherwise
3778    return false.  */
3779 bool
3780 commutative_tree_code (enum tree_code code)
3781 {
3782   switch (code)
3783     {
3784     case PLUS_EXPR:
3785     case MULT_EXPR:
3786     case MIN_EXPR:
3787     case MAX_EXPR:
3788     case BIT_IOR_EXPR:
3789     case BIT_XOR_EXPR:
3790     case BIT_AND_EXPR:
3791     case NE_EXPR:
3792     case EQ_EXPR:
3793       return true;
3794
3795     default:
3796       break;
3797     }
3798   return false;
3799 }
3800
3801 /* Generate a hash value for an expression.  This can be used iteratively
3802    by passing a previous result as the "val" argument.
3803
3804    This function is intended to produce the same hash for expressions which
3805    would compare equal using operand_equal_p.  */
3806
3807 hashval_t
3808 iterative_hash_expr (tree t, hashval_t val)
3809 {
3810   int i;
3811   enum tree_code code;
3812   char class;
3813
3814   if (t == NULL_TREE)
3815     return iterative_hash_object (t, val);
3816
3817   code = TREE_CODE (t);
3818   class = TREE_CODE_CLASS (code);
3819
3820   if (class == 'd')
3821     {
3822       /* Decls we can just compare by pointer.  */
3823       val = iterative_hash_object (t, val);
3824     }
3825   else if (class == 'c')
3826     {
3827       /* Alas, constants aren't shared, so we can't rely on pointer
3828          identity.  */
3829       if (code == INTEGER_CST)
3830         {
3831           val = iterative_hash_object (TREE_INT_CST_LOW (t), val);
3832           val = iterative_hash_object (TREE_INT_CST_HIGH (t), val);
3833         }
3834       else if (code == REAL_CST)
3835         val = iterative_hash (TREE_REAL_CST_PTR (t),
3836                               sizeof (REAL_VALUE_TYPE), val);
3837       else if (code == STRING_CST)
3838         val = iterative_hash (TREE_STRING_POINTER (t),
3839                               TREE_STRING_LENGTH (t), val);
3840       else if (code == COMPLEX_CST)
3841         {
3842           val = iterative_hash_expr (TREE_REALPART (t), val);
3843           val = iterative_hash_expr (TREE_IMAGPART (t), val);
3844         }
3845       else if (code == VECTOR_CST)
3846         val = iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
3847       else
3848         abort ();
3849     }
3850   else if (IS_EXPR_CODE_CLASS (class))
3851     {
3852       val = iterative_hash_object (code, val);
3853
3854       if (code == NOP_EXPR || code == CONVERT_EXPR
3855           || code == NON_LVALUE_EXPR)
3856         val = iterative_hash_object (TREE_TYPE (t), val);
3857
3858       if (commutative_tree_code (code))
3859         {
3860           /* It's a commutative expression.  We want to hash it the same
3861              however it appears.  We do this by first hashing both operands
3862              and then rehashing based on the order of their independent
3863              hashes.  */
3864           hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
3865           hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
3866           hashval_t t;
3867
3868           if (one > two)
3869             t = one, one = two, two = t;
3870
3871           val = iterative_hash_object (one, val);
3872           val = iterative_hash_object (two, val);
3873         }
3874       else
3875         for (i = first_rtl_op (code) - 1; i >= 0; --i)
3876           val = iterative_hash_expr (TREE_OPERAND (t, i), val);
3877     }
3878   else if (code == TREE_LIST)
3879     {
3880       /* A list of expressions, for a CALL_EXPR or as the elements of a
3881          VECTOR_CST.  */
3882       for (; t; t = TREE_CHAIN (t))
3883         val = iterative_hash_expr (TREE_VALUE (t), val);
3884     }
3885   else
3886     abort ();
3887
3888   return val;
3889 }
3890 \f
3891 /* Constructors for pointer, array and function types.
3892    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3893    constructed by language-dependent code, not here.)  */
3894
3895 /* Construct, lay out and return the type of pointers to TO_TYPE with
3896    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
3897    reference all of memory. If such a type has already been
3898    constructed, reuse it.  */
3899
3900 tree
3901 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
3902                              bool can_alias_all)
3903 {
3904   tree t;
3905
3906   /* In some cases, languages will have things that aren't a POINTER_TYPE
3907      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
3908      In that case, return that type without regard to the rest of our
3909      operands.
3910
3911      ??? This is a kludge, but consistent with the way this function has
3912      always operated and there doesn't seem to be a good way to avoid this
3913      at the moment.  */
3914   if (TYPE_POINTER_TO (to_type) != 0
3915       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
3916     return TYPE_POINTER_TO (to_type);
3917
3918   /* First, if we already have a type for pointers to TO_TYPE and it's
3919      the proper mode, use it.  */
3920   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
3921     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
3922       return t;
3923
3924   t = make_node (POINTER_TYPE);
3925
3926   TREE_TYPE (t) = to_type;
3927   TYPE_MODE (t) = mode;
3928   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
3929   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
3930   TYPE_POINTER_TO (to_type) = t;
3931
3932   /* Lay out the type.  This function has many callers that are concerned
3933      with expression-construction, and this simplifies them all.  */
3934   layout_type (t);
3935
3936   return t;
3937 }
3938
3939 /* By default build pointers in ptr_mode.  */
3940
3941 tree
3942 build_pointer_type (tree to_type)
3943 {
3944   return build_pointer_type_for_mode (to_type, ptr_mode, false);
3945 }
3946
3947 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
3948
3949 tree
3950 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
3951                                bool can_alias_all)
3952 {
3953   tree t;
3954
3955   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
3956      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
3957      In that case, return that type without regard to the rest of our
3958      operands.
3959
3960      ??? This is a kludge, but consistent with the way this function has
3961      always operated and there doesn't seem to be a good way to avoid this
3962      at the moment.  */
3963   if (TYPE_REFERENCE_TO (to_type) != 0
3964       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
3965     return TYPE_REFERENCE_TO (to_type);
3966
3967   /* First, if we already have a type for pointers to TO_TYPE and it's
3968      the proper mode, use it.  */
3969   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
3970     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
3971       return t;
3972
3973   t = make_node (REFERENCE_TYPE);
3974
3975   TREE_TYPE (t) = to_type;
3976   TYPE_MODE (t) = mode;
3977   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
3978   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
3979   TYPE_REFERENCE_TO (to_type) = t;
3980
3981   layout_type (t);
3982
3983   return t;
3984 }
3985
3986
3987 /* Build the node for the type of references-to-TO_TYPE by default
3988    in ptr_mode.  */
3989
3990 tree
3991 build_reference_type (tree to_type)
3992 {
3993   return build_reference_type_for_mode (to_type, ptr_mode, false);
3994 }
3995
3996 /* Build a type that is compatible with t but has no cv quals anywhere
3997    in its type, thus
3998
3999    const char *const *const *  ->  char ***.  */
4000
4001 tree
4002 build_type_no_quals (tree t)
4003 {
4004   switch (TREE_CODE (t))
4005     {
4006     case POINTER_TYPE:
4007       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4008                                           TYPE_MODE (t),
4009                                           TYPE_REF_CAN_ALIAS_ALL (t));
4010     case REFERENCE_TYPE:
4011       return
4012         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4013                                        TYPE_MODE (t),
4014                                        TYPE_REF_CAN_ALIAS_ALL (t));
4015     default:
4016       return TYPE_MAIN_VARIANT (t);
4017     }
4018 }
4019
4020 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4021    MAXVAL should be the maximum value in the domain
4022    (one less than the length of the array).
4023
4024    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4025    We don't enforce this limit, that is up to caller (e.g. language front end).
4026    The limit exists because the result is a signed type and we don't handle
4027    sizes that use more than one HOST_WIDE_INT.  */
4028
4029 tree
4030 build_index_type (tree maxval)
4031 {
4032   tree itype = make_node (INTEGER_TYPE);
4033
4034   TREE_TYPE (itype) = sizetype;
4035   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4036   TYPE_MIN_VALUE (itype) = size_zero_node;
4037   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
4038   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4039   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4040   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4041   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4042   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4043
4044   if (host_integerp (maxval, 1))
4045     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4046   else
4047     return itype;
4048 }
4049
4050 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4051    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4052    low bound LOWVAL and high bound HIGHVAL.
4053    if TYPE==NULL_TREE, sizetype is used.  */
4054
4055 tree
4056 build_range_type (tree type, tree lowval, tree highval)
4057 {
4058   tree itype = make_node (INTEGER_TYPE);
4059
4060   TREE_TYPE (itype) = type;
4061   if (type == NULL_TREE)
4062     type = sizetype;
4063
4064   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4065   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4066
4067   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4068   TYPE_MODE (itype) = TYPE_MODE (type);
4069   TYPE_SIZE (itype) = TYPE_SIZE (type);
4070   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4071   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4072   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4073
4074   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4075     return type_hash_canon (tree_low_cst (highval, 0)
4076                             - tree_low_cst (lowval, 0),
4077                             itype);
4078   else
4079     return itype;
4080 }
4081
4082 /* Just like build_index_type, but takes lowval and highval instead
4083    of just highval (maxval).  */
4084
4085 tree
4086 build_index_2_type (tree lowval, tree highval)
4087 {
4088   return build_range_type (sizetype, lowval, highval);
4089 }
4090
4091 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4092    and number of elements specified by the range of values of INDEX_TYPE.
4093    If such a type has already been constructed, reuse it.  */
4094
4095 tree
4096 build_array_type (tree elt_type, tree index_type)
4097 {
4098   tree t;
4099   hashval_t hashcode = 0;
4100
4101   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4102     {
4103       error ("arrays of functions are not meaningful");
4104       elt_type = integer_type_node;
4105     }
4106
4107   t = make_node (ARRAY_TYPE);
4108   TREE_TYPE (t) = elt_type;
4109   TYPE_DOMAIN (t) = index_type;
4110
4111   if (index_type == 0)
4112     return t;
4113
4114   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4115   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4116   t = type_hash_canon (hashcode, t);
4117
4118   if (!COMPLETE_TYPE_P (t))
4119     layout_type (t);
4120   return t;
4121 }
4122
4123 /* Return the TYPE of the elements comprising
4124    the innermost dimension of ARRAY.  */
4125
4126 tree
4127 get_inner_array_type (tree array)
4128 {
4129   tree type = TREE_TYPE (array);
4130
4131   while (TREE_CODE (type) == ARRAY_TYPE)
4132     type = TREE_TYPE (type);
4133
4134   return type;
4135 }
4136
4137 /* Construct, lay out and return
4138    the type of functions returning type VALUE_TYPE
4139    given arguments of types ARG_TYPES.
4140    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4141    are data type nodes for the arguments of the function.
4142    If such a type has already been constructed, reuse it.  */
4143
4144 tree
4145 build_function_type (tree value_type, tree arg_types)
4146 {
4147   tree t;
4148   hashval_t hashcode = 0;
4149
4150   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4151     {
4152       error ("function return type cannot be function");
4153       value_type = integer_type_node;
4154     }
4155
4156   /* Make a node of the sort we want.  */
4157   t = make_node (FUNCTION_TYPE);
4158   TREE_TYPE (t) = value_type;
4159   TYPE_ARG_TYPES (t) = arg_types;
4160
4161   /* If we already have such a type, use the old one.  */
4162   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4163   hashcode = type_hash_list (arg_types, hashcode);
4164   t = type_hash_canon (hashcode, t);
4165
4166   if (!COMPLETE_TYPE_P (t))
4167     layout_type (t);
4168   return t;
4169 }
4170
4171 /* Build a function type.  The RETURN_TYPE is the type returned by the
4172    function.  If additional arguments are provided, they are
4173    additional argument types.  The list of argument types must always
4174    be terminated by NULL_TREE.  */
4175
4176 tree
4177 build_function_type_list (tree return_type, ...)
4178 {
4179   tree t, args, last;
4180   va_list p;
4181
4182   va_start (p, return_type);
4183
4184   t = va_arg (p, tree);
4185   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4186     args = tree_cons (NULL_TREE, t, args);
4187
4188   last = args;
4189   args = nreverse (args);
4190   TREE_CHAIN (last) = void_list_node;
4191   args = build_function_type (return_type, args);
4192
4193   va_end (p);
4194   return args;
4195 }
4196
4197 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4198    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4199    for the method.  An implicit additional parameter (of type
4200    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4201
4202 tree
4203 build_method_type_directly (tree basetype,
4204                             tree rettype,
4205                             tree argtypes)
4206 {
4207   tree t;
4208   tree ptype;
4209   int hashcode = 0;
4210
4211   /* Make a node of the sort we want.  */
4212   t = make_node (METHOD_TYPE);
4213
4214   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4215   TREE_TYPE (t) = rettype;
4216   ptype = build_pointer_type (basetype);
4217
4218   /* The actual arglist for this function includes a "hidden" argument
4219      which is "this".  Put it into the list of argument types.  */
4220   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4221   TYPE_ARG_TYPES (t) = argtypes;
4222
4223   /* If we already have such a type, use the old one.  */
4224   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4225   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4226   hashcode = type_hash_list (argtypes, hashcode);
4227   t = type_hash_canon (hashcode, t);
4228
4229   if (!COMPLETE_TYPE_P (t))
4230     layout_type (t);
4231
4232   return t;
4233 }
4234
4235 /* Construct, lay out and return the type of methods belonging to class
4236    BASETYPE and whose arguments and values are described by TYPE.
4237    If that type exists already, reuse it.
4238    TYPE must be a FUNCTION_TYPE node.  */
4239
4240 tree
4241 build_method_type (tree basetype, tree type)
4242 {
4243   if (TREE_CODE (type) != FUNCTION_TYPE)
4244     abort ();
4245
4246   return build_method_type_directly (basetype,
4247                                      TREE_TYPE (type),
4248                                      TYPE_ARG_TYPES (type));
4249 }
4250
4251 /* Construct, lay out and return the type of offsets to a value
4252    of type TYPE, within an object of type BASETYPE.
4253    If a suitable offset type exists already, reuse it.  */
4254
4255 tree
4256 build_offset_type (tree basetype, tree type)
4257 {
4258   tree t;
4259   hashval_t hashcode = 0;
4260
4261   /* Make a node of the sort we want.  */
4262   t = make_node (OFFSET_TYPE);
4263
4264   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4265   TREE_TYPE (t) = type;
4266
4267   /* If we already have such a type, use the old one.  */
4268   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4269   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4270   t = type_hash_canon (hashcode, t);
4271
4272   if (!COMPLETE_TYPE_P (t))
4273     layout_type (t);
4274
4275   return t;
4276 }
4277
4278 /* Create a complex type whose components are COMPONENT_TYPE.  */
4279
4280 tree
4281 build_complex_type (tree component_type)
4282 {
4283   tree t;
4284   hashval_t hashcode;
4285
4286   /* Make a node of the sort we want.  */
4287   t = make_node (COMPLEX_TYPE);
4288
4289   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4290
4291   /* If we already have such a type, use the old one.  */
4292   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4293   t = type_hash_canon (hashcode, t);
4294
4295   if (!COMPLETE_TYPE_P (t))
4296     layout_type (t);
4297
4298   /* If we are writing Dwarf2 output we need to create a name,
4299      since complex is a fundamental type.  */
4300   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4301       && ! TYPE_NAME (t))
4302     {
4303       const char *name;
4304       if (component_type == char_type_node)
4305         name = "complex char";
4306       else if (component_type == signed_char_type_node)
4307         name = "complex signed char";
4308       else if (component_type == unsigned_char_type_node)
4309         name = "complex unsigned char";
4310       else if (component_type == short_integer_type_node)
4311         name = "complex short int";
4312       else if (component_type == short_unsigned_type_node)
4313         name = "complex short unsigned int";
4314       else if (component_type == integer_type_node)
4315         name = "complex int";
4316       else if (component_type == unsigned_type_node)
4317         name = "complex unsigned int";
4318       else if (component_type == long_integer_type_node)
4319         name = "complex long int";
4320       else if (component_type == long_unsigned_type_node)
4321         name = "complex long unsigned int";
4322       else if (component_type == long_long_integer_type_node)
4323         name = "complex long long int";
4324       else if (component_type == long_long_unsigned_type_node)
4325         name = "complex long long unsigned int";
4326       else
4327         name = 0;
4328
4329       if (name != 0)
4330         TYPE_NAME (t) = get_identifier (name);
4331     }
4332
4333   return build_qualified_type (t, TYPE_QUALS (component_type));
4334 }
4335 \f
4336 /* Return OP, stripped of any conversions to wider types as much as is safe.
4337    Converting the value back to OP's type makes a value equivalent to OP.
4338
4339    If FOR_TYPE is nonzero, we return a value which, if converted to
4340    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4341
4342    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4343    narrowest type that can hold the value, even if they don't exactly fit.
4344    Otherwise, bit-field references are changed to a narrower type
4345    only if they can be fetched directly from memory in that type.
4346
4347    OP must have integer, real or enumeral type.  Pointers are not allowed!
4348
4349    There are some cases where the obvious value we could return
4350    would regenerate to OP if converted to OP's type,
4351    but would not extend like OP to wider types.
4352    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4353    For example, if OP is (unsigned short)(signed char)-1,
4354    we avoid returning (signed char)-1 if FOR_TYPE is int,
4355    even though extending that to an unsigned short would regenerate OP,
4356    since the result of extending (signed char)-1 to (int)
4357    is different from (int) OP.  */
4358
4359 tree
4360 get_unwidened (tree op, tree for_type)
4361 {
4362   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4363   tree type = TREE_TYPE (op);
4364   unsigned final_prec
4365     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4366   int uns
4367     = (for_type != 0 && for_type != type
4368        && final_prec > TYPE_PRECISION (type)
4369        && TYPE_UNSIGNED (type));
4370   tree win = op;
4371
4372   while (TREE_CODE (op) == NOP_EXPR)
4373     {
4374       int bitschange
4375         = TYPE_PRECISION (TREE_TYPE (op))
4376           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4377
4378       /* Truncations are many-one so cannot be removed.
4379          Unless we are later going to truncate down even farther.  */
4380       if (bitschange < 0
4381           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4382         break;
4383
4384       /* See what's inside this conversion.  If we decide to strip it,
4385          we will set WIN.  */
4386       op = TREE_OPERAND (op, 0);
4387
4388       /* If we have not stripped any zero-extensions (uns is 0),
4389          we can strip any kind of extension.
4390          If we have previously stripped a zero-extension,
4391          only zero-extensions can safely be stripped.
4392          Any extension can be stripped if the bits it would produce
4393          are all going to be discarded later by truncating to FOR_TYPE.  */
4394
4395       if (bitschange > 0)
4396         {
4397           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4398             win = op;
4399           /* TYPE_UNSIGNED says whether this is a zero-extension.
4400              Let's avoid computing it if it does not affect WIN
4401              and if UNS will not be needed again.  */
4402           if ((uns || TREE_CODE (op) == NOP_EXPR)
4403               && TYPE_UNSIGNED (TREE_TYPE (op)))
4404             {
4405               uns = 1;
4406               win = op;
4407             }
4408         }
4409     }
4410
4411   if (TREE_CODE (op) == COMPONENT_REF
4412       /* Since type_for_size always gives an integer type.  */
4413       && TREE_CODE (type) != REAL_TYPE
4414       /* Don't crash if field not laid out yet.  */
4415       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4416       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4417     {
4418       unsigned int innerprec
4419         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4420       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4421                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4422       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4423
4424       /* We can get this structure field in the narrowest type it fits in.
4425          If FOR_TYPE is 0, do this only for a field that matches the
4426          narrower type exactly and is aligned for it
4427          The resulting extension to its nominal type (a fullword type)
4428          must fit the same conditions as for other extensions.  */
4429
4430       if (type != 0
4431           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
4432           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4433           && (! uns || final_prec <= innerprec || unsignedp))
4434         {
4435           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4436                        TREE_OPERAND (op, 1));
4437           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4438           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4439         }
4440     }
4441
4442   return win;
4443 }
4444 \f
4445 /* Return OP or a simpler expression for a narrower value
4446    which can be sign-extended or zero-extended to give back OP.
4447    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4448    or 0 if the value should be sign-extended.  */
4449
4450 tree
4451 get_narrower (tree op, int *unsignedp_ptr)
4452 {
4453   int uns = 0;
4454   int first = 1;
4455   tree win = op;
4456
4457   while (TREE_CODE (op) == NOP_EXPR)
4458     {
4459       int bitschange
4460         = (TYPE_PRECISION (TREE_TYPE (op))
4461            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4462
4463       /* Truncations are many-one so cannot be removed.  */
4464       if (bitschange < 0)
4465         break;
4466
4467       /* See what's inside this conversion.  If we decide to strip it,
4468          we will set WIN.  */
4469
4470       if (bitschange > 0)
4471         {
4472           op = TREE_OPERAND (op, 0);
4473           /* An extension: the outermost one can be stripped,
4474              but remember whether it is zero or sign extension.  */
4475           if (first)
4476             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4477           /* Otherwise, if a sign extension has been stripped,
4478              only sign extensions can now be stripped;
4479              if a zero extension has been stripped, only zero-extensions.  */
4480           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
4481             break;
4482           first = 0;
4483         }
4484       else /* bitschange == 0 */
4485         {
4486           /* A change in nominal type can always be stripped, but we must
4487              preserve the unsignedness.  */
4488           if (first)
4489             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4490           first = 0;
4491           op = TREE_OPERAND (op, 0);
4492         }
4493
4494       win = op;
4495     }
4496
4497   if (TREE_CODE (op) == COMPONENT_REF
4498       /* Since type_for_size always gives an integer type.  */
4499       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4500       /* Ensure field is laid out already.  */
4501       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0)
4502     {
4503       unsigned HOST_WIDE_INT innerprec
4504         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4505       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4506                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4507       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4508
4509       /* We can get this structure field in a narrower type that fits it,
4510          but the resulting extension to its nominal type (a fullword type)
4511          must satisfy the same conditions as for other extensions.
4512
4513          Do this only for fields that are aligned (not bit-fields),
4514          because when bit-field insns will be used there is no
4515          advantage in doing this.  */
4516
4517       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4518           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4519           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
4520           && type != 0)
4521         {
4522           if (first)
4523             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
4524           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4525                        TREE_OPERAND (op, 1));
4526           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4527           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4528         }
4529     }
4530   *unsignedp_ptr = uns;
4531   return win;
4532 }
4533 \f
4534 /* Nonzero if integer constant C has a value that is permissible
4535    for type TYPE (an INTEGER_TYPE).  */
4536
4537 int
4538 int_fits_type_p (tree c, tree type)
4539 {
4540   tree type_low_bound = TYPE_MIN_VALUE (type);
4541   tree type_high_bound = TYPE_MAX_VALUE (type);
4542   int ok_for_low_bound, ok_for_high_bound;
4543
4544   /* Perform some generic filtering first, which may allow making a decision
4545      even if the bounds are not constant.  First, negative integers never fit
4546      in unsigned types, */
4547   if ((TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4548       /* Also, unsigned integers with top bit set never fit signed types.  */
4549       || (! TYPE_UNSIGNED (type)
4550           && TYPE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4551     return 0;
4552
4553   /* If at least one bound of the type is a constant integer, we can check
4554      ourselves and maybe make a decision. If no such decision is possible, but
4555      this type is a subtype, try checking against that.  Otherwise, use
4556      force_fit_type, which checks against the precision.
4557
4558      Compute the status for each possibly constant bound, and return if we see
4559      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4560      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4561      for "constant known to fit".  */
4562
4563   ok_for_low_bound = -1;
4564   ok_for_high_bound = -1;
4565
4566   /* Check if C >= type_low_bound.  */
4567   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4568     {
4569       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4570       if (! ok_for_low_bound)
4571         return 0;
4572     }
4573
4574   /* Check if c <= type_high_bound.  */
4575   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4576     {
4577       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4578       if (! ok_for_high_bound)
4579         return 0;
4580     }
4581
4582   /* If the constant fits both bounds, the result is known.  */
4583   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4584     return 1;
4585
4586   /* If we haven't been able to decide at this point, there nothing more we
4587      can check ourselves here. Look at the base type if we have one.  */
4588   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4589     return int_fits_type_p (c, TREE_TYPE (type));
4590
4591   /* Or to force_fit_type, if nothing else.  */
4592   else
4593     {
4594       c = copy_node (c);
4595       TREE_TYPE (c) = type;
4596       return !force_fit_type (c, 0);
4597     }
4598 }
4599
4600 /* Returns true if T is, contains, or refers to a type with variable
4601    size.  This concept is more general than that of C99 'variably
4602    modified types': in C99, a struct type is never variably modified
4603    because a VLA may not appear as a structure member.  However, in
4604    GNU C code like:
4605
4606      struct S { int i[f()]; };
4607
4608    is valid, and other languages may define similar constructs.  */
4609
4610 bool
4611 variably_modified_type_p (tree type)
4612 {
4613   tree t;
4614
4615   if (type == error_mark_node)
4616     return false;
4617
4618   /* If TYPE itself has variable size, it is variably modified.
4619
4620      We do not yet have a representation of the C99 '[*]' syntax.
4621      When a representation is chosen, this function should be modified
4622      to test for that case as well.  */
4623   t = TYPE_SIZE (type);
4624   if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4625     return true;
4626
4627   switch (TREE_CODE (type))
4628     {
4629     case POINTER_TYPE:
4630     case REFERENCE_TYPE:
4631     case ARRAY_TYPE:
4632       /* If TYPE is a pointer or reference, it is variably modified if
4633          the type pointed to is variably modified.  Similarly for arrays;
4634          note that VLAs are handled by the TYPE_SIZE check above.  */
4635       return variably_modified_type_p (TREE_TYPE (type));
4636
4637     case FUNCTION_TYPE:
4638     case METHOD_TYPE:
4639       /* If TYPE is a function type, it is variably modified if any of the
4640          parameters or the return type are variably modified.  */
4641       {
4642         tree parm;
4643
4644         if (variably_modified_type_p (TREE_TYPE (type)))
4645           return true;
4646         for (parm = TYPE_ARG_TYPES (type);
4647              parm && parm != void_list_node;
4648              parm = TREE_CHAIN (parm))
4649           if (variably_modified_type_p (TREE_VALUE (parm)))
4650             return true;
4651       }
4652       break;
4653
4654     case INTEGER_TYPE:
4655       /* Scalar types are variably modified if their end points
4656          aren't constant.  */
4657       t = TYPE_MIN_VALUE (type);
4658       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4659         return true;
4660       t = TYPE_MAX_VALUE (type);
4661       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4662         return true;
4663       return false;
4664
4665     default:
4666       break;
4667     }
4668
4669   /* The current language may have other cases to check, but in general,
4670      all other types are not variably modified.  */
4671   return lang_hooks.tree_inlining.var_mod_type_p (type);
4672 }
4673
4674 /* Given a DECL or TYPE, return the scope in which it was declared, or
4675    NULL_TREE if there is no containing scope.  */
4676
4677 tree
4678 get_containing_scope (tree t)
4679 {
4680   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4681 }
4682
4683 /* Return the innermost context enclosing DECL that is
4684    a FUNCTION_DECL, or zero if none.  */
4685
4686 tree
4687 decl_function_context (tree decl)
4688 {
4689   tree context;
4690
4691   if (TREE_CODE (decl) == ERROR_MARK)
4692     return 0;
4693
4694   if (TREE_CODE (decl) == SAVE_EXPR)
4695     context = SAVE_EXPR_CONTEXT (decl);
4696
4697   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4698      where we look up the function at runtime.  Such functions always take
4699      a first argument of type 'pointer to real context'.
4700
4701      C++ should really be fixed to use DECL_CONTEXT for the real context,
4702      and use something else for the "virtual context".  */
4703   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4704     context
4705       = TYPE_MAIN_VARIANT
4706         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4707   else
4708     context = DECL_CONTEXT (decl);
4709
4710   while (context && TREE_CODE (context) != FUNCTION_DECL)
4711     {
4712       if (TREE_CODE (context) == BLOCK)
4713         context = BLOCK_SUPERCONTEXT (context);
4714       else
4715         context = get_containing_scope (context);
4716     }
4717
4718   return context;
4719 }
4720
4721 /* Return the innermost context enclosing DECL that is
4722    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4723    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4724
4725 tree
4726 decl_type_context (tree decl)
4727 {
4728   tree context = DECL_CONTEXT (decl);
4729
4730   while (context)
4731     switch (TREE_CODE (context))
4732       {
4733       case NAMESPACE_DECL:
4734       case TRANSLATION_UNIT_DECL:
4735         return NULL_TREE;
4736
4737       case RECORD_TYPE:
4738       case UNION_TYPE:
4739       case QUAL_UNION_TYPE:
4740         return context;
4741
4742       case TYPE_DECL:
4743       case FUNCTION_DECL:
4744         context = DECL_CONTEXT (context);
4745         break;
4746
4747       case BLOCK:
4748         context = BLOCK_SUPERCONTEXT (context);
4749         break;
4750
4751       default:
4752         abort ();
4753       }
4754
4755   return NULL_TREE;
4756 }
4757
4758 /* CALL is a CALL_EXPR.  Return the declaration for the function
4759    called, or NULL_TREE if the called function cannot be
4760    determined.  */
4761
4762 tree
4763 get_callee_fndecl (tree call)
4764 {
4765   tree addr;
4766
4767   /* It's invalid to call this function with anything but a
4768      CALL_EXPR.  */
4769   if (TREE_CODE (call) != CALL_EXPR)
4770     abort ();
4771
4772   /* The first operand to the CALL is the address of the function
4773      called.  */
4774   addr = TREE_OPERAND (call, 0);
4775
4776   STRIP_NOPS (addr);
4777
4778   /* If this is a readonly function pointer, extract its initial value.  */
4779   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4780       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4781       && DECL_INITIAL (addr))
4782     addr = DECL_INITIAL (addr);
4783
4784   /* If the address is just `&f' for some function `f', then we know
4785      that `f' is being called.  */
4786   if (TREE_CODE (addr) == ADDR_EXPR
4787       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4788     return TREE_OPERAND (addr, 0);
4789
4790   /* We couldn't figure out what was being called.  Maybe the front
4791      end has some idea.  */
4792   return lang_hooks.lang_get_callee_fndecl (call);
4793 }
4794
4795 /* Print debugging information about tree nodes generated during the compile,
4796    and any language-specific information.  */
4797
4798 void
4799 dump_tree_statistics (void)
4800 {
4801 #ifdef GATHER_STATISTICS
4802   int i;
4803   int total_nodes, total_bytes;
4804 #endif
4805
4806   fprintf (stderr, "\n??? tree nodes created\n\n");
4807 #ifdef GATHER_STATISTICS
4808   fprintf (stderr, "Kind                   Nodes      Bytes\n");
4809   fprintf (stderr, "---------------------------------------\n");
4810   total_nodes = total_bytes = 0;
4811   for (i = 0; i < (int) all_kinds; i++)
4812     {
4813       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
4814                tree_node_counts[i], tree_node_sizes[i]);
4815       total_nodes += tree_node_counts[i];
4816       total_bytes += tree_node_sizes[i];
4817     }
4818   fprintf (stderr, "---------------------------------------\n");
4819   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
4820   fprintf (stderr, "---------------------------------------\n");
4821 #else
4822   fprintf (stderr, "(No per-node statistics)\n");
4823 #endif
4824   print_type_hash_statistics ();
4825   lang_hooks.print_statistics ();
4826 }
4827 \f
4828 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4829
4830 /* Generate a crc32 of a string.  */
4831
4832 unsigned
4833 crc32_string (unsigned chksum, const char *string)
4834 {
4835   do
4836     {
4837       unsigned value = *string << 24;
4838       unsigned ix;
4839
4840       for (ix = 8; ix--; value <<= 1)
4841         {
4842           unsigned feedback;
4843
4844           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
4845           chksum <<= 1;
4846           chksum ^= feedback;
4847         }
4848     }
4849   while (*string++);
4850   return chksum;
4851 }
4852
4853 /* P is a string that will be used in a symbol.  Mask out any characters
4854    that are not valid in that context.  */
4855
4856 void
4857 clean_symbol_name (char *p)
4858 {
4859   for (; *p; p++)
4860     if (! (ISALNUM (*p)
4861 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4862             || *p == '$'
4863 #endif
4864 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4865             || *p == '.'
4866 #endif
4867            ))
4868       *p = '_';
4869 }
4870
4871 /* Generate a name for a function unique to this translation unit.
4872    TYPE is some string to identify the purpose of this function to the
4873    linker or collect2.  */
4874
4875 tree
4876 get_file_function_name_long (const char *type)
4877 {
4878   char *buf;
4879   const char *p;
4880   char *q;
4881
4882   if (first_global_object_name)
4883     p = first_global_object_name;
4884   else
4885     {
4886       /* We don't have anything that we know to be unique to this translation
4887          unit, so use what we do have and throw in some randomness.  */
4888       unsigned len;
4889       const char *name = weak_global_object_name;
4890       const char *file = main_input_filename;
4891
4892       if (! name)
4893         name = "";
4894       if (! file)
4895         file = input_filename;
4896
4897       len = strlen (file);
4898       q = alloca (9 * 2 + len + 1);
4899       memcpy (q, file, len + 1);
4900       clean_symbol_name (q);
4901
4902       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
4903                crc32_string (0, flag_random_seed));
4904
4905       p = q;
4906     }
4907
4908   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
4909
4910   /* Set up the name of the file-level functions we may need.
4911      Use a global object (which is already required to be unique over
4912      the program) rather than the file name (which imposes extra
4913      constraints).  */
4914   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
4915
4916   return get_identifier (buf);
4917 }
4918
4919 /* If KIND=='I', return a suitable global initializer (constructor) name.
4920    If KIND=='D', return a suitable global clean-up (destructor) name.  */
4921
4922 tree
4923 get_file_function_name (int kind)
4924 {
4925   char p[2];
4926
4927   p[0] = kind;
4928   p[1] = 0;
4929
4930   return get_file_function_name_long (p);
4931 }
4932 \f
4933 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4934    The result is placed in BUFFER (which has length BIT_SIZE),
4935    with one bit in each char ('\000' or '\001').
4936
4937    If the constructor is constant, NULL_TREE is returned.
4938    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4939
4940 tree
4941 get_set_constructor_bits (tree init, char *buffer, int bit_size)
4942 {
4943   int i;
4944   tree vals;
4945   HOST_WIDE_INT domain_min
4946     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
4947   tree non_const_bits = NULL_TREE;
4948
4949   for (i = 0; i < bit_size; i++)
4950     buffer[i] = 0;
4951
4952   for (vals = TREE_OPERAND (init, 1);
4953        vals != NULL_TREE; vals = TREE_CHAIN (vals))
4954     {
4955       if (!host_integerp (TREE_VALUE (vals), 0)
4956           || (TREE_PURPOSE (vals) != NULL_TREE
4957               && !host_integerp (TREE_PURPOSE (vals), 0)))
4958         non_const_bits
4959           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
4960       else if (TREE_PURPOSE (vals) != NULL_TREE)
4961         {
4962           /* Set a range of bits to ones.  */
4963           HOST_WIDE_INT lo_index
4964             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
4965           HOST_WIDE_INT hi_index
4966             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4967
4968           if (lo_index < 0 || lo_index >= bit_size
4969               || hi_index < 0 || hi_index >= bit_size)
4970             abort ();
4971           for (; lo_index <= hi_index; lo_index++)
4972             buffer[lo_index] = 1;
4973         }
4974       else
4975         {
4976           /* Set a single bit to one.  */
4977           HOST_WIDE_INT index
4978             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4979           if (index < 0 || index >= bit_size)
4980             {
4981               error ("invalid initializer for bit string");
4982               return NULL_TREE;
4983             }
4984           buffer[index] = 1;
4985         }
4986     }
4987   return non_const_bits;
4988 }
4989
4990 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4991    The result is placed in BUFFER (which is an array of bytes).
4992    If the constructor is constant, NULL_TREE is returned.
4993    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4994
4995 tree
4996 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
4997 {
4998   int i;
4999   int set_word_size = BITS_PER_UNIT;
5000   int bit_size = wd_size * set_word_size;
5001   int bit_pos = 0;
5002   unsigned char *bytep = buffer;
5003   char *bit_buffer = alloca (bit_size);
5004   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
5005
5006   for (i = 0; i < wd_size; i++)
5007     buffer[i] = 0;
5008
5009   for (i = 0; i < bit_size; i++)
5010     {
5011       if (bit_buffer[i])
5012         {
5013           if (BYTES_BIG_ENDIAN)
5014             *bytep |= (1 << (set_word_size - 1 - bit_pos));
5015           else
5016             *bytep |= 1 << bit_pos;
5017         }
5018       bit_pos++;
5019       if (bit_pos >= set_word_size)
5020         bit_pos = 0, bytep++;
5021     }
5022   return non_const_bits;
5023 }
5024 \f
5025 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5026
5027 /* Complain that the tree code of NODE does not match the expected CODE.
5028    FILE, LINE, and FUNCTION are of the caller.  */
5029
5030 void
5031 tree_check_failed (const tree node, enum tree_code code, const char *file,
5032                    int line, const char *function)
5033 {
5034   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
5035                   tree_code_name[code], tree_code_name[TREE_CODE (node)],
5036                   function, trim_filename (file), line);
5037 }
5038
5039 /* Similar to above except that we allowed the code to be one of two
5040    different codes.  */
5041
5042 void
5043 tree_check2_failed (const tree node, enum tree_code code1,
5044                     enum tree_code code2, const char *file,
5045                     int line, const char *function)
5046 {
5047   internal_error ("tree check: expected %s or %s, have %s in %s, at %s:%d",
5048                   tree_code_name[code1], tree_code_name[code2],
5049                   tree_code_name[TREE_CODE (node)],
5050                   function, trim_filename (file), line);
5051 }
5052
5053 /* Likewise for three different codes.  */
5054
5055 void
5056 tree_check3_failed (const tree node, enum tree_code code1,
5057                     enum tree_code code2, enum tree_code code3,
5058                     const char *file, int line, const char *function)
5059 {
5060   internal_error ("tree check: expected %s, %s or %s; have %s in %s, at %s:%d",
5061                   tree_code_name[code1], tree_code_name[code2],
5062                   tree_code_name[code3], tree_code_name[TREE_CODE (node)],
5063                   function, trim_filename (file), line);
5064 }
5065
5066 /* ... and for four different codes.  */
5067
5068 void
5069 tree_check4_failed (const tree node, enum tree_code code1,
5070                     enum tree_code code2, enum tree_code code3,
5071                     enum tree_code code4, const char *file, int line,
5072                     const char *function)
5073 {
5074   internal_error
5075     ("tree check: expected %s, %s, %s or %s; have %s in %s, at %s:%d",
5076      tree_code_name[code1], tree_code_name[code2], tree_code_name[code3],
5077      tree_code_name[code4], tree_code_name[TREE_CODE (node)], function,
5078      trim_filename (file), line);
5079 }
5080
5081 /* ... and for five different codes.  */
5082
5083 void
5084 tree_check5_failed (const tree node, enum tree_code code1,
5085                     enum tree_code code2, enum tree_code code3,
5086                     enum tree_code code4, enum tree_code code5,
5087                     const char *file, int line, const char *function)
5088 {
5089   internal_error
5090     ("tree check: expected %s, %s, %s, %s or %s; have %s in %s, at %s:%d",
5091      tree_code_name[code1], tree_code_name[code2], tree_code_name[code3],
5092      tree_code_name[code4], tree_code_name[code5],
5093      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5094 }
5095
5096 /* Similar to tree_check_failed, except that we check for a class of tree
5097    code, given in CL.  */
5098
5099 void
5100 tree_class_check_failed (const tree node, int cl, const char *file,
5101                          int line, const char *function)
5102 {
5103   internal_error
5104     ("tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
5105      cl, TREE_CODE_CLASS (TREE_CODE (node)),
5106      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5107 }
5108
5109 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
5110    (dynamically sized) vector.  */
5111
5112 void
5113 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
5114                            const char *function)
5115 {
5116   internal_error
5117     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
5118      idx + 1, len, function, trim_filename (file), line);
5119 }
5120
5121 /* Similar to above, except that the check is for the bounds of the operand
5122    vector of an expression node.  */
5123
5124 void
5125 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
5126                            int line, const char *function)
5127 {
5128   internal_error
5129     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
5130      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
5131      function, trim_filename (file), line);
5132 }
5133 #endif /* ENABLE_TREE_CHECKING */
5134 \f
5135 /* For a new vector type node T, build the information necessary for
5136    debugging output.  */
5137
5138 static void
5139 finish_vector_type (tree t)
5140 {
5141   layout_type (t);
5142
5143   {
5144     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
5145     tree array = build_array_type (TREE_TYPE (t),
5146                                    build_index_type (index));
5147     tree rt = make_node (RECORD_TYPE);
5148
5149     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
5150     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
5151     layout_type (rt);
5152     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
5153     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
5154        the representation type, and we want to find that die when looking up
5155        the vector type.  This is most easily achieved by making the TYPE_UID
5156        numbers equal.  */
5157     TYPE_UID (rt) = TYPE_UID (t);
5158   }
5159 }
5160
5161 /* Create nodes for all integer types (and error_mark_node) using the sizes
5162    of C datatypes.  The caller should call set_sizetype soon after calling
5163    this function to select one of the types as sizetype.  */
5164
5165 void
5166 build_common_tree_nodes (int signed_char)
5167 {
5168   error_mark_node = make_node (ERROR_MARK);
5169   TREE_TYPE (error_mark_node) = error_mark_node;
5170
5171   initialize_sizetypes ();
5172
5173   /* Define both `signed char' and `unsigned char'.  */
5174   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
5175   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
5176
5177   /* Define `char', which is like either `signed char' or `unsigned char'
5178      but not the same as either.  */
5179   char_type_node
5180     = (signed_char
5181        ? make_signed_type (CHAR_TYPE_SIZE)
5182        : make_unsigned_type (CHAR_TYPE_SIZE));
5183
5184   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
5185   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
5186   integer_type_node = make_signed_type (INT_TYPE_SIZE);
5187   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
5188   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
5189   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
5190   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
5191   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
5192
5193   /* Define a boolean type.  This type only represents boolean values but
5194      may be larger than char depending on the value of BOOL_TYPE_SIZE.
5195      Front ends which want to override this size (i.e. Java) can redefine
5196      boolean_type_node before calling build_common_tree_nodes_2.  */
5197   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
5198   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
5199   TYPE_MAX_VALUE (boolean_type_node) = build_int_2 (1, 0);
5200   TREE_TYPE (TYPE_MAX_VALUE (boolean_type_node)) = boolean_type_node;
5201   TYPE_PRECISION (boolean_type_node) = 1;
5202
5203   intQI_type_node = make_signed_type (GET_MODE_BITSIZE (QImode));
5204   intHI_type_node = make_signed_type (GET_MODE_BITSIZE (HImode));
5205   intSI_type_node = make_signed_type (GET_MODE_BITSIZE (SImode));
5206   intDI_type_node = make_signed_type (GET_MODE_BITSIZE (DImode));
5207   intTI_type_node = make_signed_type (GET_MODE_BITSIZE (TImode));
5208
5209   unsigned_intQI_type_node = make_unsigned_type (GET_MODE_BITSIZE (QImode));
5210   unsigned_intHI_type_node = make_unsigned_type (GET_MODE_BITSIZE (HImode));
5211   unsigned_intSI_type_node = make_unsigned_type (GET_MODE_BITSIZE (SImode));
5212   unsigned_intDI_type_node = make_unsigned_type (GET_MODE_BITSIZE (DImode));
5213   unsigned_intTI_type_node = make_unsigned_type (GET_MODE_BITSIZE (TImode));
5214
5215   access_public_node = get_identifier ("public");
5216   access_protected_node = get_identifier ("protected");
5217   access_private_node = get_identifier ("private");
5218 }
5219
5220 /* Call this function after calling build_common_tree_nodes and set_sizetype.
5221    It will create several other common tree nodes.  */
5222
5223 void
5224 build_common_tree_nodes_2 (int short_double)
5225 {
5226   /* Define these next since types below may used them.  */
5227   integer_zero_node = build_int_2 (0, 0);
5228   integer_one_node = build_int_2 (1, 0);
5229   integer_minus_one_node = build_int_2 (-1, -1);
5230
5231   size_zero_node = size_int (0);
5232   size_one_node = size_int (1);
5233   bitsize_zero_node = bitsize_int (0);
5234   bitsize_one_node = bitsize_int (1);
5235   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
5236
5237   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
5238   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
5239
5240   void_type_node = make_node (VOID_TYPE);
5241   layout_type (void_type_node);
5242
5243   /* We are not going to have real types in C with less than byte alignment,
5244      so we might as well not have any types that claim to have it.  */
5245   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
5246   TYPE_USER_ALIGN (void_type_node) = 0;
5247
5248   null_pointer_node = build_int_2 (0, 0);
5249   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
5250   layout_type (TREE_TYPE (null_pointer_node));
5251
5252   ptr_type_node = build_pointer_type (void_type_node);
5253   const_ptr_type_node
5254     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
5255
5256   float_type_node = make_node (REAL_TYPE);
5257   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
5258   layout_type (float_type_node);
5259
5260   double_type_node = make_node (REAL_TYPE);
5261   if (short_double)
5262     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
5263   else
5264     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
5265   layout_type (double_type_node);
5266
5267   long_double_type_node = make_node (REAL_TYPE);
5268   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
5269   layout_type (long_double_type_node);
5270
5271   float_ptr_type_node = build_pointer_type (float_type_node);
5272   double_ptr_type_node = build_pointer_type (double_type_node);
5273   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
5274   integer_ptr_type_node = build_pointer_type (integer_type_node);
5275
5276   complex_integer_type_node = make_node (COMPLEX_TYPE);
5277   TREE_TYPE (complex_integer_type_node) = integer_type_node;
5278   layout_type (complex_integer_type_node);
5279
5280   complex_float_type_node = make_node (COMPLEX_TYPE);
5281   TREE_TYPE (complex_float_type_node) = float_type_node;
5282   layout_type (complex_float_type_node);
5283
5284   complex_double_type_node = make_node (COMPLEX_TYPE);
5285   TREE_TYPE (complex_double_type_node) = double_type_node;
5286   layout_type (complex_double_type_node);
5287
5288   complex_long_double_type_node = make_node (COMPLEX_TYPE);
5289   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
5290   layout_type (complex_long_double_type_node);
5291
5292   {
5293     tree t = targetm.build_builtin_va_list ();
5294
5295     /* Many back-ends define record types without setting TYPE_NAME.
5296        If we copied the record type here, we'd keep the original
5297        record type without a name.  This breaks name mangling.  So,
5298        don't copy record types and let c_common_nodes_and_builtins()
5299        declare the type to be __builtin_va_list.  */
5300     if (TREE_CODE (t) != RECORD_TYPE)
5301       t = build_type_copy (t);
5302
5303     va_list_type_node = t;
5304   }
5305 }
5306
5307 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
5308    better way.
5309
5310    If we requested a pointer to a vector, build up the pointers that
5311    we stripped off while looking for the inner type.  Similarly for
5312    return values from functions.
5313
5314    The argument TYPE is the top of the chain, and BOTTOM is the
5315    new type which we will point to.  */
5316
5317 tree
5318 reconstruct_complex_type (tree type, tree bottom)
5319 {
5320   tree inner, outer;
5321
5322   if (POINTER_TYPE_P (type))
5323     {
5324       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5325       outer = build_pointer_type (inner);
5326     }
5327   else if (TREE_CODE (type) == ARRAY_TYPE)
5328     {
5329       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5330       outer = build_array_type (inner, TYPE_DOMAIN (type));
5331     }
5332   else if (TREE_CODE (type) == FUNCTION_TYPE)
5333     {
5334       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5335       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
5336     }
5337   else if (TREE_CODE (type) == METHOD_TYPE)
5338     {
5339       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5340       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
5341                                           inner,
5342                                           TYPE_ARG_TYPES (type));
5343     }
5344   else
5345     return bottom;
5346
5347   TREE_READONLY (outer) = TREE_READONLY (type);
5348   TREE_THIS_VOLATILE (outer) = TREE_THIS_VOLATILE (type);
5349
5350   return outer;
5351 }
5352
5353 /* Returns a vector tree node given a vector mode and inner type.  */
5354 tree
5355 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
5356 {
5357   tree t;
5358   t = make_node (VECTOR_TYPE);
5359   TREE_TYPE (t) = innertype;
5360   TYPE_MODE (t) = mode;
5361   finish_vector_type (t);
5362   return t;
5363 }
5364
5365 /* Similarly, but takes inner type and units.  */
5366
5367 tree
5368 build_vector_type (tree innertype, int nunits)
5369 {
5370   enum machine_mode innermode = TYPE_MODE (innertype);
5371   enum machine_mode mode;
5372
5373   if (GET_MODE_CLASS (innermode) == MODE_FLOAT)
5374     mode = MIN_MODE_VECTOR_FLOAT;
5375   else
5376     mode = MIN_MODE_VECTOR_INT;
5377
5378   for (; mode != VOIDmode ; mode = GET_MODE_WIDER_MODE (mode))
5379     if (GET_MODE_NUNITS (mode) == nunits && GET_MODE_INNER (mode) == innermode)
5380       return build_vector_type_for_mode (innertype, mode);
5381
5382   return NULL_TREE;
5383 }
5384
5385 /* Given an initializer INIT, return TRUE if INIT is zero or some
5386    aggregate of zeros.  Otherwise return FALSE.  */
5387 bool
5388 initializer_zerop (tree init)
5389 {
5390   STRIP_NOPS (init);
5391
5392   switch (TREE_CODE (init))
5393     {
5394     case INTEGER_CST:
5395       return integer_zerop (init);
5396     case REAL_CST:
5397       return real_zerop (init)
5398         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
5399     case COMPLEX_CST:
5400       return integer_zerop (init)
5401         || (real_zerop (init)
5402             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
5403             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
5404     case CONSTRUCTOR:
5405       {
5406         /* Set is empty if it has no elements.  */
5407         if ((TREE_CODE (TREE_TYPE (init)) == SET_TYPE)
5408              && CONSTRUCTOR_ELTS (init))
5409           return false;
5410
5411         if (AGGREGATE_TYPE_P (TREE_TYPE (init)))
5412           {
5413             tree aggr_init = CONSTRUCTOR_ELTS (init);
5414
5415             while (aggr_init)
5416               {
5417                 if (! initializer_zerop (TREE_VALUE (aggr_init)))
5418                   return false;
5419                 aggr_init = TREE_CHAIN (aggr_init);
5420               }
5421             return true;
5422           }
5423         return false;
5424       }
5425     default:
5426       return false;
5427     }
5428 }
5429
5430 #include "gt-tree.h"