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, 2006, 2007
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 #include "fixed-value.h"
  54
  55 /* Each tree code class has an associated string representation.
  56    These must correspond to the tree_code_class entries.  */
  57
  58 const char *const tree_code_class_strings[] =
  59 {
  60   "exceptional",
  61   "constant",
  62   "type",
  63   "declaration",
  64   "reference",
  65   "comparison",
  66   "unary",
  67   "binary",
  68   "statement",
  69   "vl_exp",
  70   "expression",
  71   "gimple_stmt"
  72 };
  73
  74 /* obstack.[ch] explicitly declined to prototype this.  */
  75 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  76
  77 #ifdef GATHER_STATISTICS
  78 /* Statistics-gathering stuff.  */
  79
  80 int tree_node_counts[(int) all_kinds];
  81 int tree_node_sizes[(int) all_kinds];
  82
  83 /* Keep in sync with tree.h:enum tree_node_kind.  */
  84 static const char * const tree_node_kind_names[] = {
  85   "decls",
  86   "types",
  87   "blocks",
  88   "stmts",
  89   "refs",
  90   "exprs",
  91   "constants",
  92   "identifiers",
  93   "perm_tree_lists",
  94   "temp_tree_lists",
  95   "vecs",
  96   "binfos",
  97   "phi_nodes",
  98   "ssa names",
  99   "constructors",
 100   "random kinds",
 101   "lang_decl kinds",
 102   "lang_type kinds",
 103   "omp clauses",
 104   "gimple statements"
 105 };
 106 #endif /* GATHER_STATISTICS */
 107
 108 /* Unique id for next decl created.  */
 109 static GTY(()) int next_decl_uid;
 110 /* Unique id for next type created.  */
 111 static GTY(()) int next_type_uid = 1;
 112
 113 /* Since we cannot rehash a type after it is in the table, we have to
 114    keep the hash code.  */
 115
 116 struct type_hash GTY(())
 117 {
 118   unsigned long hash;
 119   tree type;
 120 };
 121
 122 /* Initial size of the hash table (rounded to next prime).  */
 123 #define TYPE_HASH_INITIAL_SIZE 1000
 124
 125 /* Now here is the hash table.  When recording a type, it is added to
 126    the slot whose index is the hash code.  Note that the hash table is
 127    used for several kinds of types (function types, array types and
 128    array index range types, for now).  While all these live in the
 129    same table, they are completely independent, and the hash code is
 130    computed differently for each of these.  */
 131
 132 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 133      htab_t type_hash_table;
 134
 135 /* Hash table and temporary node for larger integer const values.  */
 136 static GTY (()) tree int_cst_node;
 137 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
 138      htab_t int_cst_hash_table;
 139
 140 /* General tree->tree mapping  structure for use in hash tables.  */
 141
 142
 143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 144      htab_t debug_expr_for_decl;
 145
 146 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 147      htab_t value_expr_for_decl;
 148
 149 static GTY ((if_marked ("tree_priority_map_marked_p"),
 150              param_is (struct tree_priority_map)))
 151   htab_t init_priority_for_decl;
 152
 153 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 154   htab_t restrict_base_for_decl;
 155
 156 static void set_type_quals (tree, int);
 157 static int type_hash_eq (const void *, const void *);
 158 static hashval_t type_hash_hash (const void *);
 159 static hashval_t int_cst_hash_hash (const void *);
 160 static int int_cst_hash_eq (const void *, const void *);
 161 static void print_type_hash_statistics (void);
 162 static void print_debug_expr_statistics (void);
 163 static void print_value_expr_statistics (void);
 164 static int type_hash_marked_p (const void *);
 165 static unsigned int type_hash_list (const_tree, hashval_t);
 166 static unsigned int attribute_hash_list (const_tree, hashval_t);
 167
 168 tree global_trees[TI_MAX];
 169 tree integer_types[itk_none];
 170
 171 unsigned char tree_contains_struct[MAX_TREE_CODES][64];
 172
 173 /* Number of operands for each OpenMP clause.  */
 174 unsigned const char omp_clause_num_ops[] =
 175 {
 176   0, /* OMP_CLAUSE_ERROR  */
 177   1, /* OMP_CLAUSE_PRIVATE  */
 178   1, /* OMP_CLAUSE_SHARED  */
 179   1, /* OMP_CLAUSE_FIRSTPRIVATE  */
 180   1, /* OMP_CLAUSE_LASTPRIVATE  */
 181   4, /* OMP_CLAUSE_REDUCTION  */
 182   1, /* OMP_CLAUSE_COPYIN  */
 183   1, /* OMP_CLAUSE_COPYPRIVATE  */
 184   1, /* OMP_CLAUSE_IF  */
 185   1, /* OMP_CLAUSE_NUM_THREADS  */
 186   1, /* OMP_CLAUSE_SCHEDULE  */
 187   0, /* OMP_CLAUSE_NOWAIT  */
 188   0, /* OMP_CLAUSE_ORDERED  */
 189   0  /* OMP_CLAUSE_DEFAULT  */
 190 };
 191
 192 const char * const omp_clause_code_name[] =
 193 {
 194   "error_clause",
 195   "private",
 196   "shared",
 197   "firstprivate",
 198   "lastprivate",
 199   "reduction",
 200   "copyin",
 201   "copyprivate",
 202   "if",
 203   "num_threads",
 204   "schedule",
 205   "nowait",
 206   "ordered",
 207   "default"
 208 };
 209 \f
 210 /* Init tree.c.  */
 211
 212 void
 213 init_ttree (void)
 214 {
 215   /* Initialize the hash table of types.  */
 216   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 217                                      type_hash_eq, 0);
 218
 219   debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 220                                          tree_map_eq, 0);
 221
 222   value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 223                                          tree_map_eq, 0);
 224   init_priority_for_decl = htab_create_ggc (512, tree_priority_map_hash,
 225                                             tree_priority_map_eq, 0);
 226   restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
 227                                             tree_map_eq, 0);
 228
 229   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
 230                                         int_cst_hash_eq, NULL);
 231
 232   int_cst_node = make_node (INTEGER_CST);
 233
 234   tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
 235   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
 236   tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
 237
 238
 239   tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
 240   tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
 241   tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
 242   tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
 243   tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
 244   tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
 245   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
 246   tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
 247   tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
 248
 249
 250   tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
 251   tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
 252   tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
 253   tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
 254   tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
 255   tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
 256
 257   tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
 258   tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
 259   tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
 260   tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
 261   tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
 262   tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
 263   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
 264   tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
 265   tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
 266   tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
 267   tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 268   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 269   tree_contains_struct[MEMORY_PARTITION_TAG][TS_DECL_MINIMAL] = 1;
 270
 271   tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
 272   tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 273   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 274   tree_contains_struct[MEMORY_PARTITION_TAG][TS_MEMORY_TAG] = 1;
 275
 276   tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
 277   tree_contains_struct[MEMORY_PARTITION_TAG][TS_MEMORY_PARTITION_TAG] = 1;
 278
 279   tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
 280   tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
 281   tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
 282   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
 283
 284   tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
 285   tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
 286   tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
 287   tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
 288   tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
 289   tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
 290   tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
 291   tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
 292
 293   lang_hooks.init_ts ();
 294 }
 295
 296 \f
 297 /* The name of the object as the assembler will see it (but before any
 298    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 299    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 300 tree
 301 decl_assembler_name (tree decl)
 302 {
 303   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 304     lang_hooks.set_decl_assembler_name (decl);
 305   return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
 306 }
 307
 308 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL.  */
 309
 310 bool
 311 decl_assembler_name_equal (tree decl, tree asmname)
 312 {
 313   tree decl_asmname = DECL_ASSEMBLER_NAME (decl);
 314
 315   if (decl_asmname == asmname)
 316     return true;
 317
 318   /* If the target assembler name was set by the user, things are trickier.
 319      We have a leading '*' to begin with.  After that, it's arguable what
 320      is the correct thing to do with -fleading-underscore.  Arguably, we've
 321      historically been doing the wrong thing in assemble_alias by always
 322      printing the leading underscore.  Since we're not changing that, make
 323      sure user_label_prefix follows the '*' before matching.  */
 324   if (IDENTIFIER_POINTER (decl_asmname)[0] == '*')
 325     {
 326       const char *decl_str = IDENTIFIER_POINTER (decl_asmname) + 1;
 327       size_t ulp_len = strlen (user_label_prefix);
 328
 329       if (ulp_len == 0)
 330         ;
 331       else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
 332         decl_str += ulp_len;
 333       else
 334         return false;
 335
 336       return strcmp (decl_str, IDENTIFIER_POINTER (asmname)) == 0;
 337     }
 338
 339   return false;
 340 }
 341
 342 /* Compute the number of bytes occupied by a tree with code CODE.
 343    This function cannot be used for nodes that have variable sizes,
 344    including TREE_VEC, PHI_NODE, STRING_CST, and CALL_EXPR.  */
 345 size_t
 346 tree_code_size (enum tree_code code)
 347 {
 348   switch (TREE_CODE_CLASS (code))
 349     {
 350     case tcc_declaration:  /* A decl node */
 351       {
 352         switch (code)
 353           {
 354           case FIELD_DECL:
 355             return sizeof (struct tree_field_decl);
 356           case PARM_DECL:
 357             return sizeof (struct tree_parm_decl);
 358           case VAR_DECL:
 359             return sizeof (struct tree_var_decl);
 360           case LABEL_DECL:
 361             return sizeof (struct tree_label_decl);
 362           case RESULT_DECL:
 363             return sizeof (struct tree_result_decl);
 364           case CONST_DECL:
 365             return sizeof (struct tree_const_decl);
 366           case TYPE_DECL:
 367             return sizeof (struct tree_type_decl);
 368           case FUNCTION_DECL:
 369             return sizeof (struct tree_function_decl);
 370           case NAME_MEMORY_TAG:
 371           case SYMBOL_MEMORY_TAG:
 372             return sizeof (struct tree_memory_tag);
 373           case STRUCT_FIELD_TAG:
 374             return sizeof (struct tree_struct_field_tag);
 375           case MEMORY_PARTITION_TAG:
 376             return sizeof (struct tree_memory_partition_tag);
 377           default:
 378             return sizeof (struct tree_decl_non_common);
 379           }
 380       }
 381
 382     case tcc_type:  /* a type node */
 383       return sizeof (struct tree_type);
 384
 385     case tcc_reference:   /* a reference */
 386     case tcc_expression:  /* an expression */
 387     case tcc_statement:   /* an expression with side effects */
 388     case tcc_comparison:  /* a comparison expression */
 389     case tcc_unary:       /* a unary arithmetic expression */
 390     case tcc_binary:      /* a binary arithmetic expression */
 391       return (sizeof (struct tree_exp)
 392               + (TREE_CODE_LENGTH (code) - 1) * sizeof (tree));
 393
 394     case tcc_gimple_stmt:
 395       return (sizeof (struct gimple_stmt)
 396               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
 397
 398     case tcc_constant:  /* a constant */
 399       switch (code)
 400         {
 401         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 402         case REAL_CST:          return sizeof (struct tree_real_cst);
 403         case FIXED_CST:         return sizeof (struct tree_fixed_cst);
 404         case COMPLEX_CST:       return sizeof (struct tree_complex);
 405         case VECTOR_CST:        return sizeof (struct tree_vector);
 406         case STRING_CST:        gcc_unreachable ();
 407         default:
 408           return lang_hooks.tree_size (code);
 409         }
 410
 411     case tcc_exceptional:  /* something random, like an identifier.  */
 412       switch (code)
 413         {
 414         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 415         case TREE_LIST:         return sizeof (struct tree_list);
 416
 417         case ERROR_MARK:
 418         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 419
 420         case TREE_VEC:
 421         case OMP_CLAUSE:
 422         case PHI_NODE:          gcc_unreachable ();
 423
 424         case SSA_NAME:          return sizeof (struct tree_ssa_name);
 425
 426         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
 427         case BLOCK:             return sizeof (struct tree_block);
 428         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
 429         case CONSTRUCTOR:       return sizeof (struct tree_constructor);
 430
 431         default:
 432           return lang_hooks.tree_size (code);
 433         }
 434
 435     default:
 436       gcc_unreachable ();
 437     }
 438 }
 439
 440 /* Compute the number of bytes occupied by NODE.  This routine only
 441    looks at TREE_CODE, except for those nodes that have variable sizes.  */
 442 size_t
 443 tree_size (const_tree node)
 444 {
 445   const enum tree_code code = TREE_CODE (node);
 446   switch (code)
 447     {
 448     case PHI_NODE:
 449       return (sizeof (struct tree_phi_node)
 450               + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
 451
 452     case TREE_BINFO:
 453       return (offsetof (struct tree_binfo, base_binfos)
 454               + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
 455
 456     case TREE_VEC:
 457       return (sizeof (struct tree_vec)
 458               + (TREE_VEC_LENGTH (node) - 1) * sizeof (tree));
 459
 460     case STRING_CST:
 461       return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
 462
 463     case OMP_CLAUSE:
 464       return (sizeof (struct tree_omp_clause)
 465               + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
 466                 * sizeof (tree));
 467
 468     default:
 469       if (TREE_CODE_CLASS (code) == tcc_vl_exp)
 470         return (sizeof (struct tree_exp)
 471                 + (VL_EXP_OPERAND_LENGTH (node) - 1) * sizeof (tree));
 472       else
 473         return tree_code_size (code);
 474     }
 475 }
 476
 477 /* Return a newly allocated node of code CODE.  For decl and type
 478    nodes, some other fields are initialized.  The rest of the node is
 479    initialized to zero.  This function cannot be used for PHI_NODE,
 480    TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
 481    tree_code_size.
 482
 483    Achoo!  I got a code in the node.  */
 484
 485 tree
 486 make_node_stat (enum tree_code code MEM_STAT_DECL)
 487 {
 488   tree t;
 489   enum tree_code_class type = TREE_CODE_CLASS (code);
 490   size_t length = tree_code_size (code);
 491 #ifdef GATHER_STATISTICS
 492   tree_node_kind kind;
 493
 494   switch (type)
 495     {
 496     case tcc_declaration:  /* A decl node */
 497       kind = d_kind;
 498       break;
 499
 500     case tcc_type:  /* a type node */
 501       kind = t_kind;
 502       break;
 503
 504     case tcc_statement:  /* an expression with side effects */
 505       kind = s_kind;
 506       break;
 507
 508     case tcc_reference:  /* a reference */
 509       kind = r_kind;
 510       break;
 511
 512     case tcc_expression:  /* an expression */
 513     case tcc_comparison:  /* a comparison expression */
 514     case tcc_unary:  /* a unary arithmetic expression */
 515     case tcc_binary:  /* a binary arithmetic expression */
 516       kind = e_kind;
 517       break;
 518
 519     case tcc_constant:  /* a constant */
 520       kind = c_kind;
 521       break;
 522
 523     case tcc_gimple_stmt:
 524       kind = gimple_stmt_kind;
 525       break;
 526
 527     case tcc_exceptional:  /* something random, like an identifier.  */
 528       switch (code)
 529         {
 530         case IDENTIFIER_NODE:
 531           kind = id_kind;
 532           break;
 533
 534         case TREE_VEC:
 535           kind = vec_kind;
 536           break;
 537
 538         case TREE_BINFO:
 539           kind = binfo_kind;
 540           break;
 541
 542         case PHI_NODE:
 543           kind = phi_kind;
 544           break;
 545
 546         case SSA_NAME:
 547           kind = ssa_name_kind;
 548           break;
 549
 550         case BLOCK:
 551           kind = b_kind;
 552           break;
 553
 554         case CONSTRUCTOR:
 555           kind = constr_kind;
 556           break;
 557
 558         default:
 559           kind = x_kind;
 560           break;
 561         }
 562       break;
 563
 564     default:
 565       gcc_unreachable ();
 566     }
 567
 568   tree_node_counts[(int) kind]++;
 569   tree_node_sizes[(int) kind] += length;
 570 #endif
 571
 572   if (code == IDENTIFIER_NODE)
 573     t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
 574   else
 575     t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 576
 577   memset (t, 0, length);
 578
 579   TREE_SET_CODE (t, code);
 580
 581   switch (type)
 582     {
 583     case tcc_statement:
 584       TREE_SIDE_EFFECTS (t) = 1;
 585       break;
 586
 587     case tcc_declaration:
 588       if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
 589         DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 590       if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
 591         {
 592           if (code == FUNCTION_DECL)
 593             {
 594               DECL_ALIGN (t) = FUNCTION_BOUNDARY;
 595               DECL_MODE (t) = FUNCTION_MODE;
 596             }
 597           else
 598             DECL_ALIGN (t) = 1;
 599           /* We have not yet computed the alias set for this declaration.  */
 600           DECL_POINTER_ALIAS_SET (t) = -1;
 601         }
 602       DECL_SOURCE_LOCATION (t) = input_location;
 603       DECL_UID (t) = next_decl_uid++;
 604
 605       break;
 606
 607     case tcc_type:
 608       TYPE_UID (t) = next_type_uid++;
 609       TYPE_ALIGN (t) = BITS_PER_UNIT;
 610       TYPE_USER_ALIGN (t) = 0;
 611       TYPE_MAIN_VARIANT (t) = t;
 612       TYPE_CANONICAL (t) = t;
 613
 614       /* Default to no attributes for type, but let target change that.  */
 615       TYPE_ATTRIBUTES (t) = NULL_TREE;
 616       targetm.set_default_type_attributes (t);
 617
 618       /* We have not yet computed the alias set for this type.  */
 619       TYPE_ALIAS_SET (t) = -1;
 620       break;
 621
 622     case tcc_constant:
 623       TREE_CONSTANT (t) = 1;
 624       TREE_INVARIANT (t) = 1;
 625       break;
 626
 627     case tcc_expression:
 628       switch (code)
 629         {
 630         case INIT_EXPR:
 631         case MODIFY_EXPR:
 632         case VA_ARG_EXPR:
 633         case PREDECREMENT_EXPR:
 634         case PREINCREMENT_EXPR:
 635         case POSTDECREMENT_EXPR:
 636         case POSTINCREMENT_EXPR:
 637           /* All of these have side-effects, no matter what their
 638              operands are.  */
 639           TREE_SIDE_EFFECTS (t) = 1;
 640           break;
 641
 642         default:
 643           break;
 644         }
 645       break;
 646
 647     case tcc_gimple_stmt:
 648       switch (code)
 649         {
 650       case GIMPLE_MODIFY_STMT:
 651         TREE_SIDE_EFFECTS (t) = 1;
 652         break;
 653
 654       default:
 655         break;
 656         }
 657
 658     default:
 659       /* Other classes need no special treatment.  */
 660       break;
 661     }
 662
 663   return t;
 664 }
 665 \f
 666 /* Return a new node with the same contents as NODE except that its
 667    TREE_CHAIN is zero and it has a fresh uid.  */
 668
 669 tree
 670 copy_node_stat (tree node MEM_STAT_DECL)
 671 {
 672   tree t;
 673   enum tree_code code = TREE_CODE (node);
 674   size_t length;
 675
 676   gcc_assert (code != STATEMENT_LIST);
 677
 678   length = tree_size (node);
 679   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 680   memcpy (t, node, length);
 681
 682   if (!GIMPLE_TUPLE_P (node))
 683     TREE_CHAIN (t) = 0;
 684   TREE_ASM_WRITTEN (t) = 0;
 685   TREE_VISITED (t) = 0;
 686   t->base.ann = 0;
 687
 688   if (TREE_CODE_CLASS (code) == tcc_declaration)
 689     {
 690       DECL_UID (t) = next_decl_uid++;
 691       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
 692           && DECL_HAS_VALUE_EXPR_P (node))
 693         {
 694           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
 695           DECL_HAS_VALUE_EXPR_P (t) = 1;
 696         }
 697       if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
 698         {
 699           SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 700           DECL_HAS_INIT_PRIORITY_P (t) = 1;
 701         }
 702       if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
 703         {
 704           SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
 705           DECL_BASED_ON_RESTRICT_P (t) = 1;
 706         }
 707     }
 708   else if (TREE_CODE_CLASS (code) == tcc_type)
 709     {
 710       TYPE_UID (t) = next_type_uid++;
 711       /* The following is so that the debug code for
 712          the copy is different from the original type.
 713          The two statements usually duplicate each other
 714          (because they clear fields of the same union),
 715          but the optimizer should catch that.  */
 716       TYPE_SYMTAB_POINTER (t) = 0;
 717       TYPE_SYMTAB_ADDRESS (t) = 0;
 718
 719       /* Do not copy the values cache.  */
 720       if (TYPE_CACHED_VALUES_P(t))
 721         {
 722           TYPE_CACHED_VALUES_P (t) = 0;
 723           TYPE_CACHED_VALUES (t) = NULL_TREE;
 724         }
 725     }
 726
 727   return t;
 728 }
 729
 730 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 731    For example, this can copy a list made of TREE_LIST nodes.  */
 732
 733 tree
 734 copy_list (tree list)
 735 {
 736   tree head;
 737   tree prev, next;
 738
 739   if (list == 0)
 740     return 0;
 741
 742   head = prev = copy_node (list);
 743   next = TREE_CHAIN (list);
 744   while (next)
 745     {
 746       TREE_CHAIN (prev) = copy_node (next);
 747       prev = TREE_CHAIN (prev);
 748       next = TREE_CHAIN (next);
 749     }
 750   return head;
 751 }
 752
 753 \f
 754 /* Create an INT_CST node with a LOW value sign extended.  */
 755
 756 tree
 757 build_int_cst (tree type, HOST_WIDE_INT low)
 758 {
 759   /* Support legacy code.  */
 760   if (!type)
 761     type = integer_type_node;
 762
 763   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
 764 }
 765
 766 /* Create an INT_CST node with a LOW value zero extended.  */
 767
 768 tree
 769 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
 770 {
 771   return build_int_cst_wide (type, low, 0);
 772 }
 773
 774 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
 775    if it is negative.  This function is similar to build_int_cst, but
 776    the extra bits outside of the type precision are cleared.  Constants
 777    with these extra bits may confuse the fold so that it detects overflows
 778    even in cases when they do not occur, and in general should be avoided.
 779    We cannot however make this a default behavior of build_int_cst without
 780    more intrusive changes, since there are parts of gcc that rely on the extra
 781    precision of the integer constants.  */
 782
 783 tree
 784 build_int_cst_type (tree type, HOST_WIDE_INT low)
 785 {
 786   unsigned HOST_WIDE_INT low1;
 787   HOST_WIDE_INT hi;
 788
 789   gcc_assert (type);
 790
 791   fit_double_type (low, low < 0 ? -1 : 0, &low1, &hi, type);
 792
 793   return build_int_cst_wide (type, low1, hi);
 794 }
 795
 796 /* Create an INT_CST node of TYPE and value HI:LOW.  The value is truncated
 797    and sign extended according to the value range of TYPE.  */
 798
 799 tree
 800 build_int_cst_wide_type (tree type,
 801                          unsigned HOST_WIDE_INT low, HOST_WIDE_INT high)
 802 {
 803   fit_double_type (low, high, &low, &high, type);
 804   return build_int_cst_wide (type, low, high);
 805 }
 806
 807 /* These are the hash table functions for the hash table of INTEGER_CST
 808    nodes of a sizetype.  */
 809
 810 /* Return the hash code code X, an INTEGER_CST.  */
 811
 812 static hashval_t
 813 int_cst_hash_hash (const void *x)
 814 {
 815   const_tree const t = (const_tree) x;
 816
 817   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
 818           ^ htab_hash_pointer (TREE_TYPE (t)));
 819 }
 820
 821 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
 822    is the same as that given by *Y, which is the same.  */
 823
 824 static int
 825 int_cst_hash_eq (const void *x, const void *y)
 826 {
 827   const_tree const xt = (const_tree) x;
 828   const_tree const yt = (const_tree) y;
 829
 830   return (TREE_TYPE (xt) == TREE_TYPE (yt)
 831           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
 832           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
 833 }
 834
 835 /* Create an INT_CST node of TYPE and value HI:LOW.
 836    The returned node is always shared.  For small integers we use a
 837    per-type vector cache, for larger ones we use a single hash table.  */
 838
 839 tree
 840 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 841 {
 842   tree t;
 843   int ix = -1;
 844   int limit = 0;
 845
 846   gcc_assert (type);
 847
 848   switch (TREE_CODE (type))
 849     {
 850     case POINTER_TYPE:
 851     case REFERENCE_TYPE:
 852       /* Cache NULL pointer.  */
 853       if (!hi && !low)
 854         {
 855           limit = 1;
 856           ix = 0;
 857         }
 858       break;
 859
 860     case BOOLEAN_TYPE:
 861       /* Cache false or true.  */
 862       limit = 2;
 863       if (!hi && low < 2)
 864         ix = low;
 865       break;
 866
 867     case INTEGER_TYPE:
 868     case OFFSET_TYPE:
 869       if (TYPE_UNSIGNED (type))
 870         {
 871           /* Cache 0..N */
 872           limit = INTEGER_SHARE_LIMIT;
 873           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 874             ix = low;
 875         }
 876       else
 877         {
 878           /* Cache -1..N */
 879           limit = INTEGER_SHARE_LIMIT + 1;
 880           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 881             ix = low + 1;
 882           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
 883             ix = 0;
 884         }
 885       break;
 886
 887     case ENUMERAL_TYPE:
 888       break;
 889
 890     default:
 891       gcc_unreachable ();
 892     }
 893
 894   if (ix >= 0)
 895     {
 896       /* Look for it in the type's vector of small shared ints.  */
 897       if (!TYPE_CACHED_VALUES_P (type))
 898         {
 899           TYPE_CACHED_VALUES_P (type) = 1;
 900           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
 901         }
 902
 903       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
 904       if (t)
 905         {
 906           /* Make sure no one is clobbering the shared constant.  */
 907           gcc_assert (TREE_TYPE (t) == type);
 908           gcc_assert (TREE_INT_CST_LOW (t) == low);
 909           gcc_assert (TREE_INT_CST_HIGH (t) == hi);
 910         }
 911       else
 912         {
 913           /* Create a new shared int.  */
 914           t = make_node (INTEGER_CST);
 915
 916           TREE_INT_CST_LOW (t) = low;
 917           TREE_INT_CST_HIGH (t) = hi;
 918           TREE_TYPE (t) = type;
 919
 920           TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
 921         }
 922     }
 923   else
 924     {
 925       /* Use the cache of larger shared ints.  */
 926       void **slot;
 927
 928       TREE_INT_CST_LOW (int_cst_node) = low;
 929       TREE_INT_CST_HIGH (int_cst_node) = hi;
 930       TREE_TYPE (int_cst_node) = type;
 931
 932       slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
 933       t = *slot;
 934       if (!t)
 935         {
 936           /* Insert this one into the hash table.  */
 937           t = int_cst_node;
 938           *slot = t;
 939           /* Make a new node for next time round.  */
 940           int_cst_node = make_node (INTEGER_CST);
 941         }
 942     }
 943
 944   return t;
 945 }
 946
 947 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
 948    and the rest are zeros.  */
 949
 950 tree
 951 build_low_bits_mask (tree type, unsigned bits)
 952 {
 953   unsigned HOST_WIDE_INT low;
 954   HOST_WIDE_INT high;
 955   unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
 956
 957   gcc_assert (bits <= TYPE_PRECISION (type));
 958
 959   if (bits == TYPE_PRECISION (type)
 960       && !TYPE_UNSIGNED (type))
 961     {
 962       /* Sign extended all-ones mask.  */
 963       low = all_ones;
 964       high = -1;
 965     }
 966   else if (bits <= HOST_BITS_PER_WIDE_INT)
 967     {
 968       low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 969       high = 0;
 970     }
 971   else
 972     {
 973       bits -= HOST_BITS_PER_WIDE_INT;
 974       low = all_ones;
 975       high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 976     }
 977
 978   return build_int_cst_wide (type, low, high);
 979 }
 980
 981 /* Checks that X is integer constant that can be expressed in (unsigned)
 982    HOST_WIDE_INT without loss of precision.  */
 983
 984 bool
 985 cst_and_fits_in_hwi (const_tree x)
 986 {
 987   if (TREE_CODE (x) != INTEGER_CST)
 988     return false;
 989
 990   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
 991     return false;
 992
 993   return (TREE_INT_CST_HIGH (x) == 0
 994           || TREE_INT_CST_HIGH (x) == -1);
 995 }
 996
 997 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 998    are in a list pointed to by VALS.  */
 999
1000 tree
1001 build_vector (tree type, tree vals)
1002 {
1003   tree v = make_node (VECTOR_CST);
1004   int over = 0;
1005   tree link;
1006
1007   TREE_VECTOR_CST_ELTS (v) = vals;
1008   TREE_TYPE (v) = type;
1009
1010   /* Iterate through elements and check for overflow.  */
1011   for (link = vals; link; link = TREE_CHAIN (link))
1012     {
1013       tree value = TREE_VALUE (link);
1014
1015       /* Don't crash if we get an address constant.  */
1016       if (!CONSTANT_CLASS_P (value))
1017         continue;
1018
1019       over |= TREE_OVERFLOW (value);
1020     }
1021
1022   TREE_OVERFLOW (v) = over;
1023   return v;
1024 }
1025
1026 /* Return a new VECTOR_CST node whose type is TYPE and whose values
1027    are extracted from V, a vector of CONSTRUCTOR_ELT.  */
1028
1029 tree
1030 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
1031 {
1032   tree list = NULL_TREE;
1033   unsigned HOST_WIDE_INT idx;
1034   tree value;
1035
1036   FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
1037     list = tree_cons (NULL_TREE, value, list);
1038   return build_vector (type, nreverse (list));
1039 }
1040
1041 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1042    are in the VEC pointed to by VALS.  */
1043 tree
1044 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
1045 {
1046   tree c = make_node (CONSTRUCTOR);
1047   TREE_TYPE (c) = type;
1048   CONSTRUCTOR_ELTS (c) = vals;
1049   return c;
1050 }
1051
1052 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1053    INDEX and VALUE.  */
1054 tree
1055 build_constructor_single (tree type, tree index, tree value)
1056 {
1057   VEC(constructor_elt,gc) *v;
1058   constructor_elt *elt;
1059   tree t;
1060
1061   v = VEC_alloc (constructor_elt, gc, 1);
1062   elt = VEC_quick_push (constructor_elt, v, NULL);
1063   elt->index = index;
1064   elt->value = value;
1065
1066   t = build_constructor (type, v);
1067   TREE_CONSTANT (t) = TREE_CONSTANT (value);
1068   return t;
1069 }
1070
1071
1072 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1073    are in a list pointed to by VALS.  */
1074 tree
1075 build_constructor_from_list (tree type, tree vals)
1076 {
1077   tree t, val;
1078   VEC(constructor_elt,gc) *v = NULL;
1079   bool constant_p = true;
1080
1081   if (vals)
1082     {
1083       v = VEC_alloc (constructor_elt, gc, list_length (vals));
1084       for (t = vals; t; t = TREE_CHAIN (t))
1085         {
1086           constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1087           val = TREE_VALUE (t);
1088           elt->index = TREE_PURPOSE (t);
1089           elt->value = val;
1090           if (!TREE_CONSTANT (val))
1091             constant_p = false;
1092         }
1093     }
1094
1095   t = build_constructor (type, v);
1096   TREE_CONSTANT (t) = constant_p;
1097   return t;
1098 }
1099
1100 /* Return a new FIXED_CST node whose type is TYPE and value is F.  */
1101
1102 tree
1103 build_fixed (tree type, FIXED_VALUE_TYPE f)
1104 {
1105   tree v;
1106   FIXED_VALUE_TYPE *fp;
1107
1108   v = make_node (FIXED_CST);
1109   fp = ggc_alloc (sizeof (FIXED_VALUE_TYPE));
1110   memcpy (fp, &f, sizeof (FIXED_VALUE_TYPE));
1111
1112   TREE_TYPE (v) = type;
1113   TREE_FIXED_CST_PTR (v) = fp;
1114   return v;
1115 }
1116
1117 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
1118
1119 tree
1120 build_real (tree type, REAL_VALUE_TYPE d)
1121 {
1122   tree v;
1123   REAL_VALUE_TYPE *dp;
1124   int overflow = 0;
1125
1126   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1127      Consider doing it via real_convert now.  */
1128
1129   v = make_node (REAL_CST);
1130   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1131   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1132
1133   TREE_TYPE (v) = type;
1134   TREE_REAL_CST_PTR (v) = dp;
1135   TREE_OVERFLOW (v) = overflow;
1136   return v;
1137 }
1138
1139 /* Return a new REAL_CST node whose type is TYPE
1140    and whose value is the integer value of the INTEGER_CST node I.  */
1141
1142 REAL_VALUE_TYPE
1143 real_value_from_int_cst (const_tree type, const_tree i)
1144 {
1145   REAL_VALUE_TYPE d;
1146
1147   /* Clear all bits of the real value type so that we can later do
1148      bitwise comparisons to see if two values are the same.  */
1149   memset (&d, 0, sizeof d);
1150
1151   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1152                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1153                      TYPE_UNSIGNED (TREE_TYPE (i)));
1154   return d;
1155 }
1156
1157 /* Given a tree representing an integer constant I, return a tree
1158    representing the same value as a floating-point constant of type TYPE.  */
1159
1160 tree
1161 build_real_from_int_cst (tree type, const_tree i)
1162 {
1163   tree v;
1164   int overflow = TREE_OVERFLOW (i);
1165
1166   v = build_real (type, real_value_from_int_cst (type, i));
1167
1168   TREE_OVERFLOW (v) |= overflow;
1169   return v;
1170 }
1171
1172 /* Return a newly constructed STRING_CST node whose value is
1173    the LEN characters at STR.
1174    The TREE_TYPE is not initialized.  */
1175
1176 tree
1177 build_string (int len, const char *str)
1178 {
1179   tree s;
1180   size_t length;
1181
1182   /* Do not waste bytes provided by padding of struct tree_string.  */
1183   length = len + offsetof (struct tree_string, str) + 1;
1184
1185 #ifdef GATHER_STATISTICS
1186   tree_node_counts[(int) c_kind]++;
1187   tree_node_sizes[(int) c_kind] += length;
1188 #endif
1189
1190   s = ggc_alloc_tree (length);
1191
1192   memset (s, 0, sizeof (struct tree_common));
1193   TREE_SET_CODE (s, STRING_CST);
1194   TREE_CONSTANT (s) = 1;
1195   TREE_INVARIANT (s) = 1;
1196   TREE_STRING_LENGTH (s) = len;
1197   memcpy (s->string.str, str, len);
1198   s->string.str[len] = '\0';
1199
1200   return s;
1201 }
1202
1203 /* Return a newly constructed COMPLEX_CST node whose value is
1204    specified by the real and imaginary parts REAL and IMAG.
1205    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
1206    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
1207
1208 tree
1209 build_complex (tree type, tree real, tree imag)
1210 {
1211   tree t = make_node (COMPLEX_CST);
1212
1213   TREE_REALPART (t) = real;
1214   TREE_IMAGPART (t) = imag;
1215   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1216   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1217   return t;
1218 }
1219
1220 /* Return a constant of arithmetic type TYPE which is the
1221    multiplicative identity of the set TYPE.  */
1222
1223 tree
1224 build_one_cst (tree type)
1225 {
1226   switch (TREE_CODE (type))
1227     {
1228     case INTEGER_TYPE: case ENUMERAL_TYPE: case BOOLEAN_TYPE:
1229     case POINTER_TYPE: case REFERENCE_TYPE:
1230     case OFFSET_TYPE:
1231       return build_int_cst (type, 1);
1232
1233     case REAL_TYPE:
1234       return build_real (type, dconst1);
1235
1236     case FIXED_POINT_TYPE:
1237       /* We can only generate 1 for accum types.  */
1238       gcc_assert (ALL_SCALAR_ACCUM_MODE_P (TYPE_MODE (type)));
1239       return build_fixed (type, FCONST1(TYPE_MODE (type)));
1240
1241     case VECTOR_TYPE:
1242       {
1243         tree scalar, cst;
1244         int i;
1245
1246         scalar = build_one_cst (TREE_TYPE (type));
1247
1248         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
1249         cst = NULL_TREE;
1250         for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; )
1251           cst = tree_cons (NULL_TREE, scalar, cst);
1252
1253         return build_vector (type, cst);
1254       }
1255
1256     case COMPLEX_TYPE:
1257       return build_complex (type,
1258                             build_one_cst (TREE_TYPE (type)),
1259                             fold_convert (TREE_TYPE (type), integer_zero_node));
1260
1261     default:
1262       gcc_unreachable ();
1263     }
1264 }
1265
1266 /* Build a BINFO with LEN language slots.  */
1267
1268 tree
1269 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1270 {
1271   tree t;
1272   size_t length = (offsetof (struct tree_binfo, base_binfos)
1273                    + VEC_embedded_size (tree, base_binfos));
1274
1275 #ifdef GATHER_STATISTICS
1276   tree_node_counts[(int) binfo_kind]++;
1277   tree_node_sizes[(int) binfo_kind] += length;
1278 #endif
1279
1280   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1281
1282   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1283
1284   TREE_SET_CODE (t, TREE_BINFO);
1285
1286   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1287
1288   return t;
1289 }
1290
1291
1292 /* Build a newly constructed TREE_VEC node of length LEN.  */
1293
1294 tree
1295 make_tree_vec_stat (int len MEM_STAT_DECL)
1296 {
1297   tree t;
1298   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1299
1300 #ifdef GATHER_STATISTICS
1301   tree_node_counts[(int) vec_kind]++;
1302   tree_node_sizes[(int) vec_kind] += length;
1303 #endif
1304
1305   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1306
1307   memset (t, 0, length);
1308
1309   TREE_SET_CODE (t, TREE_VEC);
1310   TREE_VEC_LENGTH (t) = len;
1311
1312   return t;
1313 }
1314 \f
1315 /* Return 1 if EXPR is the integer constant zero or a complex constant
1316    of zero.  */
1317
1318 int
1319 integer_zerop (const_tree expr)
1320 {
1321   STRIP_NOPS (expr);
1322
1323   return ((TREE_CODE (expr) == INTEGER_CST
1324            && TREE_INT_CST_LOW (expr) == 0
1325            && TREE_INT_CST_HIGH (expr) == 0)
1326           || (TREE_CODE (expr) == COMPLEX_CST
1327               && integer_zerop (TREE_REALPART (expr))
1328               && integer_zerop (TREE_IMAGPART (expr))));
1329 }
1330
1331 /* Return 1 if EXPR is the integer constant one or the corresponding
1332    complex constant.  */
1333
1334 int
1335 integer_onep (const_tree expr)
1336 {
1337   STRIP_NOPS (expr);
1338
1339   return ((TREE_CODE (expr) == INTEGER_CST
1340            && TREE_INT_CST_LOW (expr) == 1
1341            && TREE_INT_CST_HIGH (expr) == 0)
1342           || (TREE_CODE (expr) == COMPLEX_CST
1343               && integer_onep (TREE_REALPART (expr))
1344               && integer_zerop (TREE_IMAGPART (expr))));
1345 }
1346
1347 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1348    it contains.  Likewise for the corresponding complex constant.  */
1349
1350 int
1351 integer_all_onesp (const_tree expr)
1352 {
1353   int prec;
1354   int uns;
1355
1356   STRIP_NOPS (expr);
1357
1358   if (TREE_CODE (expr) == COMPLEX_CST
1359       && integer_all_onesp (TREE_REALPART (expr))
1360       && integer_zerop (TREE_IMAGPART (expr)))
1361     return 1;
1362
1363   else if (TREE_CODE (expr) != INTEGER_CST)
1364     return 0;
1365
1366   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1367   if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1368       && TREE_INT_CST_HIGH (expr) == -1)
1369     return 1;
1370   if (!uns)
1371     return 0;
1372
1373   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1374      actual bits, not the (arbitrary) range of the type.  */
1375   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1376   if (prec >= HOST_BITS_PER_WIDE_INT)
1377     {
1378       HOST_WIDE_INT high_value;
1379       int shift_amount;
1380
1381       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1382
1383       /* Can not handle precisions greater than twice the host int size.  */
1384       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1385       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1386         /* Shifting by the host word size is undefined according to the ANSI
1387            standard, so we must handle this as a special case.  */
1388         high_value = -1;
1389       else
1390         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1391
1392       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1393               && TREE_INT_CST_HIGH (expr) == high_value);
1394     }
1395   else
1396     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1397 }
1398
1399 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1400    one bit on).  */
1401
1402 int
1403 integer_pow2p (const_tree expr)
1404 {
1405   int prec;
1406   HOST_WIDE_INT high, low;
1407
1408   STRIP_NOPS (expr);
1409
1410   if (TREE_CODE (expr) == COMPLEX_CST
1411       && integer_pow2p (TREE_REALPART (expr))
1412       && integer_zerop (TREE_IMAGPART (expr)))
1413     return 1;
1414
1415   if (TREE_CODE (expr) != INTEGER_CST)
1416     return 0;
1417
1418   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1419           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1420   high = TREE_INT_CST_HIGH (expr);
1421   low = TREE_INT_CST_LOW (expr);
1422
1423   /* First clear all bits that are beyond the type's precision in case
1424      we've been sign extended.  */
1425
1426   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1427     ;
1428   else if (prec > HOST_BITS_PER_WIDE_INT)
1429     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1430   else
1431     {
1432       high = 0;
1433       if (prec < HOST_BITS_PER_WIDE_INT)
1434         low &= ~((HOST_WIDE_INT) (-1) << prec);
1435     }
1436
1437   if (high == 0 && low == 0)
1438     return 0;
1439
1440   return ((high == 0 && (low & (low - 1)) == 0)
1441           || (low == 0 && (high & (high - 1)) == 0));
1442 }
1443
1444 /* Return 1 if EXPR is an integer constant other than zero or a
1445    complex constant other than zero.  */
1446
1447 int
1448 integer_nonzerop (const_tree expr)
1449 {
1450   STRIP_NOPS (expr);
1451
1452   return ((TREE_CODE (expr) == INTEGER_CST
1453            && (TREE_INT_CST_LOW (expr) != 0
1454                || TREE_INT_CST_HIGH (expr) != 0))
1455           || (TREE_CODE (expr) == COMPLEX_CST
1456               && (integer_nonzerop (TREE_REALPART (expr))
1457                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1458 }
1459
1460 /* Return 1 if EXPR is the fixed-point constant zero.  */
1461
1462 int
1463 fixed_zerop (const_tree expr)
1464 {
1465   return (TREE_CODE (expr) == FIXED_CST
1466           && double_int_zero_p (TREE_FIXED_CST (expr).data));
1467 }
1468
1469 /* Return the power of two represented by a tree node known to be a
1470    power of two.  */
1471
1472 int
1473 tree_log2 (const_tree expr)
1474 {
1475   int prec;
1476   HOST_WIDE_INT high, low;
1477
1478   STRIP_NOPS (expr);
1479
1480   if (TREE_CODE (expr) == COMPLEX_CST)
1481     return tree_log2 (TREE_REALPART (expr));
1482
1483   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1484           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1485
1486   high = TREE_INT_CST_HIGH (expr);
1487   low = TREE_INT_CST_LOW (expr);
1488
1489   /* First clear all bits that are beyond the type's precision in case
1490      we've been sign extended.  */
1491
1492   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1493     ;
1494   else if (prec > HOST_BITS_PER_WIDE_INT)
1495     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1496   else
1497     {
1498       high = 0;
1499       if (prec < HOST_BITS_PER_WIDE_INT)
1500         low &= ~((HOST_WIDE_INT) (-1) << prec);
1501     }
1502
1503   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1504           : exact_log2 (low));
1505 }
1506
1507 /* Similar, but return the largest integer Y such that 2 ** Y is less
1508    than or equal to EXPR.  */
1509
1510 int
1511 tree_floor_log2 (const_tree expr)
1512 {
1513   int prec;
1514   HOST_WIDE_INT high, low;
1515
1516   STRIP_NOPS (expr);
1517
1518   if (TREE_CODE (expr) == COMPLEX_CST)
1519     return tree_log2 (TREE_REALPART (expr));
1520
1521   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1522           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1523
1524   high = TREE_INT_CST_HIGH (expr);
1525   low = TREE_INT_CST_LOW (expr);
1526
1527   /* First clear all bits that are beyond the type's precision in case
1528      we've been sign extended.  Ignore if type's precision hasn't been set
1529      since what we are doing is setting it.  */
1530
1531   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1532     ;
1533   else if (prec > HOST_BITS_PER_WIDE_INT)
1534     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1535   else
1536     {
1537       high = 0;
1538       if (prec < HOST_BITS_PER_WIDE_INT)
1539         low &= ~((HOST_WIDE_INT) (-1) << prec);
1540     }
1541
1542   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1543           : floor_log2 (low));
1544 }
1545
1546 /* Return 1 if EXPR is the real constant zero.  */
1547
1548 int
1549 real_zerop (const_tree expr)
1550 {
1551   STRIP_NOPS (expr);
1552
1553   return ((TREE_CODE (expr) == REAL_CST
1554            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1555           || (TREE_CODE (expr) == COMPLEX_CST
1556               && real_zerop (TREE_REALPART (expr))
1557               && real_zerop (TREE_IMAGPART (expr))));
1558 }
1559
1560 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1561
1562 int
1563 real_onep (const_tree expr)
1564 {
1565   STRIP_NOPS (expr);
1566
1567   return ((TREE_CODE (expr) == REAL_CST
1568            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1569           || (TREE_CODE (expr) == COMPLEX_CST
1570               && real_onep (TREE_REALPART (expr))
1571               && real_zerop (TREE_IMAGPART (expr))));
1572 }
1573
1574 /* Return 1 if EXPR is the real constant two.  */
1575
1576 int
1577 real_twop (const_tree expr)
1578 {
1579   STRIP_NOPS (expr);
1580
1581   return ((TREE_CODE (expr) == REAL_CST
1582            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1583           || (TREE_CODE (expr) == COMPLEX_CST
1584               && real_twop (TREE_REALPART (expr))
1585               && real_zerop (TREE_IMAGPART (expr))));
1586 }
1587
1588 /* Return 1 if EXPR is the real constant minus one.  */
1589
1590 int
1591 real_minus_onep (const_tree expr)
1592 {
1593   STRIP_NOPS (expr);
1594
1595   return ((TREE_CODE (expr) == REAL_CST
1596            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1597           || (TREE_CODE (expr) == COMPLEX_CST
1598               && real_minus_onep (TREE_REALPART (expr))
1599               && real_zerop (TREE_IMAGPART (expr))));
1600 }
1601
1602 /* Nonzero if EXP is a constant or a cast of a constant.  */
1603
1604 int
1605 really_constant_p (const_tree exp)
1606 {
1607   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1608   while (TREE_CODE (exp) == NOP_EXPR
1609          || TREE_CODE (exp) == CONVERT_EXPR
1610          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1611     exp = TREE_OPERAND (exp, 0);
1612   return TREE_CONSTANT (exp);
1613 }
1614 \f
1615 /* Return first list element whose TREE_VALUE is ELEM.
1616    Return 0 if ELEM is not in LIST.  */
1617
1618 tree
1619 value_member (tree elem, tree list)
1620 {
1621   while (list)
1622     {
1623       if (elem == TREE_VALUE (list))
1624         return list;
1625       list = TREE_CHAIN (list);
1626     }
1627   return NULL_TREE;
1628 }
1629
1630 /* Return first list element whose TREE_PURPOSE is ELEM.
1631    Return 0 if ELEM is not in LIST.  */
1632
1633 tree
1634 purpose_member (const_tree elem, tree list)
1635 {
1636   while (list)
1637     {
1638       if (elem == TREE_PURPOSE (list))
1639         return list;
1640       list = TREE_CHAIN (list);
1641     }
1642   return NULL_TREE;
1643 }
1644
1645 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1646
1647 int
1648 chain_member (const_tree elem, const_tree chain)
1649 {
1650   while (chain)
1651     {
1652       if (elem == chain)
1653         return 1;
1654       chain = TREE_CHAIN (chain);
1655     }
1656
1657   return 0;
1658 }
1659
1660 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1661    We expect a null pointer to mark the end of the chain.
1662    This is the Lisp primitive `length'.  */
1663
1664 int
1665 list_length (const_tree t)
1666 {
1667   const_tree p = t;
1668 #ifdef ENABLE_TREE_CHECKING
1669   const_tree q = t;
1670 #endif
1671   int len = 0;
1672
1673   while (p)
1674     {
1675       p = TREE_CHAIN (p);
1676 #ifdef ENABLE_TREE_CHECKING
1677       if (len % 2)
1678         q = TREE_CHAIN (q);
1679       gcc_assert (p != q);
1680 #endif
1681       len++;
1682     }
1683
1684   return len;
1685 }
1686
1687 /* Returns the number of FIELD_DECLs in TYPE.  */
1688
1689 int
1690 fields_length (const_tree type)
1691 {
1692   tree t = TYPE_FIELDS (type);
1693   int count = 0;
1694
1695   for (; t; t = TREE_CHAIN (t))
1696     if (TREE_CODE (t) == FIELD_DECL)
1697       ++count;
1698
1699   return count;
1700 }
1701
1702 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1703    by modifying the last node in chain 1 to point to chain 2.
1704    This is the Lisp primitive `nconc'.  */
1705
1706 tree
1707 chainon (tree op1, tree op2)
1708 {
1709   tree t1;
1710
1711   if (!op1)
1712     return op2;
1713   if (!op2)
1714     return op1;
1715
1716   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1717     continue;
1718   TREE_CHAIN (t1) = op2;
1719
1720 #ifdef ENABLE_TREE_CHECKING
1721   {
1722     tree t2;
1723     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1724       gcc_assert (t2 != t1);
1725   }
1726 #endif
1727
1728   return op1;
1729 }
1730
1731 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1732
1733 tree
1734 tree_last (tree chain)
1735 {
1736   tree next;
1737   if (chain)
1738     while ((next = TREE_CHAIN (chain)))
1739       chain = next;
1740   return chain;
1741 }
1742
1743 /* Reverse the order of elements in the chain T,
1744    and return the new head of the chain (old last element).  */
1745
1746 tree
1747 nreverse (tree t)
1748 {
1749   tree prev = 0, decl, next;
1750   for (decl = t; decl; decl = next)
1751     {
1752       next = TREE_CHAIN (decl);
1753       TREE_CHAIN (decl) = prev;
1754       prev = decl;
1755     }
1756   return prev;
1757 }
1758 \f
1759 /* Return a newly created TREE_LIST node whose
1760    purpose and value fields are PARM and VALUE.  */
1761
1762 tree
1763 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1764 {
1765   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1766   TREE_PURPOSE (t) = parm;
1767   TREE_VALUE (t) = value;
1768   return t;
1769 }
1770
1771 /* Return a newly created TREE_LIST node whose
1772    purpose and value fields are PURPOSE and VALUE
1773    and whose TREE_CHAIN is CHAIN.  */
1774
1775 tree
1776 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1777 {
1778   tree node;
1779
1780   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1781
1782   memset (node, 0, sizeof (struct tree_common));
1783
1784 #ifdef GATHER_STATISTICS
1785   tree_node_counts[(int) x_kind]++;
1786   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1787 #endif
1788
1789   TREE_SET_CODE (node, TREE_LIST);
1790   TREE_CHAIN (node) = chain;
1791   TREE_PURPOSE (node) = purpose;
1792   TREE_VALUE (node) = value;
1793   return node;
1794 }
1795
1796 \f
1797 /* Return the size nominally occupied by an object of type TYPE
1798    when it resides in memory.  The value is measured in units of bytes,
1799    and its data type is that normally used for type sizes
1800    (which is the first type created by make_signed_type or
1801    make_unsigned_type).  */
1802
1803 tree
1804 size_in_bytes (const_tree type)
1805 {
1806   tree t;
1807
1808   if (type == error_mark_node)
1809     return integer_zero_node;
1810
1811   type = TYPE_MAIN_VARIANT (type);
1812   t = TYPE_SIZE_UNIT (type);
1813
1814   if (t == 0)
1815     {
1816       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1817       return size_zero_node;
1818     }
1819
1820   return t;
1821 }
1822
1823 /* Return the size of TYPE (in bytes) as a wide integer
1824    or return -1 if the size can vary or is larger than an integer.  */
1825
1826 HOST_WIDE_INT
1827 int_size_in_bytes (const_tree type)
1828 {
1829   tree t;
1830
1831   if (type == error_mark_node)
1832     return 0;
1833
1834   type = TYPE_MAIN_VARIANT (type);
1835   t = TYPE_SIZE_UNIT (type);
1836   if (t == 0
1837       || TREE_CODE (t) != INTEGER_CST
1838       || TREE_INT_CST_HIGH (t) != 0
1839       /* If the result would appear negative, it's too big to represent.  */
1840       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1841     return -1;
1842
1843   return TREE_INT_CST_LOW (t);
1844 }
1845
1846 /* Return the maximum size of TYPE (in bytes) as a wide integer
1847    or return -1 if the size can vary or is larger than an integer.  */
1848
1849 HOST_WIDE_INT
1850 max_int_size_in_bytes (const_tree type)
1851 {
1852   HOST_WIDE_INT size = -1;
1853   tree size_tree;
1854
1855   /* If this is an array type, check for a possible MAX_SIZE attached.  */
1856
1857   if (TREE_CODE (type) == ARRAY_TYPE)
1858     {
1859       size_tree = TYPE_ARRAY_MAX_SIZE (type);
1860
1861       if (size_tree && host_integerp (size_tree, 1))
1862         size = tree_low_cst (size_tree, 1);
1863     }
1864
1865   /* If we still haven't been able to get a size, see if the language
1866      can compute a maximum size.  */
1867
1868   if (size == -1)
1869     {
1870       size_tree = lang_hooks.types.max_size (type);
1871
1872       if (size_tree && host_integerp (size_tree, 1))
1873         size = tree_low_cst (size_tree, 1);
1874     }
1875
1876   return size;
1877 }
1878 \f
1879 /* Return the bit position of FIELD, in bits from the start of the record.
1880    This is a tree of type bitsizetype.  */
1881
1882 tree
1883 bit_position (const_tree field)
1884 {
1885   return bit_from_pos (DECL_FIELD_OFFSET (field),
1886                        DECL_FIELD_BIT_OFFSET (field));
1887 }
1888
1889 /* Likewise, but return as an integer.  It must be representable in
1890    that way (since it could be a signed value, we don't have the
1891    option of returning -1 like int_size_in_byte can.  */
1892
1893 HOST_WIDE_INT
1894 int_bit_position (const_tree field)
1895 {
1896   return tree_low_cst (bit_position (field), 0);
1897 }
1898 \f
1899 /* Return the byte position of FIELD, in bytes from the start of the record.
1900    This is a tree of type sizetype.  */
1901
1902 tree
1903 byte_position (const_tree field)
1904 {
1905   return byte_from_pos (DECL_FIELD_OFFSET (field),
1906                         DECL_FIELD_BIT_OFFSET (field));
1907 }
1908
1909 /* Likewise, but return as an integer.  It must be representable in
1910    that way (since it could be a signed value, we don't have the
1911    option of returning -1 like int_size_in_byte can.  */
1912
1913 HOST_WIDE_INT
1914 int_byte_position (const_tree field)
1915 {
1916   return tree_low_cst (byte_position (field), 0);
1917 }
1918 \f
1919 /* Return the strictest alignment, in bits, that T is known to have.  */
1920
1921 unsigned int
1922 expr_align (const_tree t)
1923 {
1924   unsigned int align0, align1;
1925
1926   switch (TREE_CODE (t))
1927     {
1928     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1929       /* If we have conversions, we know that the alignment of the
1930          object must meet each of the alignments of the types.  */
1931       align0 = expr_align (TREE_OPERAND (t, 0));
1932       align1 = TYPE_ALIGN (TREE_TYPE (t));
1933       return MAX (align0, align1);
1934
1935     case GIMPLE_MODIFY_STMT:
1936       /* We should never ask for the alignment of a gimple statement.  */
1937       gcc_unreachable ();
1938
1939     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1940     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1941     case CLEANUP_POINT_EXPR:
1942       /* These don't change the alignment of an object.  */
1943       return expr_align (TREE_OPERAND (t, 0));
1944
1945     case COND_EXPR:
1946       /* The best we can do is say that the alignment is the least aligned
1947          of the two arms.  */
1948       align0 = expr_align (TREE_OPERAND (t, 1));
1949       align1 = expr_align (TREE_OPERAND (t, 2));
1950       return MIN (align0, align1);
1951
1952       /* FIXME: LABEL_DECL and CONST_DECL never have DECL_ALIGN set
1953          meaningfully, it's always 1.  */
1954     case LABEL_DECL:     case CONST_DECL:
1955     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1956     case FUNCTION_DECL:
1957       gcc_assert (DECL_ALIGN (t) != 0);
1958       return DECL_ALIGN (t);
1959
1960     default:
1961       break;
1962     }
1963
1964   /* Otherwise take the alignment from that of the type.  */
1965   return TYPE_ALIGN (TREE_TYPE (t));
1966 }
1967 \f
1968 /* Return, as a tree node, the number of elements for TYPE (which is an
1969    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1970
1971 tree
1972 array_type_nelts (const_tree type)
1973 {
1974   tree index_type, min, max;
1975
1976   /* If they did it with unspecified bounds, then we should have already
1977      given an error about it before we got here.  */
1978   if (! TYPE_DOMAIN (type))
1979     return error_mark_node;
1980
1981   index_type = TYPE_DOMAIN (type);
1982   min = TYPE_MIN_VALUE (index_type);
1983   max = TYPE_MAX_VALUE (index_type);
1984
1985   return (integer_zerop (min)
1986           ? max
1987           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1988 }
1989 \f
1990 /* If arg is static -- a reference to an object in static storage -- then
1991    return the object.  This is not the same as the C meaning of `static'.
1992    If arg isn't static, return NULL.  */
1993
1994 tree
1995 staticp (tree arg)
1996 {
1997   switch (TREE_CODE (arg))
1998     {
1999     case FUNCTION_DECL:
2000       /* Nested functions are static, even though taking their address will
2001          involve a trampoline as we unnest the nested function and create
2002          the trampoline on the tree level.  */
2003       return arg;
2004
2005     case VAR_DECL:
2006       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
2007               && ! DECL_THREAD_LOCAL_P (arg)
2008               && ! DECL_DLLIMPORT_P (arg)
2009               ? arg : NULL);
2010
2011     case CONST_DECL:
2012       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
2013               ? arg : NULL);
2014
2015     case CONSTRUCTOR:
2016       return TREE_STATIC (arg) ? arg : NULL;
2017
2018     case LABEL_DECL:
2019     case STRING_CST:
2020       return arg;
2021
2022     case COMPONENT_REF:
2023       /* If the thing being referenced is not a field, then it is
2024          something language specific.  */
2025       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
2026         return (*lang_hooks.staticp) (arg);
2027
2028       /* If we are referencing a bitfield, we can't evaluate an
2029          ADDR_EXPR at compile time and so it isn't a constant.  */
2030       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
2031         return NULL;
2032
2033       return staticp (TREE_OPERAND (arg, 0));
2034
2035     case BIT_FIELD_REF:
2036       return NULL;
2037
2038     case MISALIGNED_INDIRECT_REF:
2039     case ALIGN_INDIRECT_REF:
2040     case INDIRECT_REF:
2041       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
2042
2043     case ARRAY_REF:
2044     case ARRAY_RANGE_REF:
2045       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
2046           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
2047         return staticp (TREE_OPERAND (arg, 0));
2048       else
2049         return false;
2050
2051     default:
2052       if ((unsigned int) TREE_CODE (arg)
2053           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
2054         return lang_hooks.staticp (arg);
2055       else
2056         return NULL;
2057     }
2058 }
2059 \f
2060 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
2061    Do this to any expression which may be used in more than one place,
2062    but must be evaluated only once.
2063
2064    Normally, expand_expr would reevaluate the expression each time.
2065    Calling save_expr produces something that is evaluated and recorded
2066    the first time expand_expr is called on it.  Subsequent calls to
2067    expand_expr just reuse the recorded value.
2068
2069    The call to expand_expr that generates code that actually computes
2070    the value is the first call *at compile time*.  Subsequent calls
2071    *at compile time* generate code to use the saved value.
2072    This produces correct result provided that *at run time* control
2073    always flows through the insns made by the first expand_expr
2074    before reaching the other places where the save_expr was evaluated.
2075    You, the caller of save_expr, must make sure this is so.
2076
2077    Constants, and certain read-only nodes, are returned with no
2078    SAVE_EXPR because that is safe.  Expressions containing placeholders
2079    are not touched; see tree.def for an explanation of what these
2080    are used for.  */
2081
2082 tree
2083 save_expr (tree expr)
2084 {
2085   tree t = fold (expr);
2086   tree inner;
2087
2088   /* If the tree evaluates to a constant, then we don't want to hide that
2089      fact (i.e. this allows further folding, and direct checks for constants).
2090      However, a read-only object that has side effects cannot be bypassed.
2091      Since it is no problem to reevaluate literals, we just return the
2092      literal node.  */
2093   inner = skip_simple_arithmetic (t);
2094
2095   if (TREE_INVARIANT (inner)
2096       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
2097       || TREE_CODE (inner) == SAVE_EXPR
2098       || TREE_CODE (inner) == ERROR_MARK)
2099     return t;
2100
2101   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
2102      it means that the size or offset of some field of an object depends on
2103      the value within another field.
2104
2105      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
2106      and some variable since it would then need to be both evaluated once and
2107      evaluated more than once.  Front-ends must assure this case cannot
2108      happen by surrounding any such subexpressions in their own SAVE_EXPR
2109      and forcing evaluation at the proper time.  */
2110   if (contains_placeholder_p (inner))
2111     return t;
2112
2113   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2114
2115   /* This expression might be placed ahead of a jump to ensure that the
2116      value was computed on both sides of the jump.  So make sure it isn't
2117      eliminated as dead.  */
2118   TREE_SIDE_EFFECTS (t) = 1;
2119   TREE_INVARIANT (t) = 1;
2120   return t;
2121 }
2122
2123 /* Look inside EXPR and into any simple arithmetic operations.  Return
2124    the innermost non-arithmetic node.  */
2125
2126 tree
2127 skip_simple_arithmetic (tree expr)
2128 {
2129   tree inner;
2130
2131   /* We don't care about whether this can be used as an lvalue in this
2132      context.  */
2133   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2134     expr = TREE_OPERAND (expr, 0);
2135
2136   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2137      a constant, it will be more efficient to not make another SAVE_EXPR since
2138      it will allow better simplification and GCSE will be able to merge the
2139      computations if they actually occur.  */
2140   inner = expr;
2141   while (1)
2142     {
2143       if (UNARY_CLASS_P (inner))
2144         inner = TREE_OPERAND (inner, 0);
2145       else if (BINARY_CLASS_P (inner))
2146         {
2147           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2148             inner = TREE_OPERAND (inner, 0);
2149           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2150             inner = TREE_OPERAND (inner, 1);
2151           else
2152             break;
2153         }
2154       else
2155         break;
2156     }
2157
2158   return inner;
2159 }
2160
2161 /* Return which tree structure is used by T.  */
2162
2163 enum tree_node_structure_enum
2164 tree_node_structure (const_tree t)
2165 {
2166   const enum tree_code code = TREE_CODE (t);
2167
2168   switch (TREE_CODE_CLASS (code))
2169     {
2170     case tcc_declaration:
2171       {
2172         switch (code)
2173           {
2174           case FIELD_DECL:
2175             return TS_FIELD_DECL;
2176           case PARM_DECL:
2177             return TS_PARM_DECL;
2178           case VAR_DECL:
2179             return TS_VAR_DECL;
2180           case LABEL_DECL:
2181             return TS_LABEL_DECL;
2182           case RESULT_DECL:
2183             return TS_RESULT_DECL;
2184           case CONST_DECL:
2185             return TS_CONST_DECL;
2186           case TYPE_DECL:
2187             return TS_TYPE_DECL;
2188           case FUNCTION_DECL:
2189             return TS_FUNCTION_DECL;
2190           case SYMBOL_MEMORY_TAG:
2191           case NAME_MEMORY_TAG:
2192           case STRUCT_FIELD_TAG:
2193           case MEMORY_PARTITION_TAG:
2194             return TS_MEMORY_TAG;
2195           default:
2196             return TS_DECL_NON_COMMON;
2197           }
2198       }
2199     case tcc_type:
2200       return TS_TYPE;
2201     case tcc_reference:
2202     case tcc_comparison:
2203     case tcc_unary:
2204     case tcc_binary:
2205     case tcc_expression:
2206     case tcc_statement:
2207     case tcc_vl_exp:
2208       return TS_EXP;
2209     case tcc_gimple_stmt:
2210       return TS_GIMPLE_STATEMENT;
2211     default:  /* tcc_constant and tcc_exceptional */
2212       break;
2213     }
2214   switch (code)
2215     {
2216       /* tcc_constant cases.  */
2217     case INTEGER_CST:           return TS_INT_CST;
2218     case REAL_CST:              return TS_REAL_CST;
2219     case FIXED_CST:             return TS_FIXED_CST;
2220     case COMPLEX_CST:           return TS_COMPLEX;
2221     case VECTOR_CST:            return TS_VECTOR;
2222     case STRING_CST:            return TS_STRING;
2223       /* tcc_exceptional cases.  */
2224     /* FIXME tuples: eventually this should be TS_BASE.  For now, nothing
2225        returns TS_BASE.  */
2226     case ERROR_MARK:            return TS_COMMON;
2227     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2228     case TREE_LIST:             return TS_LIST;
2229     case TREE_VEC:              return TS_VEC;
2230     case PHI_NODE:              return TS_PHI_NODE;
2231     case SSA_NAME:              return TS_SSA_NAME;
2232     case PLACEHOLDER_EXPR:      return TS_COMMON;
2233     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2234     case BLOCK:                 return TS_BLOCK;
2235     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2236     case TREE_BINFO:            return TS_BINFO;
2237     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2238     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2239
2240     default:
2241       gcc_unreachable ();
2242     }
2243 }
2244 \f
2245 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2246    or offset that depends on a field within a record.  */
2247
2248 bool
2249 contains_placeholder_p (const_tree exp)
2250 {
2251   enum tree_code code;
2252
2253   if (!exp)
2254     return 0;
2255
2256   code = TREE_CODE (exp);
2257   if (code == PLACEHOLDER_EXPR)
2258     return 1;
2259
2260   switch (TREE_CODE_CLASS (code))
2261     {
2262     case tcc_reference:
2263       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2264          position computations since they will be converted into a
2265          WITH_RECORD_EXPR involving the reference, which will assume
2266          here will be valid.  */
2267       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2268
2269     case tcc_exceptional:
2270       if (code == TREE_LIST)
2271         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2272                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2273       break;
2274
2275     case tcc_unary:
2276     case tcc_binary:
2277     case tcc_comparison:
2278     case tcc_expression:
2279       switch (code)
2280         {
2281         case COMPOUND_EXPR:
2282           /* Ignoring the first operand isn't quite right, but works best.  */
2283           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2284
2285         case COND_EXPR:
2286           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2287                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2288                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2289
2290         default:
2291           break;
2292         }
2293
2294       switch (TREE_CODE_LENGTH (code))
2295         {
2296         case 1:
2297           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2298         case 2:
2299           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2300                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2301         default:
2302           return 0;
2303         }
2304
2305     case tcc_vl_exp:
2306       switch (code)
2307         {
2308         case CALL_EXPR:
2309           {
2310             const_tree arg;
2311             const_call_expr_arg_iterator iter;
2312             FOR_EACH_CONST_CALL_EXPR_ARG (arg, iter, exp)
2313               if (CONTAINS_PLACEHOLDER_P (arg))
2314                 return 1;
2315             return 0;
2316           }
2317         default:
2318           return 0;
2319         }
2320
2321     default:
2322       return 0;
2323     }
2324   return 0;
2325 }
2326
2327 /* Return true if any part of the computation of TYPE involves a
2328    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2329    (for QUAL_UNION_TYPE) and field positions.  */
2330
2331 static bool
2332 type_contains_placeholder_1 (const_tree type)
2333 {
2334   /* If the size contains a placeholder or the parent type (component type in
2335      the case of arrays) type involves a placeholder, this type does.  */
2336   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2337       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2338       || (TREE_TYPE (type) != 0
2339           && type_contains_placeholder_p (TREE_TYPE (type))))
2340     return true;
2341
2342   /* Now do type-specific checks.  Note that the last part of the check above
2343      greatly limits what we have to do below.  */
2344   switch (TREE_CODE (type))
2345     {
2346     case VOID_TYPE:
2347     case COMPLEX_TYPE:
2348     case ENUMERAL_TYPE:
2349     case BOOLEAN_TYPE:
2350     case POINTER_TYPE:
2351     case OFFSET_TYPE:
2352     case REFERENCE_TYPE:
2353     case METHOD_TYPE:
2354     case FUNCTION_TYPE:
2355     case VECTOR_TYPE:
2356       return false;
2357
2358     case INTEGER_TYPE:
2359     case REAL_TYPE:
2360     case FIXED_POINT_TYPE:
2361       /* Here we just check the bounds.  */
2362       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2363               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2364
2365     case ARRAY_TYPE:
2366       /* We're already checked the component type (TREE_TYPE), so just check
2367          the index type.  */
2368       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2369
2370     case RECORD_TYPE:
2371     case UNION_TYPE:
2372     case QUAL_UNION_TYPE:
2373       {
2374         tree field;
2375
2376         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2377           if (TREE_CODE (field) == FIELD_DECL
2378               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2379                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2380                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2381                   || type_contains_placeholder_p (TREE_TYPE (field))))
2382             return true;
2383
2384         return false;
2385       }
2386
2387     default:
2388       gcc_unreachable ();
2389     }
2390 }
2391
2392 bool
2393 type_contains_placeholder_p (tree type)
2394 {
2395   bool result;
2396
2397   /* If the contains_placeholder_bits field has been initialized,
2398      then we know the answer.  */
2399   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2400     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2401
2402   /* Indicate that we've seen this type node, and the answer is false.
2403      This is what we want to return if we run into recursion via fields.  */
2404   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2405
2406   /* Compute the real value.  */
2407   result = type_contains_placeholder_1 (type);
2408
2409   /* Store the real value.  */
2410   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2411
2412   return result;
2413 }
2414 \f
2415 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2416    return a tree with all occurrences of references to F in a
2417    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2418    contains only arithmetic expressions or a CALL_EXPR with a
2419    PLACEHOLDER_EXPR occurring only in its arglist.  */
2420
2421 tree
2422 substitute_in_expr (tree exp, tree f, tree r)
2423 {
2424   enum tree_code code = TREE_CODE (exp);
2425   tree op0, op1, op2, op3;
2426   tree new;
2427   tree inner;
2428
2429   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2430   if (code == TREE_LIST)
2431     {
2432       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2433       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2434       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2435         return exp;
2436
2437       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2438     }
2439   else if (code == COMPONENT_REF)
2440    {
2441      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2442         and it is the right field, replace it with R.  */
2443      for (inner = TREE_OPERAND (exp, 0);
2444           REFERENCE_CLASS_P (inner);
2445           inner = TREE_OPERAND (inner, 0))
2446        ;
2447      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2448          && TREE_OPERAND (exp, 1) == f)
2449        return r;
2450
2451      /* If this expression hasn't been completed let, leave it alone.  */
2452      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2453        return exp;
2454
2455      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2456      if (op0 == TREE_OPERAND (exp, 0))
2457        return exp;
2458
2459      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2460                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2461    }
2462   else
2463     switch (TREE_CODE_CLASS (code))
2464       {
2465       case tcc_constant:
2466       case tcc_declaration:
2467         return exp;
2468
2469       case tcc_exceptional:
2470       case tcc_unary:
2471       case tcc_binary:
2472       case tcc_comparison:
2473       case tcc_expression:
2474       case tcc_reference:
2475         switch (TREE_CODE_LENGTH (code))
2476           {
2477           case 0:
2478             return exp;
2479
2480           case 1:
2481             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2482             if (op0 == TREE_OPERAND (exp, 0))
2483               return exp;
2484
2485             new = fold_build1 (code, TREE_TYPE (exp), op0);
2486             break;
2487
2488           case 2:
2489             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2490             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2491
2492             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2493               return exp;
2494
2495             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2496             break;
2497
2498           case 3:
2499             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2500             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2501             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2502
2503             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2504                 && op2 == TREE_OPERAND (exp, 2))
2505               return exp;
2506
2507             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2508             break;
2509
2510           case 4:
2511             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2512             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2513             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2514             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2515
2516             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2517                 && op2 == TREE_OPERAND (exp, 2)
2518                 && op3 == TREE_OPERAND (exp, 3))
2519               return exp;
2520
2521             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2522             break;
2523
2524           default:
2525             gcc_unreachable ();
2526           }
2527         break;
2528
2529       case tcc_vl_exp:
2530         {
2531           tree copy = NULL_TREE;
2532           int i;
2533           int n = TREE_OPERAND_LENGTH (exp);
2534           for (i = 1; i < n; i++)
2535             {
2536               tree op = TREE_OPERAND (exp, i);
2537               tree newop = SUBSTITUTE_IN_EXPR (op, f, r);
2538               if (newop != op)
2539                 {
2540                   copy = copy_node (exp);
2541                   TREE_OPERAND (copy, i) = newop;
2542                 }
2543             }
2544           if (copy)
2545             new = fold (copy);
2546           else
2547             return exp;
2548         }
2549
2550       default:
2551         gcc_unreachable ();
2552       }
2553
2554   TREE_READONLY (new) = TREE_READONLY (exp);
2555   return new;
2556 }
2557
2558 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2559    for it within OBJ, a tree that is an object or a chain of references.  */
2560
2561 tree
2562 substitute_placeholder_in_expr (tree exp, tree obj)
2563 {
2564   enum tree_code code = TREE_CODE (exp);
2565   tree op0, op1, op2, op3;
2566
2567   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2568      in the chain of OBJ.  */
2569   if (code == PLACEHOLDER_EXPR)
2570     {
2571       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2572       tree elt;
2573
2574       for (elt = obj; elt != 0;
2575            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2576                    || TREE_CODE (elt) == COND_EXPR)
2577                   ? TREE_OPERAND (elt, 1)
2578                   : (REFERENCE_CLASS_P (elt)
2579                      || UNARY_CLASS_P (elt)
2580                      || BINARY_CLASS_P (elt)
2581                      || VL_EXP_CLASS_P (elt)
2582                      || EXPRESSION_CLASS_P (elt))
2583                   ? TREE_OPERAND (elt, 0) : 0))
2584         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2585           return elt;
2586
2587       for (elt = obj; elt != 0;
2588            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2589                    || TREE_CODE (elt) == COND_EXPR)
2590                   ? TREE_OPERAND (elt, 1)
2591                   : (REFERENCE_CLASS_P (elt)
2592                      || UNARY_CLASS_P (elt)
2593                      || BINARY_CLASS_P (elt)
2594                      || VL_EXP_CLASS_P (elt)
2595                      || EXPRESSION_CLASS_P (elt))
2596                   ? TREE_OPERAND (elt, 0) : 0))
2597         if (POINTER_TYPE_P (TREE_TYPE (elt))
2598             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2599                 == need_type))
2600           return fold_build1 (INDIRECT_REF, need_type, elt);
2601
2602       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2603          survives until RTL generation, there will be an error.  */
2604       return exp;
2605     }
2606
2607   /* TREE_LIST is special because we need to look at TREE_VALUE
2608      and TREE_CHAIN, not TREE_OPERANDS.  */
2609   else if (code == TREE_LIST)
2610     {
2611       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2612       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2613       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2614         return exp;
2615
2616       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2617     }
2618   else
2619     switch (TREE_CODE_CLASS (code))
2620       {
2621       case tcc_constant:
2622       case tcc_declaration:
2623         return exp;
2624
2625       case tcc_exceptional:
2626       case tcc_unary:
2627       case tcc_binary:
2628       case tcc_comparison:
2629       case tcc_expression:
2630       case tcc_reference:
2631       case tcc_statement:
2632         switch (TREE_CODE_LENGTH (code))
2633           {
2634           case 0:
2635             return exp;
2636
2637           case 1:
2638             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2639             if (op0 == TREE_OPERAND (exp, 0))
2640               return exp;
2641             else
2642               return fold_build1 (code, TREE_TYPE (exp), op0);
2643
2644           case 2:
2645             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2646             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2647
2648             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2649               return exp;
2650             else
2651               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2652
2653           case 3:
2654             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2655             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2656             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2657
2658             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2659                 && op2 == TREE_OPERAND (exp, 2))
2660               return exp;
2661             else
2662               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2663
2664           case 4:
2665             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2666             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2667             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2668             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2669
2670             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2671                 && op2 == TREE_OPERAND (exp, 2)
2672                 && op3 == TREE_OPERAND (exp, 3))
2673               return exp;
2674             else
2675               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2676
2677           default:
2678             gcc_unreachable ();
2679           }
2680         break;
2681
2682       case tcc_vl_exp:
2683         {
2684           tree copy = NULL_TREE;
2685           int i;
2686           int n = TREE_OPERAND_LENGTH (exp);
2687           for (i = 1; i < n; i++)
2688             {
2689               tree op = TREE_OPERAND (exp, i);
2690               tree newop = SUBSTITUTE_PLACEHOLDER_IN_EXPR (op, obj);
2691               if (newop != op)
2692                 {
2693                   if (!copy)
2694                     copy = copy_node (exp);
2695                   TREE_OPERAND (copy, i) = newop;
2696                 }
2697             }
2698           if (copy)
2699             return fold (copy);
2700           else
2701             return exp;
2702         }
2703
2704       default:
2705         gcc_unreachable ();
2706       }
2707 }
2708 \f
2709 /* Stabilize a reference so that we can use it any number of times
2710    without causing its operands to be evaluated more than once.
2711    Returns the stabilized reference.  This works by means of save_expr,
2712    so see the caveats in the comments about save_expr.
2713
2714    Also allows conversion expressions whose operands are references.
2715    Any other kind of expression is returned unchanged.  */
2716
2717 tree
2718 stabilize_reference (tree ref)
2719 {
2720   tree result;
2721   enum tree_code code = TREE_CODE (ref);
2722
2723   switch (code)
2724     {
2725     case VAR_DECL:
2726     case PARM_DECL:
2727     case RESULT_DECL:
2728       /* No action is needed in this case.  */
2729       return ref;
2730
2731     case NOP_EXPR:
2732     case CONVERT_EXPR:
2733     case FLOAT_EXPR:
2734     case FIX_TRUNC_EXPR:
2735       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2736       break;
2737
2738     case INDIRECT_REF:
2739       result = build_nt (INDIRECT_REF,
2740                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2741       break;
2742
2743     case COMPONENT_REF:
2744       result = build_nt (COMPONENT_REF,
2745                          stabilize_reference (TREE_OPERAND (ref, 0)),
2746                          TREE_OPERAND (ref, 1), NULL_TREE);
2747       break;
2748
2749     case BIT_FIELD_REF:
2750       result = build_nt (BIT_FIELD_REF,
2751                          stabilize_reference (TREE_OPERAND (ref, 0)),
2752                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2753                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2754       break;
2755
2756     case ARRAY_REF:
2757       result = build_nt (ARRAY_REF,
2758                          stabilize_reference (TREE_OPERAND (ref, 0)),
2759                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2760                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2761       break;
2762
2763     case ARRAY_RANGE_REF:
2764       result = build_nt (ARRAY_RANGE_REF,
2765                          stabilize_reference (TREE_OPERAND (ref, 0)),
2766                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2767                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2768       break;
2769
2770     case COMPOUND_EXPR:
2771       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2772          it wouldn't be ignored.  This matters when dealing with
2773          volatiles.  */
2774       return stabilize_reference_1 (ref);
2775
2776       /* If arg isn't a kind of lvalue we recognize, make no change.
2777          Caller should recognize the error for an invalid lvalue.  */
2778     default:
2779       return ref;
2780
2781     case ERROR_MARK:
2782       return error_mark_node;
2783     }
2784
2785   TREE_TYPE (result) = TREE_TYPE (ref);
2786   TREE_READONLY (result) = TREE_READONLY (ref);
2787   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2788   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2789
2790   return result;
2791 }
2792
2793 /* Subroutine of stabilize_reference; this is called for subtrees of
2794    references.  Any expression with side-effects must be put in a SAVE_EXPR
2795    to ensure that it is only evaluated once.
2796
2797    We don't put SAVE_EXPR nodes around everything, because assigning very
2798    simple expressions to temporaries causes us to miss good opportunities
2799    for optimizations.  Among other things, the opportunity to fold in the
2800    addition of a constant into an addressing mode often gets lost, e.g.
2801    "y[i+1] += x;".  In general, we take the approach that we should not make
2802    an assignment unless we are forced into it - i.e., that any non-side effect
2803    operator should be allowed, and that cse should take care of coalescing
2804    multiple utterances of the same expression should that prove fruitful.  */
2805
2806 tree
2807 stabilize_reference_1 (tree e)
2808 {
2809   tree result;
2810   enum tree_code code = TREE_CODE (e);
2811
2812   /* We cannot ignore const expressions because it might be a reference
2813      to a const array but whose index contains side-effects.  But we can
2814      ignore things that are actual constant or that already have been
2815      handled by this function.  */
2816
2817   if (TREE_INVARIANT (e))
2818     return e;
2819
2820   switch (TREE_CODE_CLASS (code))
2821     {
2822     case tcc_exceptional:
2823     case tcc_type:
2824     case tcc_declaration:
2825     case tcc_comparison:
2826     case tcc_statement:
2827     case tcc_expression:
2828     case tcc_reference:
2829     case tcc_vl_exp:
2830       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2831          so that it will only be evaluated once.  */
2832       /* The reference (r) and comparison (<) classes could be handled as
2833          below, but it is generally faster to only evaluate them once.  */
2834       if (TREE_SIDE_EFFECTS (e))
2835         return save_expr (e);
2836       return e;
2837
2838     case tcc_constant:
2839       /* Constants need no processing.  In fact, we should never reach
2840          here.  */
2841       return e;
2842
2843     case tcc_binary:
2844       /* Division is slow and tends to be compiled with jumps,
2845          especially the division by powers of 2 that is often
2846          found inside of an array reference.  So do it just once.  */
2847       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2848           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2849           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2850           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2851         return save_expr (e);
2852       /* Recursively stabilize each operand.  */
2853       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2854                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2855       break;
2856
2857     case tcc_unary:
2858       /* Recursively stabilize each operand.  */
2859       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2860       break;
2861
2862     default:
2863       gcc_unreachable ();
2864     }
2865
2866   TREE_TYPE (result) = TREE_TYPE (e);
2867   TREE_READONLY (result) = TREE_READONLY (e);
2868   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2869   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2870   TREE_INVARIANT (result) = 1;
2871
2872   return result;
2873 }
2874 \f
2875 /* Low-level constructors for expressions.  */
2876
2877 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2878    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2879
2880 void
2881 recompute_tree_invariant_for_addr_expr (tree t)
2882 {
2883   tree node;
2884   bool tc = true, ti = true, se = false;
2885
2886   /* We started out assuming this address is both invariant and constant, but
2887      does not have side effects.  Now go down any handled components and see if
2888      any of them involve offsets that are either non-constant or non-invariant.
2889      Also check for side-effects.
2890
2891      ??? Note that this code makes no attempt to deal with the case where
2892      taking the address of something causes a copy due to misalignment.  */
2893
2894 #define UPDATE_TITCSE(NODE)  \
2895 do { tree _node = (NODE); \
2896      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2897      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2898      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2899
2900   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2901        node = TREE_OPERAND (node, 0))
2902     {
2903       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2904          array reference (probably made temporarily by the G++ front end),
2905          so ignore all the operands.  */
2906       if ((TREE_CODE (node) == ARRAY_REF
2907            || TREE_CODE (node) == ARRAY_RANGE_REF)
2908           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2909         {
2910           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2911           if (TREE_OPERAND (node, 2))
2912             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2913           if (TREE_OPERAND (node, 3))
2914             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2915         }
2916       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2917          FIELD_DECL, apparently.  The G++ front end can put something else
2918          there, at least temporarily.  */
2919       else if (TREE_CODE (node) == COMPONENT_REF
2920                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2921         {
2922           if (TREE_OPERAND (node, 2))
2923             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2924         }
2925       else if (TREE_CODE (node) == BIT_FIELD_REF)
2926         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2927     }
2928
2929   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2930
2931   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2932      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2933      invariant and constant if the decl is static.  It's also invariant if it's
2934      a decl in the current function.  Taking the address of a volatile variable
2935      is not volatile.  If it's a constant, the address is both invariant and
2936      constant.  Otherwise it's neither.  */
2937   if (TREE_CODE (node) == INDIRECT_REF)
2938     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2939   else if (DECL_P (node))
2940     {
2941       if (staticp (node))
2942         ;
2943       else if (decl_function_context (node) == current_function_decl
2944                /* Addresses of thread-local variables are invariant.  */
2945                || (TREE_CODE (node) == VAR_DECL
2946                    && DECL_THREAD_LOCAL_P (node)))
2947         tc = false;
2948       else
2949         ti = tc = false;
2950     }
2951   else if (CONSTANT_CLASS_P (node))
2952     ;
2953   else
2954     {
2955       ti = tc = false;
2956       se |= TREE_SIDE_EFFECTS (node);
2957     }
2958
2959   TREE_CONSTANT (t) = tc;
2960   TREE_INVARIANT (t) = ti;
2961   TREE_SIDE_EFFECTS (t) = se;
2962 #undef UPDATE_TITCSE
2963 }
2964
2965 /* Build an expression of code CODE, data type TYPE, and operands as
2966    specified.  Expressions and reference nodes can be created this way.
2967    Constants, decls, types and misc nodes cannot be.
2968
2969    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2970    enough for all extant tree codes.  */
2971
2972 tree
2973 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2974 {
2975   tree t;
2976
2977   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2978
2979   t = make_node_stat (code PASS_MEM_STAT);
2980   TREE_TYPE (t) = tt;
2981
2982   return t;
2983 }
2984
2985 tree
2986 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2987 {
2988   int length = sizeof (struct tree_exp);
2989 #ifdef GATHER_STATISTICS
2990   tree_node_kind kind;
2991 #endif
2992   tree t;
2993
2994 #ifdef GATHER_STATISTICS
2995   switch (TREE_CODE_CLASS (code))
2996     {
2997     case tcc_statement:  /* an expression with side effects */
2998       kind = s_kind;
2999       break;
3000     case tcc_reference:  /* a reference */
3001       kind = r_kind;
3002       break;
3003     default:
3004       kind = e_kind;
3005       break;
3006     }
3007
3008   tree_node_counts[(int) kind]++;
3009   tree_node_sizes[(int) kind] += length;
3010 #endif
3011
3012   gcc_assert (TREE_CODE_LENGTH (code) == 1);
3013
3014   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
3015
3016   memset (t, 0, sizeof (struct tree_common));
3017
3018   TREE_SET_CODE (t, code);
3019
3020   TREE_TYPE (t) = type;
3021 #ifdef USE_MAPPED_LOCATION
3022   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
3023 #else
3024   SET_EXPR_LOCUS (t, NULL);
3025 #endif
3026   TREE_OPERAND (t, 0) = node;
3027   TREE_BLOCK (t) = NULL_TREE;
3028   if (node && !TYPE_P (node))
3029     {
3030       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
3031       TREE_READONLY (t) = TREE_READONLY (node);
3032     }
3033
3034   if (TREE_CODE_CLASS (code) == tcc_statement)
3035     TREE_SIDE_EFFECTS (t) = 1;
3036   else switch (code)
3037     {
3038     case VA_ARG_EXPR:
3039       /* All of these have side-effects, no matter what their
3040          operands are.  */
3041       TREE_SIDE_EFFECTS (t) = 1;
3042       TREE_READONLY (t) = 0;
3043       break;
3044
3045     case MISALIGNED_INDIRECT_REF:
3046     case ALIGN_INDIRECT_REF:
3047     case INDIRECT_REF:
3048       /* Whether a dereference is readonly has nothing to do with whether
3049          its operand is readonly.  */
3050       TREE_READONLY (t) = 0;
3051       break;
3052
3053     case ADDR_EXPR:
3054       if (node)
3055         recompute_tree_invariant_for_addr_expr (t);
3056       break;
3057
3058     default:
3059       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
3060           && node && !TYPE_P (node)
3061           && TREE_CONSTANT (node))
3062         TREE_CONSTANT (t) = 1;
3063       if ((TREE_CODE_CLASS (code) == tcc_unary || code == VIEW_CONVERT_EXPR)
3064           && node && TREE_INVARIANT (node))
3065         TREE_INVARIANT (t) = 1;
3066       if (TREE_CODE_CLASS (code) == tcc_reference
3067           && node && TREE_THIS_VOLATILE (node))
3068         TREE_THIS_VOLATILE (t) = 1;
3069       break;
3070     }
3071
3072   return t;
3073 }
3074
3075 #define PROCESS_ARG(N)                  \
3076   do {                                  \
3077     TREE_OPERAND (t, N) = arg##N;       \
3078     if (arg##N &&!TYPE_P (arg##N))      \
3079       {                                 \
3080         if (TREE_SIDE_EFFECTS (arg##N)) \
3081           side_effects = 1;             \
3082         if (!TREE_READONLY (arg##N))    \
3083           read_only = 0;                \
3084         if (!TREE_CONSTANT (arg##N))    \
3085           constant = 0;                 \
3086         if (!TREE_INVARIANT (arg##N))   \
3087           invariant = 0;                \
3088       }                                 \
3089   } while (0)
3090
3091 tree
3092 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
3093 {
3094   bool constant, read_only, side_effects, invariant;
3095   tree t;
3096
3097   gcc_assert (TREE_CODE_LENGTH (code) == 2);
3098
3099 #if 1
3100   /* FIXME tuples: Statement's aren't expressions!  */
3101   if (code == GIMPLE_MODIFY_STMT)
3102     return build_gimple_modify_stmt_stat (arg0, arg1 PASS_MEM_STAT);
3103 #else
3104   /* Must use build_gimple_modify_stmt to construct GIMPLE_MODIFY_STMTs.  */
3105   gcc_assert (code != GIMPLE_MODIFY_STMT);
3106 #endif
3107
3108   if ((code == MINUS_EXPR || code == PLUS_EXPR || code == MULT_EXPR)
3109       && arg0 && arg1 && tt && POINTER_TYPE_P (tt))
3110     gcc_assert (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST);
3111
3112   if (code == POINTER_PLUS_EXPR && arg0 && arg1 && tt)
3113     gcc_assert (POINTER_TYPE_P (tt) && POINTER_TYPE_P (TREE_TYPE (arg0))
3114                 && INTEGRAL_TYPE_P (TREE_TYPE (arg1))
3115                 && useless_type_conversion_p (sizetype, TREE_TYPE (arg1)));
3116
3117   t = make_node_stat (code PASS_MEM_STAT);
3118   TREE_TYPE (t) = tt;
3119
3120   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
3121      result based on those same flags for the arguments.  But if the
3122      arguments aren't really even `tree' expressions, we shouldn't be trying
3123      to do this.  */
3124
3125   /* Expressions without side effects may be constant if their
3126      arguments are as well.  */
3127   constant = (TREE_CODE_CLASS (code) == tcc_comparison
3128               || TREE_CODE_CLASS (code) == tcc_binary);
3129   read_only = 1;
3130   side_effects = TREE_SIDE_EFFECTS (t);
3131   invariant = constant;
3132
3133   PROCESS_ARG(0);
3134   PROCESS_ARG(1);
3135
3136   TREE_READONLY (t) = read_only;
3137   TREE_CONSTANT (t) = constant;
3138   TREE_INVARIANT (t) = invariant;
3139   TREE_SIDE_EFFECTS (t) = side_effects;
3140   TREE_THIS_VOLATILE (t)
3141     = (TREE_CODE_CLASS (code) == tcc_reference
3142        && arg0 && TREE_THIS_VOLATILE (arg0));
3143
3144   return t;
3145 }
3146
3147
3148 /* Build a GIMPLE_MODIFY_STMT node.  This tree code doesn't have a
3149    type, so we can't use build2 (a.k.a. build2_stat).  */
3150
3151 tree
3152 build_gimple_modify_stmt_stat (tree arg0, tree arg1 MEM_STAT_DECL)
3153 {
3154   tree t;
3155
3156   t = make_node_stat (GIMPLE_MODIFY_STMT PASS_MEM_STAT);
3157   /* ?? We don't care about setting flags for tuples...  */
3158   GIMPLE_STMT_OPERAND (t, 0) = arg0;
3159   GIMPLE_STMT_OPERAND (t, 1) = arg1;
3160   return t;
3161 }
3162
3163 tree
3164 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3165              tree arg2 MEM_STAT_DECL)
3166 {
3167   bool constant, read_only, side_effects, invariant;
3168   tree t;
3169
3170   gcc_assert (TREE_CODE_LENGTH (code) == 3);
3171   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3172
3173   t = make_node_stat (code PASS_MEM_STAT);
3174   TREE_TYPE (t) = tt;
3175
3176   /* As a special exception, if COND_EXPR has NULL branches, we
3177      assume that it is a gimple statement and always consider
3178      it to have side effects.  */
3179   if (code == COND_EXPR
3180       && tt == void_type_node
3181       && arg1 == NULL_TREE
3182       && arg2 == NULL_TREE)
3183     side_effects = true;
3184   else
3185     side_effects = TREE_SIDE_EFFECTS (t);
3186
3187   PROCESS_ARG(0);
3188   PROCESS_ARG(1);
3189   PROCESS_ARG(2);
3190
3191   TREE_SIDE_EFFECTS (t) = side_effects;
3192   TREE_THIS_VOLATILE (t)
3193     = (TREE_CODE_CLASS (code) == tcc_reference
3194        && arg0 && TREE_THIS_VOLATILE (arg0));
3195
3196   return t;
3197 }
3198
3199 tree
3200 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3201              tree arg2, tree arg3 MEM_STAT_DECL)
3202 {
3203   bool constant, read_only, side_effects, invariant;
3204   tree t;
3205
3206   gcc_assert (TREE_CODE_LENGTH (code) == 4);
3207
3208   t = make_node_stat (code PASS_MEM_STAT);
3209   TREE_TYPE (t) = tt;
3210
3211   side_effects = TREE_SIDE_EFFECTS (t);
3212
3213   PROCESS_ARG(0);
3214   PROCESS_ARG(1);
3215   PROCESS_ARG(2);
3216   PROCESS_ARG(3);
3217
3218   TREE_SIDE_EFFECTS (t) = side_effects;
3219   TREE_THIS_VOLATILE (t)
3220     = (TREE_CODE_CLASS (code) == tcc_reference
3221        && arg0 && TREE_THIS_VOLATILE (arg0));
3222
3223   return t;
3224 }
3225
3226 tree
3227 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3228              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3229 {
3230   bool constant, read_only, side_effects, invariant;
3231   tree t;
3232
3233   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3234
3235   t = make_node_stat (code PASS_MEM_STAT);
3236   TREE_TYPE (t) = tt;
3237
3238   side_effects = TREE_SIDE_EFFECTS (t);
3239
3240   PROCESS_ARG(0);
3241   PROCESS_ARG(1);
3242   PROCESS_ARG(2);
3243   PROCESS_ARG(3);
3244   PROCESS_ARG(4);
3245
3246   TREE_SIDE_EFFECTS (t) = side_effects;
3247   TREE_THIS_VOLATILE (t)
3248     = (TREE_CODE_CLASS (code) == tcc_reference
3249        && arg0 && TREE_THIS_VOLATILE (arg0));
3250
3251   return t;
3252 }
3253
3254 tree
3255 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3256              tree arg2, tree arg3, tree arg4, tree arg5,
3257              tree arg6 MEM_STAT_DECL)
3258 {
3259   bool constant, read_only, side_effects, invariant;
3260   tree t;
3261
3262   gcc_assert (code == TARGET_MEM_REF);
3263
3264   t = make_node_stat (code PASS_MEM_STAT);
3265   TREE_TYPE (t) = tt;
3266
3267   side_effects = TREE_SIDE_EFFECTS (t);
3268
3269   PROCESS_ARG(0);
3270   PROCESS_ARG(1);
3271   PROCESS_ARG(2);
3272   PROCESS_ARG(3);
3273   PROCESS_ARG(4);
3274   PROCESS_ARG(5);
3275   PROCESS_ARG(6);
3276
3277   TREE_SIDE_EFFECTS (t) = side_effects;
3278   TREE_THIS_VOLATILE (t) = 0;
3279
3280   return t;
3281 }
3282
3283 /* Similar except don't specify the TREE_TYPE
3284    and leave the TREE_SIDE_EFFECTS as 0.
3285    It is permissible for arguments to be null,
3286    or even garbage if their values do not matter.  */
3287
3288 tree
3289 build_nt (enum tree_code code, ...)
3290 {
3291   tree t;
3292   int length;
3293   int i;
3294   va_list p;
3295
3296   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3297
3298   va_start (p, code);
3299
3300   t = make_node (code);
3301   length = TREE_CODE_LENGTH (code);
3302
3303   for (i = 0; i < length; i++)
3304     TREE_OPERAND (t, i) = va_arg (p, tree);
3305
3306   va_end (p);
3307   return t;
3308 }
3309
3310 /* Similar to build_nt, but for creating a CALL_EXPR object with
3311    ARGLIST passed as a list.  */
3312
3313 tree
3314 build_nt_call_list (tree fn, tree arglist)
3315 {
3316   tree t;
3317   int i;
3318
3319   t = build_vl_exp (CALL_EXPR, list_length (arglist) + 3);
3320   CALL_EXPR_FN (t) = fn;
3321   CALL_EXPR_STATIC_CHAIN (t) = NULL_TREE;
3322   for (i = 0; arglist; arglist = TREE_CHAIN (arglist), i++)
3323     CALL_EXPR_ARG (t, i) = TREE_VALUE (arglist);
3324   return t;
3325 }
3326 \f
3327 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3328    We do NOT enter this node in any sort of symbol table.
3329
3330    layout_decl is used to set up the decl's storage layout.
3331    Other slots are initialized to 0 or null pointers.  */
3332
3333 tree
3334 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3335 {
3336   tree t;
3337
3338   t = make_node_stat (code PASS_MEM_STAT);
3339
3340 /*  if (type == error_mark_node)
3341     type = integer_type_node; */
3342 /* That is not done, deliberately, so that having error_mark_node
3343    as the type can suppress useless errors in the use of this variable.  */
3344
3345   DECL_NAME (t) = name;
3346   TREE_TYPE (t) = type;
3347
3348   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3349     layout_decl (t, 0);
3350
3351   return t;
3352 }
3353
3354 /* Builds and returns function declaration with NAME and TYPE.  */
3355
3356 tree
3357 build_fn_decl (const char *name, tree type)
3358 {
3359   tree id = get_identifier (name);
3360   tree decl = build_decl (FUNCTION_DECL, id, type);
3361
3362   DECL_EXTERNAL (decl) = 1;
3363   TREE_PUBLIC (decl) = 1;
3364   DECL_ARTIFICIAL (decl) = 1;
3365   TREE_NOTHROW (decl) = 1;
3366
3367   return decl;
3368 }
3369
3370 \f
3371 /* BLOCK nodes are used to represent the structure of binding contours
3372    and declarations, once those contours have been exited and their contents
3373    compiled.  This information is used for outputting debugging info.  */
3374
3375 tree
3376 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3377 {
3378   tree block = make_node (BLOCK);
3379
3380   BLOCK_VARS (block) = vars;
3381   BLOCK_SUBBLOCKS (block) = subblocks;
3382   BLOCK_SUPERCONTEXT (block) = supercontext;
3383   BLOCK_CHAIN (block) = chain;
3384   return block;
3385 }
3386
3387 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3388 /* ??? gengtype doesn't handle conditionals */
3389 static GTY(()) source_locus last_annotated_node;
3390 #endif
3391
3392 #ifdef USE_MAPPED_LOCATION
3393
3394 expanded_location
3395 expand_location (source_location loc)
3396 {
3397   expanded_location xloc;
3398   if (loc == 0)
3399     {
3400       xloc.file = NULL;
3401       xloc.line = 0;
3402       xloc.column = 0;
3403     }
3404   else
3405     {
3406       const struct line_map *map = linemap_lookup (line_table, loc);
3407       xloc.file = map->to_file;
3408       xloc.line = SOURCE_LINE (map, loc);
3409       xloc.column = SOURCE_COLUMN (map, loc);
3410     };
3411   return xloc;
3412 }
3413
3414 #else
3415
3416 /* Record the exact location where an expression or an identifier were
3417    encountered.  */
3418
3419 void
3420 annotate_with_file_line (tree node, const char *file, int line)
3421 {
3422   location_t *new_loc;
3423
3424   /* Roughly one percent of the calls to this function are to annotate
3425      a node with the same information already attached to that node!
3426      Just return instead of wasting memory.  */
3427   if (EXPR_LOCUS (node)
3428       && EXPR_LINENO (node) == line
3429       && (EXPR_FILENAME (node) == file
3430           || !strcmp (EXPR_FILENAME (node), file)))
3431     {
3432       last_annotated_node = EXPR_LOCUS (node);
3433       return;
3434     }
3435
3436   /* In heavily macroized code (such as GCC itself) this single
3437      entry cache can reduce the number of allocations by more
3438      than half.  */
3439   if (last_annotated_node
3440       && last_annotated_node->line == line
3441       && (last_annotated_node->file == file
3442           || !strcmp (last_annotated_node->file, file)))
3443     {
3444       SET_EXPR_LOCUS (node, last_annotated_node);
3445       return;
3446     }
3447
3448   new_loc = GGC_NEW (location_t);
3449   new_loc->file = file;
3450   new_loc->line = line;
3451   SET_EXPR_LOCUS (node, new_loc);
3452   last_annotated_node = new_loc;
3453 }
3454
3455 void
3456 annotate_with_locus (tree node, location_t locus)
3457 {
3458   annotate_with_file_line (node, locus.file, locus.line);
3459 }
3460 #endif
3461 \f
3462 /* Source location accessor functions.  */
3463
3464
3465 /* The source location of this expression.  Non-tree_exp nodes such as
3466    decls and constants can be shared among multiple locations, so
3467    return nothing.  */
3468 location_t
3469 expr_location (const_tree node)
3470 {
3471 #ifdef USE_MAPPED_LOCATION
3472   if (GIMPLE_STMT_P (node))
3473     return GIMPLE_STMT_LOCUS (node);
3474   return EXPR_P (node) ? node->exp.locus : UNKNOWN_LOCATION;
3475 #else
3476   if (GIMPLE_STMT_P (node))
3477     return EXPR_HAS_LOCATION (node)
3478       ? *GIMPLE_STMT_LOCUS (node) : UNKNOWN_LOCATION;
3479   return EXPR_HAS_LOCATION (node) ? *node->exp.locus : UNKNOWN_LOCATION;
3480 #endif
3481 }
3482
3483 void
3484 set_expr_location (tree node, location_t locus)
3485 {
3486 #ifdef USE_MAPPED_LOCATION
3487   if (GIMPLE_STMT_P (node))
3488     GIMPLE_STMT_LOCUS (node) = locus;
3489   else
3490     EXPR_CHECK (node)->exp.locus = locus;
3491 #else
3492       annotate_with_locus (node, locus);
3493 #endif
3494 }
3495
3496 bool
3497 expr_has_location (const_tree node)
3498 {
3499 #ifdef USE_MAPPED_LOCATION
3500   return expr_location (node) != UNKNOWN_LOCATION;
3501 #else
3502   return expr_locus (node) != NULL;
3503 #endif
3504 }
3505
3506 #ifdef USE_MAPPED_LOCATION
3507 source_location *
3508 #else
3509 source_locus
3510 #endif
3511 expr_locus (const_tree node)
3512 {
3513 #ifdef USE_MAPPED_LOCATION
3514   if (GIMPLE_STMT_P (node))
3515     return CONST_CAST (source_location *, &GIMPLE_STMT_LOCUS (node));
3516   return (EXPR_P (node)
3517           ? CONST_CAST (source_location *, &node->exp.locus)
3518           : (source_location *) NULL);
3519 #else
3520   if (GIMPLE_STMT_P (node))
3521     return GIMPLE_STMT_LOCUS (node);
3522   return EXPR_P (node) ? node->exp.locus : (source_locus) NULL;
3523 #endif
3524 }
3525
3526 void
3527 set_expr_locus (tree node,
3528 #ifdef USE_MAPPED_LOCATION
3529                 source_location *loc
3530 #else
3531                 source_locus loc
3532 #endif
3533                 )
3534 {
3535 #ifdef USE_MAPPED_LOCATION
3536   if (loc == NULL)
3537     {
3538       if (GIMPLE_STMT_P (node))
3539         GIMPLE_STMT_LOCUS (node) = UNKNOWN_LOCATION;
3540       else
3541         EXPR_CHECK (node)->exp.locus = UNKNOWN_LOCATION;
3542     }
3543   else
3544     {
3545       if (GIMPLE_STMT_P (node))
3546         GIMPLE_STMT_LOCUS (node) = *loc;
3547       else
3548         EXPR_CHECK (node)->exp.locus = *loc;
3549     }
3550 #else
3551   if (GIMPLE_STMT_P (node))
3552     GIMPLE_STMT_LOCUS (node) = loc;
3553   else
3554     EXPR_CHECK (node)->exp.locus = loc;
3555 #endif
3556 }
3557
3558 /* Return the file name of the location of NODE.  */
3559 const char *
3560 expr_filename (const_tree node)
3561 {
3562   if (GIMPLE_STMT_P (node))
3563     return LOCATION_FILE (location_from_locus (GIMPLE_STMT_LOCUS (node)));
3564   return LOCATION_FILE (location_from_locus (EXPR_CHECK (node)->exp.locus));
3565 }
3566
3567 /* Return the line number of the location of NODE.  */
3568 int
3569 expr_lineno (const_tree node)
3570 {
3571   if (GIMPLE_STMT_P (node))
3572     return LOCATION_LINE (location_from_locus (GIMPLE_STMT_LOCUS (node)));
3573   return LOCATION_LINE (location_from_locus (EXPR_CHECK (node)->exp.locus));
3574 }
3575
3576 \f
3577 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3578    is ATTRIBUTE.  */
3579
3580 tree
3581 build_decl_attribute_variant (tree ddecl, tree attribute)
3582 {
3583   DECL_ATTRIBUTES (ddecl) = attribute;
3584   return ddecl;
3585 }
3586
3587 /* Borrowed from hashtab.c iterative_hash implementation.  */
3588 #define mix(a,b,c) \
3589 { \
3590   a -= b; a -= c; a ^= (c>>13); \
3591   b -= c; b -= a; b ^= (a<< 8); \
3592   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3593   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3594   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3595   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3596   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3597   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3598   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3599 }
3600
3601
3602 /* Produce good hash value combining VAL and VAL2.  */
3603 static inline hashval_t
3604 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3605 {
3606   /* the golden ratio; an arbitrary value.  */
3607   hashval_t a = 0x9e3779b9;
3608
3609   mix (a, val, val2);
3610   return val2;
3611 }
3612
3613 /* Produce good hash value combining PTR and VAL2.  */
3614 static inline hashval_t
3615 iterative_hash_pointer (const void *ptr, hashval_t val2)
3616 {
3617   if (sizeof (ptr) == sizeof (hashval_t))
3618     return iterative_hash_hashval_t ((size_t) ptr, val2);
3619   else
3620     {
3621       hashval_t a = (hashval_t) (size_t) ptr;
3622       /* Avoid warnings about shifting of more than the width of the type on
3623          hosts that won't execute this path.  */
3624       int zero = 0;
3625       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3626       mix (a, b, val2);
3627       return val2;
3628     }
3629 }
3630
3631 /* Produce good hash value combining VAL and VAL2.  */
3632 static inline hashval_t
3633 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3634 {
3635   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3636     return iterative_hash_hashval_t (val, val2);
3637   else
3638     {
3639       hashval_t a = (hashval_t) val;
3640       /* Avoid warnings about shifting of more than the width of the type on
3641          hosts that won't execute this path.  */
3642       int zero = 0;
3643       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3644       mix (a, b, val2);
3645       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3646         {
3647           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3648           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3649           mix (a, b, val2);
3650         }
3651       return val2;
3652     }
3653 }
3654
3655 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3656    is ATTRIBUTE and its qualifiers are QUALS.
3657
3658    Record such modified types already made so we don't make duplicates.  */
3659
3660 static tree
3661 build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
3662 {
3663   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3664     {
3665       hashval_t hashcode = 0;
3666       tree ntype;
3667       enum tree_code code = TREE_CODE (ttype);
3668
3669       /* Building a distinct copy of a tagged type is inappropriate; it
3670          causes breakage in code that expects there to be a one-to-one
3671          relationship between a struct and its fields.
3672          build_duplicate_type is another solution (as used in
3673          handle_transparent_union_attribute), but that doesn't play well
3674          with the stronger C++ type identity model.  */
3675       if (TREE_CODE (ttype) == RECORD_TYPE
3676           || TREE_CODE (ttype) == UNION_TYPE
3677           || TREE_CODE (ttype) == QUAL_UNION_TYPE
3678           || TREE_CODE (ttype) == ENUMERAL_TYPE)
3679         {
3680           warning (OPT_Wattributes,
3681                    "ignoring attributes applied to %qT after definition",
3682                    TYPE_MAIN_VARIANT (ttype));
3683           return build_qualified_type (ttype, quals);
3684         }
3685
3686       ntype = build_distinct_type_copy (ttype);
3687
3688       TYPE_ATTRIBUTES (ntype) = attribute;
3689       set_type_quals (ntype, TYPE_UNQUALIFIED);
3690
3691       hashcode = iterative_hash_object (code, hashcode);
3692       if (TREE_TYPE (ntype))
3693         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3694                                           hashcode);
3695       hashcode = attribute_hash_list (attribute, hashcode);
3696
3697       switch (TREE_CODE (ntype))
3698         {
3699         case FUNCTION_TYPE:
3700           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3701           break;
3702         case ARRAY_TYPE:
3703           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3704                                             hashcode);
3705           break;
3706         case INTEGER_TYPE:
3707           hashcode = iterative_hash_object
3708             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3709           hashcode = iterative_hash_object
3710             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3711           break;
3712         case REAL_TYPE:
3713         case FIXED_POINT_TYPE:
3714           {
3715             unsigned int precision = TYPE_PRECISION (ntype);
3716             hashcode = iterative_hash_object (precision, hashcode);
3717           }
3718           break;
3719         default:
3720           break;
3721         }
3722
3723       ntype = type_hash_canon (hashcode, ntype);
3724
3725       /* If the target-dependent attributes make NTYPE different from
3726          its canonical type, we will need to use structural equality
3727          checks for this qualified type. */
3728       ttype = build_qualified_type (ttype, TYPE_UNQUALIFIED);
3729       if (TYPE_STRUCTURAL_EQUALITY_P (ttype)
3730           || !targetm.comp_type_attributes (ntype, ttype))
3731         SET_TYPE_STRUCTURAL_EQUALITY (ntype);
3732       else
3733         TYPE_CANONICAL (ntype) = TYPE_CANONICAL (ttype);
3734
3735       ttype = build_qualified_type (ntype, quals);
3736     }
3737
3738   return ttype;
3739 }
3740
3741
3742 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3743    is ATTRIBUTE.
3744
3745    Record such modified types already made so we don't make duplicates.  */
3746
3747 tree
3748 build_type_attribute_variant (tree ttype, tree attribute)
3749 {
3750   return build_type_attribute_qual_variant (ttype, attribute,
3751                                             TYPE_QUALS (ttype));
3752 }
3753
3754 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3755    or zero if not.
3756
3757    We try both `text' and `__text__', ATTR may be either one.  */
3758 /* ??? It might be a reasonable simplification to require ATTR to be only
3759    `text'.  One might then also require attribute lists to be stored in
3760    their canonicalized form.  */
3761
3762 static int
3763 is_attribute_with_length_p (const char *attr, int attr_len, const_tree ident)
3764 {
3765   int ident_len;
3766   const char *p;