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