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