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