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