gcc/gimple.c

   1 /* Gimple IR support functions.
   2
   3    Copyright 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
   4    Contributed by Aldy Hernandez <aldyh@redhat.com>
   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 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "target.h"
  27 #include "tree.h"
  28 #include "ggc.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "gimple.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "value-prof.h"
  35 #include "flags.h"
  36 #include "alias.h"
  37 #include "demangle.h"
  38 #include "langhooks.h"
  39
  40 /* Global type table.  FIXME lto, it should be possible to re-use some
  41    of the type hashing routines in tree.c (type_hash_canon, type_hash_lookup,
  42    etc), but those assume that types were built with the various
  43    build_*_type routines which is not the case with the streamer.  */
  44 static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
  45   htab_t gimple_types;
  46 static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
  47   htab_t gimple_canonical_types;
  48 static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
  49   htab_t type_hash_cache;
  50 static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
  51   htab_t canonical_type_hash_cache;
  52
  53 /* All the tuples have their operand vector (if present) at the very bottom
  54    of the structure.  Therefore, the offset required to find the
  55    operands vector the size of the structure minus the size of the 1
  56    element tree array at the end (see gimple_ops).  */
  57 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) \
  58         (HAS_TREE_OP ? sizeof (struct STRUCT) - sizeof (tree) : 0),
  59 EXPORTED_CONST size_t gimple_ops_offset_[] = {
  60 #include "gsstruct.def"
  61 };
  62 #undef DEFGSSTRUCT
  63
  64 #define DEFGSSTRUCT(SYM, STRUCT, HAS_TREE_OP) sizeof(struct STRUCT),
  65 static const size_t gsstruct_code_size[] = {
  66 #include "gsstruct.def"
  67 };
  68 #undef DEFGSSTRUCT
  69
  70 #define DEFGSCODE(SYM, NAME, GSSCODE)   NAME,
  71 const char *const gimple_code_name[] = {
  72 #include "gimple.def"
  73 };
  74 #undef DEFGSCODE
  75
  76 #define DEFGSCODE(SYM, NAME, GSSCODE)   GSSCODE,
  77 EXPORTED_CONST enum gimple_statement_structure_enum gss_for_code_[] = {
  78 #include "gimple.def"
  79 };
  80 #undef DEFGSCODE
  81
  82 #ifdef GATHER_STATISTICS
  83 /* Gimple stats.  */
  84
  85 int gimple_alloc_counts[(int) gimple_alloc_kind_all];
  86 int gimple_alloc_sizes[(int) gimple_alloc_kind_all];
  87
  88 /* Keep in sync with gimple.h:enum gimple_alloc_kind.  */
  89 static const char * const gimple_alloc_kind_names[] = {
  90     "assignments",
  91     "phi nodes",
  92     "conditionals",
  93     "sequences",
  94     "everything else"
  95 };
  96
  97 #endif /* GATHER_STATISTICS */
  98
  99 /* A cache of gimple_seq objects.  Sequences are created and destroyed
 100    fairly often during gimplification.  */
 101 static GTY ((deletable)) struct gimple_seq_d *gimple_seq_cache;
 102
 103 /* Private API manipulation functions shared only with some
 104    other files.  */
 105 extern void gimple_set_stored_syms (gimple, bitmap, bitmap_obstack *);
 106 extern void gimple_set_loaded_syms (gimple, bitmap, bitmap_obstack *);
 107
 108 /* Gimple tuple constructors.
 109    Note: Any constructor taking a ``gimple_seq'' as a parameter, can
 110    be passed a NULL to start with an empty sequence.  */
 111
 112 /* Set the code for statement G to CODE.  */
 113
 114 static inline void
 115 gimple_set_code (gimple g, enum gimple_code code)
 116 {
 117   g->gsbase.code = code;
 118 }
 119
 120 /* Return the number of bytes needed to hold a GIMPLE statement with
 121    code CODE.  */
 122
 123 static inline size_t
 124 gimple_size (enum gimple_code code)
 125 {
 126   return gsstruct_code_size[gss_for_code (code)];
 127 }
 128
 129 /* Allocate memory for a GIMPLE statement with code CODE and NUM_OPS
 130    operands.  */
 131
 132 gimple
 133 gimple_alloc_stat (enum gimple_code code, unsigned num_ops MEM_STAT_DECL)
 134 {
 135   size_t size;
 136   gimple stmt;
 137
 138   size = gimple_size (code);
 139   if (num_ops > 0)
 140     size += sizeof (tree) * (num_ops - 1);
 141
 142 #ifdef GATHER_STATISTICS
 143   {
 144     enum gimple_alloc_kind kind = gimple_alloc_kind (code);
 145     gimple_alloc_counts[(int) kind]++;
 146     gimple_alloc_sizes[(int) kind] += size;
 147   }
 148 #endif
 149
 150   stmt = ggc_alloc_cleared_gimple_statement_d_stat (size PASS_MEM_STAT);
 151   gimple_set_code (stmt, code);
 152   gimple_set_num_ops (stmt, num_ops);
 153
 154   /* Do not call gimple_set_modified here as it has other side
 155      effects and this tuple is still not completely built.  */
 156   stmt->gsbase.modified = 1;
 157
 158   return stmt;
 159 }
 160
 161 /* Set SUBCODE to be the code of the expression computed by statement G.  */
 162
 163 static inline void
 164 gimple_set_subcode (gimple g, unsigned subcode)
 165 {
 166   /* We only have 16 bits for the RHS code.  Assert that we are not
 167      overflowing it.  */
 168   gcc_assert (subcode < (1 << 16));
 169   g->gsbase.subcode = subcode;
 170 }
 171
 172
 173
 174 /* Build a tuple with operands.  CODE is the statement to build (which
 175    must be one of the GIMPLE_WITH_OPS tuples).  SUBCODE is the sub-code
 176    for the new tuple.  NUM_OPS is the number of operands to allocate.  */
 177
 178 #define gimple_build_with_ops(c, s, n) \
 179   gimple_build_with_ops_stat (c, s, n MEM_STAT_INFO)
 180
 181 static gimple
 182 gimple_build_with_ops_stat (enum gimple_code code, unsigned subcode,
 183                             unsigned num_ops MEM_STAT_DECL)
 184 {
 185   gimple s = gimple_alloc_stat (code, num_ops PASS_MEM_STAT);
 186   gimple_set_subcode (s, subcode);
 187
 188   return s;
 189 }
 190
 191
 192 /* Build a GIMPLE_RETURN statement returning RETVAL.  */
 193
 194 gimple
 195 gimple_build_return (tree retval)
 196 {
 197   gimple s = gimple_build_with_ops (GIMPLE_RETURN, ERROR_MARK, 1);
 198   if (retval)
 199     gimple_return_set_retval (s, retval);
 200   return s;
 201 }
 202
 203 /* Reset alias information on call S.  */
 204
 205 void
 206 gimple_call_reset_alias_info (gimple s)
 207 {
 208   if (gimple_call_flags (s) & ECF_CONST)
 209     memset (gimple_call_use_set (s), 0, sizeof (struct pt_solution));
 210   else
 211     pt_solution_reset (gimple_call_use_set (s));
 212   if (gimple_call_flags (s) & (ECF_CONST|ECF_PURE|ECF_NOVOPS))
 213     memset (gimple_call_clobber_set (s), 0, sizeof (struct pt_solution));
 214   else
 215     pt_solution_reset (gimple_call_clobber_set (s));
 216 }
 217
 218 /* Helper for gimple_build_call, gimple_build_call_vec and
 219    gimple_build_call_from_tree.  Build the basic components of a
 220    GIMPLE_CALL statement to function FN with NARGS arguments.  */
 221
 222 static inline gimple
 223 gimple_build_call_1 (tree fn, unsigned nargs)
 224 {
 225   gimple s = gimple_build_with_ops (GIMPLE_CALL, ERROR_MARK, nargs + 3);
 226   if (TREE_CODE (fn) == FUNCTION_DECL)
 227     fn = build_fold_addr_expr (fn);
 228   gimple_set_op (s, 1, fn);
 229   gimple_call_set_fntype (s, TREE_TYPE (TREE_TYPE (fn)));
 230   gimple_call_reset_alias_info (s);
 231   return s;
 232 }
 233
 234
 235 /* Build a GIMPLE_CALL statement to function FN with the arguments
 236    specified in vector ARGS.  */
 237
 238 gimple
 239 gimple_build_call_vec (tree fn, VEC(tree, heap) *args)
 240 {
 241   unsigned i;
 242   unsigned nargs = VEC_length (tree, args);
 243   gimple call = gimple_build_call_1 (fn, nargs);
 244
 245   for (i = 0; i < nargs; i++)
 246     gimple_call_set_arg (call, i, VEC_index (tree, args, i));
 247
 248   return call;
 249 }
 250
 251
 252 /* Build a GIMPLE_CALL statement to function FN.  NARGS is the number of
 253    arguments.  The ... are the arguments.  */
 254
 255 gimple
 256 gimple_build_call (tree fn, unsigned nargs, ...)
 257 {
 258   va_list ap;
 259   gimple call;
 260   unsigned i;
 261
 262   gcc_assert (TREE_CODE (fn) == FUNCTION_DECL || is_gimple_call_addr (fn));
 263
 264   call = gimple_build_call_1 (fn, nargs);
 265
 266   va_start (ap, nargs);
 267   for (i = 0; i < nargs; i++)
 268     gimple_call_set_arg (call, i, va_arg (ap, tree));
 269   va_end (ap);
 270
 271   return call;
 272 }
 273
 274
 275 /* Helper for gimple_build_call_internal and gimple_build_call_internal_vec.
 276    Build the basic components of a GIMPLE_CALL statement to internal
 277    function FN with NARGS arguments.  */
 278
 279 static inline gimple
 280 gimple_build_call_internal_1 (enum internal_fn fn, unsigned nargs)
 281 {
 282   gimple s = gimple_build_with_ops (GIMPLE_CALL, ERROR_MARK, nargs + 3);
 283   s->gsbase.subcode |= GF_CALL_INTERNAL;
 284   gimple_call_set_internal_fn (s, fn);
 285   gimple_call_reset_alias_info (s);
 286   return s;
 287 }
 288
 289
 290 /* Build a GIMPLE_CALL statement to internal function FN.  NARGS is
 291    the number of arguments.  The ... are the arguments.  */
 292
 293 gimple
 294 gimple_build_call_internal (enum internal_fn fn, unsigned nargs, ...)
 295 {
 296   va_list ap;
 297   gimple call;
 298   unsigned i;
 299
 300   call = gimple_build_call_internal_1 (fn, nargs);
 301   va_start (ap, nargs);
 302   for (i = 0; i < nargs; i++)
 303     gimple_call_set_arg (call, i, va_arg (ap, tree));
 304   va_end (ap);
 305
 306   return call;
 307 }
 308
 309
 310 /* Build a GIMPLE_CALL statement to internal function FN with the arguments
 311    specified in vector ARGS.  */
 312
 313 gimple
 314 gimple_build_call_internal_vec (enum internal_fn fn, VEC(tree, heap) *args)
 315 {
 316   unsigned i, nargs;
 317   gimple call;
 318
 319   nargs = VEC_length (tree, args);
 320   call = gimple_build_call_internal_1 (fn, nargs);
 321   for (i = 0; i < nargs; i++)
 322     gimple_call_set_arg (call, i, VEC_index (tree, args, i));
 323
 324   return call;
 325 }
 326
 327
 328 /* Build a GIMPLE_CALL statement from CALL_EXPR T.  Note that T is
 329    assumed to be in GIMPLE form already.  Minimal checking is done of
 330    this fact.  */
 331
 332 gimple
 333 gimple_build_call_from_tree (tree t)
 334 {
 335   unsigned i, nargs;
 336   gimple call;
 337   tree fndecl = get_callee_fndecl (t);
 338
 339   gcc_assert (TREE_CODE (t) == CALL_EXPR);
 340
 341   nargs = call_expr_nargs (t);
 342   call = gimple_build_call_1 (fndecl ? fndecl : CALL_EXPR_FN (t), nargs);
 343
 344   for (i = 0; i < nargs; i++)
 345     gimple_call_set_arg (call, i, CALL_EXPR_ARG (t, i));
 346
 347   gimple_set_block (call, TREE_BLOCK (t));
 348
 349   /* Carry all the CALL_EXPR flags to the new GIMPLE_CALL.  */
 350   gimple_call_set_chain (call, CALL_EXPR_STATIC_CHAIN (t));
 351   gimple_call_set_tail (call, CALL_EXPR_TAILCALL (t));
 352   gimple_call_set_cannot_inline (call, CALL_CANNOT_INLINE_P (t));
 353   gimple_call_set_return_slot_opt (call, CALL_EXPR_RETURN_SLOT_OPT (t));
 354   if (fndecl
 355       && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 356       && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA)
 357     gimple_call_set_alloca_for_var (call, CALL_ALLOCA_FOR_VAR_P (t));
 358   else
 359     gimple_call_set_from_thunk (call, CALL_FROM_THUNK_P (t));
 360   gimple_call_set_va_arg_pack (call, CALL_EXPR_VA_ARG_PACK (t));
 361   gimple_call_set_nothrow (call, TREE_NOTHROW (t));
 362   gimple_set_no_warning (call, TREE_NO_WARNING (t));
 363
 364   return call;
 365 }
 366
 367
 368 /* Extract the operands and code for expression EXPR into *SUBCODE_P,
 369    *OP1_P, *OP2_P and *OP3_P respectively.  */
 370
 371 void
 372 extract_ops_from_tree_1 (tree expr, enum tree_code *subcode_p, tree *op1_p,
 373                          tree *op2_p, tree *op3_p)
 374 {
 375   enum gimple_rhs_class grhs_class;
 376
 377   *subcode_p = TREE_CODE (expr);
 378   grhs_class = get_gimple_rhs_class (*subcode_p);
 379
 380   if (grhs_class == GIMPLE_TERNARY_RHS)
 381     {
 382       *op1_p = TREE_OPERAND (expr, 0);
 383       *op2_p = TREE_OPERAND (expr, 1);
 384       *op3_p = TREE_OPERAND (expr, 2);
 385     }
 386   else if (grhs_class == GIMPLE_BINARY_RHS)
 387     {
 388       *op1_p = TREE_OPERAND (expr, 0);
 389       *op2_p = TREE_OPERAND (expr, 1);
 390       *op3_p = NULL_TREE;
 391     }
 392   else if (grhs_class == GIMPLE_UNARY_RHS)
 393     {
 394       *op1_p = TREE_OPERAND (expr, 0);
 395       *op2_p = NULL_TREE;
 396       *op3_p = NULL_TREE;
 397     }
 398   else if (grhs_class == GIMPLE_SINGLE_RHS)
 399     {
 400       *op1_p = expr;
 401       *op2_p = NULL_TREE;
 402       *op3_p = NULL_TREE;
 403     }
 404   else
 405     gcc_unreachable ();
 406 }
 407
 408
 409 /* Build a GIMPLE_ASSIGN statement.
 410
 411    LHS of the assignment.
 412    RHS of the assignment which can be unary or binary.  */
 413
 414 gimple
 415 gimple_build_assign_stat (tree lhs, tree rhs MEM_STAT_DECL)
 416 {
 417   enum tree_code subcode;
 418   tree op1, op2, op3;
 419
 420   extract_ops_from_tree_1 (rhs, &subcode, &op1, &op2, &op3);
 421   return gimple_build_assign_with_ops_stat (subcode, lhs, op1, op2, op3
 422                                             PASS_MEM_STAT);
 423 }
 424
 425
 426 /* Build a GIMPLE_ASSIGN statement with sub-code SUBCODE and operands
 427    OP1 and OP2.  If OP2 is NULL then SUBCODE must be of class
 428    GIMPLE_UNARY_RHS or GIMPLE_SINGLE_RHS.  */
 429
 430 gimple
 431 gimple_build_assign_with_ops_stat (enum tree_code subcode, tree lhs, tree op1,
 432                                    tree op2, tree op3 MEM_STAT_DECL)
 433 {
 434   unsigned num_ops;
 435   gimple p;
 436
 437   /* Need 1 operand for LHS and 1 or 2 for the RHS (depending on the
 438      code).  */
 439   num_ops = get_gimple_rhs_num_ops (subcode) + 1;
 440
 441   p = gimple_build_with_ops_stat (GIMPLE_ASSIGN, (unsigned)subcode, num_ops
 442                                   PASS_MEM_STAT);
 443   gimple_assign_set_lhs (p, lhs);
 444   gimple_assign_set_rhs1 (p, op1);
 445   if (op2)
 446     {
 447       gcc_assert (num_ops > 2);
 448       gimple_assign_set_rhs2 (p, op2);
 449     }
 450
 451   if (op3)
 452     {
 453       gcc_assert (num_ops > 3);
 454       gimple_assign_set_rhs3 (p, op3);
 455     }
 456
 457   return p;
 458 }
 459
 460
 461 /* Build a new GIMPLE_ASSIGN tuple and append it to the end of *SEQ_P.
 462
 463    DST/SRC are the destination and source respectively.  You can pass
 464    ungimplified trees in DST or SRC, in which case they will be
 465    converted to a gimple operand if necessary.
 466
 467    This function returns the newly created GIMPLE_ASSIGN tuple.  */
 468
 469 gimple
 470 gimplify_assign (tree dst, tree src, gimple_seq *seq_p)
 471 {
 472   tree t = build2 (MODIFY_EXPR, TREE_TYPE (dst), dst, src);
 473   gimplify_and_add (t, seq_p);
 474   ggc_free (t);
 475   return gimple_seq_last_stmt (*seq_p);
 476 }
 477
 478
 479 /* Build a GIMPLE_COND statement.
 480
 481    PRED is the condition used to compare LHS and the RHS.
 482    T_LABEL is the label to jump to if the condition is true.
 483    F_LABEL is the label to jump to otherwise.  */
 484
 485 gimple
 486 gimple_build_cond (enum tree_code pred_code, tree lhs, tree rhs,
 487                    tree t_label, tree f_label)
 488 {
 489   gimple p;
 490
 491   gcc_assert (TREE_CODE_CLASS (pred_code) == tcc_comparison);
 492   p = gimple_build_with_ops (GIMPLE_COND, pred_code, 4);
 493   gimple_cond_set_lhs (p, lhs);
 494   gimple_cond_set_rhs (p, rhs);
 495   gimple_cond_set_true_label (p, t_label);
 496   gimple_cond_set_false_label (p, f_label);
 497   return p;
 498 }
 499
 500
 501 /* Extract operands for a GIMPLE_COND statement out of COND_EXPR tree COND.  */
 502
 503 void
 504 gimple_cond_get_ops_from_tree (tree cond, enum tree_code *code_p,
 505                                tree *lhs_p, tree *rhs_p)
 506 {
 507   gcc_assert (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
 508               || TREE_CODE (cond) == TRUTH_NOT_EXPR
 509               || is_gimple_min_invariant (cond)
 510               || SSA_VAR_P (cond));
 511
 512   extract_ops_from_tree (cond, code_p, lhs_p, rhs_p);
 513
 514   /* Canonicalize conditionals of the form 'if (!VAL)'.  */
 515   if (*code_p == TRUTH_NOT_EXPR)
 516     {
 517       *code_p = EQ_EXPR;
 518       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
 519       *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
 520     }
 521   /* Canonicalize conditionals of the form 'if (VAL)'  */
 522   else if (TREE_CODE_CLASS (*code_p) != tcc_comparison)
 523     {
 524       *code_p = NE_EXPR;
 525       gcc_assert (*lhs_p && *rhs_p == NULL_TREE);
 526       *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
 527     }
 528 }
 529
 530
 531 /* Build a GIMPLE_COND statement from the conditional expression tree
 532    COND.  T_LABEL and F_LABEL are as in gimple_build_cond.  */
 533
 534 gimple
 535 gimple_build_cond_from_tree (tree cond, tree t_label, tree f_label)
 536 {
 537   enum tree_code code;
 538   tree lhs, rhs;
 539
 540   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
 541   return gimple_build_cond (code, lhs, rhs, t_label, f_label);
 542 }
 543
 544 /* Set code, lhs, and rhs of a GIMPLE_COND from a suitable
 545    boolean expression tree COND.  */
 546
 547 void
 548 gimple_cond_set_condition_from_tree (gimple stmt, tree cond)
 549 {
 550   enum tree_code code;
 551   tree lhs, rhs;
 552
 553   gimple_cond_get_ops_from_tree (cond, &code, &lhs, &rhs);
 554   gimple_cond_set_condition (stmt, code, lhs, rhs);
 555 }
 556
 557 /* Build a GIMPLE_LABEL statement for LABEL.  */
 558
 559 gimple
 560 gimple_build_label (tree label)
 561 {
 562   gimple p = gimple_build_with_ops (GIMPLE_LABEL, ERROR_MARK, 1);
 563   gimple_label_set_label (p, label);
 564   return p;
 565 }
 566
 567 /* Build a GIMPLE_GOTO statement to label DEST.  */
 568
 569 gimple
 570 gimple_build_goto (tree dest)
 571 {
 572   gimple p = gimple_build_with_ops (GIMPLE_GOTO, ERROR_MARK, 1);
 573   gimple_goto_set_dest (p, dest);
 574   return p;
 575 }
 576
 577
 578 /* Build a GIMPLE_NOP statement.  */
 579
 580 gimple
 581 gimple_build_nop (void)
 582 {
 583   return gimple_alloc (GIMPLE_NOP, 0);
 584 }
 585
 586
 587 /* Build a GIMPLE_BIND statement.
 588    VARS are the variables in BODY.
 589    BLOCK is the containing block.  */
 590
 591 gimple
 592 gimple_build_bind (tree vars, gimple_seq body, tree block)
 593 {
 594   gimple p = gimple_alloc (GIMPLE_BIND, 0);
 595   gimple_bind_set_vars (p, vars);
 596   if (body)
 597     gimple_bind_set_body (p, body);
 598   if (block)
 599     gimple_bind_set_block (p, block);
 600   return p;
 601 }
 602
 603 /* Helper function to set the simple fields of a asm stmt.
 604
 605    STRING is a pointer to a string that is the asm blocks assembly code.
 606    NINPUT is the number of register inputs.
 607    NOUTPUT is the number of register outputs.
 608    NCLOBBERS is the number of clobbered registers.
 609    */
 610
 611 static inline gimple
 612 gimple_build_asm_1 (const char *string, unsigned ninputs, unsigned noutputs,
 613                     unsigned nclobbers, unsigned nlabels)
 614 {
 615   gimple p;
 616   int size = strlen (string);
 617
 618   /* ASMs with labels cannot have outputs.  This should have been
 619      enforced by the front end.  */
 620   gcc_assert (nlabels == 0 || noutputs == 0);
 621
 622   p = gimple_build_with_ops (GIMPLE_ASM, ERROR_MARK,
 623                              ninputs + noutputs + nclobbers + nlabels);
 624
 625   p->gimple_asm.ni = ninputs;
 626   p->gimple_asm.no = noutputs;
 627   p->gimple_asm.nc = nclobbers;
 628   p->gimple_asm.nl = nlabels;
 629   p->gimple_asm.string = ggc_alloc_string (string, size);
 630
 631 #ifdef GATHER_STATISTICS
 632   gimple_alloc_sizes[(int) gimple_alloc_kind (GIMPLE_ASM)] += size;
 633 #endif
 634
 635   return p;
 636 }
 637
 638 /* Build a GIMPLE_ASM statement.
 639
 640    STRING is the assembly code.
 641    NINPUT is the number of register inputs.
 642    NOUTPUT is the number of register outputs.
 643    NCLOBBERS is the number of clobbered registers.
 644    INPUTS is a vector of the input register parameters.
 645    OUTPUTS is a vector of the output register parameters.
 646    CLOBBERS is a vector of the clobbered register parameters.
 647    LABELS is a vector of destination labels.  */
 648
 649 gimple
 650 gimple_build_asm_vec (const char *string, VEC(tree,gc)* inputs,
 651                       VEC(tree,gc)* outputs, VEC(tree,gc)* clobbers,
 652                       VEC(tree,gc)* labels)
 653 {
 654   gimple p;
 655   unsigned i;
 656
 657   p = gimple_build_asm_1 (string,
 658                           VEC_length (tree, inputs),
 659                           VEC_length (tree, outputs),
 660                           VEC_length (tree, clobbers),
 661                           VEC_length (tree, labels));
 662
 663   for (i = 0; i < VEC_length (tree, inputs); i++)
 664     gimple_asm_set_input_op (p, i, VEC_index (tree, inputs, i));
 665
 666   for (i = 0; i < VEC_length (tree, outputs); i++)
 667     gimple_asm_set_output_op (p, i, VEC_index (tree, outputs, i));
 668
 669   for (i = 0; i < VEC_length (tree, clobbers); i++)
 670     gimple_asm_set_clobber_op (p, i, VEC_index (tree, clobbers, i));
 671
 672   for (i = 0; i < VEC_length (tree, labels); i++)
 673     gimple_asm_set_label_op (p, i, VEC_index (tree, labels, i));
 674
 675   return p;
 676 }
 677
 678 /* Build a GIMPLE_CATCH statement.
 679
 680   TYPES are the catch types.
 681   HANDLER is the exception handler.  */
 682
 683 gimple
 684 gimple_build_catch (tree types, gimple_seq handler)
 685 {
 686   gimple p = gimple_alloc (GIMPLE_CATCH, 0);
 687   gimple_catch_set_types (p, types);
 688   if (handler)
 689     gimple_catch_set_handler (p, handler);
 690
 691   return p;
 692 }
 693
 694 /* Build a GIMPLE_EH_FILTER statement.
 695
 696    TYPES are the filter's types.
 697    FAILURE is the filter's failure action.  */
 698
 699 gimple
 700 gimple_build_eh_filter (tree types, gimple_seq failure)
 701 {
 702   gimple p = gimple_alloc (GIMPLE_EH_FILTER, 0);
 703   gimple_eh_filter_set_types (p, types);
 704   if (failure)
 705     gimple_eh_filter_set_failure (p, failure);
 706
 707   return p;
 708 }
 709
 710 /* Build a GIMPLE_EH_MUST_NOT_THROW statement.  */
 711
 712 gimple
 713 gimple_build_eh_must_not_throw (tree decl)
 714 {
 715   gimple p = gimple_alloc (GIMPLE_EH_MUST_NOT_THROW, 0);
 716
 717   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 718   gcc_assert (flags_from_decl_or_type (decl) & ECF_NORETURN);
 719   gimple_eh_must_not_throw_set_fndecl (p, decl);
 720
 721   return p;
 722 }
 723
 724 /* Build a GIMPLE_TRY statement.
 725
 726    EVAL is the expression to evaluate.
 727    CLEANUP is the cleanup expression.
 728    KIND is either GIMPLE_TRY_CATCH or GIMPLE_TRY_FINALLY depending on
 729    whether this is a try/catch or a try/finally respectively.  */
 730
 731 gimple
 732 gimple_build_try (gimple_seq eval, gimple_seq cleanup,
 733                   enum gimple_try_flags kind)
 734 {
 735   gimple p;
 736
 737   gcc_assert (kind == GIMPLE_TRY_CATCH || kind == GIMPLE_TRY_FINALLY);
 738   p = gimple_alloc (GIMPLE_TRY, 0);
 739   gimple_set_subcode (p, kind);
 740   if (eval)
 741     gimple_try_set_eval (p, eval);
 742   if (cleanup)
 743     gimple_try_set_cleanup (p, cleanup);
 744
 745   return p;
 746 }
 747
 748 /* Construct a GIMPLE_WITH_CLEANUP_EXPR statement.
 749
 750    CLEANUP is the cleanup expression.  */
 751
 752 gimple
 753 gimple_build_wce (gimple_seq cleanup)
 754 {
 755   gimple p = gimple_alloc (GIMPLE_WITH_CLEANUP_EXPR, 0);
 756   if (cleanup)
 757     gimple_wce_set_cleanup (p, cleanup);
 758
 759   return p;
 760 }
 761
 762
 763 /* Build a GIMPLE_RESX statement.  */
 764
 765 gimple
 766 gimple_build_resx (int region)
 767 {
 768   gimple p = gimple_build_with_ops (GIMPLE_RESX, ERROR_MARK, 0);
 769   p->gimple_eh_ctrl.region = region;
 770   return p;
 771 }
 772
 773
 774 /* The helper for constructing a gimple switch statement.
 775    INDEX is the switch's index.
 776    NLABELS is the number of labels in the switch excluding the default.
 777    DEFAULT_LABEL is the default label for the switch statement.  */
 778
 779 gimple
 780 gimple_build_switch_nlabels (unsigned nlabels, tree index, tree default_label)
 781 {
 782   /* nlabels + 1 default label + 1 index.  */
 783   gimple p = gimple_build_with_ops (GIMPLE_SWITCH, ERROR_MARK,
 784                                     1 + (default_label != NULL) + nlabels);
 785   gimple_switch_set_index (p, index);
 786   if (default_label)
 787     gimple_switch_set_default_label (p, default_label);
 788   return p;
 789 }
 790
 791
 792 /* Build a GIMPLE_SWITCH statement.
 793
 794    INDEX is the switch's index.
 795    NLABELS is the number of labels in the switch excluding the DEFAULT_LABEL.
 796    ... are the labels excluding the default.  */
 797
 798 gimple
 799 gimple_build_switch (unsigned nlabels, tree index, tree default_label, ...)
 800 {
 801   va_list al;
 802   unsigned i, offset;
 803   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
 804
 805   /* Store the rest of the labels.  */
 806   va_start (al, default_label);
 807   offset = (default_label != NULL);
 808   for (i = 0; i < nlabels; i++)
 809     gimple_switch_set_label (p, i + offset, va_arg (al, tree));
 810   va_end (al);
 811
 812   return p;
 813 }
 814
 815
 816 /* Build a GIMPLE_SWITCH statement.
 817
 818    INDEX is the switch's index.
 819    DEFAULT_LABEL is the default label
 820    ARGS is a vector of labels excluding the default.  */
 821
 822 gimple
 823 gimple_build_switch_vec (tree index, tree default_label, VEC(tree, heap) *args)
 824 {
 825   unsigned i, offset, nlabels = VEC_length (tree, args);
 826   gimple p = gimple_build_switch_nlabels (nlabels, index, default_label);
 827
 828   /* Copy the labels from the vector to the switch statement.  */
 829   offset = (default_label != NULL);
 830   for (i = 0; i < nlabels; i++)
 831     gimple_switch_set_label (p, i + offset, VEC_index (tree, args, i));
 832
 833   return p;
 834 }
 835
 836 /* Build a GIMPLE_EH_DISPATCH statement.  */
 837
 838 gimple
 839 gimple_build_eh_dispatch (int region)
 840 {
 841   gimple p = gimple_build_with_ops (GIMPLE_EH_DISPATCH, ERROR_MARK, 0);
 842   p->gimple_eh_ctrl.region = region;
 843   return p;
 844 }
 845
 846 /* Build a new GIMPLE_DEBUG_BIND statement.
 847
 848    VAR is bound to VALUE; block and location are taken from STMT.  */
 849
 850 gimple
 851 gimple_build_debug_bind_stat (tree var, tree value, gimple stmt MEM_STAT_DECL)
 852 {
 853   gimple p = gimple_build_with_ops_stat (GIMPLE_DEBUG,
 854                                          (unsigned)GIMPLE_DEBUG_BIND, 2
 855                                          PASS_MEM_STAT);
 856
 857   gimple_debug_bind_set_var (p, var);
 858   gimple_debug_bind_set_value (p, value);
 859   if (stmt)
 860     {
 861       gimple_set_block (p, gimple_block (stmt));
 862       gimple_set_location (p, gimple_location (stmt));
 863     }
 864
 865   return p;
 866 }
 867
 868
 869 /* Build a new GIMPLE_DEBUG_SOURCE_BIND statement.
 870
 871    VAR is bound to VALUE; block and location are taken from STMT.  */
 872
 873 gimple
 874 gimple_build_debug_source_bind_stat (tree var, tree value,
 875                                      gimple stmt MEM_STAT_DECL)
 876 {
 877   gimple p = gimple_build_with_ops_stat (GIMPLE_DEBUG,
 878                                          (unsigned)GIMPLE_DEBUG_SOURCE_BIND, 2
 879                                          PASS_MEM_STAT);
 880
 881   gimple_debug_source_bind_set_var (p, var);
 882   gimple_debug_source_bind_set_value (p, value);
 883   if (stmt)
 884     {
 885       gimple_set_block (p, gimple_block (stmt));
 886       gimple_set_location (p, gimple_location (stmt));
 887     }
 888
 889   return p;
 890 }
 891
 892
 893 /* Build a GIMPLE_OMP_CRITICAL statement.
 894
 895    BODY is the sequence of statements for which only one thread can execute.
 896    NAME is optional identifier for this critical block.  */
 897
 898 gimple
 899 gimple_build_omp_critical (gimple_seq body, tree name)
 900 {
 901   gimple p = gimple_alloc (GIMPLE_OMP_CRITICAL, 0);
 902   gimple_omp_critical_set_name (p, name);
 903   if (body)
 904     gimple_omp_set_body (p, body);
 905
 906   return p;
 907 }
 908
 909 /* Build a GIMPLE_OMP_FOR statement.
 910
 911    BODY is sequence of statements inside the for loop.
 912    CLAUSES, are any of the OMP loop construct's clauses: private, firstprivate,
 913    lastprivate, reductions, ordered, schedule, and nowait.
 914    COLLAPSE is the collapse count.
 915    PRE_BODY is the sequence of statements that are loop invariant.  */
 916
 917 gimple
 918 gimple_build_omp_for (gimple_seq body, tree clauses, size_t collapse,
 919                       gimple_seq pre_body)
 920 {
 921   gimple p = gimple_alloc (GIMPLE_OMP_FOR, 0);
 922   if (body)
 923     gimple_omp_set_body (p, body);
 924   gimple_omp_for_set_clauses (p, clauses);
 925   p->gimple_omp_for.collapse = collapse;
 926   p->gimple_omp_for.iter
 927       = ggc_alloc_cleared_vec_gimple_omp_for_iter (collapse);
 928   if (pre_body)
 929     gimple_omp_for_set_pre_body (p, pre_body);
 930
 931   return p;
 932 }
 933
 934
 935 /* Build a GIMPLE_OMP_PARALLEL statement.
 936
 937    BODY is sequence of statements which are executed in parallel.
 938    CLAUSES, are the OMP parallel construct's clauses.
 939    CHILD_FN is the function created for the parallel threads to execute.
 940    DATA_ARG are the shared data argument(s).  */
 941
 942 gimple
 943 gimple_build_omp_parallel (gimple_seq body, tree clauses, tree child_fn,
 944                            tree data_arg)
 945 {
 946   gimple p = gimple_alloc (GIMPLE_OMP_PARALLEL, 0);
 947   if (body)
 948     gimple_omp_set_body (p, body);
 949   gimple_omp_parallel_set_clauses (p, clauses);
 950   gimple_omp_parallel_set_child_fn (p, child_fn);
 951   gimple_omp_parallel_set_data_arg (p, data_arg);
 952
 953   return p;
 954 }
 955
 956
 957 /* Build a GIMPLE_OMP_TASK statement.
 958
 959    BODY is sequence of statements which are executed by the explicit task.
 960    CLAUSES, are the OMP parallel construct's clauses.
 961    CHILD_FN is the function created for the parallel threads to execute.
 962    DATA_ARG are the shared data argument(s).
 963    COPY_FN is the optional function for firstprivate initialization.
 964    ARG_SIZE and ARG_ALIGN are size and alignment of the data block.  */
 965
 966 gimple
 967 gimple_build_omp_task (gimple_seq body, tree clauses, tree child_fn,
 968                        tree data_arg, tree copy_fn, tree arg_size,
 969                        tree arg_align)
 970 {
 971   gimple p = gimple_alloc (GIMPLE_OMP_TASK, 0);
 972   if (body)
 973     gimple_omp_set_body (p, body);
 974   gimple_omp_task_set_clauses (p, clauses);
 975   gimple_omp_task_set_child_fn (p, child_fn);
 976   gimple_omp_task_set_data_arg (p, data_arg);
 977   gimple_omp_task_set_copy_fn (p, copy_fn);
 978   gimple_omp_task_set_arg_size (p, arg_size);
 979   gimple_omp_task_set_arg_align (p, arg_align);
 980
 981   return p;
 982 }
 983
 984
 985 /* Build a GIMPLE_OMP_SECTION statement for a sections statement.
 986
 987    BODY is the sequence of statements in the section.  */
 988
 989 gimple
 990 gimple_build_omp_section (gimple_seq body)
 991 {
 992   gimple p = gimple_alloc (GIMPLE_OMP_SECTION, 0);
 993   if (body)
 994     gimple_omp_set_body (p, body);
 995
 996   return p;
 997 }
 998
 999
