gcc/gimple.c

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