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     return 1;
3178
3179   /* Check that we have two types to compare.  */
3180   if (t1 == NULL_TREE || t2 == NULL_TREE)
3181     return 0;
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     return 0;
3186
3187   /* Can't be the same type if they have different CV qualifiers.  */
3188   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
3189     return 0;
3190
3191   /* Void types are always the same.  */
3192   if (TREE_CODE (t1) == VOID_TYPE)
3193     return 1;
3194
3195   /* For numerical types do some simple checks before doing three
3196      hashtable queries.  */
3197   if (INTEGRAL_TYPE_P (t1)
3198       || SCALAR_FLOAT_TYPE_P (t1)
3199       || FIXED_POINT_TYPE_P (t1)
3200       || TREE_CODE (t1) == VECTOR_TYPE
3201       || TREE_CODE (t1) == COMPLEX_TYPE
3202       || TREE_CODE (t1) == OFFSET_TYPE)
3203     {
3204       /* Can't be the same type if they have different alignment,
3205          sign, precision or mode.  */
3206       if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
3207           || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
3208           || TYPE_MODE (t1) != TYPE_MODE (t2)
3209           || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
3210         return 0;
3211
3212       if (TREE_CODE (t1) == INTEGER_TYPE
3213           && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
3214               || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
3215         return 0;
3216
3217       /* That's all we need to check for float and fixed-point types.  */
3218       if (SCALAR_FLOAT_TYPE_P (t1)
3219           || FIXED_POINT_TYPE_P (t1))
3220         return 1;
3221
3222       /* Perform cheap tail-recursion for vector and complex types.  */
3223       if (TREE_CODE (t1) == VECTOR_TYPE
3224           || TREE_CODE (t1) == COMPLEX_TYPE)
3225         return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2));
3226
3227       /* For integral types fall thru to more complex checks.  */
3228     }
3229
3230   /* If the hash values of t1 and t2 are different the types can't
3231      possibly be the same.  This helps keeping the type-pair hashtable
3232      small, only tracking comparisons for hash collisions.  */
3233   if (gimple_type_hash (t1) != gimple_type_hash (t2))
3234     return 0;
3235
3236   /* If we've visited this type pair before (in the case of aggregates
3237      with self-referential types), and we made a decision, return it.  */
3238   p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
3239   if (p->same_p == 0 || p->same_p == 1)
3240     {
3241       /* We have already decided whether T1 and T2 are the
3242          same, return the cached result.  */
3243       return p->same_p == 1;
3244     }
3245   else if (p->same_p == -1)
3246     {
3247       /* We are currently comparing this pair of types, assume
3248          that they are the same and let the caller decide.  */
3249       return 1;
3250     }
3251
3252   gcc_assert (p->same_p == -2);
3253
3254   /* Mark the (T1, T2) comparison in progress.  */
3255   p->same_p = -1;
3256
3257   /* If their attributes are not the same they can't be the same type.  */
3258   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
3259     goto different_types;
3260
3261   /* Do type-specific comparisons.  */
3262   switch (TREE_CODE (t1))
3263     {
3264     case ARRAY_TYPE:
3265       /* Array types are the same if the element types are the same and
3266          the number of elements are the same.  */
3267       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
3268           || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
3269           || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
3270         goto different_types;
3271       else
3272         {
3273           tree i1 = TYPE_DOMAIN (t1);
3274           tree i2 = TYPE_DOMAIN (t2);
3275
3276           /* For an incomplete external array, the type domain can be
3277              NULL_TREE.  Check this condition also.  */
3278           if (i1 == NULL_TREE && i2 == NULL_TREE)
3279             goto same_types;
3280           else if (i1 == NULL_TREE || i2 == NULL_TREE)
3281             goto different_types;
3282           /* If for a complete array type the possibly gimplified sizes
3283              are different the types are different.  */
3284           else if (((TYPE_SIZE (i1) != NULL) ^ (TYPE_SIZE (i2) != NULL))
3285                    || (TYPE_SIZE (i1)
3286                        && TYPE_SIZE (i2)
3287                        && !operand_equal_p (TYPE_SIZE (i1), TYPE_SIZE (i2), 0)))
3288             goto different_types;
3289           else
3290             {
3291               tree min1 = TYPE_MIN_VALUE (i1);
3292               tree min2 = TYPE_MIN_VALUE (i2);
3293               tree max1 = TYPE_MAX_VALUE (i1);
3294               tree max2 = TYPE_MAX_VALUE (i2);
3295
3296               /* The minimum/maximum values have to be the same.  */
3297               if ((min1 == min2
3298                    || (min1 && min2 && operand_equal_p (min1, min2, 0)))
3299                   && (max1 == max2
3300                       || (max1 && max2 && operand_equal_p (max1, max2, 0))))
3301                 goto same_types;
3302               else
3303                 goto different_types;
3304             }
3305         }
3306
3307     case METHOD_TYPE:
3308       /* Method types should belong to the same class.  */
3309       if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
3310                                  TYPE_METHOD_BASETYPE (t2)))
3311         goto different_types;
3312
3313       /* Fallthru  */
3314
3315     case FUNCTION_TYPE:
3316       /* Function types are the same if the return type and arguments types
3317          are the same.  */
3318       if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3319         goto different_types;
3320       else
3321         {
3322           if (!targetm.comp_type_attributes (t1, t2))
3323             goto different_types;
3324
3325           if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
3326             goto same_types;
3327           else
3328             {
3329               tree parms1, parms2;
3330
3331               for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
3332                    parms1 && parms2;
3333                    parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
3334                 {
3335                   if (!gimple_types_compatible_p (TREE_VALUE (parms1),
3336                                              TREE_VALUE (parms2)))
3337                     goto different_types;
3338                 }
3339
3340               if (parms1 || parms2)
3341                 goto different_types;
3342
3343               goto same_types;
3344             }
3345         }
3346
3347     case OFFSET_TYPE:
3348       {
3349         if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2))
3350             || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1),
3351                                            TYPE_OFFSET_BASETYPE (t2)))
3352           goto different_types;
3353
3354         goto same_types;
3355       }
3356
3357     case POINTER_TYPE:
3358     case REFERENCE_TYPE:
3359       {
3360         /* If the two pointers have different ref-all attributes,
3361            they can't be the same type.  */
3362         if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
3363           goto different_types;
3364
3365         /* If one pointer points to an incomplete type variant of
3366            the other pointed-to type they are the same.  */
3367         if (TREE_CODE (TREE_TYPE (t1)) == TREE_CODE (TREE_TYPE (t2))
3368             && RECORD_OR_UNION_TYPE_P (TREE_TYPE (t1))
3369             && (!COMPLETE_TYPE_P (TREE_TYPE (t1))
3370                 || !COMPLETE_TYPE_P (TREE_TYPE (t2)))
3371             && compare_type_names_p (TREE_TYPE (t1), TREE_TYPE (t2), true))
3372           {
3373             /* Replace the pointed-to incomplete type with the
3374                complete one.  */
3375             if (COMPLETE_TYPE_P (TREE_TYPE (t2)))
3376               TREE_TYPE (t1) = TREE_TYPE (t2);
3377             else
3378               TREE_TYPE (t2) = TREE_TYPE (t1);
3379             goto same_types;
3380           }
3381
3382         /* Otherwise, pointer and reference types are the same if the
3383            pointed-to types are the same.  */
3384         if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3385           goto same_types;
3386
3387         goto different_types;
3388       }
3389
3390     case INTEGER_TYPE:
3391     case BOOLEAN_TYPE:
3392       {
3393         tree min1 = TYPE_MIN_VALUE (t1);
3394         tree max1 = TYPE_MAX_VALUE (t1);
3395         tree min2 = TYPE_MIN_VALUE (t2);
3396         tree max2 = TYPE_MAX_VALUE (t2);
3397         bool min_equal_p = false;
3398         bool max_equal_p = false;
3399
3400         /* If either type has a minimum value, the other type must
3401            have the same.  */
3402         if (min1 == NULL_TREE && min2 == NULL_TREE)
3403           min_equal_p = true;
3404         else if (min1 && min2 && operand_equal_p (min1, min2, 0))
3405           min_equal_p = true;
3406
3407         /* Likewise, if either type has a maximum value, the other
3408            type must have the same.  */
3409         if (max1 == NULL_TREE && max2 == NULL_TREE)
3410           max_equal_p = true;
3411         else if (max1 && max2 && operand_equal_p (max1, max2, 0))
3412           max_equal_p = true;
3413
3414         if (!min_equal_p || !max_equal_p)
3415           goto different_types;
3416
3417         goto same_types;
3418       }
3419
3420     case ENUMERAL_TYPE:
3421       {
3422         /* FIXME lto, we cannot check bounds on enumeral types because
3423            different front ends will produce different values.
3424            In C, enumeral types are integers, while in C++ each element
3425            will have its own symbolic value.  We should decide how enums
3426            are to be represented in GIMPLE and have each front end lower
3427            to that.  */
3428         tree v1, v2;
3429
3430         /* For enumeral types, all the values must be the same.  */
3431         if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
3432           goto same_types;
3433
3434         for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
3435              v1 && v2;
3436              v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
3437           {
3438             tree c1 = TREE_VALUE (v1);
3439             tree c2 = TREE_VALUE (v2);
3440
3441             if (TREE_CODE (c1) == CONST_DECL)
3442               c1 = DECL_INITIAL (c1);
3443
3444             if (TREE_CODE (c2) == CONST_DECL)
3445               c2 = DECL_INITIAL (c2);
3446
3447             if (tree_int_cst_equal (c1, c2) != 1)
3448               goto different_types;
3449           }
3450
3451         /* If one enumeration has more values than the other, they
3452            are not the same.  */
3453         if (v1 || v2)
3454           goto different_types;
3455
3456         goto same_types;
3457       }
3458
3459     case RECORD_TYPE:
3460     case UNION_TYPE:
3461     case QUAL_UNION_TYPE:
3462       {
3463         tree f1, f2;
3464
3465         /* If one type requires structural equality checks and the
3466            other doesn't, do not merge the types.  */
3467         if (TYPE_STRUCTURAL_EQUALITY_P (t1)
3468             != TYPE_STRUCTURAL_EQUALITY_P (t2))
3469           goto different_types;
3470
3471         /* The struct tags shall compare equal.  */
3472         if (!compare_type_names_p (TYPE_MAIN_VARIANT (t1),
3473                                    TYPE_MAIN_VARIANT (t2), false))
3474           goto different_types;
3475
3476         /* For aggregate types, all the fields must be the same.  */
3477         for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
3478              f1 && f2;
3479              f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
3480           {
3481             /* The fields must have the same name, offset and type.  */
3482             if (DECL_NAME (f1) != DECL_NAME (f2)
3483                 || DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
3484                 || !compare_field_offset (f1, f2)
3485                 || !gimple_types_compatible_p (TREE_TYPE (f1),
3486                                                TREE_TYPE (f2)))
3487               goto different_types;
3488           }
3489
3490         /* If one aggregate has more fields than the other, they
3491            are not the same.  */
3492         if (f1 || f2)
3493           goto different_types;
3494
3495         goto same_types;
3496       }
3497
3498     default:
3499       gcc_unreachable ();
3500     }
3501
3502   /* Common exit path for types that are not compatible.  */
3503 different_types:
3504   p->same_p = 0;
3505   return 0;
3506
3507   /* Common exit path for types that are compatible.  */
3508 same_types:
3509   p->same_p = 1;
3510   return 1;
3511 }
3512
3513
3514
3515
3516 /* Per pointer state for the SCC finding.  The on_sccstack flag
3517    is not strictly required, it is true when there is no hash value
3518    recorded for the type and false otherwise.  But querying that
3519    is slower.  */
3520
3521 struct sccs
3522 {
3523   unsigned int dfsnum;
3524   unsigned int low;
3525   bool on_sccstack;
3526   hashval_t hash;
3527 };
3528
3529 static unsigned int next_dfs_num;
3530
3531 static hashval_t
3532 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
3533                             struct pointer_map_t *, struct obstack *);
3534
3535 /* DFS visit the edge from the callers type with state *STATE to T.
3536    Update the callers type hash V with the hash for T if it is not part
3537    of the SCC containing the callers type and return it.
3538    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.  */
3539
3540 static hashval_t
3541 visit (tree t, struct sccs *state, hashval_t v,
3542        VEC (tree, heap) **sccstack,
3543        struct pointer_map_t *sccstate,
3544        struct obstack *sccstate_obstack)
3545 {
3546   struct sccs *cstate = NULL;
3547   void **slot;
3548
3549   /* If there is a hash value recorded for this type then it can't
3550      possibly be part of our parent SCC.  Simply mix in its hash.  */
3551   if ((slot = pointer_map_contains (type_hash_cache, t)))
3552     return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, v);
3553
3554   if ((slot = pointer_map_contains (sccstate, t)) != NULL)
3555     cstate = (struct sccs *)*slot;
3556   if (!cstate)
3557     {
3558       hashval_t tem;
3559       /* Not yet visited.  DFS recurse.  */
3560       tem = iterative_hash_gimple_type (t, v,
3561                                         sccstack, sccstate, sccstate_obstack);
3562       if (!cstate)
3563         cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
3564       state->low = MIN (state->low, cstate->low);
3565       /* If the type is no longer on the SCC stack and thus is not part
3566          of the parents SCC mix in its hash value.  Otherwise we will
3567          ignore the type for hashing purposes and return the unaltered
3568          hash value.  */
3569       if (!cstate->on_sccstack)
3570         return tem;
3571     }
3572   if (cstate->dfsnum < state->dfsnum
3573       && cstate->on_sccstack)
3574     state->low = MIN (cstate->dfsnum, state->low);
3575
3576   /* We are part of our parents SCC, skip this type during hashing
3577      and return the unaltered hash value.  */
3578   return v;
3579 }
3580
3581 /* Hash NAME with the previous hash value V and return it.  */
3582
3583 static hashval_t
3584 iterative_hash_name (tree name, hashval_t v)
3585 {
3586   if (!name)
3587     return v;
3588   if (TREE_CODE (name) == TYPE_DECL)
3589     name = DECL_NAME (name);
3590   if (!name)
3591     return v;
3592   gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
3593   return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
3594 }
3595
3596 /* Returning a hash value for gimple type TYPE combined with VAL.
3597    SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
3598
3599    To hash a type we end up hashing in types that are reachable.
3600    Through pointers we can end up with cycles which messes up the
3601    required property that we need to compute the same hash value
3602    for structurally equivalent types.  To avoid this we have to
3603    hash all types in a cycle (the SCC) in a commutative way.  The
3604    easiest way is to not mix in the hashes of the SCC members at
3605    all.  To make this work we have to delay setting the hash
3606    values of the SCC until it is complete.  */
3607
3608 static hashval_t
3609 iterative_hash_gimple_type (tree type, hashval_t val,
3610                             VEC(tree, heap) **sccstack,
3611                             struct pointer_map_t *sccstate,
3612                             struct obstack *sccstate_obstack)
3613 {
3614   hashval_t v;
3615   void **slot;
3616   struct sccs *state;
3617
3618 #ifdef ENABLE_CHECKING
3619   /* Not visited during this DFS walk nor during previous walks.  */
3620   gcc_assert (!pointer_map_contains (type_hash_cache, type)
3621               && !pointer_map_contains (sccstate, type));
3622 #endif
3623   state = XOBNEW (sccstate_obstack, struct sccs);
3624   *pointer_map_insert (sccstate, type) = state;
3625
3626   VEC_safe_push (tree, heap, *sccstack, type);
3627   state->dfsnum = next_dfs_num++;
3628   state->low = state->dfsnum;
3629   state->on_sccstack = true;
3630
3631   /* Combine a few common features of types so that types are grouped into
3632      smaller sets; when searching for existing matching types to merge,
3633      only existing types having the same features as the new type will be
3634      checked.  */
3635   v = iterative_hash_hashval_t (TREE_CODE (type), 0);
3636   v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
3637   v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
3638
3639   /* Do not hash the types size as this will cause differences in
3640      hash values for the complete vs. the incomplete type variant.  */
3641
3642   /* Incorporate common features of numerical types.  */
3643   if (INTEGRAL_TYPE_P (type)
3644       || SCALAR_FLOAT_TYPE_P (type)
3645       || FIXED_POINT_TYPE_P (type))
3646     {
3647       v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
3648       v = iterative_hash_hashval_t (TYPE_MODE (type), v);
3649       v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
3650     }
3651
3652   /* For pointer and reference types, fold in information about the type
3653      pointed to but do not recurse into possibly incomplete types to
3654      avoid hash differences for complete vs. incomplete types.  */
3655   if (POINTER_TYPE_P (type))
3656     {
3657       if (RECORD_OR_UNION_TYPE_P (TREE_TYPE (type)))
3658         {
3659           v = iterative_hash_hashval_t (TREE_CODE (TREE_TYPE (type)), v);
3660           v = iterative_hash_name
3661               (TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (type))), v);
3662         }
3663       else
3664         v = visit (TREE_TYPE (type), state, v,
3665                    sccstack, sccstate, sccstate_obstack);
3666     }
3667
3668   /* For integer types hash the types min/max values and the string flag.  */
3669   if (TREE_CODE (type) == INTEGER_TYPE)
3670     {
3671       v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
3672       v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
3673       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
3674     }
3675
3676   /* For array types hash their domain and the string flag.  */
3677   if (TREE_CODE (type) == ARRAY_TYPE
3678       && TYPE_DOMAIN (type))
3679     {
3680       v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
3681       v = visit (TYPE_DOMAIN (type), state, v,
3682                  sccstack, sccstate, sccstate_obstack);
3683     }
3684
3685   /* Recurse for aggregates with a single element type.  */
3686   if (TREE_CODE (type) == ARRAY_TYPE
3687       || TREE_CODE (type) == COMPLEX_TYPE
3688       || TREE_CODE (type) == VECTOR_TYPE)
3689     v = visit (TREE_TYPE (type), state, v,
3690                sccstack, sccstate, sccstate_obstack);
3691
3692   /* Incorporate function return and argument types.  */
3693   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
3694     {
3695       unsigned na;
3696       tree p;
3697
3698       /* For method types also incorporate their parent class.  */
3699       if (TREE_CODE (type) == METHOD_TYPE)
3700         v = visit (TYPE_METHOD_BASETYPE (type), state, v,
3701                    sccstack, sccstate, sccstate_obstack);
3702
3703       v = visit (TREE_TYPE (type), state, v,
3704                  sccstack, sccstate, sccstate_obstack);
3705
3706       for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
3707         {
3708           v = visit (TREE_VALUE (p), state, v,
3709                      sccstack, sccstate, sccstate_obstack);
3710           na++;
3711         }
3712
3713       v = iterative_hash_hashval_t (na, v);
3714     }
3715
3716   if (TREE_CODE (type) == RECORD_TYPE
3717       || TREE_CODE (type) == UNION_TYPE
3718       || TREE_CODE (type) == QUAL_UNION_TYPE)
3719     {
3720       unsigned nf;
3721       tree f;
3722
3723       v = iterative_hash_name (TYPE_NAME (TYPE_MAIN_VARIANT (type)), v);
3724
3725       for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
3726         {
3727           v = iterative_hash_name (DECL_NAME (f), v);
3728           v = visit (TREE_TYPE (f), state, v,
3729                      sccstack, sccstate, sccstate_obstack);
3730           nf++;
3731         }
3732
3733       v = iterative_hash_hashval_t (nf, v);
3734     }
3735
3736   /* Record hash for us.  */
3737   state->hash = v;
3738
3739   /* See if we found an SCC.  */
3740   if (state->low == state->dfsnum)
3741     {
3742       tree x;
3743
3744       /* Pop off the SCC and set its hash values.  */
3745       do
3746         {
3747           struct sccs *cstate;
3748           x = VEC_pop (tree, *sccstack);
3749           gcc_assert (!pointer_map_contains (type_hash_cache, x));
3750           cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
3751           cstate->on_sccstack = false;
3752           slot = pointer_map_insert (type_hash_cache, x);
3753           *slot = (void *) (size_t) cstate->hash;
3754         }
3755       while (x != type);
3756     }
3757
3758   return iterative_hash_hashval_t (v, val);
3759 }
3760
3761
3762 /* Returns a hash value for P (assumed to be a type).  The hash value
3763    is computed using some distinguishing features of the type.  Note
3764    that we cannot use pointer hashing here as we may be dealing with
3765    two distinct instances of the same type.
3766
3767    This function should produce the same hash value for two compatible
3768    types according to gimple_types_compatible_p.  */
3769
3770 static hashval_t
3771 gimple_type_hash (const void *p)
3772 {
3773   const_tree t = (const_tree) p;
3774   VEC(tree, heap) *sccstack = NULL;
3775   struct pointer_map_t *sccstate;
3776   struct obstack sccstate_obstack;
3777   hashval_t val;
3778   void **slot;
3779
3780   if (type_hash_cache == NULL)
3781     type_hash_cache = pointer_map_create ();
3782
3783   if ((slot = pointer_map_contains (type_hash_cache, p)) != NULL)
3784     return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, 0);
3785
3786   /* Perform a DFS walk and pre-hash all reachable types.  */
3787   next_dfs_num = 1;
3788   sccstate = pointer_map_create ();
3789   gcc_obstack_init (&sccstate_obstack);
3790   val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
3791                                     &sccstack, sccstate, &sccstate_obstack);
3792   VEC_free (tree, heap, sccstack);
3793   pointer_map_destroy (sccstate);
3794   obstack_free (&sccstate_obstack, NULL);
3795
3796   return val;
3797 }
3798
3799
3800 /* Returns nonzero if P1 and P2 are equal.  */
3801
3802 static int
3803 gimple_type_eq (const void *p1, const void *p2)
3804 {
3805   const_tree t1 = (const_tree) p1;
3806   const_tree t2 = (const_tree) p2;
3807   return gimple_types_compatible_p (CONST_CAST_TREE (t1), CONST_CAST_TREE (t2));
3808 }
3809
3810
3811 /* Register type T in the global type table gimple_types.
3812    If another type T', compatible with T, already existed in
3813    gimple_types then return T', otherwise return T.  This is used by
3814    LTO to merge identical types read from different TUs.  */
3815
3816 tree
3817 gimple_register_type (tree t)
3818 {
3819   void **slot;
3820
3821   gcc_assert (TYPE_P (t));
3822
3823   /* Always register the main variant first.  This is important so we
3824      pick up the non-typedef variants as canonical, otherwise we'll end
3825      up taking typedef ids for structure tags during comparison.  */
3826   if (TYPE_MAIN_VARIANT (t) != t)
3827     gimple_register_type (TYPE_MAIN_VARIANT (t));
3828
3829   if (gimple_types == NULL)
3830     gimple_types = htab_create (16381, gimple_type_hash, gimple_type_eq, 0);
3831
3832   slot = htab_find_slot (gimple_types, t, INSERT);
3833   if (*slot
3834       && *(tree *)slot != t)
3835     {
3836       tree new_type = (tree) *((tree *) slot);
3837
3838       /* Do not merge types with different addressability.  */
3839       gcc_assert (TREE_ADDRESSABLE (t) == TREE_ADDRESSABLE (new_type));
3840
3841       /* If t is not its main variant then make t unreachable from its
3842          main variant list.  Otherwise we'd queue up a lot of duplicates
3843          there.  */
3844       if (t != TYPE_MAIN_VARIANT (t))
3845         {
3846           tree tem = TYPE_MAIN_VARIANT (t);
3847           while (tem && TYPE_NEXT_VARIANT (tem) != t)
3848             tem = TYPE_NEXT_VARIANT (tem);
3849           if (tem)
3850             TYPE_NEXT_VARIANT (tem) = TYPE_NEXT_VARIANT (t);
3851           TYPE_NEXT_VARIANT (t) = NULL_TREE;
3852         }
3853
3854       /* If we are a pointer then remove us from the pointer-to or
3855          reference-to chain.  Otherwise we'd queue up a lot of duplicates
3856          there.  */
3857       if (TREE_CODE (t) == POINTER_TYPE)
3858         {
3859           if (TYPE_POINTER_TO (TREE_TYPE (t)) == t)
3860             TYPE_POINTER_TO (TREE_TYPE (t)) = TYPE_NEXT_PTR_TO (t);
3861           else
3862             {
3863               tree tem = TYPE_POINTER_TO (TREE_TYPE (t));
3864               while (tem && TYPE_NEXT_PTR_TO (tem) != t)
3865                 tem = TYPE_NEXT_PTR_TO (tem);
3866               if (tem)
3867                 TYPE_NEXT_PTR_TO (tem) = TYPE_NEXT_PTR_TO (t);
3868             }
3869           TYPE_NEXT_PTR_TO (t) = NULL_TREE;
3870         }
3871       else if (TREE_CODE (t) == REFERENCE_TYPE)
3872         {
3873           if (TYPE_REFERENCE_TO (TREE_TYPE (t)) == t)
3874             TYPE_REFERENCE_TO (TREE_TYPE (t)) = TYPE_NEXT_REF_TO (t);
3875           else
3876             {
3877               tree tem = TYPE_REFERENCE_TO (TREE_TYPE (t));
3878               while (tem && TYPE_NEXT_REF_TO (tem) != t)
3879                 tem = TYPE_NEXT_REF_TO (tem);
3880               if (tem)
3881                 TYPE_NEXT_REF_TO (tem) = TYPE_NEXT_REF_TO (t);
3882             }
3883           TYPE_NEXT_REF_TO (t) = NULL_TREE;
3884         }
3885
3886       t = new_type;
3887     }
3888   else
3889     *slot = (void *) t;
3890
3891   return t;
3892 }
3893
3894
3895 /* Show statistics on references to the global type table gimple_types.  */
3896
3897 void
3898 print_gimple_types_stats (void)
3899 {
3900   if (gimple_types)
3901     fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
3902              "%ld searches, %ld collisions (ratio: %f)\n",
3903              (long) htab_size (gimple_types),
3904              (long) htab_elements (gimple_types),
3905              (long) gimple_types->searches,
3906              (long) gimple_types->collisions,
3907              htab_collisions (gimple_types));
3908   else
3909     fprintf (stderr, "GIMPLE type table is empty\n");
3910   if (gtc_visited)
3911     fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
3912              "elements, %ld searches, %ld collisions (ratio: %f)\n",
3913              (long) htab_size (gtc_visited),
3914              (long) htab_elements (gtc_visited),
3915              (long) gtc_visited->searches,
3916              (long) gtc_visited->collisions,
3917              htab_collisions (gtc_visited));
3918   else
3919     fprintf (stderr, "GIMPLE type comparison table is empty\n");
3920 }
3921
3922 /* Free the gimple type hashtables used for LTO type merging.  */
3923
3924 void
3925 free_gimple_type_tables (void)
3926 {
3927   /* Last chance to print stats for the tables.  */
3928   if (flag_lto_report)
3929     print_gimple_types_stats ();
3930
3931   if (gimple_types)
3932     {
3933       htab_delete (gimple_types);
3934       gimple_types = NULL;
3935     }
3936   if (type_hash_cache)
3937     {
3938       pointer_map_destroy (type_hash_cache);
3939       type_hash_cache = NULL;
3940     }
3941   if (gtc_visited)
3942     {
3943       htab_delete (gtc_visited);
3944       obstack_free (&gtc_ob, NULL);
3945       gtc_visited = NULL;
3946     }
3947 }
3948
3949
3950 /* Return a type the same as TYPE except unsigned or
3951    signed according to UNSIGNEDP.  */
3952
3953 static tree
3954 gimple_signed_or_unsigned_type (bool unsignedp, tree type)
3955 {
3956   tree type1;
3957
3958   type1 = TYPE_MAIN_VARIANT (type);
3959   if (type1 == signed_char_type_node
3960       || type1 == char_type_node
3961       || type1 == unsigned_char_type_node)
3962     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
3963   if (type1 == integer_type_node || type1 == unsigned_type_node)
3964     return unsignedp ? unsigned_type_node : integer_type_node;
3965   if (type1 == short_integer_type_node || type1 == short_unsigned_type_node)
3966     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
3967   if (type1 == long_integer_type_node || type1 == long_unsigned_type_node)
3968     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
3969   if (type1 == long_long_integer_type_node
3970       || type1 == long_long_unsigned_type_node)
3971     return unsignedp
3972            ? long_long_unsigned_type_node
3973            : long_long_integer_type_node;
3974 #if HOST_BITS_PER_WIDE_INT >= 64
3975   if (type1 == intTI_type_node || type1 == unsigned_intTI_type_node)
3976     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
3977 #endif
3978   if (type1 == intDI_type_node || type1 == unsigned_intDI_type_node)
3979     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
3980   if (type1 == intSI_type_node || type1 == unsigned_intSI_type_node)
3981     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
3982   if (type1 == intHI_type_node || type1 == unsigned_intHI_type_node)
3983     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
3984   if (type1 == intQI_type_node || type1 == unsigned_intQI_type_node)
3985     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
3986
3987 #define GIMPLE_FIXED_TYPES(NAME)            \
3988   if (type1 == short_ ## NAME ## _type_node \
3989       || type1 == unsigned_short_ ## NAME ## _type_node) \
3990     return unsignedp ? unsigned_short_ ## NAME ## _type_node \
3991                      : short_ ## NAME ## _type_node; \
3992   if (type1 == NAME ## _type_node \
3993       || type1 == unsigned_ ## NAME ## _type_node) \
3994     return unsignedp ? unsigned_ ## NAME ## _type_node \
3995                      : NAME ## _type_node; \
3996   if (type1 == long_ ## NAME ## _type_node \
3997       || type1 == unsigned_long_ ## NAME ## _type_node) \
3998     return unsignedp ? unsigned_long_ ## NAME ## _type_node \
3999                      : long_ ## NAME ## _type_node; \
4000   if (type1 == long_long_ ## NAME ## _type_node \
4001       || type1 == unsigned_long_long_ ## NAME ## _type_node) \
4002     return unsignedp ? unsigned_long_long_ ## NAME ## _type_node \
4003                      : long_long_ ## NAME ## _type_node;
4004
4005 #define GIMPLE_FIXED_MODE_TYPES(NAME) \
4006   if (type1 == NAME ## _type_node \
4007       || type1 == u ## NAME ## _type_node) \
4008     return unsignedp ? u ## NAME ## _type_node \
4009                      : NAME ## _type_node;
4010
4011 #define GIMPLE_FIXED_TYPES_SAT(NAME) \
4012   if (type1 == sat_ ## short_ ## NAME ## _type_node \
4013       || type1 == sat_ ## unsigned_short_ ## NAME ## _type_node) \
4014     return unsignedp ? sat_ ## unsigned_short_ ## NAME ## _type_node \
4015                      : sat_ ## short_ ## NAME ## _type_node; \
4016   if (type1 == sat_ ## NAME ## _type_node \
4017       || type1 == sat_ ## unsigned_ ## NAME ## _type_node) \
4018     return unsignedp ? sat_ ## unsigned_ ## NAME ## _type_node \
4019                      : sat_ ## NAME ## _type_node; \
4020   if (type1 == sat_ ## long_ ## NAME ## _type_node \
4021       || type1 == sat_ ## unsigned_long_ ## NAME ## _type_node) \
4022     return unsignedp ? sat_ ## unsigned_long_ ## NAME ## _type_node \
4023                      : sat_ ## long_ ## NAME ## _type_node; \
4024   if (type1 == sat_ ## long_long_ ## NAME ## _type_node \
4025       || type1 == sat_ ## unsigned_long_long_ ## NAME ## _type_node) \
4026     return unsignedp ? sat_ ## unsigned_long_long_ ## NAME ## _type_node \
4027                      : sat_ ## long_long_ ## NAME ## _type_node;
4028
4029 #define GIMPLE_FIXED_MODE_TYPES_SAT(NAME)       \
4030   if (type1 == sat_ ## NAME ## _type_node \
4031       || type1 == sat_ ## u ## NAME ## _type_node) \
4032     return unsignedp ? sat_ ## u ## NAME ## _type_node \
4033                      : sat_ ## NAME ## _type_node;
4034
4035   GIMPLE_FIXED_TYPES (fract);
4036   GIMPLE_FIXED_TYPES_SAT (fract);
4037   GIMPLE_FIXED_TYPES (accum);
4038   GIMPLE_FIXED_TYPES_SAT (accum);
4039
4040   GIMPLE_FIXED_MODE_TYPES (qq);
4041   GIMPLE_FIXED_MODE_TYPES (hq);
4042   GIMPLE_FIXED_MODE_TYPES (sq);
4043   GIMPLE_FIXED_MODE_TYPES (dq);
4044   GIMPLE_FIXED_MODE_TYPES (tq);
4045   GIMPLE_FIXED_MODE_TYPES_SAT (qq);
4046   GIMPLE_FIXED_MODE_TYPES_SAT (hq);
4047   GIMPLE_FIXED_MODE_TYPES_SAT (sq);
4048   GIMPLE_FIXED_MODE_TYPES_SAT (dq);
4049   GIMPLE_FIXED_MODE_TYPES_SAT (tq);
4050   GIMPLE_FIXED_MODE_TYPES (ha);
4051   GIMPLE_FIXED_MODE_TYPES (sa);
4052   GIMPLE_FIXED_MODE_TYPES (da);
4053   GIMPLE_FIXED_MODE_TYPES (ta);
4054   GIMPLE_FIXED_MODE_TYPES_SAT (ha);
4055   GIMPLE_FIXED_MODE_TYPES_SAT (sa);
4056   GIMPLE_FIXED_MODE_TYPES_SAT (da);
4057   GIMPLE_FIXED_MODE_TYPES_SAT (ta);
4058
4059   /* For ENUMERAL_TYPEs in C++, must check the mode of the types, not
4060      the precision; they have precision set to match their range, but
4061      may use a wider mode to match an ABI.  If we change modes, we may
4062      wind up with bad conversions.  For INTEGER_TYPEs in C, must check
4063      the precision as well, so as to yield correct results for
4064      bit-field types.  C++ does not have these separate bit-field
4065      types, and producing a signed or unsigned variant of an
4066      ENUMERAL_TYPE may cause other problems as well.  */
4067   if (!INTEGRAL_TYPE_P (type)
4068       || TYPE_UNSIGNED (type) == unsignedp)
4069     return type;
4070
4071 #define TYPE_OK(node)                                                       \
4072   (TYPE_MODE (type) == TYPE_MODE (node)                                     \
4073    && TYPE_PRECISION (type) == TYPE_PRECISION (node))
4074   if (TYPE_OK (signed_char_type_node))
4075     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
4076   if (TYPE_OK (integer_type_node))
4077     return unsignedp ? unsigned_type_node : integer_type_node;
4078   if (TYPE_OK (short_integer_type_node))
4079     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
4080   if (TYPE_OK (long_integer_type_node))
4081     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
4082   if (TYPE_OK (long_long_integer_type_node))
4083     return (unsignedp
4084             ? long_long_unsigned_type_node
4085             : long_long_integer_type_node);
4086
4087 #if HOST_BITS_PER_WIDE_INT >= 64
4088   if (TYPE_OK (intTI_type_node))
4089     return unsignedp ? unsigned_intTI_type_node : intTI_type_node;
4090 #endif
4091   if (TYPE_OK (intDI_type_node))
4092     return unsignedp ? unsigned_intDI_type_node : intDI_type_node;
4093   if (TYPE_OK (intSI_type_node))
4094     return unsignedp ? unsigned_intSI_type_node : intSI_type_node;
4095   if (TYPE_OK (intHI_type_node))
4096     return unsignedp ? unsigned_intHI_type_node : intHI_type_node;
4097   if (TYPE_OK (intQI_type_node))
4098     return unsignedp ? unsigned_intQI_type_node : intQI_type_node;
4099
4100 #undef GIMPLE_FIXED_TYPES
4101 #undef GIMPLE_FIXED_MODE_TYPES
4102 #undef GIMPLE_FIXED_TYPES_SAT
4103 #undef GIMPLE_FIXED_MODE_TYPES_SAT
4104 #undef TYPE_OK
4105
4106   return build_nonstandard_integer_type (TYPE_PRECISION (type), unsignedp);
4107 }
4108
4109
4110 /* Return an unsigned type the same as TYPE in other respects.  */
4111
4112 tree
4113 gimple_unsigned_type (tree type)
4114 {
4115   return gimple_signed_or_unsigned_type (true, type);
4116 }
4117
4118
4119 /* Return a signed type the same as TYPE in other respects.  */
4120
4121 tree
4122 gimple_signed_type (tree type)
4123 {
4124   return gimple_signed_or_unsigned_type (false, type);
4125 }
4126
4127
4128 /* Return the typed-based alias set for T, which may be an expression
4129    or a type.  Return -1 if we don't do anything special.  */
4130
4131 alias_set_type
4132 gimple_get_alias_set (tree t)
4133 {
4134   tree u;
4135
4136   /* Permit type-punning when accessing a union, provided the access
4137      is directly through the union.  For example, this code does not
4138      permit taking the address of a union member and then storing
4139      through it.  Even the type-punning allowed here is a GCC
4140      extension, albeit a common and useful one; the C standard says
4141      that such accesses have implementation-defined behavior.  */
4142   for (u = t;
4143        TREE_CODE (u) == COMPONENT_REF || TREE_CODE (u) == ARRAY_REF;
4144        u = TREE_OPERAND (u, 0))
4145     if (TREE_CODE (u) == COMPONENT_REF
4146         && TREE_CODE (TREE_TYPE (TREE_OPERAND (u, 0))) == UNION_TYPE)
4147       return 0;
4148
4149   /* That's all the expressions we handle specially.  */
4150   if (!TYPE_P (t))
4151     return -1;
4152
4153   /* For convenience, follow the C standard when dealing with
4154      character types.  Any object may be accessed via an lvalue that
4155      has character type.  */
4156   if (t == char_type_node
4157       || t == signed_char_type_node
4158       || t == unsigned_char_type_node)
4159     return 0;
4160
4161   /* Allow aliasing between signed and unsigned variants of the same
4162      type.  We treat the signed variant as canonical.  */
4163   if (TREE_CODE (t) == INTEGER_TYPE && TYPE_UNSIGNED (t))
4164     {
4165       tree t1 = gimple_signed_type (t);
4166
4167       /* t1 == t can happen for boolean nodes which are always unsigned.  */
4168       if (t1 != t)
4169         return get_alias_set (t1);
4170     }
4171   else if (POINTER_TYPE_P (t))
4172     {
4173       /* From the common C and C++ langhook implementation:
4174
4175          Unfortunately, there is no canonical form of a pointer type.
4176          In particular, if we have `typedef int I', then `int *', and
4177          `I *' are different types.  So, we have to pick a canonical
4178          representative.  We do this below.
4179
4180          Technically, this approach is actually more conservative that
4181          it needs to be.  In particular, `const int *' and `int *'
4182          should be in different alias sets, according to the C and C++
4183          standard, since their types are not the same, and so,
4184          technically, an `int **' and `const int **' cannot point at
4185          the same thing.
4186
4187          But, the standard is wrong.  In particular, this code is
4188          legal C++:
4189
4190          int *ip;
4191          int **ipp = &ip;
4192          const int* const* cipp = ipp;
4193          And, it doesn't make sense for that to be legal unless you
4194          can dereference IPP and CIPP.  So, we ignore cv-qualifiers on
4195          the pointed-to types.  This issue has been reported to the
4196          C++ committee.  */
4197
4198       /* In addition to the above canonicalization issue with LTO
4199          we should also canonicalize `T (*)[]' to `T *' avoiding
4200          alias issues with pointer-to element types and pointer-to
4201          array types.
4202
4203          Likewise we need to deal with the situation of incomplete
4204          pointed-to types and make `*(struct X **)&a' and
4205          `*(struct X {} **)&a' alias.  Otherwise we will have to
4206          guarantee that all pointer-to incomplete type variants
4207          will be replaced by pointer-to complete type variants if
4208          they are available.
4209
4210          With LTO the convenient situation of using `void *' to
4211          access and store any pointer type will also become
4212          more apparent (and `void *' is just another pointer-to
4213          incomplete type).  Assigning alias-set zero to `void *'
4214          and all pointer-to incomplete types is a not appealing
4215          solution.  Assigning an effective alias-set zero only
4216          affecting pointers might be - by recording proper subset
4217          relationships of all pointer alias-sets.
4218
4219          Pointer-to function types are another grey area which
4220          needs caution.  Globbing them all into one alias-set
4221          or the above effective zero set would work.  */
4222
4223       /* For now just assign the same alias-set to all pointers.
4224          That's simple and avoids all the above problems.  */
4225       if (t != ptr_type_node)
4226         return get_alias_set (ptr_type_node);
4227     }
4228
4229   return -1;
4230 }
4231
4232
4233 /* Data structure used to count the number of dereferences to PTR
4234    inside an expression.  */
4235 struct count_ptr_d
4236 {
4237   tree ptr;
4238   unsigned num_stores;
4239   unsigned num_loads;
4240 };
4241
4242 /* Helper for count_uses_and_derefs.  Called by walk_tree to look for
4243    (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
4244
4245 static tree
4246 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
4247 {
4248   struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
4249   struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
4250
4251   /* Do not walk inside ADDR_EXPR nodes.  In the expression &ptr->fld,
4252      pointer 'ptr' is *not* dereferenced, it is simply used to compute
4253      the address of 'fld' as 'ptr + offsetof(fld)'.  */
4254   if (TREE_CODE (*tp) == ADDR_EXPR)
4255     {
4256       *walk_subtrees = 0;
4257       return NULL_TREE;
4258     }
4259
4260   if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
4261     {
4262       if (wi_p->is_lhs)
4263         count_p->num_stores++;
4264       else
4265         count_p->num_loads++;
4266     }
4267
4268   return NULL_TREE;
4269 }
4270
4271 /* Count the number of direct and indirect uses for pointer PTR in
4272    statement STMT.  The number of direct uses is stored in
4273    *NUM_USES_P.  Indirect references are counted separately depending
4274    on whether they are store or load operations.  The counts are
4275    stored in *NUM_STORES_P and *NUM_LOADS_P.  */
4276
4277 void
4278 count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
4279                        unsigned *num_loads_p, unsigned *num_stores_p)
4280 {
4281   ssa_op_iter i;
4282   tree use;
4283
4284   *num_uses_p = 0;
4285   *num_loads_p = 0;
4286   *num_stores_p = 0;
4287
4288   /* Find out the total number of uses of PTR in STMT.  */
4289   FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
4290     if (use == ptr)
4291       (*num_uses_p)++;
4292
4293   /* Now count the number of indirect references to PTR.  This is
4294      truly awful, but we don't have much choice.  There are no parent
4295      pointers inside INDIRECT_REFs, so an expression like
4296      '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
4297      find all the indirect and direct uses of x_1 inside.  The only
4298      shortcut we can take is the fact that GIMPLE only allows
4299      INDIRECT_REFs inside the expressions below.  */
4300   if (is_gimple_assign (stmt)
4301       || gimple_code (stmt) == GIMPLE_RETURN
4302       || gimple_code (stmt) == GIMPLE_ASM
4303       || is_gimple_call (stmt))
4304     {
4305       struct walk_stmt_info wi;
4306       struct count_ptr_d count;
4307
4308       count.ptr = ptr;
4309       count.num_stores = 0;
4310       count.num_loads = 0;
4311
4312       memset (&wi, 0, sizeof (wi));
4313       wi.info = &count;
4314       walk_gimple_op (stmt, count_ptr_derefs, &wi);
4315
4316       *num_stores_p = count.num_stores;
4317       *num_loads_p = count.num_loads;
4318     }
4319
4320   gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
4321 }
4322
4323 /* From a tree operand OP return the base of a load or store operation
4324    or NULL_TREE if OP is not a load or a store.  */
4325
4326 static tree
4327 get_base_loadstore (tree op)
4328 {
4329   while (handled_component_p (op))
4330     op = TREE_OPERAND (op, 0);
4331   if (DECL_P (op)
4332       || INDIRECT_REF_P (op)
4333       || TREE_CODE (op) == TARGET_MEM_REF)
4334     return op;
4335   return NULL_TREE;
4336 }
4337
4338 /* For the statement STMT call the callbacks VISIT_LOAD, VISIT_STORE and
4339    VISIT_ADDR if non-NULL on loads, store and address-taken operands
4340    passing the STMT, the base of the operand and DATA to it.  The base
4341    will be either a decl, an indirect reference (including TARGET_MEM_REF)
4342    or the argument of an address expression.
4343    Returns the results of these callbacks or'ed.  */
4344
4345 bool
4346 walk_stmt_load_store_addr_ops (gimple stmt, void *data,
4347                                bool (*visit_load)(gimple, tree, void *),
4348                                bool (*visit_store)(gimple, tree, void *),
4349                                bool (*visit_addr)(gimple, tree, void *))
4350 {
4351   bool ret = false;
4352   unsigned i;
4353   if (gimple_assign_single_p (stmt))
4354     {
4355       tree lhs, rhs;
4356       if (visit_store)
4357         {
4358           lhs = get_base_loadstore (gimple_assign_lhs (stmt));
4359           if (lhs)
4360             ret |= visit_store (stmt, lhs, data);
4361         }
4362       rhs = gimple_assign_rhs1 (stmt);
4363       while (handled_component_p (rhs))
4364         rhs = TREE_OPERAND (rhs, 0);
4365       if (visit_addr)
4366         {
4367           if (TREE_CODE (rhs) == ADDR_EXPR)
4368             ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
4369           else if (TREE_CODE (rhs) == TARGET_MEM_REF
4370                    && TMR_BASE (rhs) != NULL_TREE
4371                    && TREE_CODE (TMR_BASE (rhs)) == ADDR_EXPR)
4372             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (rhs), 0), data);
4373           else if (TREE_CODE (rhs) == OBJ_TYPE_REF
4374                    && TREE_CODE (OBJ_TYPE_REF_OBJECT (rhs)) == ADDR_EXPR)
4375             ret |= visit_addr (stmt, TREE_OPERAND (OBJ_TYPE_REF_OBJECT (rhs),
4376                                                    0), data);
4377           lhs = gimple_assign_lhs (stmt);
4378           if (TREE_CODE (lhs) == TARGET_MEM_REF
4379               && TMR_BASE (lhs) != NULL_TREE
4380               && TREE_CODE (TMR_BASE (lhs)) == ADDR_EXPR)
4381             ret |= visit_addr (stmt, TREE_OPERAND (TMR_BASE (lhs), 0), data);
4382         }
4383       if (visit_load)
4384         {
4385           rhs = get_base_loadstore (rhs);
4386           if (rhs)
4387             ret |= visit_load (stmt, rhs, data);
4388         }
4389     }
4390   else if (visit_addr
4391            && (is_gimple_assign (stmt)
4392                || gimple_code (stmt) == GIMPLE_COND))
4393     {
4394       for (i = 0; i < gimple_num_ops (stmt); ++i)
4395         if (gimple_op (stmt, i)
4396             && TREE_CODE (gimple_op (stmt, i)) == ADDR_EXPR)
4397           ret |= visit_addr (stmt, TREE_OPERAND (gimple_op (stmt, i), 0), data);
4398     }
4399   else if (is_gimple_call (stmt))
4400     {
4401       if (visit_store)
4402         {
4403           tree lhs = gimple_call_lhs (stmt);
4404           if (lhs)
4405             {
4406               lhs = get_base_loadstore (lhs);
4407               if (lhs)
4408                 ret |= visit_store (stmt, lhs, data);
4409             }
4410         }
4411       if (visit_load || visit_addr)
4412         for (i = 0; i < gimple_call_num_args (stmt); ++i)
4413           {
4414             tree rhs = gimple_call_arg (stmt, i);
4415             if (visit_addr
4416                 && TREE_CODE (rhs) == ADDR_EXPR)
4417               ret |= visit_addr (stmt, TREE_OPERAND (rhs, 0), data);
4418             else if (visit_load)
4419               {
4420                 rhs = get_base_loadstore (rhs);
4421                 if (rhs)
4422                   ret |= visit_load (stmt, rhs, data);
4423               }
4424           }
4425       if (visit_addr
4426           && gimple_call_chain (stmt)
4427           && TREE_CODE (gimple_call_chain (stmt)) == ADDR_EXPR)
4428         ret |= visit_addr (stmt, TREE_OPERAND (gimple_call_chain (stmt), 0),
4429                            data);
4430       if (visit_addr
4431           && gimple_call_return_slot_opt_p (stmt)
4432           && gimple_call_lhs (stmt) != NULL_TREE
4433           && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt))))
4434         ret |= visit_addr (stmt, gimple_call_lhs (stmt), data);
4435     }
4436   else if (gimple_code (stmt) == GIMPLE_ASM)
4437     {
4438       unsigned noutputs;
4439       const char *constraint;
4440       const char **oconstraints;
4441       bool allows_mem, allows_reg, is_inout;
4442       noutputs = gimple_asm_noutputs (stmt);
4443       oconstraints = XALLOCAVEC (const char *, noutputs);
4444       if (visit_store || visit_addr)
4445         for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
4446           {
4447             tree link = gimple_asm_output_op (stmt, i);
4448             tree op = get_base_loadstore (TREE_VALUE (link));
4449             if (op && visit_store)
4450               ret |= visit_store (stmt, op, data);
4451             if (visit_addr)
4452               {
4453                 constraint = TREE_STRING_POINTER
4454                     (TREE_VALUE (TREE_PURPOSE (link)));
4455                 oconstraints[i] = constraint;
4456                 parse_output_constraint (&constraint, i, 0, 0, &allows_mem,
4457                                          &allows_reg, &is_inout);
4458                 if (op && !allows_reg && allows_mem)
4459                   ret |= visit_addr (stmt, op, data);
4460               }
4461           }
4462       if (visit_load || visit_addr)
4463         for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
4464           {
4465             tree link = gimple_asm_input_op (stmt, i);
4466             tree op = TREE_VALUE (link);
4467             if (visit_addr
4468                 && TREE_CODE (op) == ADDR_EXPR)
4469               ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4470             else if (visit_load || visit_addr)
4471               {
4472                 op = get_base_loadstore (op);
4473                 if (op)
4474                   {
4475                     if (visit_load)
4476                       ret |= visit_load (stmt, op, data);
4477                     if (visit_addr)
4478                       {
4479                         constraint = TREE_STRING_POINTER
4480                             (TREE_VALUE (TREE_PURPOSE (link)));
4481                         parse_input_constraint (&constraint, 0, 0, noutputs,
4482                                                 0, oconstraints,
4483                                                 &allows_mem, &allows_reg);
4484                         if (!allows_reg && allows_mem)
4485                           ret |= visit_addr (stmt, op, data);
4486                       }
4487                   }
4488               }
4489           }
4490     }
4491   else if (gimple_code (stmt) == GIMPLE_RETURN)
4492     {
4493       tree op = gimple_return_retval (stmt);
4494       if (op)
4495         {
4496           if (visit_addr
4497               && TREE_CODE (op) == ADDR_EXPR)
4498             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4499           else if (visit_load)
4500             {
4501               op = get_base_loadstore (op);
4502               if (op)
4503                 ret |= visit_load (stmt, op, data);
4504             }
4505         }
4506     }
4507   else if (visit_addr
4508            && gimple_code (stmt) == GIMPLE_PHI)
4509     {
4510       for (i = 0; i < gimple_phi_num_args (stmt); ++i)
4511         {
4512           tree op = PHI_ARG_DEF (stmt, i);
4513           if (TREE_CODE (op) == ADDR_EXPR)
4514             ret |= visit_addr (stmt, TREE_OPERAND (op, 0), data);
4515         }
4516     }
4517
4518   return ret;
4519 }
4520
4521 /* Like walk_stmt_load_store_addr_ops but with NULL visit_addr.  IPA-CP
4522    should make a faster clone for this case.  */
4523
4524 bool
4525 walk_stmt_load_store_ops (gimple stmt, void *data,
4526                           bool (*visit_load)(gimple, tree, void *),
4527                           bool (*visit_store)(gimple, tree, void *))
4528 {
4529   return walk_stmt_load_store_addr_ops (stmt, data,
4530                                         visit_load, visit_store, NULL);
4531 }
4532
4533 /* Helper for gimple_ior_addresses_taken_1.  */
4534
4535 static bool
4536 gimple_ior_addresses_taken_1 (gimple stmt ATTRIBUTE_UNUSED,
4537                               tree addr, void *data)
4538 {
4539   bitmap addresses_taken = (bitmap)data;
4540   while (handled_component_p (addr))
4541     addr = TREE_OPERAND (addr, 0);
4542   if (DECL_P (addr))
4543     {
4544       bitmap_set_bit (addresses_taken, DECL_UID (addr));
4545       return true;
4546     }
4547   return false;
4548 }
4549
4550 /* Set the bit for the uid of all decls that have their address taken
4551    in STMT in the ADDRESSES_TAKEN bitmap.  Returns true if there
4552    were any in this stmt.  */
4553
4554 bool
4555 gimple_ior_addresses_taken (bitmap addresses_taken, gimple stmt)
4556 {
4557   return walk_stmt_load_store_addr_ops (stmt, addresses_taken, NULL, NULL,
4558                                         gimple_ior_addresses_taken_1);
4559 }
4560
4561
4562 /* Return a printable name for symbol DECL.  */
4563
4564 const char *
4565 gimple_decl_printable_name (tree decl, int verbosity)
4566 {
4567   gcc_assert (decl && DECL_NAME (decl));
4568
4569   if (DECL_ASSEMBLER_NAME_SET_P (decl))
4570     {
4571       const char *str, *mangled_str;
4572       int dmgl_opts = DMGL_NO_OPTS;
4573
4574       if (verbosity >= 2)
4575         {
4576           dmgl_opts = DMGL_VERBOSE
4577                       | DMGL_ANSI
4578                       | DMGL_GNU_V3
4579                       | DMGL_RET_POSTFIX;
4580           if (TREE_CODE (decl) == FUNCTION_DECL)
4581             dmgl_opts |= DMGL_PARAMS;
4582         }
4583
4584       mangled_str = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
4585       str = cplus_demangle_v3 (mangled_str, dmgl_opts);
4586       return (str) ? str : mangled_str;
4587     }
4588
4589   return IDENTIFIER_POINTER (DECL_NAME (decl));
4590 }
4591
4592
4593 /* Fold a OBJ_TYPE_REF expression to the address of a function.
4594    KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF).  Adapted
4595    from cp_fold_obj_type_ref, but it tolerates types with no binfo
4596    data.  */
4597
4598 tree
4599 gimple_fold_obj_type_ref (tree ref, tree known_type)
4600 {
4601   HOST_WIDE_INT index;
4602   HOST_WIDE_INT i;
4603   tree v;
4604   tree fndecl;
4605
4606   if (TYPE_BINFO (known_type) == NULL_TREE)
4607     return NULL_TREE;
4608
4609   v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
4610   index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
4611   i = 0;
4612   while (i != index)
4613     {
4614       i += (TARGET_VTABLE_USES_DESCRIPTORS
4615             ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
4616       v = TREE_CHAIN (v);
4617     }
4618
4619   fndecl = TREE_VALUE (v);
4620
4621 #ifdef ENABLE_CHECKING
4622   gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
4623                                   DECL_VINDEX (fndecl)));
4624 #endif
4625
4626   cgraph_node (fndecl)->local.vtable_method = true;
4627
4628   return build_fold_addr_expr (fndecl);
4629 }
4630
4631 #include "gt-gimple.h"