1000 /* Build a GIMPLE_OMP_MASTER statement.
1001
1002    BODY is the sequence of statements to be executed by just the master.  */
1003
1004 gimple
1005 gimple_build_omp_master (gimple_seq body)
1006 {
1007   gimple p = gimple_alloc (GIMPLE_OMP_MASTER, 0);
1008   if (body)
1009     gimple_omp_set_body (p, body);
1010
1011   return p;
1012 }
1013
1014
1015 /* Build a GIMPLE_OMP_CONTINUE statement.
1016
1017    CONTROL_DEF is the definition of the control variable.
1018    CONTROL_USE is the use of the control variable.  */
1019
1020 gimple
1021 gimple_build_omp_continue (tree control_def, tree control_use)
1022 {
1023   gimple p = gimple_alloc (GIMPLE_OMP_CONTINUE, 0);
1024   gimple_omp_continue_set_control_def (p, control_def);
1025   gimple_omp_continue_set_control_use (p, control_use);
1026   return p;
1027 }
1028
1029 /* Build a GIMPLE_OMP_ORDERED statement.
1030
1031    BODY is the sequence of statements inside a loop that will executed in
1032    sequence.  */
1033
1034 gimple
1035 gimple_build_omp_ordered (gimple_seq body)
1036 {
1037   gimple p = gimple_alloc (GIMPLE_OMP_ORDERED, 0);
1038   if (body)
1039     gimple_omp_set_body (p, body);
1040
1041   return p;
1042 }
1043
1044
1045 /* Build a GIMPLE_OMP_RETURN statement.
1046    WAIT_P is true if this is a non-waiting return.  */
1047
1048 gimple
1049 gimple_build_omp_return (bool wait_p)
1050 {
1051   gimple p = gimple_alloc (GIMPLE_OMP_RETURN, 0);
1052   if (wait_p)
1053     gimple_omp_return_set_nowait (p);
1054
1055   return p;
1056 }
1057
1058
1059 /* Build a GIMPLE_OMP_SECTIONS statement.
1060
1061    BODY is a sequence of section statements.
1062    CLAUSES are any of the OMP sections contsruct's clauses: private,
1063    firstprivate, lastprivate, reduction, and nowait.  */
1064
1065 gimple
1066 gimple_build_omp_sections (gimple_seq body, tree clauses)
1067 {
1068   gimple p = gimple_alloc (GIMPLE_OMP_SECTIONS, 0);
1069   if (body)
1070     gimple_omp_set_body (p, body);
1071   gimple_omp_sections_set_clauses (p, clauses);
1072
1073   return p;
1074 }
1075
1076
1077 /* Build a GIMPLE_OMP_SECTIONS_SWITCH.  */
1078
1079 gimple
1080 gimple_build_omp_sections_switch (void)
1081 {
1082   return gimple_alloc (GIMPLE_OMP_SECTIONS_SWITCH, 0);
1083 }
1084
1085
1086 /* Build a GIMPLE_OMP_SINGLE statement.
1087
1088    BODY is the sequence of statements that will be executed once.
1089    CLAUSES are any of the OMP single construct's clauses: private, firstprivate,
1090    copyprivate, nowait.  */
1091
1092 gimple
1093 gimple_build_omp_single (gimple_seq body, tree clauses)
1094 {
1095   gimple p = gimple_alloc (GIMPLE_OMP_SINGLE, 0);
1096   if (body)
1097     gimple_omp_set_body (p, body);
1098   gimple_omp_single_set_clauses (p, clauses);
1099
1100   return p;
1101 }
1102
1103
1104 /* Build a GIMPLE_OMP_ATOMIC_LOAD statement.  */
1105
1106 gimple
1107 gimple_build_omp_atomic_load (tree lhs, tree rhs)
1108 {
1109   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_LOAD, 0);
1110   gimple_omp_atomic_load_set_lhs (p, lhs);
1111   gimple_omp_atomic_load_set_rhs (p, rhs);
1112   return p;
1113 }
1114
1115 /* Build a GIMPLE_OMP_ATOMIC_STORE statement.
1116
1117    VAL is the value we are storing.  */
1118
1119 gimple
1120 gimple_build_omp_atomic_store (tree val)
1121 {
1122   gimple p = gimple_alloc (GIMPLE_OMP_ATOMIC_STORE, 0);
1123   gimple_omp_atomic_store_set_val (p, val);
1124   return p;
1125 }
1126
1127 /* Build a GIMPLE_PREDICT statement.  PREDICT is one of the predictors from
1128    predict.def, OUTCOME is NOT_TAKEN or TAKEN.  */
1129
1130 gimple
1131 gimple_build_predict (enum br_predictor predictor, enum prediction outcome)
1132 {
1133   gimple p = gimple_alloc (GIMPLE_PREDICT, 0);
1134   /* Ensure all the predictors fit into the lower bits of the subcode.  */
1135   gcc_assert ((int) END_PREDICTORS <= GF_PREDICT_TAKEN);
1136   gimple_predict_set_predictor (p, predictor);
1137   gimple_predict_set_outcome (p, outcome);
1138   return p;
1139 }
1140
1141 #if defined ENABLE_GIMPLE_CHECKING
1142 /* Complain of a gimple type mismatch and die.  */
1143
1144 void
1145 gimple_check_failed (const_gimple gs, const char *file, int line,
1146                      const char *function, enum gimple_code code,
1147                      enum tree_code subcode)
1148 {
1149   internal_error ("gimple check: expected %s(%s), have %s(%s) in %s, at %s:%d",
1150                   gimple_code_name[code],
1151                   tree_code_name[subcode],
1152                   gimple_code_name[gimple_code (gs)],
1153                   gs->gsbase.subcode > 0
1154                     ? tree_code_name[gs->gsbase.subcode]
1155                     : "",
1156                   function, trim_filename (file), line);
1157 }
1158 #endif /* ENABLE_GIMPLE_CHECKING */
1159
1160
1161 /* Allocate a new GIMPLE sequence in GC memory and return it.  If
1162    there are free sequences in GIMPLE_SEQ_CACHE return one of those
1163    instead.  */
1164
1165 gimple_seq
1166 gimple_seq_alloc (void)
1167 {
1168   gimple_seq seq = gimple_seq_cache;
1169   if (seq)
1170     {
1171       gimple_seq_cache = gimple_seq_cache->next_free;
1172       gcc_assert (gimple_seq_cache != seq);
1173       memset (seq, 0, sizeof (*seq));
1174     }
1175   else
1176     {
1177       seq = ggc_alloc_cleared_gimple_seq_d ();
1178 #ifdef GATHER_STATISTICS
1179       gimple_alloc_counts[(int) gimple_alloc_kind_seq]++;
1180       gimple_alloc_sizes[(int) gimple_alloc_kind_seq] += sizeof (*seq);
1181 #endif
1182     }
1183
1184   return seq;
1185 }
1186
1187 /* Return SEQ to the free pool of GIMPLE sequences.  */
1188
1189 void
1190 gimple_seq_free (gimple_seq seq)
1191 {
1192   if (seq == NULL)
1193     return;
1194
1195   gcc_assert (gimple_seq_first (seq) == NULL);
1196   gcc_assert (gimple_seq_last (seq) == NULL);
1197
1198   /* If this triggers, it's a sign that the same list is being freed
1199      twice.  */
1200   gcc_assert (seq != gimple_seq_cache || gimple_seq_cache == NULL);
1201
1202   /* Add SEQ to the pool of free sequences.  */
1203   seq->next_free = gimple_seq_cache;
1204   gimple_seq_cache = seq;
1205 }
1206
1207
1208 /* Link gimple statement GS to the end of the sequence *SEQ_P.  If
1209    *SEQ_P is NULL, a new sequence is allocated.  */
1210
1211 void
1212 gimple_seq_add_stmt (gimple_seq *seq_p, gimple gs)
1213 {
1214   gimple_stmt_iterator si;
1215
1216   if (gs == NULL)
1217     return;
1218
1219   if (*seq_p == NULL)
1220     *seq_p = gimple_seq_alloc ();
1221
1222   si = gsi_last (*seq_p);
1223   gsi_insert_after (&si, gs, GSI_NEW_STMT);
1224 }
1225
1226
1227 /* Append sequence SRC to the end of sequence *DST_P.  If *DST_P is
1228    NULL, a new sequence is allocated.  */
1229
1230 void
1231 gimple_seq_add_seq (gimple_seq *dst_p, gimple_seq src)
1232 {
1233   gimple_stmt_iterator si;
1234
1235   if (src == NULL)
1236     return;
1237
1238   if (*dst_p == NULL)
1239     *dst_p = gimple_seq_alloc ();
1240
1241   si = gsi_last (*dst_p);
1242   gsi_insert_seq_after (&si, src, GSI_NEW_STMT);
1243 }
1244
1245
1246 /* Helper function of empty_body_p.  Return true if STMT is an empty
1247    statement.  */
1248
1249 static bool
1250 empty_stmt_p (gimple stmt)
1251 {
1252   if (gimple_code (stmt) == GIMPLE_NOP)
1253     return true;
1254   if (gimple_code (stmt) == GIMPLE_BIND)
1255     return empty_body_p (gimple_bind_body (stmt));
1256   return false;
1257 }
1258
1259
1260 /* Return true if BODY contains nothing but empty statements.  */
1261
1262 bool
1263 empty_body_p (gimple_seq body)
1264 {
1265   gimple_stmt_iterator i;
1266
1267   if (gimple_seq_empty_p (body))
1268     return true;
1269   for (i = gsi_start (body); !gsi_end_p (i); gsi_next (&i))
1270     if (!empty_stmt_p (gsi_stmt (i))
1271         && !is_gimple_debug (gsi_stmt (i)))
1272       return false;
1273
1274   return true;
1275 }
1276
1277
1278 /* Perform a deep copy of sequence SRC and return the result.  */
1279
1280 gimple_seq
1281 gimple_seq_copy (gimple_seq src)
1282 {
1283   gimple_stmt_iterator gsi;
1284   gimple_seq new_seq = gimple_seq_alloc ();
1285   gimple stmt;
1286
1287   for (gsi = gsi_start (src); !gsi_end_p (gsi); gsi_next (&gsi))
1288     {
1289       stmt = gimple_copy (gsi_stmt (gsi));
1290       gimple_seq_add_stmt (&new_seq, stmt);
1291     }
1292
1293   return new_seq;
1294 }
1295
1296
1297 /* Walk all the statements in the sequence SEQ calling walk_gimple_stmt
1298    on each one.  WI is as in walk_gimple_stmt.
1299
1300    If walk_gimple_stmt returns non-NULL, the walk is stopped, the
1301    value is stored in WI->CALLBACK_RESULT and the statement that
1302    produced the value is returned.
1303
1304    Otherwise, all the statements are walked and NULL returned.  */
1305
1306 gimple
1307 walk_gimple_seq (gimple_seq seq, walk_stmt_fn callback_stmt,
1308                  walk_tree_fn callback_op, struct walk_stmt_info *wi)
1309 {
1310   gimple_stmt_iterator gsi;
1311
1312   for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
1313     {
1314       tree ret = walk_gimple_stmt (&gsi, callback_stmt, callback_op, wi);
1315       if (ret)
1316         {
1317           /* If CALLBACK_STMT or CALLBACK_OP return a value, WI must exist
1318              to hold it.  */
1319           gcc_assert (wi);
1320           wi->callback_result = ret;
1321           return gsi_stmt (gsi);
1322         }
1323     }
1324
1325   if (wi)
1326     wi->callback_result = NULL_TREE;
1327
1328   return NULL;
1329 }
1330
1331
1332 /* Helper function for walk_gimple_stmt.  Walk operands of a GIMPLE_ASM.  */
1333
1334 static tree
1335 walk_gimple_asm (gimple stmt, walk_tree_fn callback_op,
1336                  struct walk_stmt_info *wi)
1337 {
1338   tree ret, op;
1339   unsigned noutputs;
1340   const char **oconstraints;
1341   unsigned i, n;
1342   const char *constraint;
1343   bool allows_mem, allows_reg, is_inout;
1344
1345   noutputs = gimple_asm_noutputs (stmt);
1346   oconstraints = (const char **) alloca ((noutputs) * sizeof (const char *));
1347
1348   if (wi)
1349     wi->is_lhs = true;
1350
1351   for (i = 0; i < noutputs; i++)
1352     {
1353       op = gimple_asm_output_op (stmt, i);
1354       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1355       oconstraints[i] = constraint;
1356       parse_output_constraint (&constraint, i, 0, 0, &allows_mem, &allows_reg,
1357                                &is_inout);
1358       if (wi)
1359         wi->val_only = (allows_reg || !allows_mem);
1360       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1361       if (ret)
1362         return ret;
1363     }
1364
1365   n = gimple_asm_ninputs (stmt);
1366   for (i = 0; i < n; i++)
1367     {
1368       op = gimple_asm_input_op (stmt, i);
1369       constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
1370       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
1371                               oconstraints, &allows_mem, &allows_reg);
1372       if (wi)
1373         {
1374           wi->val_only = (allows_reg || !allows_mem);
1375           /* Although input "m" is not really a LHS, we need a lvalue.  */
1376           wi->is_lhs = !wi->val_only;
1377         }
1378       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1379       if (ret)
1380         return ret;
1381     }
1382
1383   if (wi)
1384     {
1385       wi->is_lhs = false;
1386       wi->val_only = true;
1387     }
1388
1389   n = gimple_asm_nlabels (stmt);
1390   for (i = 0; i < n; i++)
1391     {
1392       op = gimple_asm_label_op (stmt, i);
1393       ret = walk_tree (&TREE_VALUE (op), callback_op, wi, NULL);
1394       if (ret)
1395         return ret;
1396     }
1397
1398   return NULL_TREE;
1399 }
1400
1401
1402 /* Helper function of WALK_GIMPLE_STMT.  Walk every tree operand in
1403    STMT.  CALLBACK_OP and WI are as in WALK_GIMPLE_STMT.
1404
1405    CALLBACK_OP is called on each operand of STMT via walk_tree.
1406    Additional parameters to walk_tree must be stored in WI.  For each operand
1407    OP, walk_tree is called as:
1408
1409         walk_tree (&OP, CALLBACK_OP, WI, WI->PSET)
1410
1411    If CALLBACK_OP returns non-NULL for an operand, the remaining
1412    operands are not scanned.
1413
1414    The return value is that returned by the last call to walk_tree, or
1415    NULL_TREE if no CALLBACK_OP is specified.  */
1416
1417 tree
1418 walk_gimple_op (gimple stmt, walk_tree_fn callback_op,
1419                 struct walk_stmt_info *wi)
1420 {
1421   struct pointer_set_t *pset = (wi) ? wi->pset : NULL;
1422   unsigned i;
1423   tree ret = NULL_TREE;
1424
1425   switch (gimple_code (stmt))
1426     {
1427     case GIMPLE_ASSIGN:
1428       /* Walk the RHS operands.  If the LHS is of a non-renamable type or
1429          is a register variable, we may use a COMPONENT_REF on the RHS.  */
1430       if (wi)
1431         {
1432           tree lhs = gimple_assign_lhs (stmt);
1433           wi->val_only
1434             = (is_gimple_reg_type (TREE_TYPE (lhs)) && !is_gimple_reg (lhs))
1435               || !gimple_assign_single_p (stmt);
1436         }
1437
1438       for (i = 1; i < gimple_num_ops (stmt); i++)
1439         {
1440           ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi,
1441                            pset);
1442           if (ret)
1443             return ret;
1444         }
1445
1446       /* Walk the LHS.  If the RHS is appropriate for a memory, we
1447          may use a COMPONENT_REF on the LHS.  */
1448       if (wi)
1449         {
1450           /* If the RHS has more than 1 operand, it is not appropriate
1451              for the memory.  */
1452           wi->val_only = !is_gimple_mem_rhs (gimple_assign_rhs1 (stmt))
1453                          || !gimple_assign_single_p (stmt);
1454           wi->is_lhs = true;
1455         }
1456
1457       ret = walk_tree (gimple_op_ptr (stmt, 0), callback_op, wi, pset);
1458       if (ret)
1459         return ret;
1460
1461       if (wi)
1462         {
1463           wi->val_only = true;
1464           wi->is_lhs = false;
1465         }
1466       break;
1467
1468     case GIMPLE_CALL:
1469       if (wi)
1470         {
1471           wi->is_lhs = false;
1472           wi->val_only = true;
1473         }
1474
1475       ret = walk_tree (gimple_call_chain_ptr (stmt), callback_op, wi, pset);
1476       if (ret)
1477         return ret;
1478
1479       ret = walk_tree (gimple_call_fn_ptr (stmt), callback_op, wi, pset);
1480       if (ret)
1481         return ret;
1482
1483       for (i = 0; i < gimple_call_num_args (stmt); i++)
1484         {
1485           if (wi)
1486             wi->val_only
1487               = is_gimple_reg_type (TREE_TYPE (gimple_call_arg (stmt, i)));
1488           ret = walk_tree (gimple_call_arg_ptr (stmt, i), callback_op, wi,
1489                            pset);
1490           if (ret)
1491             return ret;
1492         }
1493
1494       if (gimple_call_lhs (stmt))
1495         {
1496           if (wi)
1497             {
1498               wi->is_lhs = true;
1499               wi->val_only
1500                 = is_gimple_reg_type (TREE_TYPE (gimple_call_lhs (stmt)));
1501             }
1502
1503           ret = walk_tree (gimple_call_lhs_ptr (stmt), callback_op, wi, pset);
1504           if (ret)
1505             return ret;
1506         }
1507
1508       if (wi)
1509         {
1510           wi->is_lhs = false;
1511           wi->val_only = true;
1512         }
1513       break;
1514
1515     case GIMPLE_CATCH:
1516       ret = walk_tree (gimple_catch_types_ptr (stmt), callback_op, wi,
1517                        pset);
1518       if (ret)
1519         return ret;
1520       break;
1521
1522     case GIMPLE_EH_FILTER:
1523       ret = walk_tree (gimple_eh_filter_types_ptr (stmt), callback_op, wi,
1524                        pset);
1525       if (ret)
1526         return ret;
1527       break;
1528
1529     case GIMPLE_ASM:
1530       ret = walk_gimple_asm (stmt, callback_op, wi);
1531       if (ret)
1532         return ret;
1533       break;
1534
1535     case GIMPLE_OMP_CONTINUE:
1536       ret = walk_tree (gimple_omp_continue_control_def_ptr (stmt),
1537                        callback_op, wi, pset);
1538       if (ret)
1539         return ret;
1540
1541       ret = walk_tree (gimple_omp_continue_control_use_ptr (stmt),
1542                        callback_op, wi, pset);
1543       if (ret)
1544         return ret;
1545       break;
1546
1547     case GIMPLE_OMP_CRITICAL:
1548       ret = walk_tree (gimple_omp_critical_name_ptr (stmt), callback_op, wi,
1549                        pset);
1550       if (ret)
1551         return ret;
1552       break;
1553
1554     case GIMPLE_OMP_FOR:
1555       ret = walk_tree (gimple_omp_for_clauses_ptr (stmt), callback_op, wi,
1556                        pset);
1557       if (ret)
1558         return ret;
1559       for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
1560         {
1561           ret = walk_tree (gimple_omp_for_index_ptr (stmt, i), callback_op,
1562                            wi, pset);
1563           if (ret)
1564             return ret;
1565           ret = walk_tree (gimple_omp_for_initial_ptr (stmt, i), callback_op,
1566                            wi, pset);
1567           if (ret)
1568             return ret;
1569           ret = walk_tree (gimple_omp_for_final_ptr (stmt, i), callback_op,
1570                            wi, pset);
1571           if (ret)
1572             return ret;
1573           ret = walk_tree (gimple_omp_for_incr_ptr (stmt, i), callback_op,
1574                            wi, pset);
1575         }
1576       if (ret)
1577         return ret;
1578       break;
1579
1580     case GIMPLE_OMP_PARALLEL:
1581       ret = walk_tree (gimple_omp_parallel_clauses_ptr (stmt), callback_op,
1582                        wi, pset);
1583       if (ret)
1584         return ret;
1585       ret = walk_tree (gimple_omp_parallel_child_fn_ptr (stmt), callback_op,
1586                        wi, pset);
1587       if (ret)
1588         return ret;
1589       ret = walk_tree (gimple_omp_parallel_data_arg_ptr (stmt), callback_op,
1590                        wi, pset);
1591       if (ret)
1592         return ret;
1593       break;
1594
1595     case GIMPLE_OMP_TASK:
1596       ret = walk_tree (gimple_omp_task_clauses_ptr (stmt), callback_op,
1597                        wi, pset);
1598       if (ret)
1599         return ret;
1600       ret = walk_tree (gimple_omp_task_child_fn_ptr (stmt), callback_op,
1601                        wi, pset);
1602       if (ret)
1603         return ret;
1604       ret = walk_tree (gimple_omp_task_data_arg_ptr (stmt), callback_op,
1605                        wi, pset);
1606       if (ret)
1607         return ret;
1608       ret = walk_tree (gimple_omp_task_copy_fn_ptr (stmt), callback_op,
1609                        wi, pset);
1610       if (ret)
1611         return ret;
1612       ret = walk_tree (gimple_omp_task_arg_size_ptr (stmt), callback_op,
1613                        wi, pset);
1614       if (ret)
1615         return ret;
1616       ret = walk_tree (gimple_omp_task_arg_align_ptr (stmt), callback_op,
1617                        wi, pset);
1618       if (ret)
1619         return ret;
1620       break;
1621
1622     case GIMPLE_OMP_SECTIONS:
1623       ret = walk_tree (gimple_omp_sections_clauses_ptr (stmt), callback_op,
1624                        wi, pset);
1625       if (ret)
1626         return ret;
1627
1628       ret = walk_tree (gimple_omp_sections_control_ptr (stmt), callback_op,
1629                        wi, pset);
1630       if (ret)
1631         return ret;
1632
1633       break;
1634
1635     case GIMPLE_OMP_SINGLE:
1636       ret = walk_tree (gimple_omp_single_clauses_ptr (stmt), callback_op, wi,
1637                        pset);
1638       if (ret)
1639         return ret;
1640       break;
1641
1642     case GIMPLE_OMP_ATOMIC_LOAD:
1643       ret = walk_tree (gimple_omp_atomic_load_lhs_ptr (stmt), callback_op, wi,
1644                        pset);
1645       if (ret)
1646         return ret;
1647
1648       ret = walk_tree (gimple_omp_atomic_load_rhs_ptr (stmt), callback_op, wi,
1649                        pset);
1650       if (ret)
1651         return ret;
1652       break;
1653
1654     case GIMPLE_OMP_ATOMIC_STORE:
1655       ret = walk_tree (gimple_omp_atomic_store_val_ptr (stmt), callback_op,
1656                        wi, pset);
1657       if (ret)
1658         return ret;
1659       break;
1660
1661       /* Tuples that do not have operands.  */
1662     case GIMPLE_NOP:
1663     case GIMPLE_RESX:
1664     case GIMPLE_OMP_RETURN:
1665     case GIMPLE_PREDICT:
1666       break;
1667
1668     default:
1669       {
1670         enum gimple_statement_structure_enum gss;
1671         gss = gimple_statement_structure (stmt);
1672         if (gss == GSS_WITH_OPS || gss == GSS_WITH_MEM_OPS)
1673           for (i = 0; i < gimple_num_ops (stmt); i++)
1674             {
1675               ret = walk_tree (gimple_op_ptr (stmt, i), callback_op, wi, pset);
1676               if (ret)
1677                 return ret;
1678             }
1679       }
1680       break;
1681     }
1682
1683   return NULL_TREE;
1684 }
1685
1686
1687 /* Walk the current statement in GSI (optionally using traversal state
1688    stored in WI).  If WI is NULL, no state is kept during traversal.
1689    The callback CALLBACK_STMT is called.  If CALLBACK_STMT indicates
1690    that it has handled all the operands of the statement, its return
1691    value is returned.  Otherwise, the return value from CALLBACK_STMT
1692    is discarded and its operands are scanned.
1693
1694    If CALLBACK_STMT is NULL or it didn't handle the operands,
1695    CALLBACK_OP is called on each operand of the statement via
1696    walk_gimple_op.  If walk_gimple_op returns non-NULL for any
1697    operand, the remaining operands are not scanned.  In this case, the
1698    return value from CALLBACK_OP is returned.
1699
1700    In any other case, NULL_TREE is returned.  */
1701
1702 tree
1703 walk_gimple_stmt (gimple_stmt_iterator *gsi, walk_stmt_fn callback_stmt,
1704                   walk_tree_fn callback_op, struct walk_stmt_info *wi)
1705 {
1706   gimple ret;
1707   tree tree_ret;
1708   gimple stmt = gsi_stmt (*gsi);
1709
1710   if (wi)
1711     wi->gsi = *gsi;
1712
1713   if (wi && wi->want_locations && gimple_has_location (stmt))
1714     input_location = gimple_location (stmt);
1715
1716   ret = NULL;
1717
1718   /* Invoke the statement callback.  Return if the callback handled
1719      all of STMT operands by itself.  */
1720   if (callback_stmt)
1721     {
1722       bool handled_ops = false;
1723       tree_ret = callback_stmt (gsi, &handled_ops, wi);
1724       if (handled_ops)
1725         return tree_ret;
1726
1727       /* If CALLBACK_STMT did not handle operands, it should not have
1728          a value to return.  */
1729       gcc_assert (tree_ret == NULL);
1730
1731       /* Re-read stmt in case the callback changed it.  */
1732       stmt = gsi_stmt (*gsi);
1733     }
1734
1735   /* If CALLBACK_OP is defined, invoke it on every operand of STMT.  */
1736   if (callback_op)
1737     {
1738       tree_ret = walk_gimple_op (stmt, callback_op, wi);
1739       if (tree_ret)
1740         return tree_ret;
1741     }
1742
1743   /* If STMT can have statements inside (e.g. GIMPLE_BIND), walk them.  */
1744   switch (gimple_code (stmt))
1745     {
1746     case GIMPLE_BIND:
1747       ret = walk_gimple_seq (gimple_bind_body (stmt), callback_stmt,
1748                              callback_op, wi);
1749       if (ret)
1750         return wi->callback_result;
1751       break;
1752
1753     case GIMPLE_CATCH:
1754       ret = walk_gimple_seq (gimple_catch_handler (stmt), callback_stmt,
1755                              callback_op, wi);
1756       if (ret)
1757         return wi->callback_result;
1758       break;
1759
1760     case GIMPLE_EH_FILTER:
1761       ret = walk_gimple_seq (gimple_eh_filter_failure (stmt), callback_stmt,
1762                              callback_op, wi);
1763       if (ret)
1764         return wi->callback_result;
1765       break;
1766
1767     case GIMPLE_TRY:
1768       ret = walk_gimple_seq (gimple_try_eval (stmt), callback_stmt, callback_op,
1769                              wi);
1770       if (ret)
1771         return wi->callback_result;
1772
1773       ret = walk_gimple_seq (gimple_try_cleanup (stmt), callback_stmt,
1774                              callback_op, wi);
1775       if (ret)
1776         return wi->callback_result;
1777       break;
1778
1779     case GIMPLE_OMP_FOR:
1780       ret = walk_gimple_seq (gimple_omp_for_pre_body (stmt), callback_stmt,
1781                              callback_op, wi);
1782       if (ret)
1783         return wi->callback_result;
1784
1785       /* FALL THROUGH.  */
1786     case GIMPLE_OMP_CRITICAL:
1787     case GIMPLE_OMP_MASTER:
1788     case GIMPLE_OMP_ORDERED:
1789     case GIMPLE_OMP_SECTION:
1790     case GIMPLE_OMP_PARALLEL:
1791     case GIMPLE_OMP_TASK:
1792     case GIMPLE_OMP_SECTIONS:
1793     case GIMPLE_OMP_SINGLE:
1794       ret = walk_gimple_seq (gimple_omp_body (stmt), callback_stmt, callback_op,
1795                              wi);
1796       if (ret)
1797         return wi->callback_result;
1798       break;
1799
1800     case GIMPLE_WITH_CLEANUP_EXPR:
1801       ret = walk_gimple_seq (gimple_wce_cleanup (stmt), callback_stmt,
1802                              callback_op, wi);
1803       if (ret)
1804         return wi->callback_result;
1805       break;
1806
1807     default:
1808       gcc_assert (!gimple_has_substatements (stmt));
1809       break;
1810     }
1811
1812   return NULL;
1813 }
1814
1815
1816 /* Set sequence SEQ to be the GIMPLE body for function FN.  */
1817
1818 void
1819 gimple_set_body (tree fndecl, gimple_seq seq)
1820 {
1821   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1822   if (fn == NULL)
1823     {
1824       /* If FNDECL still does not have a function structure associated
1825          with it, then it does not make sense for it to receive a
1826          GIMPLE body.  */
1827       gcc_assert (seq == NULL);
1828     }
1829   else
1830     fn->gimple_body = seq;
1831 }
1832
1833
1834 /* Return the body of GIMPLE statements for function FN.  After the
1835    CFG pass, the function body doesn't exist anymore because it has
1836    been split up into basic blocks.  In this case, it returns
1837    NULL.  */
1838
1839 gimple_seq
1840 gimple_body (tree fndecl)
1841 {
1842   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1843   return fn ? fn->gimple_body : NULL;
1844 }
1845
1846 /* Return true when FNDECL has Gimple body either in unlowered
1847    or CFG form.  */
1848 bool
1849 gimple_has_body_p (tree fndecl)
1850 {
1851   struct function *fn = DECL_STRUCT_FUNCTION (fndecl);
1852   return (gimple_body (fndecl) || (fn && fn->cfg));
1853 }
1854
1855 /* Return true if calls C1 and C2 are known to go to the same function.  */
1856
1857 bool
1858 gimple_call_same_target_p (const_gimple c1, const_gimple c2)
1859 {
1860   if (gimple_call_internal_p (c1))
1861     return (gimple_call_internal_p (c2)
1862             && gimple_call_internal_fn (c1) == gimple_call_internal_fn (c2));
1863   else
1864     return (gimple_call_fn (c1) == gimple_call_fn (c2)
1865             || (gimple_call_fndecl (c1)
1866                 && gimple_call_fndecl (c1) == gimple_call_fndecl (c2)));
1867 }
1868
1869 /* Detect flags from a GIMPLE_CALL.  This is just like
1870    call_expr_flags, but for gimple tuples.  */
1871
1872 int
1873 gimple_call_flags (const_gimple stmt)
1874 {
1875   int flags;
1876   tree decl = gimple_call_fndecl (stmt);
1877
1878   if (decl)
1879     flags = flags_from_decl_or_type (decl);
1880   else if (gimple_call_internal_p (stmt))
1881     flags = internal_fn_flags (gimple_call_internal_fn (stmt));
1882   else
1883     flags = flags_from_decl_or_type (gimple_call_fntype (stmt));
1884
1885   if (stmt->gsbase.subcode & GF_CALL_NOTHROW)
1886     flags |= ECF_NOTHROW;
1887
1888   return flags;
1889 }
1890
1891 /* Return the "fn spec" string for call STMT.  */
1892
1893 static tree
1894 gimple_call_fnspec (const_gimple stmt)
1895 {
1896   tree type, attr;
1897
1898   type = gimple_call_fntype (stmt);
1899   if (!type)
1900     return NULL_TREE;
1901
1902   attr = lookup_attribute ("fn spec", TYPE_ATTRIBUTES (type));
1903   if (!attr)
1904     return NULL_TREE;
1905
1906   return TREE_VALUE (TREE_VALUE (attr));
1907 }
1908
1909 /* Detects argument flags for argument number ARG on call STMT.  */
1910
1911 int
1912 gimple_call_arg_flags (const_gimple stmt, unsigned arg)
1913 {
1914   tree attr = gimple_call_fnspec (stmt);
1915
1916   if (!attr || 1 + arg >= (unsigned) TREE_STRING_LENGTH (attr))
1917     return 0;
1918
1919   switch (TREE_STRING_POINTER (attr)[1 + arg])
1920     {
1921     case 'x':
1922     case 'X':
1923       return EAF_UNUSED;
1924
1925     case 'R':
1926       return EAF_DIRECT | EAF_NOCLOBBER | EAF_NOESCAPE;
1927
1928     case 'r':
1929       return EAF_NOCLOBBER | EAF_NOESCAPE;
1930
1931     case 'W':
1932       return EAF_DIRECT | EAF_NOESCAPE;
1933
1934     case 'w':
1935       return EAF_NOESCAPE;
1936
1937     case '.':
1938     default:
1939       return 0;
1940     }
1941 }
1942
1943 /* Detects return flags for the call STMT.  */
1944
1945 int
1946 gimple_call_return_flags (const_gimple stmt)
1947 {
1948   tree attr;
1949
1950   if (gimple_call_flags (stmt) & ECF_MALLOC)
1951     return ERF_NOALIAS;
1952
1953   attr = gimple_call_fnspec (stmt);
1954   if (!attr || TREE_STRING_LENGTH (attr) < 1)
1955     return 0;
1956
1957   switch (TREE_STRING_POINTER (attr)[0])
1958     {
1959     case '1':
1960     case '2':
1961     case '3':
1962     case '4':
1963       return ERF_RETURNS_ARG | (TREE_STRING_POINTER (attr)[0] - '1');
1964
1965     case 'm':
1966       return ERF_NOALIAS;
1967
1968     case '.':
1969     default:
1970       return 0;
1971     }
1972 }
1973
1974
1975 /* Return true if GS is a copy assignment.  */
1976
1977 bool
1978 gimple_assign_copy_p (gimple gs)
1979 {
1980   return (gimple_assign_single_p (gs)
1981           && is_gimple_val (gimple_op (gs, 1)));
1982 }
1983
1984
1985 /* Return true if GS is a SSA_NAME copy assignment.  */
1986
1987 bool
1988 gimple_assign_ssa_name_copy_p (gimple gs)
1989 {
1990   return (gimple_assign_single_p (gs)
1991           && TREE_CODE (gimple_assign_lhs (gs)) == SSA_NAME
1992           && TREE_CODE (gimple_assign_rhs1 (gs)) == SSA_NAME);
1993 }
1994
1995
1996 /* Return true if GS is an assignment with a unary RHS, but the
1997    operator has no effect on the assigned value.  The logic is adapted
1998    from STRIP_NOPS.  This predicate is intended to be used in tuplifying
1999    instances in which STRIP_NOPS was previously applied to the RHS of
2000    an assignment.
2001
2002    NOTE: In the use cases that led to the creation of this function
2003    and of gimple_assign_single_p, it is typical to test for either
2004    condition and to proceed in the same manner.  In each case, the
2005    assigned value is represented by the single RHS operand of the
2006    assignment.  I suspect there may be cases where gimple_assign_copy_p,
2007    gimple_assign_single_p, or equivalent logic is used where a similar
2008    treatment of unary NOPs is appropriate.  */
2009
2010 bool
2011 gimple_assign_unary_nop_p (gimple gs)
2012 {
2013   return (is_gimple_assign (gs)
2014           && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))
2015               || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR)
2016           && gimple_assign_rhs1 (gs) != error_mark_node
2017           && (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs)))
2018               == TYPE_MODE (TREE_TYPE (gimple_assign_rhs1 (gs)))));
2019 }
2020
2021 /* Set BB to be the basic block holding G.  */
2022
2023 void
2024 gimple_set_bb (gimple stmt, basic_block bb)
2025 {
2026   stmt->gsbase.bb = bb;
2027
2028   /* If the statement is a label, add the label to block-to-labels map
2029      so that we can speed up edge creation for GIMPLE_GOTOs.  */
2030   if (cfun->cfg && gimple_code (stmt) == GIMPLE_LABEL)
2031     {
2032       tree t;
2033       int uid;
2034
2035       t = gimple_label_label (stmt);
2036       uid = LABEL_DECL_UID (t);
2037       if (uid == -1)
2038         {
2039           unsigned old_len = VEC_length (basic_block, label_to_block_map);
2040           LABEL_DECL_UID (t) = uid = cfun->cfg->last_label_uid++;
2041           if (old_len <= (unsigned) uid)
2042             {
2043               unsigned new_len = 3 * uid / 2 + 1;
2044
2045               VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
2046                                      new_len);
2047             }
2048         }
2049
2050       VEC_replace (basic_block, label_to_block_map, uid, bb);
2051     }
2052 }
2053
2054
2055 /* Modify the RHS of the assignment pointed-to by GSI using the
2056    operands in the expression tree EXPR.
2057
2058    NOTE: The statement pointed-to by GSI may be reallocated if it
2059    did not have enough operand slots.
2060
2061    This function is useful to convert an existing tree expression into
2062    the flat representation used for the RHS of a GIMPLE assignment.
2063    It will reallocate memory as needed to expand or shrink the number
2064    of operand slots needed to represent EXPR.
2065
2066    NOTE: If you find yourself building a tree and then calling this
2067    function, you are most certainly doing it the slow way.  It is much
2068    better to build a new assignment or to use the function
2069    gimple_assign_set_rhs_with_ops, which does not require an
2070    expression tree to be built.  */
2071
2072 void
2073 gimple_assign_set_rhs_from_tree (gimple_stmt_iterator *gsi, tree expr)
2074 {
2075   enum tree_code subcode;
2076   tree op1, op2, op3;
2077
2078   extract_ops_from_tree_1 (expr, &subcode, &op1, &op2, &op3);
2079   gimple_assign_set_rhs_with_ops_1 (gsi, subcode, op1, op2, op3);
2080 }
2081
2082
2083 /* Set the RHS of assignment statement pointed-to by GSI to CODE with
2084    operands OP1, OP2 and OP3.
2085
2086    NOTE: The statement pointed-to by GSI may be reallocated if it
2087    did not have enough operand slots.  */
2088
2089 void
2090 gimple_assign_set_rhs_with_ops_1 (gimple_stmt_iterator *gsi, enum tree_code code,
2091                                   tree op1, tree op2, tree op3)
2092 {
2093   unsigned new_rhs_ops = get_gimple_rhs_num_ops (code);
2094   gimple stmt = gsi_stmt (*gsi);
2095
2096   /* If the new CODE needs more operands, allocate a new statement.  */
2097   if (gimple_num_ops (stmt) < new_rhs_ops + 1)
2098     {
2099       tree lhs = gimple_assign_lhs (stmt);
2100       gimple new_stmt = gimple_alloc (gimple_code (stmt), new_rhs_ops + 1);
2101       memcpy (new_stmt, stmt, gimple_size (gimple_code (stmt)));
2102       gsi_replace (gsi, new_stmt, true);
2103       stmt = new_stmt;
2104
2105       /* The LHS needs to be reset as this also changes the SSA name
2106          on the LHS.  */
2107       gimple_assign_set_lhs (stmt, lhs);
2108     }
2109
2110   gimple_set_num_ops (stmt, new_rhs_ops + 1);
2111   gimple_set_subcode (stmt, code);
2112   gimple_assign_set_rhs1 (stmt, op1);
2113   if (new_rhs_ops > 1)
2114     gimple_assign_set_rhs2 (stmt, op2);
2115   if (new_rhs_ops > 2)
2116     gimple_assign_set_rhs3 (stmt, op3);
2117 }
2118
2119
2120 /* Return the LHS of a statement that performs an assignment,
2121    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  Returns NULL_TREE
2122    for a call to a function that returns no value, or for a
2123    statement other than an assignment or a call.  */
2124
2125 tree
2126 gimple_get_lhs (const_gimple stmt)
2127 {
2128   enum gimple_code code = gimple_code (stmt);
2129
2130   if (code == GIMPLE_ASSIGN)
2131     return gimple_assign_lhs (stmt);
2132   else if (code == GIMPLE_CALL)
2133     return gimple_call_lhs (stmt);
2134   else
2135     return NULL_TREE;
2136 }
2137
2138
2139 /* Set the LHS of a statement that performs an assignment,
2140    either a GIMPLE_ASSIGN or a GIMPLE_CALL.  */
2141
2142 void
2143 gimple_set_lhs (gimple stmt, tree lhs)
2144 {
2145   enum gimple_code code = gimple_code (stmt);
2146
2147   if (code == GIMPLE_ASSIGN)
2148     gimple_assign_set_lhs (stmt, lhs);
2149   else if (code == GIMPLE_CALL)
2150     gimple_call_set_lhs (stmt, lhs);
2151   else
2152     gcc_unreachable();
2153 }
2154
2155 /* Replace the LHS of STMT, an assignment, either a GIMPLE_ASSIGN or a
2156    GIMPLE_CALL, with NLHS, in preparation for modifying the RHS to an
2157    expression with a different value.
2158
2159    This will update any annotations (say debug bind stmts) referring
2160    to the original LHS, so that they use the RHS instead.  This is
2161    done even if NLHS and LHS are the same, for it is understood that
2162    the RHS will be modified afterwards, and NLHS will not be assigned
2163    an equivalent value.
2164
2165    Adjusting any non-annotation uses of the LHS, if needed, is a
2166    responsibility of the caller.
2167
2168    The effect of this call should be pretty much the same as that of
2169    inserting a copy of STMT before STMT, and then removing the
2170    original stmt, at which time gsi_remove() would have update
2171    annotations, but using this function saves all the inserting,
2172    copying and removing.  */
2173
2174 void
2175 gimple_replace_lhs (gimple stmt, tree nlhs)
2176 {
2177   if (MAY_HAVE_DEBUG_STMTS)
2178     {
2179       tree lhs = gimple_get_lhs (stmt);
2180
2181       gcc_assert (SSA_NAME_DEF_STMT (lhs) == stmt);
2182
2183       insert_debug_temp_for_var_def (NULL, lhs);
2184     }
2185
2186   gimple_set_lhs (stmt, nlhs);
2187 }
2188
2189 /* Return a deep copy of statement STMT.  All the operands from STMT
2190    are reallocated and copied using unshare_expr.  The DEF, USE, VDEF
2191    and VUSE operand arrays are set to empty in the new copy.  */
2192
2193 gimple
2194 gimple_copy (gimple stmt)
2195 {
2196   enum gimple_code code = gimple_code (stmt);
2197   unsigned num_ops = gimple_num_ops (stmt);
2198   gimple copy = gimple_alloc (code, num_ops);
2199   unsigned i;
2200
2201   /* Shallow copy all the fields from STMT.  */
2202   memcpy (copy, stmt, gimple_size (code));
2203
2204   /* If STMT has sub-statements, deep-copy them as well.  */
2205   if (gimple_has_substatements (stmt))
2206     {
2207       gimple_seq new_seq;
2208       tree t;
2209
2210       switch (gimple_code (stmt))
2211         {
2212         case GIMPLE_BIND:
2213           new_seq = gimple_seq_copy (gimple_bind_body (stmt));
2214           gimple_bind_set_body (copy, new_seq);
2215           gimple_bind_set_vars (copy, unshare_expr (gimple_bind_vars (stmt)));
2216           gimple_bind_set_block (copy, gimple_bind_block (stmt));
2217           break;
2218
2219         case GIMPLE_CATCH:
2220           new_seq = gimple_seq_copy (gimple_catch_handler (stmt));
2221           gimple_catch_set_handler (copy, new_seq);
2222           t = unshare_expr (gimple_catch_types (stmt));
2223           gimple_catch_set_types (copy, t);
2224           break;
2225
2226         case GIMPLE_EH_FILTER:
2227           new_seq = gimple_seq_copy (gimple_eh_filter_failure (stmt));
2228           gimple_eh_filter_set_failure (copy, new_seq);
2229           t = unshare_expr (gimple_eh_filter_types (stmt));
2230           gimple_eh_filter_set_types (copy, t);
2231           break;
2232
2233         case GIMPLE_TRY:
2234           new_seq = gimple_seq_copy (gimple_try_eval (stmt));
2235           gimple_try_set_eval (copy, new_seq);
2236           new_seq = gimple_seq_copy (gimple_try_cleanup (stmt));
2237           gimple_try_set_cleanup (copy, new_seq);
2238           break;
2239
2240         case GIMPLE_OMP_FOR:
2241           new_seq = gimple_seq_copy (gimple_omp_for_pre_body (stmt));
2242           gimple_omp_for_set_pre_body (copy, new_seq);
2243           t = unshare_expr (gimple_omp_for_clauses (stmt));
2244           gimple_omp_for_set_clauses (copy, t);
2245           copy->gimple_omp_for.iter
2246             = ggc_alloc_vec_gimple_omp_for_iter
2247             (gimple_omp_for_collapse (stmt));
2248           for (i = 0; i < gimple_omp_for_collapse (stmt); i++)
2249             {
2250               gimple_omp_for_set_cond (copy, i,
2251                                        gimple_omp_for_cond (stmt, i));
2252               gimple_omp_for_set_index (copy, i,
2253                                         gimple_omp_for_index (stmt, i));
2254               t = unshare_expr (gimple_omp_for_initial (stmt, i));
2255               gimple_omp_for_set_initial (copy, i, t);
2256               t = unshare_expr (gimple_omp_for_final (stmt, i));
2257               gimple_omp_for_set_final (copy, i, t);
2258               t = unshare_expr (gimple_omp_for_incr (stmt, i));
2259               gimple_omp_for_set_incr (copy, i, t);
2260             }
2261           goto copy_omp_body;
2262
2263         case GIMPLE_OMP_PARALLEL:
2264           t = unshare_expr (gimple_omp_parallel_clauses (stmt));
2265           gimple_omp_parallel_set_clauses (copy, t);
2266           t = unshare_expr (gimple_omp_parallel_child_fn (stmt));
2267           gimple_omp_parallel_set_child_fn (copy, t);
2268           t = unshare_expr (gimple_omp_parallel_data_arg (stmt));
2269           gimple_omp_parallel_set_data_arg (copy, t);
2270           goto copy_omp_body;
2271
2272         case GIMPLE_OMP_TASK:
2273           t = unshare_expr (gimple_omp_task_clauses (stmt));
2274           gimple_omp_task_set_clauses (copy, t);
2275           t = unshare_expr (gimple_omp_task_child_fn (stmt));
2276           gimple_omp_task_set_child_fn (copy, t);
2277           t = unshare_expr (gimple_omp_task_data_arg (stmt));
2278           gimple_omp_task_set_data_arg (copy, t);
2279           t = unshare_expr (gimple_omp_task_copy_fn (stmt));
2280           gimple_omp_task_set_copy_fn (copy, t);
2281           t = unshare_expr (gimple_omp_task_arg_size (stmt));
2282           gimple_omp_task_set_arg_size (copy, t);
2283           t = unshare_expr (gimple_omp_task_arg_align (stmt));
2284           gimple_omp_task_set_arg_align (copy, t);
2285           goto copy_omp_body;
2286
2287         case GIMPLE_OMP_CRITICAL:
2288           t = unshare_expr (gimple_omp_critical_name (stmt));
2289           gimple_omp_critical_set_name (copy, t);
2290           goto copy_omp_body;
2291
2292         case GIMPLE_OMP_SECTIONS:
2293           t = unshare_expr (gimple_omp_sections_clauses (stmt));
2294           gimple_omp_sections_set_clauses (copy, t);
2295           t = unshare_expr (gimple_omp_sections_control (stmt));
2296           gimple_omp_sections_set_control (copy, t);
2297           /* FALLTHRU  */
2298
2299         case GIMPLE_OMP_SINGLE:
2300         case GIMPLE_OMP_SECTION:
2301         case GIMPLE_OMP_MASTER:
2302         case GIMPLE_OMP_ORDERED:
2303         copy_omp_body:
2304           new_seq = gimple_seq_copy (gimple_omp_body (stmt));
2305           gimple_omp_set_body (copy, new_seq);
2306           break;
2307
2308         case GIMPLE_WITH_CLEANUP_EXPR:
2309           new_seq = gimple_seq_copy (gimple_wce_cleanup (stmt));
2310           gimple_wce_set_cleanup (copy, new_seq);
2311           break;
2312
2313         default:
2314           gcc_unreachable ();
2315         }
2316     }
2317
2318   /* Make copy of operands.  */
2319   if (num_ops > 0)
2320     {
2321       for (i = 0; i < num_ops; i++)
2322         gimple_set_op (copy, i, unshare_expr (gimple_op (stmt, i)));
2323
2324       /* Clear out SSA operand vectors on COPY.  */
2325       if (gimple_has_ops (stmt))
2326         {
2327           gimple_set_def_ops (copy, NULL);
2328           gimple_set_use_ops (copy, NULL);
2329         }
2330
2331       if (gimple_has_mem_ops (stmt))
2332         {
2333           gimple_set_vdef (copy, gimple_vdef (stmt));
2334           gimple_set_vuse (copy, gimple_vuse (stmt));
2335         }
2336
2337       /* SSA operands need to be updated.  */
2338       gimple_set_modified (copy, true);
2339     }
2340
2341   return copy;
2342 }
2343
2344
2345 /* Set the MODIFIED flag to MODIFIEDP, iff the gimple statement G has
2346    a MODIFIED field.  */
2347
2348 void
2349 gimple_set_modified (gimple s, bool modifiedp)
2350 {
2351   if (gimple_has_ops (s))
2352     s->gsbase.modified = (unsigned) modifiedp;
2353 }
2354
2355
2356 /* Return true if statement S has side-effects.  We consider a
2357    statement to have side effects if:
2358
2359    - It is a GIMPLE_CALL not marked with ECF_PURE or ECF_CONST.
2360    - Any of its operands are marked TREE_THIS_VOLATILE or TREE_SIDE_EFFECTS.  */
2361
2362 bool
2363 gimple_has_side_effects (const_gimple s)
2364 {
2365   unsigned i;
2366
2367   if (is_gimple_debug (s))
2368     return false;
2369
2370   /* We don't have to scan the arguments to check for
2371      volatile arguments, though, at present, we still
2372      do a scan to check for TREE_SIDE_EFFECTS.  */
2373   if (gimple_has_volatile_ops (s))
2374     return true;
2375
2376   if (gimple_code (s) == GIMPLE_ASM
2377       && gimple_asm_volatile_p (s))
2378     return true;
2379
2380   if (is_gimple_call (s))
2381     {
2382       unsigned nargs = gimple_call_num_args (s);
2383       tree fn;
2384
2385       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2386         return true;
2387       else if (gimple_call_flags (s) & ECF_LOOPING_CONST_OR_PURE)
2388         /* An infinite loop is considered a side effect.  */
2389         return true;
2390
2391       if (gimple_call_lhs (s)
2392           && TREE_SIDE_EFFECTS (gimple_call_lhs (s)))
2393         {
2394           gcc_checking_assert (gimple_has_volatile_ops (s));
2395           return true;
2396         }
2397
2398       fn = gimple_call_fn (s);
2399       if (fn && TREE_SIDE_EFFECTS (fn))
2400         return true;
2401
2402       for (i = 0; i < nargs; i++)
2403         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i)))
2404           {
2405             gcc_checking_assert (gimple_has_volatile_ops (s));
2406             return true;
2407           }
2408
2409       return false;
2410     }
2411   else
2412     {
2413       for (i = 0; i < gimple_num_ops (s); i++)
2414         {
2415           tree op = gimple_op (s, i);
2416           if (op && TREE_SIDE_EFFECTS (op))
2417             {
2418               gcc_checking_assert (gimple_has_volatile_ops (s));
2419               return true;
2420             }
2421         }
2422     }
2423
2424   return false;
2425 }
2426
2427 /* Return true if the RHS of statement S has side effects.
2428    We may use it to determine if it is admissable to replace
2429    an assignment or call with a copy of a previously-computed
2430    value.  In such cases, side-effects due to the LHS are
2431    preserved.  */
2432
2433 bool
2434 gimple_rhs_has_side_effects (const_gimple s)
2435 {
2436   unsigned i;
2437
2438   if (is_gimple_call (s))
2439     {
2440       unsigned nargs = gimple_call_num_args (s);
2441       tree fn;
2442
2443       if (!(gimple_call_flags (s) & (ECF_CONST | ECF_PURE)))
2444         return true;
2445
2446       /* We cannot use gimple_has_volatile_ops here,
2447          because we must ignore a volatile LHS.  */
2448       fn = gimple_call_fn (s);
2449       if (fn && (TREE_SIDE_EFFECTS (fn) || TREE_THIS_VOLATILE (fn)))
2450         {
2451           gcc_assert (gimple_has_volatile_ops (s));
2452           return true;
2453         }
2454
2455       for (i = 0; i < nargs; i++)
2456         if (TREE_SIDE_EFFECTS (gimple_call_arg (s, i))
2457             || TREE_THIS_VOLATILE (gimple_call_arg (s, i)))
2458           return true;
2459
2460       return false;
2461     }
2462   else if (is_gimple_assign (s))
2463     {
2464       /* Skip the first operand, the LHS. */
2465       for (i = 1; i < gimple_num_ops (s); i++)
2466         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2467             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2468           {
2469             gcc_assert (gimple_has_volatile_ops (s));
2470             return true;
2471           }
2472     }
2473   else if (is_gimple_debug (s))
2474     return false;
2475   else
2476     {
2477       /* For statements without an LHS, examine all arguments.  */
2478       for (i = 0; i < gimple_num_ops (s); i++)
2479         if (TREE_SIDE_EFFECTS (gimple_op (s, i))
2480             || TREE_THIS_VOLATILE (gimple_op (s, i)))
2481           {
2482             gcc_assert (gimple_has_volatile_ops (s));
2483             return true;
2484           }
2485     }
2486
2487   return false;
2488 }
2489
2490 /* Helper for gimple_could_trap_p and gimple_assign_rhs_could_trap_p.
2491    Return true if S can trap.  When INCLUDE_MEM is true, check whether
2492    the memory operations could trap.  When INCLUDE_STORES is true and
2493    S is a GIMPLE_ASSIGN, the LHS of the assignment is also checked.  */
2494
2495 bool
2496 gimple_could_trap_p_1 (gimple s, bool include_mem, bool include_stores)
2497 {
2498   tree t, div = NULL_TREE;
2499   enum tree_code op;
2500
2501   if (include_mem)
2502     {
2503       unsigned i, start = (is_gimple_assign (s) && !include_stores) ? 1 : 0;
2504
2505       for (i = start; i < gimple_num_ops (s); i++)
2506         if (tree_could_trap_p (gimple_op (s, i)))
2507           return true;
2508     }
2509
2510   switch (gimple_code (s))
2511     {
2512     case GIMPLE_ASM:
2513       return gimple_asm_volatile_p (s);
2514
2515     case GIMPLE_CALL:
2516       t = gimple_call_fndecl (s);
2517       /* Assume that calls to weak functions may trap.  */
2518       if (!t || !DECL_P (t) || DECL_WEAK (t))
2519         return true;
2520       return false;
2521
2522     case GIMPLE_ASSIGN:
2523       t = gimple_expr_type (s);
2524       op = gimple_assign_rhs_code (s);
2525       if (get_gimple_rhs_class (op) == GIMPLE_BINARY_RHS)
2526         div = gimple_assign_rhs2 (s);
2527       return (operation_could_trap_p (op, FLOAT_TYPE_P (t),
2528                                       (INTEGRAL_TYPE_P (t)
2529                                        && TYPE_OVERFLOW_TRAPS (t)),
2530                                       div));
2531
2532     default:
2533       break;
2534     }
2535
2536   return false;
2537 }
2538
2539 /* Return true if statement S can trap.  */
2540
2541 bool
2542 gimple_could_trap_p (gimple s)
2543 {
2544   return gimple_could_trap_p_1 (s, true, true);
2545 }
2546
2547 /* Return true if RHS of a GIMPLE_ASSIGN S can trap.  */
2548
2549 bool
2550 gimple_assign_rhs_could_trap_p (gimple s)
2551 {
2552   gcc_assert (is_gimple_assign (s));
2553   return gimple_could_trap_p_1 (s, true, false);
2554 }
2555
2556
2557 /* Print debugging information for gimple stmts generated.  */
2558
2559 void
2560 dump_gimple_statistics (void)
2561 {
2562 #ifdef GATHER_STATISTICS
2563   int i, total_tuples = 0, total_bytes = 0;
2564
2565   fprintf (stderr, "\nGIMPLE statements\n");
2566   fprintf (stderr, "Kind                   Stmts      Bytes\n");
2567   fprintf (stderr, "---------------------------------------\n");
2568   for (i = 0; i < (int) gimple_alloc_kind_all; ++i)
2569     {
2570       fprintf (stderr, "%-20s %7d %10d\n", gimple_alloc_kind_names[i],
2571           gimple_alloc_counts[i], gimple_alloc_sizes[i]);
2572       total_tuples += gimple_alloc_counts[i];
2573       total_bytes += gimple_alloc_sizes[i];
2574     }
2575   fprintf (stderr, "---------------------------------------\n");
2576   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_tuples, total_bytes);
2577   fprintf (stderr, "---------------------------------------\n");
2578 #else
2579   fprintf (stderr, "No gimple statistics\n");
2580 #endif
2581 }
2582
2583
2584 /* Return the number of operands needed on the RHS of a GIMPLE
2585    assignment for an expression with tree code CODE.  */
2586
2587 unsigned
2588 get_gimple_rhs_num_ops (enum tree_code code)
2589 {
2590   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
2591
2592   if (rhs_class == GIMPLE_UNARY_RHS || rhs_class == GIMPLE_SINGLE_RHS)
2593     return 1;
2594   else if (rhs_class == GIMPLE_BINARY_RHS)
2595     return 2;
2596   else if (rhs_class == GIMPLE_TERNARY_RHS)
2597     return 3;
2598   else
2599     gcc_unreachable ();
2600 }
2601
2602 #define DEFTREECODE(SYM, STRING, TYPE, NARGS)                               \
2603   (unsigned char)                                                           \
2604   ((TYPE) == tcc_unary ? GIMPLE_UNARY_RHS                                   \
2605    : ((TYPE) == tcc_binary                                                  \
2606       || (TYPE) == tcc_comparison) ? GIMPLE_BINARY_RHS                      \
2607    : ((TYPE) == tcc_constant                                                \
2608       || (TYPE) == tcc_declaration                                          \
2609       || (TYPE) == tcc_reference) ? GIMPLE_SINGLE_RHS                       \
2610    : ((SYM) == TRUTH_AND_EXPR                                               \
2611       || (SYM) == TRUTH_OR_EXPR                                             \
2612       || (SYM) == TRUTH_XOR_EXPR) ? GIMPLE_BINARY_RHS                       \
2613    : (SYM) == TRUTH_NOT_EXPR ? GIMPLE_UNARY_RHS                             \
2614    : ((SYM) == WIDEN_MULT_PLUS_EXPR                                         \
2615       || (SYM) == WIDEN_MULT_MINUS_EXPR                                     \
2616       || (SYM) == DOT_PROD_EXPR                                             \
2617       || (SYM) == REALIGN_LOAD_EXPR                                         \
2618       || (SYM) == FMA_EXPR) ? GIMPLE_TERNARY_RHS                            \
2619    : ((SYM) == COND_EXPR                                                    \
2620       || (SYM) == CONSTRUCTOR                                               \
2621       || (SYM) == OBJ_TYPE_REF                                              \
2622       || (SYM) == ASSERT_EXPR                                               \
2623       || (SYM) == ADDR_EXPR                                                 \
2624       || (SYM) == WITH_SIZE_EXPR                                            \
2625       || (SYM) == SSA_NAME                                                  \
2626       || (SYM) == VEC_COND_EXPR) ? GIMPLE_SINGLE_RHS                        \
2627    : GIMPLE_INVALID_RHS),
2628 #define END_OF_BASE_TREE_CODES (unsigned char) GIMPLE_INVALID_RHS,
2629
2630 const unsigned char gimple_rhs_class_table[] = {
2631 #include "all-tree.def"
2632 };
2633
2634 #undef DEFTREECODE
2635 #undef END_OF_BASE_TREE_CODES
2636
2637 /* For the definitive definition of GIMPLE, see doc/tree-ssa.texi.  */
2638
2639 /* Validation of GIMPLE expressions.  */
2640
2641 /* Returns true iff T is a valid RHS for an assignment to a renamed
2642    user -- or front-end generated artificial -- variable.  */
2643
2644 bool
2645 is_gimple_reg_rhs (tree t)
2646 {
2647   return get_gimple_rhs_class (TREE_CODE (t)) != GIMPLE_INVALID_RHS;
2648 }
2649
2650 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
2651    LHS, or for a call argument.  */
2652
2653 bool
2654 is_gimple_mem_rhs (tree t)
2655 {
2656   /* If we're dealing with a renamable type, either source or dest must be
2657      a renamed variable.  */
2658   if (is_gimple_reg_type (TREE_TYPE (t)))
2659     return is_gimple_val (t);
2660   else
2661     return is_gimple_val (t) || is_gimple_lvalue (t);
2662 }
2663
2664 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
2665
2666 bool
2667 is_gimple_lvalue (tree t)
2668 {
2669   return (is_gimple_addressable (t)
2670           || TREE_CODE (t) == WITH_SIZE_EXPR
2671           /* These are complex lvalues, but don't have addresses, so they
2672              go here.  */
2673           || TREE_CODE (t) == BIT_FIELD_REF);
2674 }
2675
2676 /*  Return true if T is a GIMPLE condition.  */
2677
2678 bool
2679 is_gimple_condexpr (tree t)
2680 {
2681   return (is_gimple_val (t) || (COMPARISON_CLASS_P (t)
2682                                 && !tree_could_throw_p (t)
2683                                 && is_gimple_val (TREE_OPERAND (t, 0))
2684                                 && is_gimple_val (TREE_OPERAND (t, 1))));
2685 }
2686
2687 /*  Return true if T is something whose address can be taken.  */
2688
2689 bool
2690 is_gimple_addressable (tree t)
2691 {
2692   return (is_gimple_id (t) || handled_component_p (t)
2693           || TREE_CODE (t) == MEM_REF);
2694 }
2695
2696 /* Return true if T is a valid gimple constant.  */
2697
2698 bool
2699 is_gimple_constant (const_tree t)
2700 {
2701   switch (TREE_CODE (t))
2702     {
2703     case INTEGER_CST:
2704     case REAL_CST:
2705     case FIXED_CST:
2706     case STRING_CST:
2707     case COMPLEX_CST:
2708     case VECTOR_CST:
2709       return true;
2710
2711     /* Vector constant constructors are gimple invariant.  */
2712     case CONSTRUCTOR:
2713       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2714         return TREE_CONSTANT (t);
2715       else
2716         return false;
2717
2718     default:
2719       return false;
2720     }
2721 }
2722
2723 /* Return true if T is a gimple address.  */
2724
2725 bool
2726 is_gimple_address (const_tree t)
2727 {
2728   tree op;
2729
2730   if (TREE_CODE (t) != ADDR_EXPR)
2731     return false;
2732
2733   op = TREE_OPERAND (t, 0);
2734   while (handled_component_p (op))
2735     {
2736       if ((TREE_CODE (op) == ARRAY_REF
2737            || TREE_CODE (op) == ARRAY_RANGE_REF)
2738           && !is_gimple_val (TREE_OPERAND (op, 1)))
2739             return false;
2740
2741       op = TREE_OPERAND (op, 0);
2742     }
2743
2744   if (CONSTANT_CLASS_P (op) || TREE_CODE (op) == MEM_REF)
2745     return true;
2746
2747   switch (TREE_CODE (op))
2748     {
2749     case PARM_DECL:
2750     case RESULT_DECL:
2751     case LABEL_DECL:
2752     case FUNCTION_DECL:
2753     case VAR_DECL:
2754     case CONST_DECL:
2755       return true;
2756
2757     default:
2758       return false;
2759     }
2760 }
2761
2762 /* Strip out all handled components that produce invariant
2763    offsets.  */
2764
2765 static const_tree
2766 strip_invariant_refs (const_tree op)
2767 {
2768   while (handled_component_p (op))
2769     {
2770       switch (TREE_CODE (op))
2771         {
2772         case ARRAY_REF:
2773         case ARRAY_RANGE_REF:
2774           if (!is_gimple_constant (TREE_OPERAND (op, 1))
2775               || TREE_OPERAND (op, 2) != NULL_TREE
2776               || TREE_OPERAND (op, 3) != NULL_TREE)
2777             return NULL;
2778           break;
2779
2780         case COMPONENT_REF:
2781           if (TREE_OPERAND (op, 2) != NULL_TREE)
2782             return NULL;
2783           break;
2784
2785         default:;
2786         }
2787       op = TREE_OPERAND (op, 0);
2788     }
2789
2790   return op;
2791 }
2792
2793 /* Return true if T is a gimple invariant address.  */
2794
2795 bool
2796 is_gimple_invariant_address (const_tree t)
2797 {
2798   const_tree op;
2799
2800   if (TREE_CODE (t) != ADDR_EXPR)
2801     return false;
2802
2803   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2804   if (!op)
2805     return false;
2806
2807   if (TREE_CODE (op) == MEM_REF)
2808     {
2809       const_tree op0 = TREE_OPERAND (op, 0);
2810       return (TREE_CODE (op0) == ADDR_EXPR
2811               && (CONSTANT_CLASS_P (TREE_OPERAND (op0, 0))
2812                   || decl_address_invariant_p (TREE_OPERAND (op0, 0))));
2813     }
2814
2815   return CONSTANT_CLASS_P (op) || decl_address_invariant_p (op);
2816 }
2817
2818 /* Return true if T is a gimple invariant address at IPA level
2819    (so addresses of variables on stack are not allowed).  */
2820
2821 bool
2822 is_gimple_ip_invariant_address (const_tree t)
2823 {
2824   const_tree op;
2825
2826   if (TREE_CODE (t) != ADDR_EXPR)
2827     return false;
2828
2829   op = strip_invariant_refs (TREE_OPERAND (t, 0));
2830
2831   return op && (CONSTANT_CLASS_P (op) || decl_address_ip_invariant_p (op));
2832 }
2833
2834 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
2835    form of function invariant.  */
2836
2837 bool
2838 is_gimple_min_invariant (const_tree t)
2839 {
2840   if (TREE_CODE (t) == ADDR_EXPR)
2841     return is_gimple_invariant_address (t);
2842
2843   return is_gimple_constant (t);
2844 }
2845
2846 /* Return true if T is a GIMPLE interprocedural invariant.  It's a restricted
2847    form of gimple minimal invariant.  */
2848
2849 bool
2850 is_gimple_ip_invariant (const_tree t)
2851 {
2852   if (TREE_CODE (t) == ADDR_EXPR)
2853     return is_gimple_ip_invariant_address (t);
2854
2855   return is_gimple_constant (t);
2856 }
2857
2858 /* Return true if T looks like a valid GIMPLE statement.  */
2859
2860 bool
2861 is_gimple_stmt (tree t)
2862 {
2863   const enum tree_code code = TREE_CODE (t);
2864
2865   switch (code)
2866     {
2867     case NOP_EXPR:
2868       /* The only valid NOP_EXPR is the empty statement.  */
2869       return IS_EMPTY_STMT (t);
2870
2871     case BIND_EXPR:
2872     case COND_EXPR:
2873       /* These are only valid if they're void.  */
2874       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
2875
2876     case SWITCH_EXPR:
2877     case GOTO_EXPR:
2878     case RETURN_EXPR:
2879     case LABEL_EXPR:
2880     case CASE_LABEL_EXPR:
2881     case TRY_CATCH_EXPR:
2882     case TRY_FINALLY_EXPR:
2883     case EH_FILTER_EXPR:
2884     case CATCH_EXPR:
2885     case ASM_EXPR:
2886     case STATEMENT_LIST:
2887     case OMP_PARALLEL:
2888     case OMP_FOR:
2889     case OMP_SECTIONS:
2890     case OMP_SECTION:
2891     case OMP_SINGLE:
2892     case OMP_MASTER:
2893     case OMP_ORDERED:
2894     case OMP_CRITICAL:
2895     case OMP_TASK:
2896       /* These are always void.  */
2897       return true;
2898
2899     case CALL_EXPR:
2900     case MODIFY_EXPR:
2901     case PREDICT_EXPR:
2902       /* These are valid regardless of their type.  */
2903       return true;
2904
2905     default:
2906       return false;
2907     }
2908 }
2909
2910 /* Return true if T is a variable.  */
2911
2912 bool
2913 is_gimple_variable (tree t)
2914 {
2915   return (TREE_CODE (t) == VAR_DECL
2916           || TREE_CODE (t) == PARM_DECL
2917           || TREE_CODE (t) == RESULT_DECL
2918           || TREE_CODE (t) == SSA_NAME);
2919 }
2920
2921 /*  Return true if T is a GIMPLE identifier (something with an address).  */
2922
2923 bool
2924 is_gimple_id (tree t)
2925 {
2926   return (is_gimple_variable (t)
2927           || TREE_CODE (t) == FUNCTION_DECL
2928           || TREE_CODE (t) == LABEL_DECL
2929           || TREE_CODE (t) == CONST_DECL
2930           /* Allow string constants, since they are addressable.  */
2931           || TREE_CODE (t) == STRING_CST);
2932 }
2933
2934 /* Return true if TYPE is a suitable type for a scalar register variable.  */
2935
2936 bool
2937 is_gimple_reg_type (tree type)
2938 {
2939   return !AGGREGATE_TYPE_P (type);
2940 }
2941
2942 /* Return true if T is a non-aggregate register variable.  */
2943
2944 bool
2945 is_gimple_reg (tree t)
2946 {
2947   if (TREE_CODE (t) == SSA_NAME)
2948     t = SSA_NAME_VAR (t);
2949
2950   if (!is_gimple_variable (t))
2951     return false;
2952
2953   if (!is_gimple_reg_type (TREE_TYPE (t)))
2954     return false;
2955
2956   /* A volatile decl is not acceptable because we can't reuse it as
2957      needed.  We need to copy it into a temp first.  */
2958   if (TREE_THIS_VOLATILE (t))
2959     return false;
2960
2961   /* We define "registers" as things that can be renamed as needed,
2962      which with our infrastructure does not apply to memory.  */
2963   if (needs_to_live_in_memory (t))
2964     return false;
2965
2966   /* Hard register variables are an interesting case.  For those that
2967      are call-clobbered, we don't know where all the calls are, since
2968      we don't (want to) take into account which operations will turn
2969      into libcalls at the rtl level.  For those that are call-saved,
2970      we don't currently model the fact that calls may in fact change
2971      global hard registers, nor do we examine ASM_CLOBBERS at the tree
2972      level, and so miss variable changes that might imply.  All around,
2973      it seems safest to not do too much optimization with these at the
2974      tree level at all.  We'll have to rely on the rtl optimizers to
2975      clean this up, as there we've got all the appropriate bits exposed.  */
2976   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
2977     return false;
2978
2979   /* Complex and vector values must have been put into SSA-like form.
2980      That is, no assignments to the individual components.  */
2981   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
2982       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2983     return DECL_GIMPLE_REG_P (t);
2984
2985   return true;
2986 }
2987
2988
2989 /* Return true if T is a GIMPLE variable whose address is not needed.  */
2990
2991 bool
2992 is_gimple_non_addressable (tree t)
2993 {
2994   if (TREE_CODE (t) == SSA_NAME)
2995     t = SSA_NAME_VAR (t);
2996
2997   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
2998 }
2999
3000 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
3001
3002 bool
3003 is_gimple_val (tree t)
3004 {
3005   /* Make loads from volatiles and memory vars explicit.  */
3006   if (is_gimple_variable (t)
3007       && is_gimple_reg_type (TREE_TYPE (t))
3008       && !is_gimple_reg (t))
3009     return false;
3010
3011   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
3012 }
3013
3014 /* Similarly, but accept hard registers as inputs to asm statements.  */
3015
3016 bool
3017 is_gimple_asm_val (tree t)
3018 {
3019   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
3020     return true;
3021
3022   return is_gimple_val (t);
3023 }
3024
3025 /* Return true if T is a GIMPLE minimal lvalue.  */
3026
3027 bool
3028 is_gimple_min_lval (tree t)
3029 {
3030   if (!(t = CONST_CAST_TREE (strip_invariant_refs (t))))
3031     return false;
3032   return (is_gimple_id (t) || TREE_CODE (t) == MEM_REF);
3033 }
3034
3035 /* Return true if T is a valid function operand of a CALL_EXPR.  */
3036
3037 bool
3038 is_gimple_call_addr (tree t)
3039 {
3040   return (TREE_CODE (t) == OBJ_TYPE_REF || is_gimple_val (t));
3041 }
3042
3043 /* Return true if T is a valid address operand of a MEM_REF.  */
3044
3045 bool
3046 is_gimple_mem_ref_addr (tree t)
3047 {
3048   return (is_gimple_reg (t)
3049           || TREE_CODE (t) == INTEGER_CST
3050           || (TREE_CODE (t) == ADDR_EXPR
3051               && (CONSTANT_CLASS_P (TREE_OPERAND (t, 0))
3052                   || decl_address_invariant_p (TREE_OPERAND (t, 0)))));
3053 }
3054
3055 /* If T makes a function call, return the corresponding CALL_EXPR operand.
3056    Otherwise, return NULL_TREE.  */
3057
3058 tree
3059 get_call_expr_in (tree t)
3060 {
3061   if (TREE_CODE (t) == MODIFY_EXPR)
3062     t = TREE_OPERAND (t, 1);
3063   if (TREE_CODE (t) == WITH_SIZE_EXPR)
3064     t = TREE_OPERAND (t, 0);
3065   if (TREE_CODE (t) == CALL_EXPR)
3066     return t;
3067   return NULL_TREE;
3068 }
3069
3070
3071 /* Given a memory reference expression T, return its base address.
3072    The base address of a memory reference expression is the main
3073    object being referenced.  For instance, the base address for
3074    'array[i].fld[j]' is 'array'.  You can think of this as stripping
3075    away the offset part from a memory address.
3076
3077    This function calls handled_component_p to strip away all the inner
3078    parts of the memory reference until it reaches the base object.  */
3079
3080 tree
3081 get_base_address (tree t)
3082 {
3083   while (handled_component_p (t))
3084     t = TREE_OPERAND (t, 0);
3085
3086   if ((TREE_CODE (t) == MEM_REF
3087        || TREE_CODE (t) == TARGET_MEM_REF)
3088       && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR)
3089     t = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
3090
3091   if (TREE_CODE (t) == SSA_NAME
3092       || DECL_P (t)
3093       || TREE_CODE (t) == STRING_CST
3094       || TREE_CODE (t) == CONSTRUCTOR
3095       || INDIRECT_REF_P (t)
3096       || TREE_CODE (t) == MEM_REF
3097       || TREE_CODE (t) == TARGET_MEM_REF)
3098     return t;
3099   else
3100     return NULL_TREE;
3101 }
3102
3103 void
3104 recalculate_side_effects (tree t)
3105 {
3106   enum tree_code code = TREE_CODE (t);
3107   int len = TREE_OPERAND_LENGTH (t);
3108   int i;
3109
3110   switch (TREE_CODE_CLASS (code))
3111     {
3112     case tcc_expression:
3113       switch (code)
3114         {
3115         case INIT_EXPR:
3116         case MODIFY_EXPR:
3117         case VA_ARG_EXPR:
3118         case PREDECREMENT_EXPR:
3119         case PREINCREMENT_EXPR:
3120         case POSTDECREMENT_EXPR:
3121         case POSTINCREMENT_EXPR:
3122           /* All of these have side-effects, no matter what their
3123              operands are.  */
3124           return;
3125
3126         default:
3127           break;
3128         }
3129       /* Fall through.  */
3130
3131     case tcc_comparison:  /* a comparison expression */
3132     case tcc_unary:       /* a unary arithmetic expression */
3133     case tcc_binary:      /* a binary arithmetic expression */
3134     case tcc_reference:   /* a reference */
3135     case tcc_vl_exp:        /* a function call */
3136       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
3137       for (i = 0; i < len; ++i)
3138         {
3139           tree op = TREE_OPERAND (t, i);
3140           if (op && TREE_SIDE_EFFECTS (op))
3141             TREE_SIDE_EFFECTS (t) = 1;
3142         }
3143       break;
3144
3145     case tcc_constant:
3146       /* No side-effects.  */
3147       return;
3148
3149     default:
3150       gcc_unreachable ();
3151    }
3152 }
3153
3154 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
3155    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
3156    we failed to create one.  */
3157
3158 tree
3159 canonicalize_cond_expr_cond (tree t)
3160 {
3161   /* Strip conversions around boolean operations.  */
3162   if (CONVERT_EXPR_P (t)
3163       && truth_value_p (TREE_CODE (TREE_OPERAND (t, 0))))
3164     t = TREE_OPERAND (t, 0);
3165
3166   /* For !x use x == 0.  */
3167   if (TREE_CODE (t) == TRUTH_NOT_EXPR)
3168     {
3169       tree top0 = TREE_OPERAND (t, 0);
3170       t = build2 (EQ_EXPR, TREE_TYPE (t),
3171                   top0, build_int_cst (TREE_TYPE (top0), 0));
3172     }
3173   /* For cmp ? 1 : 0 use cmp.  */
3174   else if (TREE_CODE (t) == COND_EXPR
3175            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
3176            && integer_onep (TREE_OPERAND (t, 1))
3177            && integer_zerop (TREE_OPERAND (t, 2)))
3178     {
3179       tree top0 = TREE_OPERAND (t, 0);
3180       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
3181                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
3182     }
3183
3184   if (is_gimple_condexpr (t))
3185     return t;
3186
3187   return NULL_TREE;
3188 }
3189
3190 /* Build a GIMPLE_CALL identical to STMT but skipping the arguments in
3191    the positions marked by the set ARGS_TO_SKIP.  */
3192
3193 gimple
3194 gimple_call_copy_skip_args (gimple stmt, bitmap args_to_skip)
3195 {
3196   int i;
3197   int nargs = gimple_call_num_args (stmt);
3198   VEC(tree, heap) *vargs = VEC_alloc (tree, heap, nargs);
3199   gimple new_stmt;
3200
3201   for (i = 0; i < nargs; i++)
3202     if (!bitmap_bit_p (args_to_skip, i))
3203       VEC_quick_push (tree, vargs, gimple_call_arg (stmt, i));
3204
3205   if (gimple_call_internal_p (stmt))
3206     new_stmt = gimple_build_call_internal_vec (gimple_call_internal_fn (stmt),
3207                                                vargs);
3208   else
3209     new_stmt = gimple_build_call_vec (gimple_call_fn (stmt), vargs);
3210   VEC_free (tree, heap, vargs);
3211   if (gimple_call_lhs (stmt))
3212     gimple_call_set_lhs (new_stmt, gimple_call_lhs (stmt));
3213
3214   gimple_set_vuse (new_stmt, gimple_vuse (stmt));
3215   gimple_set_vdef (new_stmt, gimple_vdef (stmt));
3216
3217   gimple_set_block (new_stmt, gimple_block (stmt));
3218   if (gimple_has_location (stmt))
3219     gimple_set_location (new_stmt, gimple_location (stmt));
3220   gimple_call_copy_flags (new_stmt, stmt);
3221   gimple_call_set_chain (new_stmt, gimple_call_chain (stmt));
3222
3223   gimple_set_modified (new_stmt, true);
3224
3225   return new_stmt;
3226 }
3227
3228
3229 enum gtc_mode { GTC_MERGE = 0, GTC_DIAG = 1 };
3230
3231 static hashval_t gimple_type_hash (const void *);
3232
3233 /* Structure used to maintain a cache of some type pairs compared by
3234    gimple_types_compatible_p when comparing aggregate types.  There are
3235    three possible values for SAME_P:
3236
3237         -2: The pair (T1, T2) has just been inserted in the table.
3238          0: T1 and T2 are different types.
3239          1: T1 and T2 are the same type.
3240
3241    The two elements in the SAME_P array are indexed by the comparison
3242    mode gtc_mode.  */
3243
3244 struct type_pair_d
3245 {
3246   unsigned int uid1;
3247   unsigned int uid2;
3248   signed char same_p[2];
3249 };
3250 typedef struct type_pair_d *type_pair_t;
3251 DEF_VEC_P(type_pair_t);
3252 DEF_VEC_ALLOC_P(type_pair_t,heap);
3253
3254 #define GIMPLE_TYPE_PAIR_SIZE 16381
3255 struct type_pair_d *type_pair_cache;
3256
3257
3258 /* Lookup the pair of types T1 and T2 in *VISITED_P.  Insert a new
3259    entry if none existed.  */
3260
3261 static inline type_pair_t
3262 lookup_type_pair (tree t1, tree t2)
3263 {
3264   unsigned int index;
3265   unsigned int uid1, uid2;
3266
3267   if (type_pair_cache == NULL)
3268     type_pair_cache = XCNEWVEC (struct type_pair_d, GIMPLE_TYPE_PAIR_SIZE);
3269
3270   if (TYPE_UID (t1) < TYPE_UID (t2))
3271     {
3272       uid1 = TYPE_UID (t1);
3273       uid2 = TYPE_UID (t2);
3274     }
3275   else
3276     {
3277       uid1 = TYPE_UID (t2);
3278       uid2 = TYPE_UID (t1);
3279     }
3280   gcc_checking_assert (uid1 != uid2);
3281
3282   /* iterative_hash_hashval_t imply an function calls.
3283      We know that UIDS are in limited range.  */
3284   index = ((((unsigned HOST_WIDE_INT)uid1 << HOST_BITS_PER_WIDE_INT / 2) + uid2)
3285            % GIMPLE_TYPE_PAIR_SIZE);
3286   if (type_pair_cache [index].uid1 == uid1
3287       && type_pair_cache [index].uid2 == uid2)
3288     return &type_pair_cache[index];
3289
3290   type_pair_cache [index].uid1 = uid1;
3291   type_pair_cache [index].uid2 = uid2;
3292   type_pair_cache [index].same_p[0] = -2;
3293   type_pair_cache [index].same_p[1] = -2;
3294
3295   return &type_pair_cache[index];
3296 }
3297
3298 /* Per pointer state for the SCC finding.  The on_sccstack flag
3299    is not strictly required, it is true when there is no hash value
3300    recorded for the type and false otherwise.  But querying that
3301    is slower.  */
3302
3303 struct sccs
3304 {
3305   unsigned int dfsnum;
3306   unsigned int low;
3307   bool on_sccstack;
3308   union {
3309     hashval_t hash;
3310     signed char same_p;
3311   } u;
3312 };
3313
3314 static unsigned int next_dfs_num;
3315 static unsigned int gtc_next_dfs_num;
3316
3317
3318 /* GIMPLE type merging cache.  A direct-mapped cache based on TYPE_UID.  */
3319
3320 typedef struct GTY(()) gimple_type_leader_entry_s {
3321   tree type;
3322   tree leader;
3323 } gimple_type_leader_entry;
3324
3325 #define GIMPLE_TYPE_LEADER_SIZE 16381
3326 static GTY((deletable, length("GIMPLE_TYPE_LEADER_SIZE")))
3327   gimple_type_leader_entry *gimple_type_leader;
3328
3329 /* Lookup an existing leader for T and return it or NULL_TREE, if
3330    there is none in the cache.  */
3331
3332 static inline tree
3333 gimple_lookup_type_leader (tree t)
3334 {
3335   gimple_type_leader_entry *leader;
3336
3337   if (!gimple_type_leader)
3338     return NULL_TREE;
3339
3340   leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
3341   if (leader->type != t)
3342     return NULL_TREE;
3343
3344   return leader->leader;
3345 }
3346
3347 /* Return true if T1 and T2 have the same name.  If FOR_COMPLETION_P is
3348    true then if any type has no name return false, otherwise return
3349    true if both types have no names.  */
3350
3351 static bool
3352 compare_type_names_p (tree t1, tree t2)
3353 {
3354   tree name1 = TYPE_NAME (t1);
3355   tree name2 = TYPE_NAME (t2);
3356
3357   if (name1 && TREE_CODE (name1) == TYPE_DECL)
3358     name1 = DECL_NAME (name1);
3359   gcc_checking_assert (!name1 || TREE_CODE (name1) == IDENTIFIER_NODE);
3360
3361   if (name2 && TREE_CODE (name2) == TYPE_DECL)
3362     name2 = DECL_NAME (name2);
3363   gcc_checking_assert (!name2 || TREE_CODE (name2) == IDENTIFIER_NODE);
3364
3365   /* Identifiers can be compared with pointer equality rather
3366      than a string comparison.  */
3367   if (name1 == name2)
3368     return true;
3369
3370   return false;
3371 }
3372
3373 /* Return true if the field decls F1 and F2 are at the same offset.
3374
3375    This is intended to be used on GIMPLE types only.  */
3376
3377 bool
3378 gimple_compare_field_offset (tree f1, tree f2)
3379 {
3380   if (DECL_OFFSET_ALIGN (f1) == DECL_OFFSET_ALIGN (f2))
3381     {
3382       tree offset1 = DECL_FIELD_OFFSET (f1);
3383       tree offset2 = DECL_FIELD_OFFSET (f2);
3384       return ((offset1 == offset2
3385                /* Once gimplification is done, self-referential offsets are
3386                   instantiated as operand #2 of the COMPONENT_REF built for
3387                   each access and reset.  Therefore, they are not relevant
3388                   anymore and fields are interchangeable provided that they
3389                   represent the same access.  */
3390                || (TREE_CODE (offset1) == PLACEHOLDER_EXPR
3391                    && TREE_CODE (offset2) == PLACEHOLDER_EXPR
3392                    && (DECL_SIZE (f1) == DECL_SIZE (f2)
3393                        || (TREE_CODE (DECL_SIZE (f1)) == PLACEHOLDER_EXPR
3394                            && TREE_CODE (DECL_SIZE (f2)) == PLACEHOLDER_EXPR)
3395                        || operand_equal_p (DECL_SIZE (f1), DECL_SIZE (f2), 0))
3396                    && DECL_ALIGN (f1) == DECL_ALIGN (f2))
3397                || operand_equal_p (offset1, offset2, 0))
3398               && tree_int_cst_equal (DECL_FIELD_BIT_OFFSET (f1),
3399                                      DECL_FIELD_BIT_OFFSET (f2)));
3400     }
3401
3402   /* Fortran and C do not always agree on what DECL_OFFSET_ALIGN
3403      should be, so handle differing ones specially by decomposing
3404      the offset into a byte and bit offset manually.  */
3405   if (host_integerp (DECL_FIELD_OFFSET (f1), 0)
3406       && host_integerp (DECL_FIELD_OFFSET (f2), 0))
3407     {
3408       unsigned HOST_WIDE_INT byte_offset1, byte_offset2;
3409       unsigned HOST_WIDE_INT bit_offset1, bit_offset2;
3410       bit_offset1 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f1));
3411       byte_offset1 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f1))
3412                       + bit_offset1 / BITS_PER_UNIT);
3413       bit_offset2 = TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (f2));
3414       byte_offset2 = (TREE_INT_CST_LOW (DECL_FIELD_OFFSET (f2))
3415                       + bit_offset2 / BITS_PER_UNIT);
3416       if (byte_offset1 != byte_offset2)
3417         return false;
3418       return bit_offset1 % BITS_PER_UNIT == bit_offset2 % BITS_PER_UNIT;
3419     }
3420
3421   return false;
3422 }
3423
3424 static bool
3425 gimple_types_compatible_p_1 (tree, tree, type_pair_t,
3426                              VEC(type_pair_t, heap) **,
3427                              struct pointer_map_t *, struct obstack *);
3428
3429 /* DFS visit the edge from the callers type pair with state *STATE to
3430    the pair T1, T2 while operating in FOR_MERGING_P mode.
3431    Update the merging status if it is not part of the SCC containing the
3432    callers pair and return it.
3433    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3434
3435 static bool
3436 gtc_visit (tree t1, tree t2,
3437            struct sccs *state,
3438            VEC(type_pair_t, heap) **sccstack,
3439            struct pointer_map_t *sccstate,
3440            struct obstack *sccstate_obstack)
3441 {
3442   struct sccs *cstate = NULL;
3443   type_pair_t p;
3444   void **slot;
3445   tree leader1, leader2;
3446
3447   /* Check first for the obvious case of pointer identity.  */
3448   if (t1 == t2)
3449     return true;
3450
3451   /* Check that we have two types to compare.  */
3452   if (t1 == NULL_TREE || t2 == NULL_TREE)
3453     return false;
3454
3455   /* Can't be the same type if the types don't have the same code.  */
3456   if (TREE_CODE (t1) != TREE_CODE (t2))
3457     return false;
3458
3459   /* Can't be the same type if they have different CV qualifiers.  */
3460   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3461     return false;
3462
3463   if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
3464     return false;
3465
3466   /* Void types and nullptr types are always the same.  */
3467   if (TREE_CODE (t1) == VOID_TYPE
3468       || TREE_CODE (t1) == NULLPTR_TYPE)
3469     return true;
3470
3471   /* Can't be the same type if they have different alignment or mode.  */
3472   if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3473       || TYPE_MODE (t1) != TYPE_MODE (t2))
3474     return false;
3475
3476   /* Do some simple checks before doing three hashtable queries.  */
3477   if (INTEGRAL_TYPE_P (t1)
3478       || SCALAR_FLOAT_TYPE_P (t1)
3479       || FIXED_POINT_TYPE_P (t1)
3480       || TREE_CODE (t1) == VECTOR_TYPE
3481       || TREE_CODE (t1) == COMPLEX_TYPE
3482       || TREE_CODE (t1) == OFFSET_TYPE
3483       || POINTER_TYPE_P (t1))
3484     {
3485       /* Can't be the same type if they have different sign or precision.  */
3486       if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3487           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3488         return false;
3489
3490       if (TREE_CODE (t1) == INTEGER_TYPE
3491           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3492               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3493         return false;
3494
3495       /* That's all we need to check for float and fixed-point types.  */
3496       if (SCALAR_FLOAT_TYPE_P (t1)
3497           || FIXED_POINT_TYPE_P (t1))
3498         return true;
3499
3500       /* For other types fall thru to more complex checks.  */
3501     }
3502
3503   /* If the types have been previously registered and found equal
3504      they still are.  */
3505   leader1 = gimple_lookup_type_leader (t1);
3506   leader2 = gimple_lookup_type_leader (t2);
3507   if (leader1 == t2
3508       || t1 == leader2
3509       || (leader1 && leader1 == leader2))
3510     return true;
3511
3512   /* If the hash values of t1 and t2 are different the types can't
3513      possibly be the same.  This helps keeping the type-pair hashtable
3514      small, only tracking comparisons for hash collisions.  */
3515   if (gimple_type_hash (t1) != gimple_type_hash (t2))
3516     return false;
3517
3518   /* Allocate a new cache entry for this comparison.  */
3519   p = lookup_type_pair (t1, t2);
3520   if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
3521     {
3522       /* We have already decided whether T1 and T2 are the
3523          same, return the cached result.  */
3524       return p->same_p[GTC_MERGE] == 1;
3525     }
3526
3527   if ((slot = pointer_map_contains (sccstate, p)) != NULL)
3528     cstate = (struct sccs *)*slot;
3529   /* Not yet visited.  DFS recurse.  */
3530   if (!cstate)
3531     {
3532       gimple_types_compatible_p_1 (t1, t2, p,
3533                                    sccstack, sccstate, sccstate_obstack);
3534       cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
3535       state->low = MIN (state->low, cstate->low);
3536     }
3537   /* If the type is still on the SCC stack adjust the parents low.  */
3538   if (cstate->dfsnum < state->dfsnum
3539       && cstate->on_sccstack)
3540     state->low = MIN (cstate->dfsnum, state->low);
3541
3542   /* Return the current lattice value.  We start with an equality
3543      assumption so types part of a SCC will be optimistically
3544      treated equal unless proven otherwise.  */
3545   return cstate->u.same_p;
3546 }
3547
3548 /* Worker for gimple_types_compatible.
3549    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3550
3551 static bool
3552 gimple_types_compatible_p_1 (tree t1, tree t2, type_pair_t p,
3553                              VEC(type_pair_t, heap) **sccstack,
3554                              struct pointer_map_t *sccstate,
3555                              struct obstack *sccstate_obstack)
3556 {
3557   struct sccs *state;
3558
3559   gcc_assert (p->same_p[GTC_MERGE] == -2);
3560
3561   state = XOBNEW (sccstate_obstack, struct sccs);
3562   *pointer_map_insert (sccstate, p) = state;
3563
3564   VEC_safe_push (type_pair_t, heap, *sccstack, p);
3565   state->dfsnum = gtc_next_dfs_num++;
3566   state->low = state->dfsnum;
3567   state->on_sccstack = true;
3568   /* Start with an equality assumption.  As we DFS recurse into child
3569      SCCs this assumption may get revisited.  */
3570   state->u.same_p = 1;
3571
3572   /* The struct tags shall compare equal.  */
3573   if (!compare_type_names_p (t1, t2))
3574     goto different_types;
3575
3576   /* If their attributes are not the same they can't be the same type.  */
3577   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
3578     goto different_types;
3579
3580   /* Do type-specific comparisons.  */
3581   switch (TREE_CODE (t1))
3582     {
3583     case VECTOR_TYPE:
3584     case COMPLEX_TYPE:
3585       if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
3586                       state, sccstack, sccstate, sccstate_obstack))
3587         goto different_types;
3588       goto same_types;
3589
3590     case ARRAY_TYPE:
3591       /* Array types are the same if the element types are the same and
3592          the number of elements are the same.  */
3593       if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
3594                       state, sccstack, sccstate, sccstate_obstack)
3595           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
3596           || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
3597         goto different_types;
3598       else
3599         {
3600           tree i1 = TYPE_DOMAIN (t1);
3601           tree i2 = TYPE_DOMAIN (t2);
3602
3603           /* For an incomplete external array, the type domain can be
3604              NULL_TREE.  Check this condition also.  */
3605           if (i1 == NULL_TREE && i2 == NULL_TREE)
3606             goto same_types;
3607           else if (i1 == NULL_TREE || i2 == NULL_TREE)
3608             goto different_types;
3609           /* If for a complete array type the possibly gimplified sizes
3610              are different the types are different.  */
3611           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
3612                    || (TYPE_SIZE (i1)
3613                        && TYPE_SIZE (i2)
3614                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
3615             goto different_types;
3616           else
3617             {
3618               tree min1 = TYPE_MIN_VALUE (i1);
3619               tree min2 = TYPE_MIN_VALUE (i2);
3620               tree max1 = TYPE_MAX_VALUE (i1);
3621               tree max2 = TYPE_MAX_VALUE (i2);
3622
3623               /* The minimum/maximum values have to be the same.  */
3624               if ((min1 == min2
3625                    || (min1 && min2
3626                        && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
3627                             && TREE_CODE (min2) == PLACEHOLDER_EXPR)
3628                            || operand_equal_p (min1, min2, 0))))
3629                   && (max1 == max2
3630                       || (max1 && max2
3631                           && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
3632                                && TREE_CODE (max2) == PLACEHOLDER_EXPR)
3633                               || operand_equal_p (max1, max2, 0)))))
3634                 goto same_types;
3635               else
3636                 goto different_types;
3637             }
3638         }
3639
3640     case METHOD_TYPE:
3641       /* Method types should belong to the same class.  */
3642       if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2),
3643                       state, sccstack, sccstate, sccstate_obstack))
3644         goto different_types;
3645
3646       /* Fallthru  */
3647
3648     case FUNCTION_TYPE:
3649       /* Function types are the same if the return type and arguments types
3650          are the same.  */
3651       if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
3652                       state, sccstack, sccstate, sccstate_obstack))
3653         goto different_types;
3654
3655       if (!comp_type_attributes (t1, t2))
3656         goto different_types;
3657
3658       if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
3659         goto same_types;
3660       else
3661         {
3662           tree parms1, parms2;
3663
3664           for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
3665                parms1 && parms2;
3666                parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
3667             {
3668               if (!gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2),
3669                               state, sccstack, sccstate, sccstate_obstack))
3670                 goto different_types;
3671             }
3672
3673           if (parms1 || parms2)
3674             goto different_types;
3675
3676           goto same_types;
3677         }
3678
3679     case OFFSET_TYPE:
3680       {
3681         if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
3682                         state, sccstack, sccstate, sccstate_obstack)
3683             || !gtc_visit (TYPE_OFFSET_BASETYPE (t1),
3684                            TYPE_OFFSET_BASETYPE (t2),
3685                            state, sccstack, sccstate, sccstate_obstack))
3686           goto different_types;
3687
3688         goto same_types;
3689       }
3690
3691     case POINTER_TYPE:
3692     case REFERENCE_TYPE:
3693       {
3694         /* If the two pointers have different ref-all attributes,
3695            they can't be the same type.  */
3696         if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
3697           goto different_types;
3698
3699         /* Otherwise, pointer and reference types are the same if the
3700            pointed-to types are the same.  */
3701         if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
3702                        state, sccstack, sccstate, sccstate_obstack))
3703           goto same_types;
3704
3705         goto different_types;
3706       }
3707
3708     case INTEGER_TYPE:
3709     case BOOLEAN_TYPE:
3710       {
3711         tree min1 = TYPE_MIN_VALUE (t1);
3712         tree max1 = TYPE_MAX_VALUE (t1);
3713         tree min2 = TYPE_MIN_VALUE (t2);
3714         tree max2 = TYPE_MAX_VALUE (t2);
3715         bool min_equal_p = false;
3716         bool max_equal_p = false;
3717
3718         /* If either type has a minimum value, the other type must
3719            have the same.  */
3720         if (min1 == NULL_TREE && min2 == NULL_TREE)
3721           min_equal_p = true;
3722         else if (min1 && min2 && operand_equal_p (min1, min2, 0))
3723           min_equal_p = true;
3724
3725         /* Likewise, if either type has a maximum value, the other
3726            type must have the same.  */
3727         if (max1 == NULL_TREE && max2 == NULL_TREE)
3728           max_equal_p = true;
3729         else if (max1 && max2 && operand_equal_p (max1, max2, 0))
3730           max_equal_p = true;
3731
3732         if (!min_equal_p || !max_equal_p)
3733           goto different_types;
3734
3735         goto same_types;
3736       }
3737
3738     case ENUMERAL_TYPE:
3739       {
3740         /* FIXME lto, we cannot check bounds on enumeral types because
3741            different front ends will produce different values.
3742            In C, enumeral types are integers, while in C++ each element
3743            will have its own symbolic value.  We should decide how enums
3744            are to be represented in GIMPLE and have each front end lower
3745            to that.  */
3746         tree v1, v2;
3747
3748         /* For enumeral types, all the values must be the same.  */
3749         if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
3750           goto same_types;
3751
3752         for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
3753              v1 && v2;
3754              v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
3755           {
3756             tree c1 = TREE_VALUE (v1);
3757             tree c2 = TREE_VALUE (v2);
3758
3759             if (TREE_CODE (c1) == CONST_DECL)
3760               c1 = DECL_INITIAL (c1);
3761
3762             if (TREE_CODE (c2) == CONST_DECL)
3763               c2 = DECL_INITIAL (c2);
3764
3765             if (tree_int_cst_equal (c1, c2) != 1)
3766               goto different_types;
3767
3768             if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
3769               goto different_types;
3770           }
3771
3772         /* If one enumeration has more values than the other, they
3773            are not the same.  */
3774         if (v1 || v2)
3775           goto different_types;
3776
3777         goto same_types;
3778       }
3779
3780     case RECORD_TYPE:
3781     case UNION_TYPE:
3782     case QUAL_UNION_TYPE:
3783       {
3784         tree f1, f2;
3785
3786         /* For aggregate types, all the fields must be the same.  */
3787         for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
3788              f1 && f2;
3789              f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
3790           {
3791             /* Different field kinds are not compatible.  */
3792             if (TREE_CODE (f1) != TREE_CODE (f2))
3793               goto different_types;
3794             /* Field decls must have the same name and offset.  */
3795             if (TREE_CODE (f1) == FIELD_DECL
3796                 && (DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
3797                     || !gimple_compare_field_offset (f1, f2)))
3798               goto different_types;
3799             /* All entities should have the same name and type.  */
3800             if (DECL_NAME (f1) != DECL_NAME (f2)
3801                 || !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2),
3802                                state, sccstack, sccstate, sccstate_obstack))
3803               goto different_types;
3804           }
3805
3806         /* If one aggregate has more fields than the other, they
3807            are not the same.  */
3808         if (f1 || f2)
3809           goto different_types;
3810
3811         goto same_types;
3812       }
3813
3814     default:
3815       gcc_unreachable ();
3816     }
3817
3818   /* Common exit path for types that are not compatible.  */
3819 different_types:
3820   state->u.same_p = 0;
3821   goto pop;
3822
3823   /* Common exit path for types that are compatible.  */
3824 same_types:
3825   gcc_assert (state->u.same_p == 1);
3826
3827 pop:
3828   if (state->low == state->dfsnum)
3829     {
3830       type_pair_t x;
3831
3832       /* Pop off the SCC and set its cache values to the final
3833          comparison result.  */
3834       do
3835         {
3836           struct sccs *cstate;
3837           x = VEC_pop (type_pair_t, *sccstack);
3838           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
3839           cstate->on_sccstack = false;
3840           x->same_p[GTC_MERGE] = state->u.same_p;
3841         }
3842       while (x != p);
3843     }
3844
3845   return state->u.same_p;
3846 }
3847
3848 /* Return true iff T1 and T2 are structurally identical.  When
3849    FOR_MERGING_P is true the an incomplete type and a complete type
3850    are considered different, otherwise they are considered compatible.  */
3851
3852 static bool
3853 gimple_types_compatible_p (tree t1, tree t2)
3854 {
3855   VEC(type_pair_t, heap) *sccstack = NULL;
3856   struct pointer_map_t *sccstate;
3857   struct obstack sccstate_obstack;
3858   type_pair_t p = NULL;
3859   bool res;
3860   tree leader1, leader2;
3861
3862   /* Before starting to set up the SCC machinery handle simple cases.  */
3863
3864   /* Check first for the obvious case of pointer identity.  */
3865   if (t1 == t2)
3866     return true;
3867
3868   /* Check that we have two types to compare.  */
3869   if (t1 == NULL_TREE || t2 == NULL_TREE)
3870     return false;
3871
3872   /* Can't be the same type if the types don't have the same code.  */
3873   if (TREE_CODE (t1) != TREE_CODE (t2))
3874     return false;
3875
3876   /* Can't be the same type if they have different CV qualifiers.  */
3877   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3878     return false;
3879
3880   if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
3881     return false;
3882
3883   /* Void types and nullptr types are always the same.  */
3884   if (TREE_CODE (t1) == VOID_TYPE
3885       || TREE_CODE (t1) == NULLPTR_TYPE)
3886     return true;
3887
3888   /* Can't be the same type if they have different alignment or mode.  */
3889   if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3890       || TYPE_MODE (t1) != TYPE_MODE (t2))
3891     return false;
3892
3893   /* Do some simple checks before doing three hashtable queries.  */
3894   if (INTEGRAL_TYPE_P (t1)
3895       || SCALAR_FLOAT_TYPE_P (t1)
3896       || FIXED_POINT_TYPE_P (t1)
3897       || TREE_CODE (t1) == VECTOR_TYPE
3898       || TREE_CODE (t1) == COMPLEX_TYPE
3899       || TREE_CODE (t1) == OFFSET_TYPE
3900       || POINTER_TYPE_P (t1))
3901     {
3902       /* Can't be the same type if they have different sign or precision.  */
3903       if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3904           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3905         return false;
3906
3907       if (TREE_CODE (t1) == INTEGER_TYPE
3908           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3909               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3910         return false;
3911
3912       /* That's all we need to check for float and fixed-point types.  */
3913       if (SCALAR_FLOAT_TYPE_P (t1)
3914           || FIXED_POINT_TYPE_P (t1))
3915         return true;
3916
3917       /* For other types fall thru to more complex checks.  */
3918     }
3919
3920   /* If the types have been previously registered and found equal
3921      they still are.  */
3922   leader1 = gimple_lookup_type_leader (t1);
3923   leader2 = gimple_lookup_type_leader (t2);
3924   if (leader1 == t2
3925       || t1 == leader2
3926       || (leader1 && leader1 == leader2))
3927     return true;
3928
3929   /* If the hash values of t1 and t2 are different the types can't
3930      possibly be the same.  This helps keeping the type-pair hashtable
3931      small, only tracking comparisons for hash collisions.  */
3932   if (gimple_type_hash (t1) != gimple_type_hash (t2))
3933     return false;
3934
3935   /* If we've visited this type pair before (in the case of aggregates
3936      with self-referential types), and we made a decision, return it.  */
3937   p = lookup_type_pair (t1, t2);
3938   if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
3939     {
3940       /* We have already decided whether T1 and T2 are the
3941          same, return the cached result.  */
3942       return p->same_p[GTC_MERGE] == 1;
3943     }
3944
3945   /* Now set up the SCC machinery for the comparison.  */
3946   gtc_next_dfs_num = 1;
3947   sccstate = pointer_map_create ();
3948   gcc_obstack_init (&sccstate_obstack);
3949   res = gimple_types_compatible_p_1 (t1, t2, p,
3950                                      &sccstack, sccstate, &sccstate_obstack);
3951   VEC_free (type_pair_t, heap, sccstack);
3952   pointer_map_destroy (sccstate);
3953   obstack_free (&sccstate_obstack, NULL);
3954
3955   return res;
3956 }
3957
3958
3959 static hashval_t
3960 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
3961                             struct pointer_map_t *, struct obstack *);
3962
3963 /* DFS visit the edge from the callers type with state *STATE to T.
3964    Update the callers type hash V with the hash for T if it is not part
3965    of the SCC containing the callers type and return it.
3966    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3967
3968 static hashval_t
3969 visit (tree t, struct sccs *state, hashval_t v,
3970        VEC (tree, heap) **sccstack,
3971        struct pointer_map_t *sccstate,
3972        struct obstack *sccstate_obstack)
3973 {
3974   struct sccs *cstate = NULL;
3975   struct tree_int_map m;
3976   void **slot;
3977
3978   /* If there is a hash value recorded for this type then it can't
3979      possibly be part of our parent SCC.  Simply mix in its hash.  */
3980   m.base.from = t;
3981   if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
3982       && *slot)
3983     return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, v);
3984
3985   if ((slot = pointer_map_contains (sccstate, t)) != NULL)
3986     cstate = (struct sccs *)*slot;
3987   if (!cstate)
3988     {
3989       hashval_t tem;
3990       /* Not yet visited.  DFS recurse.  */
3991       tem = iterative_hash_gimple_type (t, v,
3992                                         sccstack, sccstate, sccstate_obstack);
3993       if (!cstate)
3994         cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
3995       state->low = MIN (state->low, cstate->low);
3996       /* If the type is no longer on the SCC stack and thus is not part
3997          of the parents SCC mix in its hash value.  Otherwise we will
3998          ignore the type for hashing purposes and return the unaltered
3999          hash value.  */
4000       if (!cstate->on_sccstack)
4001         return tem;
4002     }
4003   if (cstate->dfsnum < state->dfsnum
4004       && cstate->on_sccstack)
4005     state->low = MIN (cstate->dfsnum, state->low);
4006
4007   /* We are part of our parents SCC, skip this type during hashing
4008      and return the unaltered hash value.  */
4009   return v;
4010 }
4011
4012 /* Hash NAME with the previous hash value V and return it.  */
4013
4014 static hashval_t
4015 iterative_hash_name (tree name, hashval_t v)
4016 {
4017   if (!name)
4018     return v;
4019   if (TREE_CODE (name) == TYPE_DECL)
4020     name = DECL_NAME (name);
4021   if (!name)
4022     return v;
4023   gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
4024   return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
4025 }
4026
4027 /* A type, hashvalue pair for sorting SCC members.  */
4028
4029 struct type_hash_pair {
4030   tree type;
4031   hashval_t hash;
4032 };
4033
4034 /* Compare two type, hashvalue pairs.  */
4035
4036 static int
4037 type_hash_pair_compare (const void *p1_, const void *p2_)
4038 {
4039   const struct type_hash_pair *p1 = (const struct type_hash_pair *) p1_;
4040   const struct type_hash_pair *p2 = (const struct type_hash_pair *) p2_;
4041   if (p1->hash < p2->hash)
4042     return -1;
4043   else if (p1->hash > p2->hash)
4044     return 1;
4045   return 0;
4046 }
4047
4048 /* Returning a hash value for gimple type TYPE combined with VAL.
4049    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
4050
4051    To hash a type we end up hashing in types that are reachable.
4052    Through pointers we can end up with cycles which messes up the
4053    required property that we need to compute the same hash value
4054    for structurally equivalent types.  To avoid this we have to
4055    hash all types in a cycle (the SCC) in a commutative way.  The
4056    easiest way is to not mix in the hashes of the SCC members at
4057    all.  To make this work we have to delay setting the hash
4058    values of the SCC until it is complete.  */
4059
4060 static hashval_t
4061 iterative_hash_gimple_type (tree type, hashval_t val,
4062                             VEC(tree, heap) **sccstack,
4063                             struct pointer_map_t *sccstate,
4064                             struct obstack *sccstate_obstack)
4065 {
4066   hashval_t v;
4067   void **slot;
4068   struct sccs *state;
4069
4070   /* Not visited during this DFS walk.  */
4071   gcc_checking_assert (!pointer_map_contains (sccstate, type));
4072   state = XOBNEW (sccstate_obstack, struct sccs);
4073   *pointer_map_insert (sccstate, type) = state;
4074
4075   VEC_safe_push (tree, heap, *sccstack, type);
4076   state->dfsnum = next_dfs_num++;
4077   state->low = state->dfsnum;
4078   state->on_sccstack = true;
4079
4080   /* Combine a few common features of types so that types are grouped into
4081      smaller sets; when searching for existing matching types to merge,
4082      only existing types having the same features as the new type will be
4083      checked.  */
4084   v = iterative_hash_name (TYPE_NAME (type), 0);
4085   v = iterative_hash_hashval_t (TREE_CODE (type), v);
4086   v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
4087   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
4088
4089   /* Do not hash the types size as this will cause differences in
4090      hash values for the complete vs. the incomplete type variant.  */
4091
4092   /* Incorporate common features of numerical types.  */
4093   if (INTEGRAL_TYPE_P (type)
4094       || SCALAR_FLOAT_TYPE_P (type)
4095       || FIXED_POINT_TYPE_P (type))
4096     {
4097       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
4098       v = iterative_hash_hashval_t (TYPE_MODE (type), v);
4099       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
4100     }
4101
4102   /* For pointer and reference types, fold in information about the type
4103      pointed to.  */
4104   if (POINTER_TYPE_P (type))
4105     v = visit (TREE_TYPE (type), state, v,
4106                sccstack, sccstate, sccstate_obstack);
4107
4108   /* For integer types hash the types min/max values and the string flag.  */
4109   if (TREE_CODE (type) == INTEGER_TYPE)
4110     {
4111       /* OMP lowering can introduce error_mark_node in place of
4112          random local decls in types.  */
4113       if (TYPE_MIN_VALUE (type) != error_mark_node)
4114         v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
4115       if (TYPE_MAX_VALUE (type) != error_mark_node)
4116         v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
4117       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4118     }
4119
4120   /* For array types hash their domain and the string flag.  */
4121   if (TREE_CODE (type) == ARRAY_TYPE
4122       && TYPE_DOMAIN (type))
4123     {
4124       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4125       v = visit (TYPE_DOMAIN (type), state, v,
4126                  sccstack, sccstate, sccstate_obstack);
4127     }
4128
4129   /* Recurse for aggregates with a single element type.  */
4130   if (TREE_CODE (type) == ARRAY_TYPE
4131       || TREE_CODE (type) == COMPLEX_TYPE
4132       || TREE_CODE (type) == VECTOR_TYPE)
4133     v = visit (TREE_TYPE (type), state, v,
4134                sccstack, sccstate, sccstate_obstack);
4135
4136   /* Incorporate function return and argument types.  */
4137   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
4138     {
4139       unsigned na;
4140       tree p;
4141
4142       /* For method types also incorporate their parent class.  */
4143       if (TREE_CODE (type) == METHOD_TYPE)
4144         v = visit (TYPE_METHOD_BASETYPE (type), state, v,
4145                    sccstack, sccstate, sccstate_obstack);
4146
4147       /* Check result and argument types.  */
4148       v = visit (TREE_TYPE (type), state, v,
4149                  sccstack, sccstate, sccstate_obstack);
4150       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
4151         {
4152           v = visit (TREE_VALUE (p), state, v,
4153                      sccstack, sccstate, sccstate_obstack);
4154           na++;
4155         }
4156
4157       v = iterative_hash_hashval_t (na, v);
4158     }
4159
4160   if (TREE_CODE (type) == RECORD_TYPE
4161       || TREE_CODE (type) == UNION_TYPE
4162       || TREE_CODE (type) == QUAL_UNION_TYPE)
4163     {
4164       unsigned nf;
4165       tree f;
4166
4167       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
4168         {
4169           v = iterative_hash_name (DECL_NAME (f), v);
4170           v = visit (TREE_TYPE (f), state, v,
4171                      sccstack, sccstate, sccstate_obstack);
4172           nf++;
4173         }
4174
4175       v = iterative_hash_hashval_t (nf, v);
4176     }
4177
4178   /* Record hash for us.  */
4179   state->u.hash = v;
4180
4181   /* See if we found an SCC.  */
4182   if (state->low == state->dfsnum)
4183     {
4184       tree x;
4185       struct tree_int_map *m;
4186
4187       /* Pop off the SCC and set its hash values.  */
4188       x = VEC_pop (tree, *sccstack);
4189       /* Optimize SCC size one.  */
4190       if (x == type)
4191         {
4192           state->on_sccstack = false;
4193           m = ggc_alloc_cleared_tree_int_map ();
4194           m->base.from = x;
4195           m->to = v;
4196           slot = htab_find_slot (type_hash_cache, m, INSERT);
4197           gcc_assert (!*slot);
4198           *slot = (void *) m;
4199         }
4200       else
4201         {
4202           struct sccs *cstate;
4203           unsigned first, i, size, j;
4204           struct type_hash_pair *pairs;
4205           /* Pop off the SCC and build an array of type, hash pairs.  */
4206           first = VEC_length (tree, *sccstack) - 1;
4207           while (VEC_index (tree, *sccstack, first) != type)
4208             --first;
4209           size = VEC_length (tree, *sccstack) - first + 1;
4210           pairs = XALLOCAVEC (struct type_hash_pair, size);
4211           i = 0;
4212           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
4213           cstate->on_sccstack = false;
4214           pairs[i].type = x;
4215           pairs[i].hash = cstate->u.hash;
4216           do
4217             {
4218               x = VEC_pop (tree, *sccstack);
4219               cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
4220               cstate->on_sccstack = false;
4221               ++i;
4222               pairs[i].type = x;
4223               pairs[i].hash = cstate->u.hash;
4224             }
4225           while (x != type);
4226           gcc_assert (i + 1 == size);
4227           /* Sort the arrays of type, hash pairs so that when we mix in
4228              all members of the SCC the hash value becomes independent on
4229              the order we visited the SCC.  Disregard hashes equal to
4230              the hash of the type we mix into because we cannot guarantee
4231              a stable sort for those across different TUs.  */
4232           qsort (pairs, size, sizeof (struct type_hash_pair),
4233                  type_hash_pair_compare);
4234           for (i = 0; i < size; ++i)
4235             {
4236               hashval_t hash;
4237               m = ggc_alloc_cleared_tree_int_map ();
4238               m->base.from = pairs[i].type;
4239               hash = pairs[i].hash;
4240               /* Skip same hashes.  */
4241               for (j = i + 1; j < size && pairs[j].hash == pairs[i].hash; ++j)
4242                 ;
4243               for (; j < size; ++j)
4244                 hash = iterative_hash_hashval_t (pairs[j].hash, hash);
4245               for (j = 0; pairs[j].hash != pairs[i].hash; ++j)
4246                 hash = iterative_hash_hashval_t (pairs[j].hash, hash);
4247               m->to = hash;
4248               if (pairs[i].type == type)
4249                 v = hash;
4250               slot = htab_find_slot (type_hash_cache, m, INSERT);
4251               gcc_assert (!*slot);
4252               *slot = (void *) m;
4253             }
4254         }
4255     }
4256
4257   return iterative_hash_hashval_t (v, val);
4258 }
4259
4260
4261 /* Returns a hash value for P (assumed to be a type).  The hash value
4262    is computed using some distinguishing features of the type.  Note
4263    that we cannot use pointer hashing here as we may be dealing with
4264    two distinct instances of the same type.
4265
4266    This function should produce the same hash value for two compatible
4267    types according to gimple_types_compatible_p.  */
4268
4269 static hashval_t
4270 gimple_type_hash (const void *p)
4271 {
4272   const_tree t = (const_tree) p;
4273   VEC(tree, heap) *sccstack = NULL;
4274   struct pointer_map_t *sccstate;
4275   struct obstack sccstate_obstack;
4276   hashval_t val;
4277   void **slot;
4278   struct tree_int_map m;
4279
4280   if (type_hash_cache == NULL)
4281     type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
4282                                        tree_int_map_eq, NULL);
4283
4284   m.base.from = CONST_CAST_TREE (t);
4285   if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
4286       && *slot)
4287     return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, 0);
4288
4289   /* Perform a DFS walk and pre-hash all reachable types.  */
4290   next_dfs_num = 1;
4291   sccstate = pointer_map_create ();
4292   gcc_obstack_init (&sccstate_obstack);
4293   val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
4294                                     &sccstack, sccstate, &sccstate_obstack);
4295   VEC_free (tree, heap, sccstack);
4296   pointer_map_destroy (sccstate);
4297   obstack_free (&sccstate_obstack, NULL);
4298
4299   return val;
4300 }
4301
4302 /* Returning a hash value for gimple type TYPE combined with VAL.
4303
4304    The hash value returned is equal for types considered compatible
4305    by gimple_canonical_types_compatible_p.  */
4306
4307 static hashval_t
4308 iterative_hash_canonical_type (tree type, hashval_t val)
4309 {
4310   hashval_t v;
4311   void **slot;
4312   struct tree_int_map *mp, m;
4313
4314   m.base.from = type;
4315   if ((slot = htab_find_slot (canonical_type_hash_cache, &m, INSERT))
4316       && *slot)
4317     return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, val);
4318
4319   /* Combine a few common features of types so that types are grouped into
4320      smaller sets; when searching for existing matching types to merge,
4321      only existing types having the same features as the new type will be
4322      checked.  */
4323   v = iterative_hash_hashval_t (TREE_CODE (type), 0);
4324   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
4325   v = iterative_hash_hashval_t (TYPE_ALIGN (type), v);
4326   v = iterative_hash_hashval_t (TYPE_MODE (type), v);
4327
4328   /* Incorporate common features of numerical types.  */
4329   if (INTEGRAL_TYPE_P (type)
4330       || SCALAR_FLOAT_TYPE_P (type)
4331       || FIXED_POINT_TYPE_P (type)
4332       || TREE_CODE (type) == VECTOR_TYPE
4333       || TREE_CODE (type) == COMPLEX_TYPE
4334       || TREE_CODE (type) == OFFSET_TYPE
4335       || POINTER_TYPE_P (type))
4336     {
4337       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
4338       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
4339     }
4340
4341   /* For pointer and reference types, fold in information about the type
4342      pointed to but do not recurse to the pointed-to type.  */
4343   if (POINTER_TYPE_P (type))
4344     {
4345       v = iterative_hash_hashval_t (TYPE_REF_CAN_ALIAS_ALL (type), v);
4346       v = iterative_hash_hashval_t (TYPE_ADDR_SPACE (TREE_TYPE (type)), v);
4347       v = iterative_hash_hashval_t (TYPE_RESTRICT (type), v);
4348       v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
4349     }
4350
4351   /* For integer types hash the types min/max values and the string flag.  */
4352   if (TREE_CODE (type) == INTEGER_TYPE)
4353     {
4354       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4355       v = iterative_hash_hashval_t (TYPE_IS_SIZETYPE (type), v);
4356     }
4357
4358   /* For array types hash their domain and the string flag.  */
4359   if (TREE_CODE (type) == ARRAY_TYPE
4360       && TYPE_DOMAIN (type))
4361     {
4362       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
4363       v = iterative_hash_canonical_type (TYPE_DOMAIN (type), v);
4364     }
4365
4366   /* Recurse for aggregates with a single element type.  */
4367   if (TREE_CODE (type) == ARRAY_TYPE
4368       || TREE_CODE (type) == COMPLEX_TYPE
4369       || TREE_CODE (type) == VECTOR_TYPE)
4370     v = iterative_hash_canonical_type (TREE_TYPE (type), v);
4371
4372   /* Incorporate function return and argument types.  */
4373   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
4374     {
4375       unsigned na;
4376       tree p;
4377
4378       /* For method types also incorporate their parent class.  */
4379       if (TREE_CODE (type) == METHOD_TYPE)
4380         v = iterative_hash_canonical_type (TYPE_METHOD_BASETYPE (type), v);
4381
4382       v = iterative_hash_canonical_type (TREE_TYPE (type), v);
4383
4384       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
4385         {
4386           v = iterative_hash_canonical_type (TREE_VALUE (p), v);
4387           na++;
4388         }
4389
4390       v = iterative_hash_hashval_t (na, v);
4391     }
4392
4393   if (TREE_CODE (type) == RECORD_TYPE
4394       || TREE_CODE (type) == UNION_TYPE
4395       || TREE_CODE (type) == QUAL_UNION_TYPE)
4396     {
4397       unsigned nf;
4398       tree f;
4399
4400       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
4401         if (TREE_CODE (f) == FIELD_DECL)
4402           {
4403             v = iterative_hash_canonical_type (TREE_TYPE (f), v);
4404             nf++;
4405           }
4406
4407       v = iterative_hash_hashval_t (nf, v);
4408     }
4409
4410   /* Cache the just computed hash value.  */
4411   mp = ggc_alloc_cleared_tree_int_map ();
4412   mp->base.from = type;
4413   mp->to = v;
4414   *slot = (void *) mp;
4415
4416   return iterative_hash_hashval_t (v, val);
4417 }
4418
4419 static hashval_t
4420 gimple_canonical_type_hash (const void *p)
4421 {
4422   if (canonical_type_hash_cache == NULL)
4423     canonical_type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
4424                                                  tree_int_map_eq, NULL);
4425
4426   return iterative_hash_canonical_type (CONST_CAST_TREE ((const_tree) p), 0);
4427 }
4428
4429
4430 /* Returns nonzero if P1 and P2 are equal.  */
4431
4432 static int
4433 gimple_type_eq (const void *p1, const void *p2)
4434 {
4435   const_tree t1 = (const_tree) p1;
4436   const_tree t2 = (const_tree) p2;
4437   return gimple_types_compatible_p (CONST_CAST_TREE (t1),
4438                                     CONST_CAST_TREE (t2));
4439 }
4440
4441
4442 /* Worker for gimple_register_type.
4443    Register type T in the global type table gimple_types.
4444    When REGISTERING_MV is false first recurse for the main variant of T.  */
4445
4446 static tree
4447 gimple_register_type_1 (tree t, bool registering_mv)
4448 {
4449   void **slot;
4450   gimple_type_leader_entry *leader;
4451
4452   /* If we registered this type before return the cached result.  */
4453   leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
4454   if (leader->type == t)
4455     return leader->leader;
4456
4457   /* Always register the main variant first.  This is important so we
4458      pick up the non-typedef variants as canonical, otherwise we'll end
4459      up taking typedef ids for structure tags during comparison.
4460      It also makes sure that main variants will be merged to main variants.
4461      As we are operating on a possibly partially fixed up type graph
4462      do not bother to recurse more than once, otherwise we may end up
4463      walking in circles.
4464      If we are registering a main variant it will either remain its
4465      own main variant or it will be merged to something else in which
4466      case we do not care for the main variant leader.  */
4467   if (!registering_mv
4468       && TYPE_MAIN_VARIANT (t) != t)
4469     gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
4470
4471   /* See if we already have an equivalent type registered.  */
4472   slot = htab_find_slot (gimple_types, t, INSERT);
4473   if (*slot
4474       && *(tree *)slot != t)
4475     {
4476       tree new_type = (tree) *((tree *) slot);
4477       leader->type = t;
4478       leader->leader = new_type;
4479       return new_type;
4480     }
4481
4482   /* If not, insert it to the cache and the hash.  */
4483   leader->type = t;
4484   leader->leader = t;
4485   *slot = (void *) t;
4486   return t;
4487 }
4488
4489 /* Register type T in the global type table gimple_types.
4490    If another type T', compatible with T, already existed in
4491    gimple_types then return T', otherwise return T.  This is used by
4492    LTO to merge identical types read from different TUs.  */
4493
4494 tree
4495 gimple_register_type (tree t)
4496 {
4497   gcc_assert (TYPE_P (t));
4498
4499   if (!gimple_type_leader)
4500     gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
4501                                 (GIMPLE_TYPE_LEADER_SIZE);
4502
4503   if (gimple_types == NULL)
4504     gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
4505
4506   return gimple_register_type_1 (t, false);
4507 }
4508
4509 /* The TYPE_CANONICAL merging machinery.  It should closely resemble
4510    the middle-end types_compatible_p function.  It needs to avoid
4511    claiming types are different for types that should be treated
4512    the same with respect to TBAA.  Canonical types are also used
4513    for IL consistency checks via the useless_type_conversion_p
4514    predicate which does not handle all type kinds itself but falls
4515    back to pointer-comparison of TYPE_CANONICAL for aggregates
4516    for example.  */
4517
4518 /* Return true iff T1 and T2 are structurally identical for what
4519    TBAA is concerned.  */
4520
4521 static bool
4522 gimple_canonical_types_compatible_p (tree t1, tree t2)
4523 {
4524   /* Before starting to set up the SCC machinery handle simple cases.  */
4525
4526   /* Check first for the obvious case of pointer identity.  */
4527   if (t1 == t2)
4528     return true;
4529
4530   /* Check that we have two types to compare.  */
4531   if (t1 == NULL_TREE || t2 == NULL_TREE)
4532     return false;
4533
4534   /* If the types have been previously registered and found equal
4535      they still are.  */
4536   if (TYPE_CANONICAL (t1)
4537       && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
4538     return true;
4539
4540   /* Can't be the same type if the types don't have the same code.  */
4541   if (TREE_CODE (t1) != TREE_CODE (t2))
4542     return false;
4543
4544   if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
4545     return false;
4546
4547   /* Qualifiers do not matter for canonical type comparison purposes.  */
4548
4549   /* Void types and nullptr types are always the same.  */
4550   if (TREE_CODE (t1) == VOID_TYPE
4551       || TREE_CODE (t1) == NULLPTR_TYPE)
4552     return true;
4553
4554   /* Can't be the same type if they have different alignment, or mode.  */
4555   if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
4556       || TYPE_MODE (t1) != TYPE_MODE (t2))
4557     return false;
4558
4559   /* Non-aggregate types can be handled cheaply.  */
4560   if (INTEGRAL_TYPE_P (t1)
4561       || SCALAR_FLOAT_TYPE_P (t1)
4562       || FIXED_POINT_TYPE_P (t1)
4563       || TREE_CODE (t1) == VECTOR_TYPE
4564       || TREE_CODE (t1) == COMPLEX_TYPE
4565       || TREE_CODE (t1) == OFFSET_TYPE
4566       || POINTER_TYPE_P (t1))
4567     {
4568       /* Can't be the same type if they have different sign or precision.  */
4569       if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
4570           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
4571         return false;
4572
4573       if (TREE_CODE (t1) == INTEGER_TYPE
4574           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
4575               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
4576         return false;
4577
4578       /* For canonical type comparisons we do not want to build SCCs
4579          so we cannot compare pointed-to types.  But we can, for now,
4580          require the same pointed-to type kind and match what
4581          useless_type_conversion_p would do.  */
4582       if (POINTER_TYPE_P (t1))
4583         {
4584           /* If the two pointers have different ref-all attributes,
4585              they can't be the same type.  */
4586           if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
4587             return false;
4588
4589           if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
4590               != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
4591             return false;
4592
4593           if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
4594             return false;
4595
4596           if (TREE_CODE (TREE_TYPE (t1)) != TREE_CODE (TREE_TYPE (t2)))
4597             return false;
4598         }
4599
4600       /* Tail-recurse to components.  */
4601       if (TREE_CODE (t1) == VECTOR_TYPE
4602           || TREE_CODE (t1) == COMPLEX_TYPE)
4603         return gimple_canonical_types_compatible_p (TREE_TYPE (t1),
4604                                                     TREE_TYPE (t2));
4605
4606       return true;
4607     }
4608
4609   /* If their attributes are not the same they can't be the same type.  */
4610   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
4611     return false;
4612
4613   /* Do type-specific comparisons.  */
4614   switch (TREE_CODE (t1))
4615     {
4616     case ARRAY_TYPE:
4617       /* Array types are the same if the element types are the same and
4618          the number of elements are the same.  */
4619       if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
4620           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
4621           || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
4622         return false;
4623       else
4624         {
4625           tree i1 = TYPE_DOMAIN (t1);
4626           tree i2 = TYPE_DOMAIN (t2);
4627
4628           /* For an incomplete external array, the type domain can be
4629              NULL_TREE.  Check this condition also.  */
4630           if (i1 == NULL_TREE && i2 == NULL_TREE)
4631             return true;
4632           else if (i1 == NULL_TREE || i2 == NULL_TREE)
4633             return false;
4634           /* If for a complete array type the possibly gimplified sizes
4635              are different the types are different.  */
4636           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
4637                    || (TYPE_SIZE (i1)
4638                        && TYPE_SIZE (i2)
4639                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
4640             return false;
4641           else
4642             {
4643               tree min1 = TYPE_MIN_VALUE (i1);
4644               tree min2 = TYPE_MIN_VALUE (i2);
4645               tree max1 = TYPE_MAX_VALUE (i1);
4646               tree max2 = TYPE_MAX_VALUE (i2);
4647
4648               /* The minimum/maximum values have to be the same.  */
4649               if ((min1 == min2
4650                    || (min1 && min2
4651                        && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
4652                             && TREE_CODE (min2) == PLACEHOLDER_EXPR)
4653                            || operand_equal_p (min1, min2, 0))))
4654                   && (max1 == max2
4655                       || (max1 && max2
4656                           && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
4657                                && TREE_CODE (max2) == PLACEHOLDER_EXPR)
4658                               || operand_equal_p (max1, max2, 0)))))
4659                 return true;
4660               else
4661                 return false;
4662             }
4663         }
4664
4665     case METHOD_TYPE:
4666       /* Method types should belong to the same class.  */
4667       if (!gimple_canonical_types_compatible_p
4668              (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2)))
4669         return false;
4670
4671       /* Fallthru  */
4672
4673     case FUNCTION_TYPE:
4674       /* Function types are the same if the return type and arguments types
4675          are the same.  */
4676       if (!gimple_canonical_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
4677         return false;
4678
4679       if (!comp_type_attributes (t1, t2))
4680         return false;
4681
4682       if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
4683         return true;
4684       else
4685         {
4686           tree parms1, parms2;
4687
4688           for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
4689                parms1 && parms2;
4690                parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
4691             {
4692               if (!gimple_canonical_types_compatible_p
4693                      (TREE_VALUE (parms1), TREE_VALUE (parms2)))
4694                 return false;
4695             }
4696
4697           if (parms1 || parms2)
4698             return false;
4699
4700           return true;
4701         }
4702
4703     case RECORD_TYPE:
4704     case UNION_TYPE:
4705     case QUAL_UNION_TYPE:
4706       {
4707         tree f1, f2;
4708
4709         /* For aggregate types, all the fields must be the same.  */
4710         for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
4711              f1 && f2;
4712              f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
4713           {
4714             /* Skip non-fields.  */
4715             while (f1 && TREE_CODE (f1) != FIELD_DECL)
4716               f1 = TREE_CHAIN (f1);
4717             while (f2 && TREE_CODE (f2) != FIELD_DECL)
4718               f2 = TREE_CHAIN (f2);
4719             if (!f1 || !f2)
4720               break;
4721             /* The fields must have the same name, offset and type.  */
4722             if (DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
4723                 || !gimple_compare_field_offset (f1, f2)
4724                 || !gimple_canonical_types_compatible_p
4725                       (TREE_TYPE (f1), TREE_TYPE (f2)))
4726               return false;
4727           }
4728
4729         /* If one aggregate has more fields than the other, they
4730            are not the same.  */
4731         if (f1 || f2)
4732           return false;
4733
4734         return true;
4735       }
4736
4737     default:
4738       gcc_unreachable ();
4739     }
4740 }
4741
4742
4743 /* Returns nonzero if P1 and P2 are equal.  */
4744
4745 static int
4746 gimple_canonical_type_eq (const void *p1, const void *p2)
4747 {
4748   const_tree t1 = (const_tree) p1;
4749   const_tree t2 = (const_tree) p2;
4750   return gimple_canonical_types_compatible_p (CONST_CAST_TREE (t1),
4751                                               CONST_CAST_TREE (t2));
4752 }
4753
4754 /* Register type T in the global type table gimple_types.
4755    If another type T', compatible with T, already existed in
4756    gimple_types then return T', otherwise return T.  This is used by
4757    LTO to merge identical types read from different TUs.
4758
4759    ???  This merging does not exactly match how the tree.c middle-end
4760    functions will assign TYPE_CANONICAL when new types are created
4761    during optimization (which at least happens for pointer and array
4762    types).  */
4763
4764 tree
4765 gimple_register_canonical_type (tree t)
4766 {
4767   void **slot;
4768
4769   gcc_assert (TYPE_P (t));
4770
4771   if (TYPE_CANONICAL (t))
4772     return TYPE_CANONICAL (t);
4773
4774   if (gimple_canonical_types == NULL)
4775     gimple_canonical_types = htab_create_ggc (16381, gimple_canonical_type_hash,
4776                                               gimple_canonical_type_eq, 0);
4777
4778   slot = htab_find_slot (gimple_canonical_types, t, INSERT);
4779   if (*slot
4780       && *(tree *)slot != t)
4781     {
4782       tree new_type = (tree) *((tree *) slot);
4783
4784       TYPE_CANONICAL (t) = new_type;
4785       t = new_type;
4786     }
4787   else
4788     {
4789       TYPE_CANONICAL (t) = t;
4790       *slot = (void *) t;
4791     }
4792
4793   return t;
4794 }
4795
4796
4797 /* Show statistics on references to the global type table gimple_types.  */
4798
4799 void
4800 print_gimple_types_stats (void)
4801 {
4802   if (gimple_types)
4803     fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
4804              "%ld searches, %ld collisions (ratio: %f)\n",
4805              (long) htab_size (gimple_types),
4806              (long) htab_elements (gimple_types),
4807              (long) gimple_types->searches,
4808              (long) gimple_types->collisions,
4809              htab_collisions (gimple_types));
4810   else
4811     fprintf (stderr, "GIMPLE type table is empty\n");
4812   if (type_hash_cache)
4813     fprintf (stderr, "GIMPLE type hash table: size %ld, %ld elements, "
4814              "%ld searches, %ld collisions (ratio: %f)\n",
4815              (long) htab_size (type_hash_cache),
4816              (long) htab_elements (type_hash_cache),
4817              (long) type_hash_cache->searches,
4818              (long) type_hash_cache->collisions,
4819              htab_collisions (type_hash_cache));
4820   else
4821     fprintf (stderr, "GIMPLE type hash table is empty\n");
4822   if (gimple_canonical_types)
4823     fprintf (stderr, "GIMPLE canonical type table: size %ld, %ld elements, "
4824              "%ld searches, %ld collisions (ratio: %f)\n",
4825              (long) htab_size (gimple_canonical_types),
4826              (long) htab_elements (gimple_canonical_types),
4827              (long) gimple_canonical_types->searches,
4828              (long) gimple_canonical_types->collisions,
4829              htab_collisions (gimple_canonical_types));
4830   else
4831     fprintf (stderr, "GIMPLE canonical type table is empty\n");
4832   if (canonical_type_hash_cache)
4833     fprintf (stderr, "GIMPLE canonical type hash table: size %ld, %ld elements, "
4834              "%ld searches, %ld collisions (ratio: %f)\n",
4835              (long) htab_size (canonical_type_hash_cache),
4836              (long) htab_elements (canonical_type_hash_cache),
4837              (long) canonical_type_hash_cache->searches,
4838              (long) canonical_type_hash_cache->collisions,
4839              htab_collisions (canonical_type_hash_cache));
4840   else
4841     fprintf (stderr, "GIMPLE canonical type hash table is empty\n");
4842 }
4843
4844 /* Free the gimple type hashtables used for LTO type merging.  */
4845
4846 void
4847 free_gimple_type_tables (void)
4848 {
4849   /* Last chance to print stats for the tables.  */
4850   if (flag_lto_report)
4851     print_gimple_types_stats ();
4852
4853   if (gimple_types)
4854     {
4855       htab_delete (gimple_types);
4856       gimple_types = NULL;
4857     }
4858   if (gimple_canonical_types)
4859     {
4860       htab_delete (gimple_canonical_types);
4861       gimple_canonical_types = NULL;
4862     }
4863   if (type_hash_cache)
4864     {
4865       htab_delete (type_hash_cache);
4866       type_hash_cache = NULL;
4867     }
4868   if (canonical_type_hash_cache)
4869     {
4870       htab_delete (canonical_type_hash_cache);
4871       canonical_type_hash_cache = NULL;
4872     }
4873   if (type_pair_cache)
4874     {
4875       free (type_pair_cache);
4876       type_pair_cache = NULL;
4877     }
4878   gimple_type_leader = NULL;
4879 }
4880
4881
4882 /* Return a type the same as TYPE except unsigned or
4883    signed according to UNSIGNEDP.  */
4884
4885 static tree
4886 gimple_signed_or_unsigned_type (bool unsignedp, tree type)
4887 {
4888   tree type1;
4889
4890   type1 = TYPE_MAIN_VARIANT (type);
4891   if (type1 == signed_char_type_node
4892       || type1 == char_type_node
4893       || type1 == unsigned_char_type_node)
4894     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4895   if (type1 == integer_type_node || type1 == unsigned_type_node)
4896     return unsignedp ? unsigned_type_node : integer_type_node;
4897   if (type1 == short_integer_type_node || type1 == short_unsigned_type_node)
4898     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4899   if (type1 == long_integer_type_node || type1 == long_unsigned_type_node)
4900     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4901   if (type1 == long_long_integer_type_node
4902       || type1 == long_long_unsigned_type_node)
4903     return unsignedp
4904            ? long_long_unsigned_type_node
4905            : long_long_integer_type_node;
4906   if (int128_integer_type_node && (type1 == int128_integer_type_node || type1 == int128_unsigned_type_node))
4907     return unsignedp
4908            ? int128_unsigned_type_node
4909            : int128_integer_type_node;
4910 #if HOST_BITS_PER_WIDE_INT >= 64
4911   if (type1 == intTI_type_node || type1 == unsigned_intTI_type_node)
4912     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4913 #endif
4914   if (type1 == intDI_type_node || type1 == unsigned_intDI_type_node)
4915     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4916   if (type1 == intSI_type_node || type1 == unsigned_intSI_type_node)
4917     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4918   if (type1 == intHI_type_node || type1 == unsigned_intHI_type_node)
4919     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4920   if (type1 == intQI_type_node || type1 == unsigned_intQI_type_node)
4921     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4922
4923 #define GIMPLE_FIXED_TYPES(NAME)            \
4924   if (type1 == short_ ## NAME ## _type_node \
4925       || type1 == unsigned_short_ ## NAME ## _type_node) \
4926     return unsignedp ? unsigned_short_ ## NAME ## _type_node \
4927                      : short_ ## NAME ## _type_node; \
4928   if (type1 == NAME ## _type_node \
4929       || type1 == unsigned_ ## NAME ## _type_node) \
4930     return unsignedp ? unsigned_ ## NAME ## _type_node \
4931                      : NAME ## _type_node; \
4932   if (type1 == long_ ## NAME ## _type_node \
4933       || type1 == unsigned_long_ ## NAME ## _type_node) \
4934     return unsignedp ? unsigned_long_ ## NAME ## _type_node \
4935                      : long_ ## NAME ## _type_node; \
4936   if (type1 == long_long_ ## NAME ## _type_node \
4937       || type1 == unsigned_long_long_ ## NAME ## _type_node) \
4938     return unsignedp ? unsigned_long_long_ ## NAME ## _type_node \
4939                      : long_long_ ## NAME ## _type_node;
4940
4941 #define GIMPLE_FIXED_MODE_TYPES(NAME) \
4942   if (type1 == NAME ## _type_node \
4943       || type1 == u ## NAME ## _type_node) \
4944     return unsignedp ? u ## NAME ## _type_node \
4945                      : NAME ## _type_node;
4946
4947 #define GIMPLE_FIXED_TYPES_SAT(NAME) \
4948   if (type1 == sat_ ## short_ ## NAME ## _type_node \
4949       || type1 == sat_ ## unsigned_short_ ## NAME ## _type_node) \
4950     return unsignedp ? sat_ ## unsigned_short_ ## NAME ## _type_node \
4951                      : sat_ ## short_ ## NAME ## _type_node; \
4952   if (type1 == sat_ ## NAME ## _type_node \
4953       || type1 == sat_ ## unsigned_ ## NAME ## _type_node) \
4954     return unsignedp ? sat_ ## unsigned_ ## NAME ## _type_node \
4955                      : sat_ ## NAME ## _type_node; \
4956   if (type1 == sat_ ## long_ ## NAME ## _type_node \
4957       || type1 == sat_ ## unsigned_long_ ## NAME ## _type_node) \
4958     return unsignedp ? sat_ ## unsigned_long_ ## NAME ## _type_node \
4959                      : sat_ ## long_ ## NAME ## _type_node; \
4960   if (type1 == sat_ ## long_long_ ## NAME ## _type_node \
4961       || type1 == sat_ ## unsigned_long_long_ ## NAME ## _type_node) \
4962     return unsignedp ? sat_ ## unsigned_long_long_ ## NAME ## _type_node \
4963                      : sat_ ## long_long_ ## NAME ## _type_node;
4964
4965 #define GIMPLE_FIXED_MODE_TYPES_SAT(NAME)       \
4966   if (type1 == sat_ ## NAME ## _type_node \
4967       || type1 == sat_ ## u ## NAME ## _type_node) \
4968     return unsignedp ? sat_ ## u ## NAME ## _type_node \
4969                      : sat_ ## NAME ## _type_node;
4970
4971   GIMPLE_FIXED_TYPES (fract);
4972   GIMPLE_FIXED_TYPES_SAT (fract);
4973   GIMPLE_FIXED_TYPES (accum);
4974   GIMPLE_FIXED_TYPES_SAT (accum);
4975
4976   GIMPLE_FIXED_MODE_TYPES (qq);
4977   GIMPLE_FIXED_MODE_TYPES (hq);
4978   GIMPLE_FIXED_MODE_TYPES (sq);
4979   GIMPLE_FIXED_MODE_TYPES (dq);
4980   GIMPLE_FIXED_MODE_TYPES (tq);
4981   GIMPLE_FIXED_MODE_TYPES_SAT (qq);
4982   GIMPLE_FIXED_MODE_TYPES_SAT (hq);
4983   GIMPLE_FIXED_MODE_TYPES_SAT (sq);
4984   GIMPLE_FIXED_MODE_TYPES_SAT (dq);
4985   GIMPLE_FIXED_MODE_TYPES_SAT (tq);
4986   GIMPLE_FIXED_MODE_TYPES (ha);
4987   GIMPLE_FIXED_MODE_TYPES (sa);
4988   GIMPLE_FIXED_MODE_TYPES (da);
4989   GIMPLE_FIXED_MODE_TYPES (ta);
4990   GIMPLE_FIXED_MODE_TYPES_SAT (ha);
4991   GIMPLE_FIXED_MODE_TYPES_SAT (sa);
4992   GIMPLE_FIXED_MODE_TYPES_SAT (da);
4993   GIMPLE_FIXED_MODE_TYPES_SAT (ta);
4994
4995   /* For ENUMERAL_TYPEs in C++, must check the mode of the types, not
4996      the precision; they have precision set to match their range, but
4997      may use a wider mode to match an ABI.  If we change modes, we may
4998      wind up with bad conversions.  For INTEGER_TYPEs in C, must check
4999      the precision as well, so as to yield correct results for
5000      bit-field types.  C++ does not have these separate bit-field
5001      types, and producing a signed or unsigned variant of an
5002      ENUMERAL_TYPE may cause other problems as well.  */
5003   if (!INTEGRAL_TYPE_P (type)
5004       || TYPE_UNSIGNED (type) == unsignedp)
5005     return type;
5006
5007 #define TYPE_OK(node)                                                       \
5008   (TYPE_MODE (type) == TYPE_MODE (node)                                     \
5009    && TYPE_PRECISION (type) == TYPE_PRECISION (node))
5010   if (TYPE_OK (signed_char_type_node))
5011     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
5012   if (TYPE_OK (integer_type_node))
5013     return unsignedp ? unsigned_type_node : integer_type_node;
5014   if (TYPE_OK (short_integer_type_node))
5015     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
5016   if (TYPE_OK (long_integer_type_node))
5017     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
5018   if (TYPE_OK (long_long_integer_type_node))
5019     return (unsignedp
5020             ? long_long_unsigned_type_node
5021             : long_long_integer_type_node);
5022   if (int128_integer_type_node && TYPE_OK (int128_integer_type_node))
5023     return (unsignedp
5024             ? int128_unsigned_type_node
5025             : int128_integer_type_node);
5026
5027 #if HOST_BITS_PER_WIDE_INT >= 64
5028   if (TYPE_OK (intTI_type_node))
5029     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
5030 #endif
5031   if (TYPE_OK (intDI_type_node))
5032     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
5033   if (TYPE_OK (intSI_type_node))
5034     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
5035   if (TYPE_OK (intHI_type_node))
5036     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
5037   if (TYPE_OK (intQI_type_node))
5038     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
5039
5040 #undef GIMPLE_FIXED_TYPES
5041 #undef GIMPLE_FIXED_MODE_TYPES
5042 #undef GIMPLE_FIXED_TYPES_SAT
5043 #undef GIMPLE_FIXED_MODE_TYPES_SAT
5044 #undef TYPE_OK
5045
5046   return build_nonstandard_integer_type (TYPE_PRECISION (type), unsignedp);
5047 }
5048
5049
5050 /* Return an unsigned type the same as TYPE in other respects.  */
5051
5052 tree
5053 gimple_unsigned_type (tree type)
5054 {
5055   return gimple_signed_or_unsigned_type (true, type);
5056 }
5057
5058
5059 /* Return a signed type the same as TYPE in other respects.  */
5060
5061 tree
5062 gimple_signed_type (tree type)
5063 {
5064   return gimple_signed_or_unsigned_type (false, type);
5065 }
5066
5067
5068 /* Return the typed-based alias set for T, which may be an expression
5069    or a type.  Return -1 if we don't do anything special.  */
5070
5071 alias_set_type
5072 gimple_get_alias_set (tree t)
5073 {
5074   tree u;
5075
5076   /* Permit type-punning when accessing a union, provided the access
5077      is directly through the union.  For example, this code does not
5078      permit taking the address of a union member and then storing
5079      through it.  Even the type-punning allowed here is a GCC
5080      extension, albeit a common and useful one; the C standard says
5081      that such accesses have implementation-defined behavior.  */
5082   for (u = t;
5083        TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
5084        u = TREE_OPERAND (u, 0))
5085     if (TREE_CODE (u) == COMPONENT_REF
5086         && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
5087       return 0;
5088
5089   /* That's all the expressions we handle specially.  */
5090   if (!TYPE_P (t))
5091     return -1;
5092
5093   /* For convenience, follow the C standard when dealing with
5094      character types.  Any object may be accessed via an lvalue that
5095      has character type.  */
5096   if (t == char_type_node
5097       || t == signed_char_type_node
5098       || t == unsigned_char_type_node)
5099     return 0;
5100
5101   /* Allow aliasing between signed and unsigned variants of the same
5102      type.  We treat the signed variant as canonical.  */
5103   if (TREE_CODE (t) == INTEGER_TYPE && TYPE_UNSIGNED (t))
5104     {
5105       tree t1 = gimple_signed_type (t);
5106
5107       /* t1 == t can happen for boolean nodes which are always unsigned.  */
5108       if (t1 != t)
5109         return get_alias_set (t1);
5110     }
5111
5112   return -1;
5113 }
5114
5115
5116 /* Data structure used to count the number of dereferences to PTR
5117    inside an expression.  */
5118 struct count_ptr_d
5119 {
5120   tree ptr;
5121   unsigned num_stores;
5122   unsigned num_loads;
5123 };
5124
5125 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
5126    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
5127
5128 static tree
5129 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
5130 {
5131   struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
5132   struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
5133
5134   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
5135      pointer 'ptr' is *not* dereferenced, it is simply used to compute
5136      the address of 'fld' as 'ptr + offsetof(fld)'.  */
5137   if (TREE_CODE (*tp) == ADDR_EXPR)
5138     {
5139       *walk_subtrees = 0;
5140       return NULL_TREE;
5141     }
5142
5143   if (TREE_CODE (*tp) == MEM_REF && TREE_OPERAND (*tp, 0) == count_p->ptr)
5144     {
5145       if (wi_p->is_lhs)
5146         count_p->num_stores++;
5147       else
5148         count_p->num_loads++;
5149     }
5150
5151   return NULL_TREE;
5152 }
5153
5154 /* Count the number of direct and indirect uses for pointer PTR in
5155    statement STMT.  The number of direct uses is stored in
5156    *NUM_USES_P.  Indirect references are counted separately depending
5157    on whether they are store or load operations.  The counts are
5158    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
5159
5160 void
5161 count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
5162                        unsigned *num_loads_p, unsigned *num_stores_p)
5163 {
5164   ssa_op_iter i;
5165   tree use;
5166
5167   *num_uses_p = 0;
5168   *num_loads_p = 0;
5169   *num_stores_p = 0;
5170
5171   /* Find out the total number of uses of PTR in STMT.  */
5172   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
5173     if (use == ptr)
5174       (*num_uses_p)++;
5175
5176   /* Now count the number of indirect references to PTR.  This is
5177      truly awful, but we don't have much choice.  There are no parent
5178      pointers inside INDIRECT_REFs, so an expression like
5179      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
5180      find all the indirect and direct uses of x_1 inside.  The only
5181      shortcut we can take is the fact that GIMPLE only allows
5182      INDIRECT_REFs inside the expressions below.  */
5183   if (is_gimple_assign (stmt)
5184       || gimple_code (stmt) == GIMPLE_RETURN
5185       || gimple_code (stmt) == GIMPLE_ASM
5186       || is_gimple_call (stmt))
5187     {
5188       struct walk_stmt_info wi;
5189       struct count_ptr_d count;
5190
5191       count.ptr = ptr;
5192       count.num_stores = 0;
5193       count.num_loads = 0;
5194
5195       memset (&wi, 0, sizeof (wi));
5196       wi.info = &count;
5197       walk_gimple_op (stmt, count_ptr_derefs, &wi);
5198
5199       *num_stores_p = count.num_stores;
5200       *num_loads_p = count.num_loads;
5201     }
5202
5203   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
5204 }
5205
5206 /* From a tree operand OP return the base of a load or store operation
5207    or NULL_TREE if OP is not a load or a store.  */
5208
5209 static tree
5210 get_base_loadstore (tree op)
5211 {
5212   while (handled_component_p (op))
5213     op = TREE_OPERAND (op, 0);
5214   if (DECL_P (op)
5215       || INDIRECT_REF_P (op)
5216       || TREE_CODE (op) == MEM_REF
5217       || TREE_CODE (op) == TARGET_MEM_REF)
5218     return op;
5219   return NULL_TREE;
5220 }
5221
5222 /* For the statement STMT call the callbacks VISIT_LOAD, VISIT_STORE and
5223    VISIT_ADDR if non-NULL on loads, store and address-taken operands
5224    passing the STMT, the base of the operand and DATA to it.  The base
5225    will be either a decl, an indirect reference (including TARGET_MEM_REF)
5226    or the argument of an address expression.
5227    Returns the results of these callbacks or'ed.  */
5228
5229 bool
5230 walk_stmt_load_store_addr_ops (gimple stmt, void *data,
5231                                bool (*visit_load)(gimple, tree, void *),
5232                                bool (*visit_store)(gimple, tree, void *),
5233                                bool (*visit_addr)(gimple, tree, void *))
5234 {
5235   bool ret = false;
5236   unsigned i;
5237   if (gimple_assign_single_p (stmt))
5238     {
5239       tree lhs, rhs;
5240       if (visit_store)
5241         {
5242           lhs = get_base_loadstore (gimple_assign_lhs (stmt));
5243           if (lhs)
5244             ret |= visit_store (stmt, lhs, data);
5245         }
5246       rhs = gimple_assign_rhs1 (stmt);
5247       while (handled_component_p (rhs))
5248         rhs = TREE_OPERAND (rhs, 0);
5249       if (visit_addr)
5250         {
5251           if (TREE_CODE (rhs) == ADDR_EXPR)
5252             ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
5253           else if (TREE_CODE (rhs) == TARGET_MEM_REF
5254                    && TREE_CODE (TMR_BASE (rhs)) == ADDR_EXPR)
5255             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (rhs), 0), data);
5256           else if (TREE_CODE (rhs) == OBJ_TYPE_REF
5257                    && TREE_CODE (OBJ_TYPE_REF_OBJECT (rhs)) == ADDR_EXPR)
5258             ret |= visit_addr (stmt, TREE_OPERAND (OBJ_TYPE_REF_OBJECT (rhs),
5259                                                    0), data);
5260           lhs = gimple_assign_lhs (stmt);
5261           if (TREE_CODE (lhs) == TARGET_MEM_REF
5262               && TREE_CODE (TMR_BASE (lhs)) == ADDR_EXPR)
5263             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (lhs), 0), data);
5264         }
5265       if (visit_load)
5266         {
5267           rhs = get_base_loadstore (rhs);
5268           if (rhs)
5269             ret |= visit_load (stmt, rhs, data);
5270         }
5271     }
5272   else if (visit_addr
5273            && (is_gimple_assign (stmt)
5274                || gimple_code (stmt) == GIMPLE_COND))
5275     {
5276       for (i = 0; i < gimple_num_ops (stmt); ++i)
5277         if (gimple_op (stmt, i)
5278             && TREE_CODE (gimple_op (stmt, i)) == ADDR_EXPR)
5279           ret |= visit_addr (stmt, TREE_OPERAND (gimple_op (stmt, i), 0), data);
5280     }
5281   else if (is_gimple_call (stmt))
5282     {
5283       if (visit_store)
5284         {
5285           tree lhs = gimple_call_lhs (stmt);
5286           if (lhs)
5287             {
5288               lhs = get_base_loadstore (lhs);
5289               if (lhs)
5290                 ret |= visit_store (stmt, lhs, data);
5291             }
5292         }
5293       if (visit_load || visit_addr)
5294         for (i = 0; i < gimple_call_num_args (stmt); ++i)
5295           {
5296             tree rhs = gimple_call_arg (stmt, i);
5297             if (visit_addr
5298                 && TREE_CODE (rhs) == ADDR_EXPR)
5299               ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
5300             else if (visit_load)
5301               {
5302                 rhs = get_base_loadstore (rhs);
5303                 if (rhs)
5304                   ret |= visit_load (stmt, rhs, data);
5305               }
5306           }
5307       if (visit_addr
5308           && gimple_call_chain (stmt)
5309           && TREE_CODE (gimple_call_chain (stmt)) == ADDR_EXPR)
5310         ret |= visit_addr (stmt, TREE_OPERAND (gimple_call_chain (stmt), 0),
5311                            data);
5312       if (visit_addr
5313           && gimple_call_return_slot_opt_p (stmt)
5314           && gimple_call_lhs (stmt) != NULL_TREE
5315           && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
5316         ret |= visit_addr (stmt, gimple_call_lhs (stmt), data);
5317     }
5318   else if (gimple_code (stmt) == GIMPLE_ASM)
5319     {
5320       unsigned noutputs;
5321       const char *constraint;
5322       const char **oconstraints;
5323       bool allows_mem, allows_reg, is_inout;
5324       noutputs = gimple_asm_noutputs (stmt);
5325       oconstraints = XALLOCAVEC (const char *, noutputs);
5326       if (visit_store || visit_addr)
5327         for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
5328           {
5329             tree link = gimple_asm_output_op (stmt, i);
5330             tree op = get_base_loadstore (TREE_VALUE (link));
5331             if (op && visit_store)
5332               ret |= visit_store (stmt, op, data);
5333             if (visit_addr)
5334               {
5335                 constraint = TREE_STRING_POINTER
5336                     (TREE_VALUE (TREE_PURPOSE (link)));
5337                 oconstraints[i] = constraint;
5338                 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
5339                                          &allows_reg, &is_inout);
5340                 if (op && !allows_reg && allows_mem)
5341                   ret |= visit_addr (stmt, op, data);
5342               }
5343           }
5344       if (visit_load || visit_addr)
5345         for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
5346           {
5347             tree link = gimple_asm_input_op (stmt, i);
5348             tree op = TREE_VALUE (link);
5349             if (visit_addr
5350                 && TREE_CODE (op) == ADDR_EXPR)
5351               ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5352             else if (visit_load || visit_addr)
5353               {
5354                 op = get_base_loadstore (op);
5355                 if (op)
5356                   {
5357                     if (visit_load)
5358                       ret |= visit_load (stmt, op, data);
5359                     if (visit_addr)
5360                       {
5361                         constraint = TREE_STRING_POINTER
5362                             (TREE_VALUE (TREE_PURPOSE (link)));
5363                         parse_input_constraint (&constraint, 0, 0, noutputs,
5364                                                 0, oconstraints,
5365                                                 &allows_mem, &allows_reg);
5366                         if (!allows_reg && allows_mem)
5367                           ret |= visit_addr (stmt, op, data);
5368                       }
5369                   }
5370               }
5371           }
5372     }
5373   else if (gimple_code (stmt) == GIMPLE_RETURN)
5374     {
5375       tree op = gimple_return_retval (stmt);
5376       if (op)
5377         {
5378           if (visit_addr
5379               && TREE_CODE (op) == ADDR_EXPR)
5380             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5381           else if (visit_load)
5382             {
5383               op = get_base_loadstore (op);
5384               if (op)
5385                 ret |= visit_load (stmt, op, data);
5386             }
5387         }
5388     }
5389   else if (visit_addr
5390            && gimple_code (stmt) == GIMPLE_PHI)
5391     {
5392       for (i = 0; i < gimple_phi_num_args (stmt); ++i)
5393         {
5394           tree op = PHI_ARG_DEF (stmt, i);
5395           if (TREE_CODE (op) == ADDR_EXPR)
5396             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
5397         }
5398     }
5399
5400   return ret;
5401 }
5402
5403 /* Like walk_stmt_load_store_addr_ops but with NULL visit_addr.  IPA-CP
5404    should make a faster clone for this case.  */
5405
5406 bool
5407 walk_stmt_load_store_ops (gimple stmt, void *data,
5408                           bool (*visit_load)(gimple, tree, void *),
5409                           bool (*visit_store)(gimple, tree, void *))
5410 {
5411   return walk_stmt_load_store_addr_ops (stmt, data,
5412                                         visit_load, visit_store, NULL);
5413 }
5414
5415 /* Helper for gimple_ior_addresses_taken_1.  */
5416
5417 static bool
5418 gimple_ior_addresses_taken_1 (gimple stmt ATTRIBUTE_UNUSED,
5419                               tree addr, void *data)
5420 {
5421   bitmap addresses_taken = (bitmap)data;
5422   addr = get_base_address (addr);
5423   if (addr
5424       && DECL_P (addr))
5425     {
5426       bitmap_set_bit (addresses_taken, DECL_UID (addr));
5427       return true;
5428     }
5429   return false;
5430 }
5431
5432 /* Set the bit for the uid of all decls that have their address taken
5433    in STMT in the ADDRESSES_TAKEN bitmap.  Returns true if there
5434    were any in this stmt.  */
5435
5436 bool
5437 gimple_ior_addresses_taken (bitmap addresses_taken, gimple stmt)
5438 {
5439   return walk_stmt_load_store_addr_ops (stmt, addresses_taken, NULL, NULL,
5440                                         gimple_ior_addresses_taken_1);
5441 }
5442
5443
5444 /* Return a printable name for symbol DECL.  */
5445
5446 const char *
5447 gimple_decl_printable_name (tree decl, int verbosity)
5448 {
5449   if (!DECL_NAME (decl))
5450     return NULL;
5451
5452   if (DECL_ASSEMBLER_NAME_SET_P (decl))
5453     {
5454       const char *str, *mangled_str;
5455       int dmgl_opts = DMGL_NO_OPTS;
5456
5457       if (verbosity >= 2)
5458         {
5459           dmgl_opts = DMGL_VERBOSE
5460                       | DMGL_ANSI
5461                       | DMGL_GNU_V3
5462                       | DMGL_RET_POSTFIX;
5463           if (TREE_CODE (decl) == FUNCTION_DECL)
5464             dmgl_opts |= DMGL_PARAMS;
5465         }
5466
5467       mangled_str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
5468       str = cplus_demangle_v3 (mangled_str, dmgl_opts);
5469       return (str) ? str : mangled_str;
5470     }
5471
5472   return IDENTIFIER_POINTER (DECL_NAME (decl));
5473 }
5474
5475 /* Return true when STMT is builtins call to CODE.  */
5476
5477 bool
5478 gimple_call_builtin_p (gimple stmt, enum built_in_function code)
5479 {
5480   tree fndecl;
5481   return (is_gimple_call (stmt)
5482           && (fndecl = gimple_call_fndecl (stmt)) != NULL
5483           && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
5484           && DECL_FUNCTION_CODE (fndecl) == code);
5485 }
5486
5487 /* Return true if STMT clobbers memory.  STMT is required to be a
5488    GIMPLE_ASM.  */
5489
5490 bool
5491 gimple_asm_clobbers_memory_p (const_gimple stmt)
5492 {
5493   unsigned i;
5494
5495   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
5496     {
5497       tree op = gimple_asm_clobber_op (stmt, i);
5498       if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op)), "memory") == 0)
5499         return true;
5500     }
5501
5502   return false;
5503 }
5504 #include "gt-gimple.h"