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