gcc/tree.c

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