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