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