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