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