gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   3    2010, 2011, 2012  Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License 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 "tree.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "flags.h"
  30 #include "function.h"
  31 #include "ggc.h"
  32 #include "langhooks.h"
  33 #include "tree-pretty-print.h"
  34 #include "gimple-pretty-print.h"
  35 #include "tree-flow.h"
  36 #include "timevar.h"
  37 #include "tree-dump.h"
  38 #include "tree-pass.h"
  39 #include "diagnostic-core.h"
  40 #include "except.h"
  41 #include "cfgloop.h"
  42 #include "tree-ssa-propagate.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "tree-inline.h"
  46
  47 /* This file contains functions for building the Control Flow Graph (CFG)
  48    for a function tree.  */
  49
  50 /* Local declarations.  */
  51
  52 /* Initial capacity for the basic block array.  */
  53 static const int initial_cfg_capacity = 20;
  54
  55 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  56    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  57    via their CASE_CHAIN field, which we clear after we're done with the
  58    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
  59
  60    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  61    update the case vector in response to edge redirections.
  62
  63    Right now this table is set up and torn down at key points in the
  64    compilation process.  It would be nice if we could make the table
  65    more persistent.  The key is getting notification of changes to
  66    the CFG (particularly edge removal, creation and redirection).  */
  67
  68 static struct pointer_map_t *edge_to_cases;
  69
  70 /* If we record edge_to_cases, this bitmap will hold indexes
  71    of basic blocks that end in a GIMPLE_SWITCH which we touched
  72    due to edge manipulations.  */
  73
  74 static bitmap touched_switch_bbs;
  75
  76 /* CFG statistics.  */
  77 struct cfg_stats_d
  78 {
  79   long num_merged_labels;
  80 };
  81
  82 static struct cfg_stats_d cfg_stats;
  83
  84 /* Nonzero if we found a computed goto while building basic blocks.  */
  85 static bool found_computed_goto;
  86
  87 /* Hash table to store last discriminator assigned for each locus.  */
  88 struct locus_discrim_map
  89 {
  90   location_t locus;
  91   int discriminator;
  92 };
  93 static htab_t discriminator_per_locus;
  94
  95 /* Basic blocks and flowgraphs.  */
  96 static void make_blocks (gimple_seq);
  97 static void factor_computed_gotos (void);
  98
  99 /* Edges.  */
 100 static void make_edges (void);
 101 static void make_cond_expr_edges (basic_block);
 102 static void make_gimple_switch_edges (basic_block);
 103 static void make_goto_expr_edges (basic_block);
 104 static void make_gimple_asm_edges (basic_block);
 105 static unsigned int locus_map_hash (const void *);
 106 static int locus_map_eq (const void *, const void *);
 107 static void assign_discriminator (location_t, basic_block);
 108 static edge gimple_redirect_edge_and_branch (edge, basic_block);
 109 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
 110 static unsigned int split_critical_edges (void);
 111
 112 /* Various helpers.  */
 113 static inline bool stmt_starts_bb_p (gimple, gimple);
 114 static int gimple_verify_flow_info (void);
 115 static void gimple_make_forwarder_block (edge);
 116 static void gimple_cfg2vcg (FILE *);
 117 static gimple first_non_label_stmt (basic_block);
 118 static bool verify_gimple_transaction (gimple);
 119
 120 /* Flowgraph optimization and cleanup.  */
 121 static void gimple_merge_blocks (basic_block, basic_block);
 122 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 123 static void remove_bb (basic_block);
 124 static edge find_taken_edge_computed_goto (basic_block, tree);
 125 static edge find_taken_edge_cond_expr (basic_block, tree);
 126 static edge find_taken_edge_switch_expr (basic_block, tree);
 127 static tree find_case_label_for_value (gimple, tree);
 128
 129 void
 130 init_empty_tree_cfg_for_function (struct function *fn)
 131 {
 132   /* Initialize the basic block array.  */
 133   init_flow (fn);
 134   profile_status_for_function (fn) = PROFILE_ABSENT;
 135   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
 136   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
 137   basic_block_info_for_function (fn)
 138     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 139   VEC_safe_grow_cleared (basic_block, gc,
 140                          basic_block_info_for_function (fn),
 141                          initial_cfg_capacity);
 142
 143   /* Build a mapping of labels to their associated blocks.  */
 144   label_to_block_map_for_function (fn)
 145     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 146   VEC_safe_grow_cleared (basic_block, gc,
 147                          label_to_block_map_for_function (fn),
 148                          initial_cfg_capacity);
 149
 150   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
 151                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
 152   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
 153                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
 154
 155   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
 156     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
 157   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
 158     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
 159 }
 160
 161 void
 162 init_empty_tree_cfg (void)
 163 {
 164   init_empty_tree_cfg_for_function (cfun);
 165 }
 166
 167 /*---------------------------------------------------------------------------
 168                               Create basic blocks
 169 ---------------------------------------------------------------------------*/
 170
 171 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
 172    statements to be added to the flowgraph.  */
 173
 174 static void
 175 build_gimple_cfg (gimple_seq seq)
 176 {
 177   /* Register specific gimple functions.  */
 178   gimple_register_cfg_hooks ();
 179
 180   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 181
 182   init_empty_tree_cfg ();
 183
 184   found_computed_goto = 0;
 185   make_blocks (seq);
 186
 187   /* Computed gotos are hell to deal with, especially if there are
 188      lots of them with a large number of destinations.  So we factor
 189      them to a common computed goto location before we build the
 190      edge list.  After we convert back to normal form, we will un-factor
 191      the computed gotos since factoring introduces an unwanted jump.  */
 192   if (found_computed_goto)
 193     factor_computed_gotos ();
 194
 195   /* Make sure there is always at least one block, even if it's empty.  */
 196   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 197     create_empty_bb (ENTRY_BLOCK_PTR);
 198
 199   /* Adjust the size of the array.  */
 200   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 201     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
 202
 203   /* To speed up statement iterator walks, we first purge dead labels.  */
 204   cleanup_dead_labels ();
 205
 206   /* Group case nodes to reduce the number of edges.
 207      We do this after cleaning up dead labels because otherwise we miss
 208      a lot of obvious case merging opportunities.  */
 209   group_case_labels ();
 210
 211   /* Create the edges of the flowgraph.  */
 212   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
 213                                          free);
 214   make_edges ();
 215   cleanup_dead_labels ();
 216   htab_delete (discriminator_per_locus);
 217
 218   /* Debugging dumps.  */
 219
 220   /* Write the flowgraph to a VCG file.  */
 221   {
 222     int local_dump_flags;
 223     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 224     if (vcg_file)
 225       {
 226         gimple_cfg2vcg (vcg_file);
 227         dump_end (TDI_vcg, vcg_file);
 228       }
 229   }
 230 }
 231
 232 static unsigned int
 233 execute_build_cfg (void)
 234 {
 235   gimple_seq body = gimple_body (current_function_decl);
 236
 237   build_gimple_cfg (body);
 238   gimple_set_body (current_function_decl, NULL);
 239   if (dump_file && (dump_flags & TDF_DETAILS))
 240     {
 241       fprintf (dump_file, "Scope blocks:\n");
 242       dump_scope_blocks (dump_file, dump_flags);
 243     }
 244   return 0;
 245 }
 246
 247 struct gimple_opt_pass pass_build_cfg =
 248 {
 249  {
 250   GIMPLE_PASS,
 251   "cfg",                                /* name */
 252   NULL,                                 /* gate */
 253   execute_build_cfg,                    /* execute */
 254   NULL,                                 /* sub */
 255   NULL,                                 /* next */
 256   0,                                    /* static_pass_number */
 257   TV_TREE_CFG,                          /* tv_id */
 258   PROP_gimple_leh,                      /* properties_required */
 259   PROP_cfg,                             /* properties_provided */
 260   0,                                    /* properties_destroyed */
 261   0,                                    /* todo_flags_start */
 262   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
 263  }
 264 };
 265
 266
 267 /* Return true if T is a computed goto.  */
 268
 269 static bool
 270 computed_goto_p (gimple t)
 271 {
 272   return (gimple_code (t) == GIMPLE_GOTO
 273           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 274 }
 275
 276
 277 /* Search the CFG for any computed gotos.  If found, factor them to a
 278    common computed goto site.  Also record the location of that site so
 279    that we can un-factor the gotos after we have converted back to
 280    normal form.  */
 281
 282 static void
 283 factor_computed_gotos (void)
 284 {
 285   basic_block bb;
 286   tree factored_label_decl = NULL;
 287   tree var = NULL;
 288   gimple factored_computed_goto_label = NULL;
 289   gimple factored_computed_goto = NULL;
 290
 291   /* We know there are one or more computed gotos in this function.
 292      Examine the last statement in each basic block to see if the block
 293      ends with a computed goto.  */
 294
 295   FOR_EACH_BB (bb)
 296     {
 297       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 298       gimple last;
 299
 300       if (gsi_end_p (gsi))
 301         continue;
 302
 303       last = gsi_stmt (gsi);
 304
 305       /* Ignore the computed goto we create when we factor the original
 306          computed gotos.  */
 307       if (last == factored_computed_goto)
 308         continue;
 309
 310       /* If the last statement is a computed goto, factor it.  */
 311       if (computed_goto_p (last))
 312         {
 313           gimple assignment;
 314
 315           /* The first time we find a computed goto we need to create
 316              the factored goto block and the variable each original
 317              computed goto will use for their goto destination.  */
 318           if (!factored_computed_goto)
 319             {
 320               basic_block new_bb = create_empty_bb (bb);
 321               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
 322
 323               /* Create the destination of the factored goto.  Each original
 324                  computed goto will put its desired destination into this
 325                  variable and jump to the label we create immediately
 326                  below.  */
 327               var = create_tmp_var (ptr_type_node, "gotovar");
 328
 329               /* Build a label for the new block which will contain the
 330                  factored computed goto.  */
 331               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
 332               factored_computed_goto_label
 333                 = gimple_build_label (factored_label_decl);
 334               gsi_insert_after (&new_gsi, factored_computed_goto_label,
 335                                 GSI_NEW_STMT);
 336
 337               /* Build our new computed goto.  */
 338               factored_computed_goto = gimple_build_goto (var);
 339               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
 340             }
 341
 342           /* Copy the original computed goto's destination into VAR.  */
 343           assignment = gimple_build_assign (var, gimple_goto_dest (last));
 344           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
 345
 346           /* And re-vector the computed goto to the new destination.  */
 347           gimple_goto_set_dest (last, factored_label_decl);
 348         }
 349     }
 350 }
 351
 352
 353 /* Build a flowgraph for the sequence of stmts SEQ.  */
 354
 355 static void
 356 make_blocks (gimple_seq seq)
 357 {
 358   gimple_stmt_iterator i = gsi_start (seq);
 359   gimple stmt = NULL;
 360   bool start_new_block = true;
 361   bool first_stmt_of_seq = true;
 362   basic_block bb = ENTRY_BLOCK_PTR;
 363
 364   while (!gsi_end_p (i))
 365     {
 366       gimple prev_stmt;
 367
 368       prev_stmt = stmt;
 369       stmt = gsi_stmt (i);
 370
 371       /* If the statement starts a new basic block or if we have determined
 372          in a previous pass that we need to create a new block for STMT, do
 373          so now.  */
 374       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 375         {
 376           if (!first_stmt_of_seq)
 377             gsi_split_seq_before (&i, &seq);
 378           bb = create_basic_block (seq, NULL, bb);
 379           start_new_block = false;
 380         }
 381
 382       /* Now add STMT to BB and create the subgraphs for special statement
 383          codes.  */
 384       gimple_set_bb (stmt, bb);
 385
 386       if (computed_goto_p (stmt))
 387         found_computed_goto = true;
 388
 389       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 390          next iteration.  */
 391       if (stmt_ends_bb_p (stmt))
 392         {
 393           /* If the stmt can make abnormal goto use a new temporary
 394              for the assignment to the LHS.  This makes sure the old value
 395              of the LHS is available on the abnormal edge.  Otherwise
 396              we will end up with overlapping life-ranges for abnormal
 397              SSA names.  */
 398           if (gimple_has_lhs (stmt)
 399               && stmt_can_make_abnormal_goto (stmt)
 400               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
 401             {
 402               tree lhs = gimple_get_lhs (stmt);
 403               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
 404               gimple s = gimple_build_assign (lhs, tmp);
 405               gimple_set_location (s, gimple_location (stmt));
 406               gimple_set_block (s, gimple_block (stmt));
 407               gimple_set_lhs (stmt, tmp);
 408               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
 409                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
 410                 DECL_GIMPLE_REG_P (tmp) = 1;
 411               gsi_insert_after (&i, s, GSI_SAME_STMT);
 412             }
 413           start_new_block = true;
 414         }
 415
 416       gsi_next (&i);
 417       first_stmt_of_seq = false;
 418     }
 419 }
 420
 421
 422 /* Create and return a new empty basic block after bb AFTER.  */
 423
 424 static basic_block
 425 create_bb (void *h, void *e, basic_block after)
 426 {
 427   basic_block bb;
 428
 429   gcc_assert (!e);
 430
 431   /* Create and initialize a new basic block.  Since alloc_block uses
 432      GC allocation that clears memory to allocate a basic block, we do
 433      not have to clear the newly allocated basic block here.  */
 434   bb = alloc_block ();
 435
 436   bb->index = last_basic_block;
 437   bb->flags = BB_NEW;
 438   set_bb_seq (bb, h ? (gimple_seq) h : NULL);
 439
 440   /* Add the new block to the linked list of blocks.  */
 441   link_block (bb, after);
 442
 443   /* Grow the basic block array if needed.  */
 444   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 445     {
 446       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 447       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
 448     }
 449
 450   /* Add the newly created block to the array.  */
 451   SET_BASIC_BLOCK (last_basic_block, bb);
 452
 453   n_basic_blocks++;
 454   last_basic_block++;
 455
 456   return bb;
 457 }
 458
 459
 460 /*---------------------------------------------------------------------------
 461                                  Edge creation
 462 ---------------------------------------------------------------------------*/
 463
 464 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 465
 466 void
 467 fold_cond_expr_cond (void)
 468 {
 469   basic_block bb;
 470
 471   FOR_EACH_BB (bb)
 472     {
 473       gimple stmt = last_stmt (bb);
 474
 475       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 476         {
 477           location_t loc = gimple_location (stmt);
 478           tree cond;
 479           bool zerop, onep;
 480
 481           fold_defer_overflow_warnings ();
 482           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 483                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 484           if (cond)
 485             {
 486               zerop = integer_zerop (cond);
 487               onep = integer_onep (cond);
 488             }
 489           else
 490             zerop = onep = false;
 491
 492           fold_undefer_overflow_warnings (zerop || onep,
 493                                           stmt,
 494                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
 495           if (zerop)
 496             gimple_cond_make_false (stmt);
 497           else if (onep)
 498             gimple_cond_make_true (stmt);
 499         }
 500     }
 501 }
 502
 503 /* Join all the blocks in the flowgraph.  */
 504
 505 static void
 506 make_edges (void)
 507 {
 508   basic_block bb;
 509   struct omp_region *cur_region = NULL;
 510
 511   /* Create an edge from entry to the first block with executable
 512      statements in it.  */
 513   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 514
 515   /* Traverse the basic block array placing edges.  */
 516   FOR_EACH_BB (bb)
 517     {
 518       gimple last = last_stmt (bb);
 519       bool fallthru;
 520
 521       if (last)
 522         {
 523           enum gimple_code code = gimple_code (last);
 524           switch (code)
 525             {
 526             case GIMPLE_GOTO:
 527               make_goto_expr_edges (bb);
 528               fallthru = false;
 529               break;
 530             case GIMPLE_RETURN:
 531               make_edge (bb, EXIT_BLOCK_PTR, 0);
 532               fallthru = false;
 533               break;
 534             case GIMPLE_COND:
 535               make_cond_expr_edges (bb);
 536               fallthru = false;
 537               break;
 538             case GIMPLE_SWITCH:
 539               make_gimple_switch_edges (bb);
 540               fallthru = false;
 541               break;
 542             case GIMPLE_RESX:
 543               make_eh_edges (last);
 544               fallthru = false;
 545               break;
 546             case GIMPLE_EH_DISPATCH:
 547               fallthru = make_eh_dispatch_edges (last);
 548               break;
 549
 550             case GIMPLE_CALL:
 551               /* If this function receives a nonlocal goto, then we need to
 552                  make edges from this call site to all the nonlocal goto
 553                  handlers.  */
 554               if (stmt_can_make_abnormal_goto (last))
 555                 make_abnormal_goto_edges (bb, true);
 556
 557               /* If this statement has reachable exception handlers, then
 558                  create abnormal edges to them.  */
 559               make_eh_edges (last);
 560
 561               /* BUILTIN_RETURN is really a return statement.  */
 562               if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
 563                 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
 564               /* Some calls are known not to return.  */
 565               else
 566                 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
 567               break;
 568
 569             case GIMPLE_ASSIGN:
 570                /* A GIMPLE_ASSIGN may throw internally and thus be considered
 571                   control-altering. */
 572               if (is_ctrl_altering_stmt (last))
 573                 make_eh_edges (last);
 574               fallthru = true;
 575               break;
 576
 577             case GIMPLE_ASM:
 578               make_gimple_asm_edges (bb);
 579               fallthru = true;
 580               break;
 581
 582             case GIMPLE_OMP_PARALLEL:
 583             case GIMPLE_OMP_TASK:
 584             case GIMPLE_OMP_FOR:
 585             case GIMPLE_OMP_SINGLE:
 586             case GIMPLE_OMP_MASTER:
 587             case GIMPLE_OMP_ORDERED:
 588             case GIMPLE_OMP_CRITICAL:
 589             case GIMPLE_OMP_SECTION:
 590               cur_region = new_omp_region (bb, code, cur_region);
 591               fallthru = true;
 592               break;
 593
 594             case GIMPLE_OMP_SECTIONS:
 595               cur_region = new_omp_region (bb, code, cur_region);
 596               fallthru = true;
 597               break;
 598
 599             case GIMPLE_OMP_SECTIONS_SWITCH:
 600               fallthru = false;
 601               break;
 602
 603             case GIMPLE_OMP_ATOMIC_LOAD:
 604             case GIMPLE_OMP_ATOMIC_STORE:
 605                fallthru = true;
 606                break;
 607
 608             case GIMPLE_OMP_RETURN:
 609               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
 610                  somewhere other than the next block.  This will be
 611                  created later.  */
 612               cur_region->exit = bb;
 613               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
 614               cur_region = cur_region->outer;
 615               break;
 616
 617             case GIMPLE_OMP_CONTINUE:
 618               cur_region->cont = bb;
 619               switch (cur_region->type)
 620                 {
 621                 case GIMPLE_OMP_FOR:
 622                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
 623                      succs edges as abnormal to prevent splitting
 624                      them.  */
 625                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
 626                   /* Make the loopback edge.  */
 627                   make_edge (bb, single_succ (cur_region->entry),
 628                              EDGE_ABNORMAL);
 629
 630                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
 631                      corresponds to the case that the body of the loop
 632                      is not executed at all.  */
 633                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
 634                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
 635                   fallthru = false;
 636                   break;
 637
 638                 case GIMPLE_OMP_SECTIONS:
 639                   /* Wire up the edges into and out of the nested sections.  */
 640                   {
 641                     basic_block switch_bb = single_succ (cur_region->entry);
 642
 643                     struct omp_region *i;
 644                     for (i = cur_region->inner; i ; i = i->next)
 645                       {
 646                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
 647                         make_edge (switch_bb, i->entry, 0);
 648                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 649                       }
 650
 651                     /* Make the loopback edge to the block with
 652                        GIMPLE_OMP_SECTIONS_SWITCH.  */
 653                     make_edge (bb, switch_bb, 0);
 654
 655                     /* Make the edge from the switch to exit.  */
 656                     make_edge (switch_bb, bb->next_bb, 0);
 657                     fallthru = false;
 658                   }
 659                   break;
 660
 661                 default:
 662                   gcc_unreachable ();
 663                 }
 664               break;
 665
 666             case GIMPLE_TRANSACTION:
 667               {
 668                 tree abort_label = gimple_transaction_label (last);
 669                 if (abort_label)
 670                   make_edge (bb, label_to_block (abort_label), 0);
 671                 fallthru = true;
 672               }
 673               break;
 674
 675             default:
 676               gcc_assert (!stmt_ends_bb_p (last));
 677               fallthru = true;
 678             }
 679         }
 680       else
 681         fallthru = true;
 682
 683       if (fallthru)
 684         {
 685           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 686           if (last)
 687             assign_discriminator (gimple_location (last), bb->next_bb);
 688         }
 689     }
 690
 691   if (root_omp_region)
 692     free_omp_regions ();
 693
 694   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 695   fold_cond_expr_cond ();
 696 }
 697
 698 /* Trivial hash function for a location_t.  ITEM is a pointer to
 699    a hash table entry that maps a location_t to a discriminator.  */
 700
 701 static unsigned int
 702 locus_map_hash (const void *item)
 703 {
 704   return ((const struct locus_discrim_map *) item)->locus;
 705 }
 706
 707 /* Equality function for the locus-to-discriminator map.  VA and VB
 708    point to the two hash table entries to compare.  */
 709
 710 static int
 711 locus_map_eq (const void *va, const void *vb)
 712 {
 713   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
 714   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
 715   return a->locus == b->locus;
 716 }
 717
 718 /* Find the next available discriminator value for LOCUS.  The
 719    discriminator distinguishes among several basic blocks that
 720    share a common locus, allowing for more accurate sample-based
 721    profiling.  */
 722
 723 static int
 724 next_discriminator_for_locus (location_t locus)
 725 {
 726   struct locus_discrim_map item;
 727   struct locus_discrim_map **slot;
 728
 729   item.locus = locus;
 730   item.discriminator = 0;
 731   slot = (struct locus_discrim_map **)
 732       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
 733                                 (hashval_t) locus, INSERT);
 734   gcc_assert (slot);
 735   if (*slot == HTAB_EMPTY_ENTRY)
 736     {
 737       *slot = XNEW (struct locus_discrim_map);
 738       gcc_assert (*slot);
 739       (*slot)->locus = locus;
 740       (*slot)->discriminator = 0;
 741     }
 742   (*slot)->discriminator++;
 743   return (*slot)->discriminator;
 744 }
 745
 746 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
 747
 748 static bool
 749 same_line_p (location_t locus1, location_t locus2)
 750 {
 751   expanded_location from, to;
 752
 753   if (locus1 == locus2)
 754     return true;
 755
 756   from = expand_location (locus1);
 757   to = expand_location (locus2);
 758
 759   if (from.line != to.line)
 760     return false;
 761   if (from.file == to.file)
 762     return true;
 763   return (from.file != NULL
 764           && to.file != NULL
 765           && filename_cmp (from.file, to.file) == 0);
 766 }
 767
 768 /* Assign a unique discriminator value to block BB if it begins at the same
 769    LOCUS as its predecessor block.  */
 770
 771 static void
 772 assign_discriminator (location_t locus, basic_block bb)
 773 {
 774   gimple first_in_to_bb, last_in_to_bb;
 775
 776   if (locus == 0 || bb->discriminator != 0)
 777     return;
 778
 779   first_in_to_bb = first_non_label_stmt (bb);
 780   last_in_to_bb = last_stmt (bb);
 781   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
 782       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
 783     bb->discriminator = next_discriminator_for_locus (locus);
 784 }
 785
 786 /* Create the edges for a GIMPLE_COND starting at block BB.  */
 787
 788 static void
 789 make_cond_expr_edges (basic_block bb)
 790 {
 791   gimple entry = last_stmt (bb);
 792   gimple then_stmt, else_stmt;
 793   basic_block then_bb, else_bb;
 794   tree then_label, else_label;
 795   edge e;
 796   location_t entry_locus;
 797
 798   gcc_assert (entry);
 799   gcc_assert (gimple_code (entry) == GIMPLE_COND);
 800
 801   entry_locus = gimple_location (entry);
 802
 803   /* Entry basic blocks for each component.  */
 804   then_label = gimple_cond_true_label (entry);
 805   else_label = gimple_cond_false_label (entry);
 806   then_bb = label_to_block (then_label);
 807   else_bb = label_to_block (else_label);
 808   then_stmt = first_stmt (then_bb);
 809   else_stmt = first_stmt (else_bb);
 810
 811   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 812   assign_discriminator (entry_locus, then_bb);
 813   e->goto_locus = gimple_location (then_stmt);
 814   if (e->goto_locus)
 815     e->goto_block = gimple_block (then_stmt);
 816   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 817   if (e)
 818     {
 819       assign_discriminator (entry_locus, else_bb);
 820       e->goto_locus = gimple_location (else_stmt);
 821       if (e->goto_locus)
 822         e->goto_block = gimple_block (else_stmt);
 823     }
 824
 825   /* We do not need the labels anymore.  */
 826   gimple_cond_set_true_label (entry, NULL_TREE);
 827   gimple_cond_set_false_label (entry, NULL_TREE);
 828 }
 829
 830
 831 /* Called for each element in the hash table (P) as we delete the
 832    edge to cases hash table.
 833
 834    Clear all the TREE_CHAINs to prevent problems with copying of
 835    SWITCH_EXPRs and structure sharing rules, then free the hash table
 836    element.  */
 837
 838 static bool
 839 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
 840                        void *data ATTRIBUTE_UNUSED)
 841 {
 842   tree t, next;
 843
 844   for (t = (tree) *value; t; t = next)
 845     {
 846       next = CASE_CHAIN (t);
 847       CASE_CHAIN (t) = NULL;
 848     }
 849
 850   *value = NULL;
 851   return true;
 852 }
 853
 854 /* Start recording information mapping edges to case labels.  */
 855
 856 void
 857 start_recording_case_labels (void)
 858 {
 859   gcc_assert (edge_to_cases == NULL);
 860   edge_to_cases = pointer_map_create ();
 861   touched_switch_bbs = BITMAP_ALLOC (NULL);
 862 }
 863
 864 /* Return nonzero if we are recording information for case labels.  */
 865
 866 static bool
 867 recording_case_labels_p (void)
 868 {
 869   return (edge_to_cases != NULL);
 870 }
 871
 872 /* Stop recording information mapping edges to case labels and
 873    remove any information we have recorded.  */
 874 void
 875 end_recording_case_labels (void)
 876 {
 877   bitmap_iterator bi;
 878   unsigned i;
 879   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
 880   pointer_map_destroy (edge_to_cases);
 881   edge_to_cases = NULL;
 882   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
 883     {
 884       basic_block bb = BASIC_BLOCK (i);
 885       if (bb)
 886         {
 887           gimple stmt = last_stmt (bb);
 888           if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 889             group_case_labels_stmt (stmt);
 890         }
 891     }
 892   BITMAP_FREE (touched_switch_bbs);
 893 }
 894
 895 /* If we are inside a {start,end}_recording_cases block, then return
 896    a chain of CASE_LABEL_EXPRs from T which reference E.
 897
 898    Otherwise return NULL.  */
 899
 900 static tree
 901 get_cases_for_edge (edge e, gimple t)
 902 {
 903   void **slot;
 904   size_t i, n;
 905
 906   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 907      chains available.  Return NULL so the caller can detect this case.  */
 908   if (!recording_case_labels_p ())
 909     return NULL;
 910
 911   slot = pointer_map_contains (edge_to_cases, e);
 912   if (slot)
 913     return (tree) *slot;
 914
 915   /* If we did not find E in the hash table, then this must be the first
 916      time we have been queried for information about E & T.  Add all the
 917      elements from T to the hash table then perform the query again.  */
 918
 919   n = gimple_switch_num_labels (t);
 920   for (i = 0; i < n; i++)
 921     {
 922       tree elt = gimple_switch_label (t, i);
 923       tree lab = CASE_LABEL (elt);
 924       basic_block label_bb = label_to_block (lab);
 925       edge this_edge = find_edge (e->src, label_bb);
 926
 927       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
 928          a new chain.  */
 929       slot = pointer_map_insert (edge_to_cases, this_edge);
 930       CASE_CHAIN (elt) = (tree) *slot;
 931       *slot = elt;
 932     }
 933
 934   return (tree) *pointer_map_contains (edge_to_cases, e);
 935 }
 936
 937 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
 938
 939 static void
 940 make_gimple_switch_edges (basic_block bb)
 941 {
 942   gimple entry = last_stmt (bb);
 943   location_t entry_locus;
 944   size_t i, n;
 945
 946   entry_locus = gimple_location (entry);
 947
 948   n = gimple_switch_num_labels (entry);
 949
 950   for (i = 0; i < n; ++i)
 951     {
 952       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
 953       basic_block label_bb = label_to_block (lab);
 954       make_edge (bb, label_bb, 0);
 955       assign_discriminator (entry_locus, label_bb);
 956     }
 957 }
 958
 959
 960 /* Return the basic block holding label DEST.  */
 961
 962 basic_block
 963 label_to_block_fn (struct function *ifun, tree dest)
 964 {
 965   int uid = LABEL_DECL_UID (dest);
 966
 967   /* We would die hard when faced by an undefined label.  Emit a label to
 968      the very first basic block.  This will hopefully make even the dataflow
 969      and undefined variable warnings quite right.  */
 970   if (seen_error () && uid < 0)
 971     {
 972       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 973       gimple stmt;
 974
 975       stmt = gimple_build_label (dest);
 976       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 977       uid = LABEL_DECL_UID (dest);
 978     }
 979   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 980       <= (unsigned int) uid)
 981     return NULL;
 982   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 983 }
 984
 985 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
 986    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
 987
 988 void
 989 make_abnormal_goto_edges (basic_block bb, bool for_call)
 990 {
 991   basic_block target_bb;
 992   gimple_stmt_iterator gsi;
 993
 994   FOR_EACH_BB (target_bb)
 995     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 996       {
 997         gimple label_stmt = gsi_stmt (gsi);
 998         tree target;
 999
1000         if (gimple_code (label_stmt) != GIMPLE_LABEL)
1001           break;
1002
1003         target = gimple_label_label (label_stmt);
1004
1005         /* Make an edge to every label block that has been marked as a
1006            potential target for a computed goto or a non-local goto.  */
1007         if ((FORCED_LABEL (target) && !for_call)
1008             || (DECL_NONLOCAL (target) && for_call))
1009           {
1010             make_edge (bb, target_bb, EDGE_ABNORMAL);
1011             break;
1012           }
1013       }
1014 }
1015
1016 /* Create edges for a goto statement at block BB.  */
1017
1018 static void
1019 make_goto_expr_edges (basic_block bb)
1020 {
1021   gimple_stmt_iterator last = gsi_last_bb (bb);
1022   gimple goto_t = gsi_stmt (last);
1023
1024   /* A simple GOTO creates normal edges.  */
1025   if (simple_goto_p (goto_t))
1026     {
1027       tree dest = gimple_goto_dest (goto_t);
1028       basic_block label_bb = label_to_block (dest);
1029       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1030       e->goto_locus = gimple_location (goto_t);
1031       assign_discriminator (e->goto_locus, label_bb);
1032       if (e->goto_locus)
1033         e->goto_block = gimple_block (goto_t);
1034       gsi_remove (&last, true);
1035       return;
1036     }
1037
1038   /* A computed GOTO creates abnormal edges.  */
1039   make_abnormal_goto_edges (bb, false);
1040 }
1041
1042 /* Create edges for an asm statement with labels at block BB.  */
1043
1044 static void
1045 make_gimple_asm_edges (basic_block bb)
1046 {
1047   gimple stmt = last_stmt (bb);
1048   location_t stmt_loc = gimple_location (stmt);
1049   int i, n = gimple_asm_nlabels (stmt);
1050
1051   for (i = 0; i < n; ++i)
1052     {
1053       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1054       basic_block label_bb = label_to_block (label);
1055       make_edge (bb, label_bb, 0);
1056       assign_discriminator (stmt_loc, label_bb);
1057     }
1058 }
1059
1060 /*---------------------------------------------------------------------------
1061                                Flowgraph analysis
1062 ---------------------------------------------------------------------------*/
1063
1064 /* Cleanup useless labels in basic blocks.  This is something we wish
1065    to do early because it allows us to group case labels before creating
1066    the edges for the CFG, and it speeds up block statement iterators in
1067    all passes later on.
1068    We rerun this pass after CFG is created, to get rid of the labels that
1069    are no longer referenced.  After then we do not run it any more, since
1070    (almost) no new labels should be created.  */
1071
1072 /* A map from basic block index to the leading label of that block.  */
1073 static struct label_record
1074 {
1075   /* The label.  */
1076   tree label;
1077
1078   /* True if the label is referenced from somewhere.  */
1079   bool used;
1080 } *label_for_bb;
1081
1082 /* Given LABEL return the first label in the same basic block.  */
1083
1084 static tree
1085 main_block_label (tree label)
1086 {
1087   basic_block bb = label_to_block (label);
1088   tree main_label = label_for_bb[bb->index].label;
1089
1090   /* label_to_block possibly inserted undefined label into the chain.  */
1091   if (!main_label)
1092     {
1093       label_for_bb[bb->index].label = label;
1094       main_label = label;
1095     }
1096
1097   label_for_bb[bb->index].used = true;
1098   return main_label;
1099 }
1100
1101 /* Clean up redundant labels within the exception tree.  */
1102
1103 static void
1104 cleanup_dead_labels_eh (void)
1105 {
1106   eh_landing_pad lp;
1107   eh_region r;
1108   tree lab;
1109   int i;
1110
1111   if (cfun->eh == NULL)
1112     return;
1113
1114   for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1115     if (lp && lp->post_landing_pad)
1116       {
1117         lab = main_block_label (lp->post_landing_pad);
1118         if (lab != lp->post_landing_pad)
1119           {
1120             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1121             EH_LANDING_PAD_NR (lab) = lp->index;
1122           }
1123       }
1124
1125   FOR_ALL_EH_REGION (r)
1126     switch (r->type)
1127       {
1128       case ERT_CLEANUP:
1129       case ERT_MUST_NOT_THROW:
1130         break;
1131
1132       case ERT_TRY:
1133         {
1134           eh_catch c;
1135           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1136             {
1137               lab = c->label;
1138               if (lab)
1139                 c->label = main_block_label (lab);
1140             }
1141         }
1142         break;
1143
1144       case ERT_ALLOWED_EXCEPTIONS:
1145         lab = r->u.allowed.label;
1146         if (lab)
1147           r->u.allowed.label = main_block_label (lab);
1148         break;
1149       }
1150 }
1151
1152
1153 /* Cleanup redundant labels.  This is a three-step process:
1154      1) Find the leading label for each block.
1155      2) Redirect all references to labels to the leading labels.
1156      3) Cleanup all useless labels.  */
1157
1158 void
1159 cleanup_dead_labels (void)
1160 {
1161   basic_block bb;
1162   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1163
1164   /* Find a suitable label for each block.  We use the first user-defined
1165      label if there is one, or otherwise just the first label we see.  */
1166   FOR_EACH_BB (bb)
1167     {
1168       gimple_stmt_iterator i;
1169
1170       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1171         {
1172           tree label;
1173           gimple stmt = gsi_stmt (i);
1174
1175           if (gimple_code (stmt) != GIMPLE_LABEL)
1176             break;
1177
1178           label = gimple_label_label (stmt);
1179
1180           /* If we have not yet seen a label for the current block,
1181              remember this one and see if there are more labels.  */
1182           if (!label_for_bb[bb->index].label)
1183             {
1184               label_for_bb[bb->index].label = label;
1185               continue;
1186             }
1187
1188           /* If we did see a label for the current block already, but it
1189              is an artificially created label, replace it if the current
1190              label is a user defined label.  */
1191           if (!DECL_ARTIFICIAL (label)
1192               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1193             {
1194               label_for_bb[bb->index].label = label;
1195               break;
1196             }
1197         }
1198     }
1199
1200   /* Now redirect all jumps/branches to the selected label.
1201      First do so for each block ending in a control statement.  */
1202   FOR_EACH_BB (bb)
1203     {
1204       gimple stmt = last_stmt (bb);
1205       tree label, new_label;
1206
1207       if (!stmt)
1208         continue;
1209
1210       switch (gimple_code (stmt))
1211         {
1212         case GIMPLE_COND:
1213           label = gimple_cond_true_label (stmt);
1214           if (label)
1215             {
1216               new_label = main_block_label (label);
1217               if (new_label != label)
1218                 gimple_cond_set_true_label (stmt, new_label);
1219             }
1220
1221           label = gimple_cond_false_label (stmt);
1222           if (label)
1223             {
1224               new_label = main_block_label (label);
1225               if (new_label != label)
1226                 gimple_cond_set_false_label (stmt, new_label);
1227             }
1228           break;
1229
1230         case GIMPLE_SWITCH:
1231           {
1232             size_t i, n = gimple_switch_num_labels (stmt);
1233
1234             /* Replace all destination labels.  */
1235             for (i = 0; i < n; ++i)
1236               {
1237                 tree case_label = gimple_switch_label (stmt, i);
1238                 label = CASE_LABEL (case_label);
1239                 new_label = main_block_label (label);
1240                 if (new_label != label)
1241                   CASE_LABEL (case_label) = new_label;
1242               }
1243             break;
1244           }
1245
1246         case GIMPLE_ASM:
1247           {
1248             int i, n = gimple_asm_nlabels (stmt);
1249
1250             for (i = 0; i < n; ++i)
1251               {
1252                 tree cons = gimple_asm_label_op (stmt, i);
1253                 tree label = main_block_label (TREE_VALUE (cons));
1254                 TREE_VALUE (cons) = label;
1255               }
1256             break;
1257           }
1258
1259         /* We have to handle gotos until they're removed, and we don't
1260            remove them until after we've created the CFG edges.  */
1261         case GIMPLE_GOTO:
1262           if (!computed_goto_p (stmt))
1263             {
1264               label = gimple_goto_dest (stmt);
1265               new_label = main_block_label (label);
1266               if (new_label != label)
1267                 gimple_goto_set_dest (stmt, new_label);
1268             }
1269           break;
1270
1271         case GIMPLE_TRANSACTION:
1272           {
1273             tree label = gimple_transaction_label (stmt);
1274             if (label)
1275               {
1276                 tree new_label = main_block_label (label);
1277                 if (new_label != label)
1278                   gimple_transaction_set_label (stmt, new_label);
1279               }
1280           }
1281           break;
1282
1283         default:
1284           break;
1285       }
1286     }
1287
1288   /* Do the same for the exception region tree labels.  */
1289   cleanup_dead_labels_eh ();
1290
1291   /* Finally, purge dead labels.  All user-defined labels and labels that
1292      can be the target of non-local gotos and labels which have their
1293      address taken are preserved.  */
1294   FOR_EACH_BB (bb)
1295     {
1296       gimple_stmt_iterator i;
1297       tree label_for_this_bb = label_for_bb[bb->index].label;
1298
1299       if (!label_for_this_bb)
1300         continue;
1301
1302       /* If the main label of the block is unused, we may still remove it.  */
1303       if (!label_for_bb[bb->index].used)
1304         label_for_this_bb = NULL;
1305
1306       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1307         {
1308           tree label;
1309           gimple stmt = gsi_stmt (i);
1310
1311           if (gimple_code (stmt) != GIMPLE_LABEL)
1312             break;
1313
1314           label = gimple_label_label (stmt);
1315
1316           if (label == label_for_this_bb
1317               || !DECL_ARTIFICIAL (label)
1318               || DECL_NONLOCAL (label)
1319               || FORCED_LABEL (label))
1320             gsi_next (&i);
1321           else
1322             gsi_remove (&i, true);
1323         }
1324     }
1325
1326   free (label_for_bb);
1327 }
1328
1329 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1330    the ones jumping to the same label.
1331    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1332
1333 void
1334 group_case_labels_stmt (gimple stmt)
1335 {
1336   int old_size = gimple_switch_num_labels (stmt);
1337   int i, j, new_size = old_size;
1338   tree default_case = NULL_TREE;
1339   tree default_label = NULL_TREE;
1340   bool has_default;
1341
1342   /* The default label is always the first case in a switch
1343      statement after gimplification if it was not optimized
1344      away */
1345   if (!CASE_LOW (gimple_switch_default_label (stmt))
1346       && !CASE_HIGH (gimple_switch_default_label (stmt)))
1347     {
1348       default_case = gimple_switch_default_label (stmt);
1349       default_label = CASE_LABEL (default_case);
1350       has_default = true;
1351     }
1352   else
1353     has_default = false;
1354
1355   /* Look for possible opportunities to merge cases.  */
1356   if (has_default)
1357     i = 1;
1358   else
1359     i = 0;
1360   while (i < old_size)
1361     {
1362       tree base_case, base_label, base_high;
1363       base_case = gimple_switch_label (stmt, i);
1364
1365       gcc_assert (base_case);
1366       base_label = CASE_LABEL (base_case);
1367
1368       /* Discard cases that have the same destination as the
1369          default case.  */
1370       if (base_label == default_label)
1371         {
1372           gimple_switch_set_label (stmt, i, NULL_TREE);
1373           i++;
1374           new_size--;
1375           continue;
1376         }
1377
1378       base_high = CASE_HIGH (base_case)
1379           ? CASE_HIGH (base_case)
1380           : CASE_LOW (base_case);
1381       i++;
1382
1383       /* Try to merge case labels.  Break out when we reach the end
1384          of the label vector or when we cannot merge the next case
1385          label with the current one.  */
1386       while (i < old_size)
1387         {
1388           tree merge_case = gimple_switch_label (stmt, i);
1389           tree merge_label = CASE_LABEL (merge_case);
1390           double_int bhp1 = double_int_add (tree_to_double_int (base_high),
1391                                             double_int_one);
1392
1393           /* Merge the cases if they jump to the same place,
1394              and their ranges are consecutive.  */
1395           if (merge_label == base_label
1396               && double_int_equal_p (tree_to_double_int (CASE_LOW (merge_case)),
1397                                      bhp1))
1398             {
1399               base_high = CASE_HIGH (merge_case) ?
1400                   CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1401               CASE_HIGH (base_case) = base_high;
1402               gimple_switch_set_label (stmt, i, NULL_TREE);
1403               new_size--;
1404               i++;
1405             }
1406           else
1407             break;
1408         }
1409     }
1410
1411   /* Compress the case labels in the label vector, and adjust the
1412      length of the vector.  */
1413   for (i = 0, j = 0; i < new_size; i++)
1414     {
1415       while (! gimple_switch_label (stmt, j))
1416         j++;
1417       gimple_switch_set_label (stmt, i,
1418                                gimple_switch_label (stmt, j++));
1419     }
1420
1421   gcc_assert (new_size <= old_size);
1422   gimple_switch_set_num_labels (stmt, new_size);
1423 }
1424
1425 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1426    and scan the sorted vector of cases.  Combine the ones jumping to the
1427    same label.  */
1428
1429 void
1430 group_case_labels (void)
1431 {
1432   basic_block bb;
1433
1434   FOR_EACH_BB (bb)
1435     {
1436       gimple stmt = last_stmt (bb);
1437       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1438         group_case_labels_stmt (stmt);
1439     }
1440 }
1441
1442 /* Checks whether we can merge block B into block A.  */
1443
1444 static bool
1445 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1446 {
1447   gimple stmt;
1448   gimple_stmt_iterator gsi;
1449   gimple_seq phis;
1450
1451   if (!single_succ_p (a))
1452     return false;
1453
1454   if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH | EDGE_PRESERVE))
1455     return false;
1456
1457   if (single_succ (a) != b)
1458     return false;
1459
1460   if (!single_pred_p (b))
1461     return false;
1462
1463   if (b == EXIT_BLOCK_PTR)
1464     return false;
1465
1466   /* If A ends by a statement causing exceptions or something similar, we
1467      cannot merge the blocks.  */
1468   stmt = last_stmt (a);
1469   if (stmt && stmt_ends_bb_p (stmt))
1470     return false;
1471
1472   /* Do not allow a block with only a non-local label to be merged.  */
1473   if (stmt
1474       && gimple_code (stmt) == GIMPLE_LABEL
1475       && DECL_NONLOCAL (gimple_label_label (stmt)))
1476     return false;
1477
1478   /* Examine the labels at the beginning of B.  */
1479   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1480     {
1481       tree lab;
1482       stmt = gsi_stmt (gsi);
1483       if (gimple_code (stmt) != GIMPLE_LABEL)
1484         break;
1485       lab = gimple_label_label (stmt);
1486
1487       /* Do not remove user forced labels or for -O0 any user labels.  */
1488       if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1489         return false;
1490     }
1491
1492   /* Protect the loop latches.  */
1493   if (current_loops && b->loop_father->latch == b)
1494     return false;
1495
1496   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1497      is not up-to-date and a name-mapping is registered, we cannot eliminate
1498      any phis.  Symbols marked for renaming are never a problem though.  */
1499   phis = phi_nodes (b);
1500   if (!gimple_seq_empty_p (phis)
1501       && name_mappings_registered_p ())
1502     return false;
1503
1504   /* When not optimizing, don't merge if we'd lose goto_locus.  */
1505   if (!optimize
1506       && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1507     {
1508       location_t goto_locus = single_succ_edge (a)->goto_locus;
1509       gimple_stmt_iterator prev, next;
1510       prev = gsi_last_nondebug_bb (a);
1511       next = gsi_after_labels (b);
1512       if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1513         gsi_next_nondebug (&next);
1514       if ((gsi_end_p (prev)
1515            || gimple_location (gsi_stmt (prev)) != goto_locus)
1516           && (gsi_end_p (next)
1517               || gimple_location (gsi_stmt (next)) != goto_locus))
1518         return false;
1519     }
1520
1521   return true;
1522 }
1523
1524 /* Return true if the var whose chain of uses starts at PTR has no
1525    nondebug uses.  */
1526 bool
1527 has_zero_uses_1 (const ssa_use_operand_t *head)
1528 {
1529   const ssa_use_operand_t *ptr;
1530
1531   for (ptr = head->next; ptr != head; ptr = ptr->next)
1532     if (!is_gimple_debug (USE_STMT (ptr)))
1533       return false;
1534
1535   return true;
1536 }
1537
1538 /* Return true if the var whose chain of uses starts at PTR has a
1539    single nondebug use.  Set USE_P and STMT to that single nondebug
1540    use, if so, or to NULL otherwise.  */
1541 bool
1542 single_imm_use_1 (const ssa_use_operand_t *head,
1543                   use_operand_p *use_p, gimple *stmt)
1544 {
1545   ssa_use_operand_t *ptr, *single_use = 0;
1546
1547   for (ptr = head->next; ptr != head; ptr = ptr->next)
1548     if (!is_gimple_debug (USE_STMT (ptr)))
1549       {
1550         if (single_use)
1551           {
1552             single_use = NULL;
1553             break;
1554           }
1555         single_use = ptr;
1556       }
1557
1558   if (use_p)
1559     *use_p = single_use;
1560
1561   if (stmt)
1562     *stmt = single_use ? single_use->loc.stmt : NULL;
1563
1564   return !!single_use;
1565 }
1566
1567 /* Replaces all uses of NAME by VAL.  */
1568
1569 void
1570 replace_uses_by (tree name, tree val)
1571 {
1572   imm_use_iterator imm_iter;
1573   use_operand_p use;
1574   gimple stmt;
1575   edge e;
1576
1577   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1578     {
1579       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1580         {
1581           replace_exp (use, val);
1582
1583           if (gimple_code (stmt) == GIMPLE_PHI)
1584             {
1585               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1586               if (e->flags & EDGE_ABNORMAL)
1587                 {
1588                   /* This can only occur for virtual operands, since
1589                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1590                      would prevent replacement.  */
1591                   gcc_checking_assert (!is_gimple_reg (name));
1592                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1593                 }
1594             }
1595         }
1596
1597       if (gimple_code (stmt) != GIMPLE_PHI)
1598         {
1599           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1600           gimple orig_stmt = stmt;
1601           size_t i;
1602
1603           /* Mark the block if we changed the last stmt in it.  */
1604           if (cfgcleanup_altered_bbs
1605               && stmt_ends_bb_p (stmt))
1606             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1607
1608           /* FIXME.  It shouldn't be required to keep TREE_CONSTANT
1609              on ADDR_EXPRs up-to-date on GIMPLE.  Propagation will
1610              only change sth from non-invariant to invariant, and only
1611              when propagating constants.  */
1612           if (is_gimple_min_invariant (val))
1613             for (i = 0; i < gimple_num_ops (stmt); i++)
1614               {
1615                 tree op = gimple_op (stmt, i);
1616                 /* Operands may be empty here.  For example, the labels
1617                    of a GIMPLE_COND are nulled out following the creation
1618                    of the corresponding CFG edges.  */
1619                 if (op && TREE_CODE (op) == ADDR_EXPR)
1620                   recompute_tree_invariant_for_addr_expr (op);
1621               }
1622
1623           if (fold_stmt (&gsi))
1624             stmt = gsi_stmt (gsi);
1625
1626           if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1627             gimple_purge_dead_eh_edges (gimple_bb (stmt));
1628
1629           update_stmt (stmt);
1630         }
1631     }
1632
1633   gcc_checking_assert (has_zero_uses (name));
1634
1635   /* Also update the trees stored in loop structures.  */
1636   if (current_loops)
1637     {
1638       struct loop *loop;
1639       loop_iterator li;
1640
1641       FOR_EACH_LOOP (li, loop, 0)
1642         {
1643           substitute_in_loop_info (loop, name, val);
1644         }
1645     }
1646 }
1647
1648 /* Merge block B into block A.  */
1649
1650 static void
1651 gimple_merge_blocks (basic_block a, basic_block b)
1652 {
1653   gimple_stmt_iterator last, gsi, psi;
1654
1655   if (dump_file)
1656     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1657
1658   /* Remove all single-valued PHI nodes from block B of the form
1659      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1660   gsi = gsi_last_bb (a);
1661   for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1662     {
1663       gimple phi = gsi_stmt (psi);
1664       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1665       gimple copy;
1666       bool may_replace_uses = !is_gimple_reg (def)
1667                               || may_propagate_copy (def, use);
1668
1669       /* In case we maintain loop closed ssa form, do not propagate arguments
1670          of loop exit phi nodes.  */
1671       if (current_loops
1672           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1673           && is_gimple_reg (def)
1674           && TREE_CODE (use) == SSA_NAME
1675           && a->loop_father != b->loop_father)
1676         may_replace_uses = false;
1677
1678       if (!may_replace_uses)
1679         {
1680           gcc_assert (is_gimple_reg (def));
1681
1682           /* Note that just emitting the copies is fine -- there is no problem
1683              with ordering of phi nodes.  This is because A is the single
1684              predecessor of B, therefore results of the phi nodes cannot
1685              appear as arguments of the phi nodes.  */
1686           copy = gimple_build_assign (def, use);
1687           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1688           remove_phi_node (&psi, false);
1689         }
1690       else
1691         {
1692           /* If we deal with a PHI for virtual operands, we can simply
1693              propagate these without fussing with folding or updating
1694              the stmt.  */
1695           if (!is_gimple_reg (def))
1696             {
1697               imm_use_iterator iter;
1698               use_operand_p use_p;
1699               gimple stmt;
1700
1701               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1702                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1703                   SET_USE (use_p, use);
1704
1705               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1706                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1707             }
1708           else
1709             replace_uses_by (def, use);
1710
1711           remove_phi_node (&psi, true);
1712         }
1713     }
1714
1715   /* Ensure that B follows A.  */
1716   move_block_after (b, a);
1717
1718   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1719   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1720
1721   /* Remove labels from B and set gimple_bb to A for other statements.  */
1722   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1723     {
1724       gimple stmt = gsi_stmt (gsi);
1725       if (gimple_code (stmt) == GIMPLE_LABEL)
1726         {
1727           tree label = gimple_label_label (stmt);
1728           int lp_nr;
1729
1730           gsi_remove (&gsi, false);
1731
1732           /* Now that we can thread computed gotos, we might have
1733              a situation where we have a forced label in block B
1734              However, the label at the start of block B might still be
1735              used in other ways (think about the runtime checking for
1736              Fortran assigned gotos).  So we can not just delete the
1737              label.  Instead we move the label to the start of block A.  */
1738           if (FORCED_LABEL (label))
1739             {
1740               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1741               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1742             }
1743           /* Other user labels keep around in a form of a debug stmt.  */
1744           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1745             {
1746               gimple dbg = gimple_build_debug_bind (label,
1747                                                     integer_zero_node,
1748                                                     stmt);
1749               gimple_debug_bind_reset_value (dbg);
1750               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1751             }
1752
1753           lp_nr = EH_LANDING_PAD_NR (label);
1754           if (lp_nr)
1755             {
1756               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1757               lp->post_landing_pad = NULL;
1758             }
1759         }
1760       else
1761         {
1762           gimple_set_bb (stmt, a);
1763           gsi_next (&gsi);
1764         }
1765     }
1766
1767   /* Merge the sequences.  */
1768   last = gsi_last_bb (a);
1769   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1770   set_bb_seq (b, NULL);
1771
1772   if (cfgcleanup_altered_bbs)
1773     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1774 }
1775
1776
1777 /* Return the one of two successors of BB that is not reachable by a
1778    complex edge, if there is one.  Else, return BB.  We use
1779    this in optimizations that use post-dominators for their heuristics,
1780    to catch the cases in C++ where function calls are involved.  */
1781
1782 basic_block
1783 single_noncomplex_succ (basic_block bb)
1784 {
1785   edge e0, e1;
1786   if (EDGE_COUNT (bb->succs) != 2)
1787     return bb;
1788
1789   e0 = EDGE_SUCC (bb, 0);
1790   e1 = EDGE_SUCC (bb, 1);
1791   if (e0->flags & EDGE_COMPLEX)
1792     return e1->dest;
1793   if (e1->flags & EDGE_COMPLEX)
1794     return e0->dest;
1795
1796   return bb;
1797 }
1798
1799 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1800
1801 void
1802 notice_special_calls (gimple call)
1803 {
1804   int flags = gimple_call_flags (call);
1805
1806   if (flags & ECF_MAY_BE_ALLOCA)
1807     cfun->calls_alloca = true;
1808   if (flags & ECF_RETURNS_TWICE)
1809     cfun->calls_setjmp = true;
1810 }
1811
1812
1813 /* Clear flags set by notice_special_calls.  Used by dead code removal
1814    to update the flags.  */
1815
1816 void
1817 clear_special_calls (void)
1818 {
1819   cfun->calls_alloca = false;
1820   cfun->calls_setjmp = false;
1821 }
1822
1823 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1824
1825 static void
1826 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1827 {
1828   /* Since this block is no longer reachable, we can just delete all
1829      of its PHI nodes.  */
1830   remove_phi_nodes (bb);
1831
1832   /* Remove edges to BB's successors.  */
1833   while (EDGE_COUNT (bb->succs) > 0)
1834     remove_edge (EDGE_SUCC (bb, 0));
1835 }
1836
1837
1838 /* Remove statements of basic block BB.  */
1839
1840 static void
1841 remove_bb (basic_block bb)
1842 {
1843   gimple_stmt_iterator i;
1844
1845   if (dump_file)
1846     {
1847       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1848       if (dump_flags & TDF_DETAILS)
1849         {
1850           dump_bb (bb, dump_file, 0);
1851           fprintf (dump_file, "\n");
1852         }
1853     }
1854
1855   if (current_loops)
1856     {
1857       struct loop *loop = bb->loop_father;
1858
1859       /* If a loop gets removed, clean up the information associated
1860          with it.  */
1861       if (loop->latch == bb
1862           || loop->header == bb)
1863         free_numbers_of_iterations_estimates_loop (loop);
1864     }
1865
1866   /* Remove all the instructions in the block.  */
1867   if (bb_seq (bb) != NULL)
1868     {
1869       /* Walk backwards so as to get a chance to substitute all
1870          released DEFs into debug stmts.  See
1871          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1872          details.  */
1873       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1874         {
1875           gimple stmt = gsi_stmt (i);
1876           if (gimple_code (stmt) == GIMPLE_LABEL
1877               && (FORCED_LABEL (gimple_label_label (stmt))
1878                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1879             {
1880               basic_block new_bb;
1881               gimple_stmt_iterator new_gsi;
1882
1883               /* A non-reachable non-local label may still be referenced.
1884                  But it no longer needs to carry the extra semantics of
1885                  non-locality.  */
1886               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1887                 {
1888                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1889                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1890                 }
1891
1892               new_bb = bb->prev_bb;
1893               new_gsi = gsi_start_bb (new_bb);
1894               gsi_remove (&i, false);
1895               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1896             }
1897           else
1898             {
1899               /* Release SSA definitions if we are in SSA.  Note that we
1900                  may be called when not in SSA.  For example,
1901                  final_cleanup calls this function via
1902                  cleanup_tree_cfg.  */
1903               if (gimple_in_ssa_p (cfun))
1904                 release_defs (stmt);
1905
1906               gsi_remove (&i, true);
1907             }
1908
1909           if (gsi_end_p (i))
1910             i = gsi_last_bb (bb);
1911           else
1912             gsi_prev (&i);
1913         }
1914     }
1915
1916   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1917   bb->il.gimple.seq = NULL;
1918   bb->il.gimple.phi_nodes = NULL;
1919 }
1920
1921
1922 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1923    predicate VAL, return the edge that will be taken out of the block.
1924    If VAL does not match a unique edge, NULL is returned.  */
1925
1926 edge
1927 find_taken_edge (basic_block bb, tree val)
1928 {
1929   gimple stmt;
1930
1931   stmt = last_stmt (bb);
1932
1933   gcc_assert (stmt);
1934   gcc_assert (is_ctrl_stmt (stmt));
1935
1936   if (val == NULL)
1937     return NULL;
1938
1939   if (!is_gimple_min_invariant (val))
1940     return NULL;
1941
1942   if (gimple_code (stmt) == GIMPLE_COND)
1943     return find_taken_edge_cond_expr (bb, val);
1944
1945   if (gimple_code (stmt) == GIMPLE_SWITCH)
1946     return find_taken_edge_switch_expr (bb, val);
1947
1948   if (computed_goto_p (stmt))
1949     {
1950       /* Only optimize if the argument is a label, if the argument is
1951          not a label then we can not construct a proper CFG.
1952
1953          It may be the case that we only need to allow the LABEL_REF to
1954          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1955          appear inside a LABEL_EXPR just to be safe.  */
1956       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1957           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1958         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1959       return NULL;
1960     }
1961
1962   gcc_unreachable ();
1963 }
1964
1965 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1966    statement, determine which of the outgoing edges will be taken out of the
1967    block.  Return NULL if either edge may be taken.  */
1968
1969 static edge
1970 find_taken_edge_computed_goto (basic_block bb, tree val)
1971 {
1972   basic_block dest;
1973   edge e = NULL;
1974
1975   dest = label_to_block (val);
1976   if (dest)
1977     {
1978       e = find_edge (bb, dest);
1979       gcc_assert (e != NULL);
1980     }
1981
1982   return e;
1983 }
1984
1985 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1986    statement, determine which of the two edges will be taken out of the
1987    block.  Return NULL if either edge may be taken.  */
1988
1989 static edge
1990 find_taken_edge_cond_expr (basic_block bb, tree val)
1991 {
1992   edge true_edge, false_edge;
1993
1994   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1995
1996   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1997   return (integer_zerop (val) ? false_edge : true_edge);
1998 }
1999
2000 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2001    statement, determine which edge will be taken out of the block.  Return
2002    NULL if any edge may be taken.  */
2003
2004 static edge
2005 find_taken_edge_switch_expr (basic_block bb, tree val)
2006 {
2007   basic_block dest_bb;
2008   edge e;
2009   gimple switch_stmt;
2010   tree taken_case;
2011
2012   switch_stmt = last_stmt (bb);
2013   taken_case = find_case_label_for_value (switch_stmt, val);
2014   dest_bb = label_to_block (CASE_LABEL (taken_case));
2015
2016   e = find_edge (bb, dest_bb);
2017   gcc_assert (e);
2018   return e;
2019 }
2020
2021
2022 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2023    We can make optimal use here of the fact that the case labels are
2024    sorted: We can do a binary search for a case matching VAL.  */
2025
2026 static tree
2027 find_case_label_for_value (gimple switch_stmt, tree val)
2028 {
2029   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2030   tree default_case = gimple_switch_default_label (switch_stmt);
2031
2032   for (low = 0, high = n; high - low > 1; )
2033     {
2034       size_t i = (high + low) / 2;
2035       tree t = gimple_switch_label (switch_stmt, i);
2036       int cmp;
2037
2038       /* Cache the result of comparing CASE_LOW and val.  */
2039       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2040
2041       if (cmp > 0)
2042         high = i;
2043       else
2044         low = i;
2045
2046       if (CASE_HIGH (t) == NULL)
2047         {
2048           /* A singe-valued case label.  */
2049           if (cmp == 0)
2050             return t;
2051         }
2052       else
2053         {
2054           /* A case range.  We can only handle integer ranges.  */
2055           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2056             return t;
2057         }
2058     }
2059
2060   return default_case;
2061 }
2062
2063
2064 /* Dump a basic block on stderr.  */
2065
2066 void
2067 gimple_debug_bb (basic_block bb)
2068 {
2069   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2070 }
2071
2072
2073 /* Dump basic block with index N on stderr.  */
2074
2075 basic_block
2076 gimple_debug_bb_n (int n)
2077 {
2078   gimple_debug_bb (BASIC_BLOCK (n));
2079   return BASIC_BLOCK (n);
2080 }
2081
2082
2083 /* Dump the CFG on stderr.
2084
2085    FLAGS are the same used by the tree dumping functions
2086    (see TDF_* in tree-pass.h).  */
2087
2088 void
2089 gimple_debug_cfg (int flags)
2090 {
2091   gimple_dump_cfg (stderr, flags);
2092 }
2093
2094
2095 /* Dump the program showing basic block boundaries on the given FILE.
2096
2097    FLAGS are the same used by the tree dumping functions (see TDF_* in
2098    tree.h).  */
2099
2100 void
2101 gimple_dump_cfg (FILE *file, int flags)
2102 {
2103   if (flags & TDF_DETAILS)
2104     {
2105       dump_function_header (file, current_function_decl, flags);
2106       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2107                n_basic_blocks, n_edges, last_basic_block);
2108
2109       brief_dump_cfg (file);
2110       fprintf (file, "\n");
2111     }
2112
2113   if (flags & TDF_STATS)
2114     dump_cfg_stats (file);
2115
2116   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2117 }
2118
2119
2120 /* Dump CFG statistics on FILE.  */
2121
2122 void
2123 dump_cfg_stats (FILE *file)
2124 {
2125   static long max_num_merged_labels = 0;
2126   unsigned long size, total = 0;
2127   long num_edges;
2128   basic_block bb;
2129   const char * const fmt_str   = "%-30s%-13s%12s\n";
2130   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2131   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2132   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2133   const char *funcname
2134     = lang_hooks.decl_printable_name (current_function_decl, 2);
2135
2136
2137   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2138
2139   fprintf (file, "---------------------------------------------------------\n");
2140   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2141   fprintf (file, fmt_str, "", "  instances  ", "used ");
2142   fprintf (file, "---------------------------------------------------------\n");
2143
2144   size = n_basic_blocks * sizeof (struct basic_block_def);
2145   total += size;
2146   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2147            SCALE (size), LABEL (size));
2148
2149   num_edges = 0;
2150   FOR_EACH_BB (bb)
2151     num_edges += EDGE_COUNT (bb->succs);
2152   size = num_edges * sizeof (struct edge_def);
2153   total += size;
2154   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2155
2156   fprintf (file, "---------------------------------------------------------\n");
2157   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2158            LABEL (total));
2159   fprintf (file, "---------------------------------------------------------\n");
2160   fprintf (file, "\n");
2161
2162   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2163     max_num_merged_labels = cfg_stats.num_merged_labels;
2164
2165   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2166            cfg_stats.num_merged_labels, max_num_merged_labels);
2167
2168   fprintf (file, "\n");
2169 }
2170
2171
2172 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2173    linked in the final executable.  */
2174
2175 DEBUG_FUNCTION void
2176 debug_cfg_stats (void)
2177 {
2178   dump_cfg_stats (stderr);
2179 }
2180
2181
2182 /* Dump the flowgraph to a .vcg FILE.  */
2183
2184 static void
2185 gimple_cfg2vcg (FILE *file)
2186 {
2187   edge e;
2188   edge_iterator ei;
2189   basic_block bb;
2190   const char *funcname
2191     = lang_hooks.decl_printable_name (current_function_decl, 2);
2192
2193   /* Write the file header.  */
2194   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2195   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2196   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2197
2198   /* Write blocks and edges.  */
2199   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2200     {
2201       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2202                e->dest->index);
2203
2204       if (e->flags & EDGE_FAKE)
2205         fprintf (file, " linestyle: dotted priority: 10");
2206       else
2207         fprintf (file, " linestyle: solid priority: 100");
2208
2209       fprintf (file, " }\n");
2210     }
2211   fputc ('\n', file);
2212
2213   FOR_EACH_BB (bb)
2214     {
2215       enum gimple_code head_code, end_code;
2216       const char *head_name, *end_name;
2217       int head_line = 0;
2218       int end_line = 0;
2219       gimple first = first_stmt (bb);
2220       gimple last = last_stmt (bb);
2221
2222       if (first)
2223         {
2224           head_code = gimple_code (first);
2225           head_name = gimple_code_name[head_code];
2226           head_line = get_lineno (first);
2227         }
2228       else
2229         head_name = "no-statement";
2230
2231       if (last)
2232         {
2233           end_code = gimple_code (last);
2234           end_name = gimple_code_name[end_code];
2235           end_line = get_lineno (last);
2236         }
2237       else
2238         end_name = "no-statement";
2239
2240       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2241                bb->index, bb->index, head_name, head_line, end_name,
2242                end_line);
2243
2244       FOR_EACH_EDGE (e, ei, bb->succs)
2245         {
2246           if (e->dest == EXIT_BLOCK_PTR)
2247             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2248           else
2249             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2250
2251           if (e->flags & EDGE_FAKE)
2252             fprintf (file, " priority: 10 linestyle: dotted");
2253           else
2254             fprintf (file, " priority: 100 linestyle: solid");
2255
2256           fprintf (file, " }\n");
2257         }
2258
2259       if (bb->next_bb != EXIT_BLOCK_PTR)
2260         fputc ('\n', file);
2261     }
2262
2263   fputs ("}\n\n", file);
2264 }
2265
2266
2267
2268 /*---------------------------------------------------------------------------
2269                              Miscellaneous helpers
2270 ---------------------------------------------------------------------------*/
2271
2272 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2273    flow.  Transfers of control flow associated with EH are excluded.  */
2274
2275 static bool
2276 call_can_make_abnormal_goto (gimple t)
2277 {
2278   /* If the function has no non-local labels, then a call cannot make an
2279      abnormal transfer of control.  */
2280   if (!cfun->has_nonlocal_label)
2281    return false;
2282
2283   /* Likewise if the call has no side effects.  */
2284   if (!gimple_has_side_effects (t))
2285     return false;
2286
2287   /* Likewise if the called function is leaf.  */
2288   if (gimple_call_flags (t) & ECF_LEAF)
2289     return false;
2290
2291   return true;
2292 }
2293
2294
2295 /* Return true if T can make an abnormal transfer of control flow.
2296    Transfers of control flow associated with EH are excluded.  */
2297
2298 bool
2299 stmt_can_make_abnormal_goto (gimple t)
2300 {
2301   if (computed_goto_p (t))
2302     return true;
2303   if (is_gimple_call (t))
2304     return call_can_make_abnormal_goto (t);
2305   return false;
2306 }
2307
2308
2309 /* Return true if T represents a stmt that always transfers control.  */
2310
2311 bool
2312 is_ctrl_stmt (gimple t)
2313 {
2314   switch (gimple_code (t))
2315     {
2316     case GIMPLE_COND:
2317     case GIMPLE_SWITCH:
2318     case GIMPLE_GOTO:
2319     case GIMPLE_RETURN:
2320     case GIMPLE_RESX:
2321       return true;
2322     default:
2323       return false;
2324     }
2325 }
2326
2327
2328 /* Return true if T is a statement that may alter the flow of control
2329    (e.g., a call to a non-returning function).  */
2330
2331 bool
2332 is_ctrl_altering_stmt (gimple t)
2333 {
2334   gcc_assert (t);
2335
2336   switch (gimple_code (t))
2337     {
2338     case GIMPLE_CALL:
2339       {
2340         int flags = gimple_call_flags (t);
2341
2342         /* A call alters control flow if it can make an abnormal goto.  */
2343         if (call_can_make_abnormal_goto (t))
2344           return true;
2345
2346         /* A call also alters control flow if it does not return.  */
2347         if (flags & ECF_NORETURN)
2348           return true;
2349
2350         /* TM ending statements have backedges out of the transaction.
2351            Return true so we split the basic block containing them.
2352            Note that the TM_BUILTIN test is merely an optimization.  */
2353         if ((flags & ECF_TM_BUILTIN)
2354             && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2355           return true;
2356
2357         /* BUILT_IN_RETURN call is same as return statement.  */
2358         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2359           return true;
2360       }
2361       break;
2362
2363     case GIMPLE_EH_DISPATCH:
2364       /* EH_DISPATCH branches to the individual catch handlers at
2365          this level of a try or allowed-exceptions region.  It can
2366          fallthru to the next statement as well.  */
2367       return true;
2368
2369     case GIMPLE_ASM:
2370       if (gimple_asm_nlabels (t) > 0)
2371         return true;
2372       break;
2373
2374     CASE_GIMPLE_OMP:
2375       /* OpenMP directives alter control flow.  */
2376       return true;
2377
2378     case GIMPLE_TRANSACTION:
2379       /* A transaction start alters control flow.  */
2380       return true;
2381
2382     default:
2383       break;
2384     }
2385
2386   /* If a statement can throw, it alters control flow.  */
2387   return stmt_can_throw_internal (t);
2388 }
2389
2390
2391 /* Return true if T is a simple local goto.  */
2392
2393 bool
2394 simple_goto_p (gimple t)
2395 {
2396   return (gimple_code (t) == GIMPLE_GOTO
2397           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2398 }
2399
2400
2401 /* Return true if STMT should start a new basic block.  PREV_STMT is
2402    the statement preceding STMT.  It is used when STMT is a label or a
2403    case label.  Labels should only start a new basic block if their
2404    previous statement wasn't a label.  Otherwise, sequence of labels
2405    would generate unnecessary basic blocks that only contain a single
2406    label.  */
2407
2408 static inline bool
2409 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2410 {
2411   if (stmt == NULL)
2412     return false;
2413
2414   /* Labels start a new basic block only if the preceding statement
2415      wasn't a label of the same type.  This prevents the creation of
2416      consecutive blocks that have nothing but a single label.  */
2417   if (gimple_code (stmt) == GIMPLE_LABEL)
2418     {
2419       /* Nonlocal and computed GOTO targets always start a new block.  */
2420       if (DECL_NONLOCAL (gimple_label_label (stmt))
2421           || FORCED_LABEL (gimple_label_label (stmt)))
2422         return true;
2423
2424       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2425         {
2426           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2427             return true;
2428
2429           cfg_stats.num_merged_labels++;
2430           return false;
2431         }
2432       else
2433         return true;
2434     }
2435
2436   return false;
2437 }
2438
2439
2440 /* Return true if T should end a basic block.  */
2441
2442 bool
2443 stmt_ends_bb_p (gimple t)
2444 {
2445   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2446 }
2447
2448 /* Remove block annotations and other data structures.  */
2449
2450 void
2451 delete_tree_cfg_annotations (void)
2452 {
2453   label_to_block_map = NULL;
2454 }
2455
2456
2457 /* Return the first statement in basic block BB.  */
2458
2459 gimple
2460 first_stmt (basic_block bb)
2461 {
2462   gimple_stmt_iterator i = gsi_start_bb (bb);
2463   gimple stmt = NULL;
2464
2465   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2466     {
2467       gsi_next (&i);
2468       stmt = NULL;
2469     }
2470   return stmt;
2471 }
2472
2473 /* Return the first non-label statement in basic block BB.  */
2474
2475 static gimple
2476 first_non_label_stmt (basic_block bb)
2477 {
2478   gimple_stmt_iterator i = gsi_start_bb (bb);
2479   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2480     gsi_next (&i);
2481   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2482 }
2483
2484 /* Return the last statement in basic block BB.  */
2485
2486 gimple
2487 last_stmt (basic_block bb)
2488 {
2489   gimple_stmt_iterator i = gsi_last_bb (bb);
2490   gimple stmt = NULL;
2491
2492   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2493     {
2494       gsi_prev (&i);
2495       stmt = NULL;
2496     }
2497   return stmt;
2498 }
2499
2500 /* Return the last statement of an otherwise empty block.  Return NULL
2501    if the block is totally empty, or if it contains more than one
2502    statement.  */
2503
2504 gimple
2505 last_and_only_stmt (basic_block bb)
2506 {
2507   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2508   gimple last, prev;
2509
2510   if (gsi_end_p (i))
2511     return NULL;
2512
2513   last = gsi_stmt (i);
2514   gsi_prev_nondebug (&i);
2515   if (gsi_end_p (i))
2516     return last;
2517
2518   /* Empty statements should no longer appear in the instruction stream.
2519      Everything that might have appeared before should be deleted by
2520      remove_useless_stmts, and the optimizers should just gsi_remove
2521      instead of smashing with build_empty_stmt.
2522
2523      Thus the only thing that should appear here in a block containing
2524      one executable statement is a label.  */
2525   prev = gsi_stmt (i);
2526   if (gimple_code (prev) == GIMPLE_LABEL)
2527     return last;
2528   else
2529     return NULL;
2530 }
2531
2532 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2533
2534 static void
2535 reinstall_phi_args (edge new_edge, edge old_edge)
2536 {
2537   edge_var_map_vector v;
2538   edge_var_map *vm;
2539   int i;
2540   gimple_stmt_iterator phis;
2541
2542   v = redirect_edge_var_map_vector (old_edge);
2543   if (!v)
2544     return;
2545
2546   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2547        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2548        i++, gsi_next (&phis))
2549     {
2550       gimple phi = gsi_stmt (phis);
2551       tree result = redirect_edge_var_map_result (vm);
2552       tree arg = redirect_edge_var_map_def (vm);
2553
2554       gcc_assert (result == gimple_phi_result (phi));
2555
2556       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm),
2557                    redirect_edge_var_map_block (vm));
2558     }
2559
2560   redirect_edge_var_map_clear (old_edge);
2561 }
2562
2563 /* Returns the basic block after which the new basic block created
2564    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2565    near its "logical" location.  This is of most help to humans looking
2566    at debugging dumps.  */
2567
2568 static basic_block
2569 split_edge_bb_loc (edge edge_in)
2570 {
2571   basic_block dest = edge_in->dest;
2572   basic_block dest_prev = dest->prev_bb;
2573
2574   if (dest_prev)
2575     {
2576       edge e = find_edge (dest_prev, dest);
2577       if (e && !(e->flags & EDGE_COMPLEX))
2578         return edge_in->src;
2579     }
2580   return dest_prev;
2581 }
2582
2583 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2584    Abort on abnormal edges.  */
2585
2586 static basic_block
2587 gimple_split_edge (edge edge_in)
2588 {
2589   basic_block new_bb, after_bb, dest;
2590   edge new_edge, e;
2591
2592   /* Abnormal edges cannot be split.  */
2593   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2594
2595   dest = edge_in->dest;
2596
2597   after_bb = split_edge_bb_loc (edge_in);
2598
2599   new_bb = create_empty_bb (after_bb);
2600   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2601   new_bb->count = edge_in->count;
2602   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2603   new_edge->probability = REG_BR_PROB_BASE;
2604   new_edge->count = edge_in->count;
2605
2606   e = redirect_edge_and_branch (edge_in, new_bb);
2607   gcc_assert (e == edge_in);
2608   reinstall_phi_args (new_edge, e);
2609
2610   return new_bb;
2611 }
2612
2613
2614 /* Verify properties of the address expression T with base object BASE.  */
2615
2616 static tree
2617 verify_address (tree t, tree base)
2618 {
2619   bool old_constant;
2620   bool old_side_effects;
2621   bool new_constant;
2622   bool new_side_effects;
2623
2624   old_constant = TREE_CONSTANT (t);
2625   old_side_effects = TREE_SIDE_EFFECTS (t);
2626
2627   recompute_tree_invariant_for_addr_expr (t);
2628   new_side_effects = TREE_SIDE_EFFECTS (t);
2629   new_constant = TREE_CONSTANT (t);
2630
2631   if (old_constant != new_constant)
2632     {
2633       error ("constant not recomputed when ADDR_EXPR changed");
2634       return t;
2635     }
2636   if (old_side_effects != new_side_effects)
2637     {
2638       error ("side effects not recomputed when ADDR_EXPR changed");
2639       return t;
2640     }
2641
2642   if (!(TREE_CODE (base) == VAR_DECL
2643         || TREE_CODE (base) == PARM_DECL
2644         || TREE_CODE (base) == RESULT_DECL))
2645     return NULL_TREE;
2646
2647   if (DECL_GIMPLE_REG_P (base))
2648     {
2649       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2650       return base;
2651     }
2652
2653   return NULL_TREE;
2654 }
2655
2656 /* Callback for walk_tree, check that all elements with address taken are
2657    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2658    inside a PHI node.  */
2659
2660 static tree
2661 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2662 {
2663   tree t = *tp, x;
2664
2665   if (TYPE_P (t))
2666     *walk_subtrees = 0;
2667
2668   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2669 #define CHECK_OP(N, MSG) \
2670   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2671        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2672
2673   switch (TREE_CODE (t))
2674     {
2675     case SSA_NAME:
2676       if (SSA_NAME_IN_FREE_LIST (t))
2677         {
2678           error ("SSA name in freelist but still referenced");
2679           return *tp;
2680         }
2681       break;
2682
2683     case INDIRECT_REF:
2684       error ("INDIRECT_REF in gimple IL");
2685       return t;
2686
2687     case MEM_REF:
2688       x = TREE_OPERAND (t, 0);
2689       if (!POINTER_TYPE_P (TREE_TYPE (x))
2690           || !is_gimple_mem_ref_addr (x))
2691         {
2692           error ("invalid first operand of MEM_REF");
2693           return x;
2694         }
2695       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2696           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2697         {
2698           error ("invalid offset operand of MEM_REF");
2699           return TREE_OPERAND (t, 1);
2700         }
2701       if (TREE_CODE (x) == ADDR_EXPR
2702           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2703         return x;
2704       *walk_subtrees = 0;
2705       break;
2706
2707     case ASSERT_EXPR:
2708       x = fold (ASSERT_EXPR_COND (t));
2709       if (x == boolean_false_node)
2710         {
2711           error ("ASSERT_EXPR with an always-false condition");
2712           return *tp;
2713         }
2714       break;
2715
2716     case MODIFY_EXPR:
2717       error ("MODIFY_EXPR not expected while having tuples");
2718       return *tp;
2719
2720     case ADDR_EXPR:
2721       {
2722         tree tem;
2723
2724         gcc_assert (is_gimple_address (t));
2725
2726         /* Skip any references (they will be checked when we recurse down the
2727            tree) and ensure that any variable used as a prefix is marked
2728            addressable.  */
2729         for (x = TREE_OPERAND (t, 0);
2730              handled_component_p (x);
2731              x = TREE_OPERAND (x, 0))
2732           ;
2733
2734         if ((tem = verify_address (t, x)))
2735           return tem;
2736
2737         if (!(TREE_CODE (x) == VAR_DECL
2738               || TREE_CODE (x) == PARM_DECL
2739               || TREE_CODE (x) == RESULT_DECL))
2740           return NULL;
2741
2742         if (!TREE_ADDRESSABLE (x))
2743           {
2744             error ("address taken, but ADDRESSABLE bit not set");
2745             return x;
2746           }
2747
2748         break;
2749       }
2750
2751     case COND_EXPR:
2752       x = COND_EXPR_COND (t);
2753       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2754         {
2755           error ("non-integral used in condition");
2756           return x;
2757         }
2758       if (!is_gimple_condexpr (x))
2759         {
2760           error ("invalid conditional operand");
2761           return x;
2762         }
2763       break;
2764
2765     case NON_LVALUE_EXPR:
2766     case TRUTH_NOT_EXPR:
2767       gcc_unreachable ();
2768
2769     CASE_CONVERT:
2770     case FIX_TRUNC_EXPR:
2771     case FLOAT_EXPR:
2772     case NEGATE_EXPR:
2773     case ABS_EXPR:
2774     case BIT_NOT_EXPR:
2775       CHECK_OP (0, "invalid operand to unary operator");
2776       break;
2777
2778     case REALPART_EXPR:
2779     case IMAGPART_EXPR:
2780     case COMPONENT_REF:
2781     case ARRAY_REF:
2782     case ARRAY_RANGE_REF:
2783     case BIT_FIELD_REF:
2784     case VIEW_CONVERT_EXPR:
2785       /* We have a nest of references.  Verify that each of the operands
2786          that determine where to reference is either a constant or a variable,
2787          verify that the base is valid, and then show we've already checked
2788          the subtrees.  */
2789       while (handled_component_p (t))
2790         {
2791           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2792             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2793           else if (TREE_CODE (t) == ARRAY_REF
2794                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2795             {
2796               CHECK_OP (1, "invalid array index");
2797               if (TREE_OPERAND (t, 2))
2798                 CHECK_OP (2, "invalid array lower bound");
2799               if (TREE_OPERAND (t, 3))
2800                 CHECK_OP (3, "invalid array stride");
2801             }
2802           else if (TREE_CODE (t) == BIT_FIELD_REF)
2803             {
2804               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2805                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2806                 {
2807                   error ("invalid position or size operand to BIT_FIELD_REF");
2808                   return t;
2809                 }
2810               if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2811                   && (TYPE_PRECISION (TREE_TYPE (t))
2812                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2813                 {
2814                   error ("integral result type precision does not match "
2815                          "field size of BIT_FIELD_REF");
2816                   return t;
2817                 }
2818               else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2819                        && !AGGREGATE_TYPE_P (TREE_TYPE (t))
2820                        && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2821                        && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2822                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2823                 {
2824                   error ("mode precision of non-integral result does not "
2825                          "match field size of BIT_FIELD_REF");
2826                   return t;
2827                 }
2828             }
2829
2830           t = TREE_OPERAND (t, 0);
2831         }
2832
2833       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2834         {
2835           error ("invalid reference prefix");
2836           return t;
2837         }
2838       *walk_subtrees = 0;
2839       break;
2840     case PLUS_EXPR:
2841     case MINUS_EXPR:
2842       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2843          POINTER_PLUS_EXPR. */
2844       if (POINTER_TYPE_P (TREE_TYPE (t)))
2845         {
2846           error ("invalid operand to plus/minus, type is a pointer");
2847           return t;
2848         }
2849       CHECK_OP (0, "invalid operand to binary operator");
2850       CHECK_OP (1, "invalid operand to binary operator");
2851       break;
2852
2853     case POINTER_PLUS_EXPR:
2854       /* Check to make sure the first operand is a pointer or reference type. */
2855       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2856         {
2857           error ("invalid operand to pointer plus, first operand is not a pointer");
2858           return t;
2859         }
2860       /* Check to make sure the second operand is a ptrofftype.  */
2861       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2862         {
2863           error ("invalid operand to pointer plus, second operand is not an "
2864                  "integer type of appropriate width");
2865           return t;
2866         }
2867       /* FALLTHROUGH */
2868     case LT_EXPR:
2869     case LE_EXPR:
2870     case GT_EXPR:
2871     case GE_EXPR:
2872     case EQ_EXPR:
2873     case NE_EXPR:
2874     case UNORDERED_EXPR:
2875     case ORDERED_EXPR:
2876     case UNLT_EXPR:
2877     case UNLE_EXPR:
2878     case UNGT_EXPR:
2879     case UNGE_EXPR:
2880     case UNEQ_EXPR:
2881     case LTGT_EXPR:
2882     case MULT_EXPR:
2883     case TRUNC_DIV_EXPR:
2884     case CEIL_DIV_EXPR:
2885     case FLOOR_DIV_EXPR:
2886     case ROUND_DIV_EXPR:
2887     case TRUNC_MOD_EXPR:
2888     case CEIL_MOD_EXPR:
2889     case FLOOR_MOD_EXPR:
2890     case ROUND_MOD_EXPR:
2891     case RDIV_EXPR:
2892     case EXACT_DIV_EXPR:
2893     case MIN_EXPR:
2894     case MAX_EXPR:
2895     case LSHIFT_EXPR:
2896     case RSHIFT_EXPR:
2897     case LROTATE_EXPR:
2898     case RROTATE_EXPR:
2899     case BIT_IOR_EXPR:
2900     case BIT_XOR_EXPR:
2901     case BIT_AND_EXPR:
2902       CHECK_OP (0, "invalid operand to binary operator");
2903       CHECK_OP (1, "invalid operand to binary operator");
2904       break;
2905
2906     case CONSTRUCTOR:
2907       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2908         *walk_subtrees = 0;
2909       break;
2910
2911     case CASE_LABEL_EXPR:
2912       if (CASE_CHAIN (t))
2913         {
2914           error ("invalid CASE_CHAIN");
2915           return t;
2916         }
2917       break;
2918
2919     default:
2920       break;
2921     }
2922   return NULL;
2923
2924 #undef CHECK_OP
2925 }
2926
2927
2928 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2929    Returns true if there is an error, otherwise false.  */
2930
2931 static bool
2932 verify_types_in_gimple_min_lval (tree expr)
2933 {
2934   tree op;
2935
2936   if (is_gimple_id (expr))
2937     return false;
2938
2939   if (TREE_CODE (expr) != TARGET_MEM_REF
2940       && TREE_CODE (expr) != MEM_REF)
2941     {
2942       error ("invalid expression for min lvalue");
2943       return true;
2944     }
2945
2946   /* TARGET_MEM_REFs are strange beasts.  */
2947   if (TREE_CODE (expr) == TARGET_MEM_REF)
2948     return false;
2949
2950   op = TREE_OPERAND (expr, 0);
2951   if (!is_gimple_val (op))
2952     {
2953       error ("invalid operand in indirect reference");
2954       debug_generic_stmt (op);
2955       return true;
2956     }
2957   /* Memory references now generally can involve a value conversion.  */
2958
2959   return false;
2960 }
2961
2962 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2963    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2964    if there is an error, otherwise false.  */
2965
2966 static bool
2967 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2968 {
2969   while (handled_component_p (expr))
2970     {
2971       tree op = TREE_OPERAND (expr, 0);
2972
2973       if (TREE_CODE (expr) == ARRAY_REF
2974           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2975         {
2976           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2977               || (TREE_OPERAND (expr, 2)
2978                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2979               || (TREE_OPERAND (expr, 3)
2980                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2981             {
2982               error ("invalid operands to array reference");
2983               debug_generic_stmt (expr);
2984               return true;
2985             }
2986         }
2987
2988       /* Verify if the reference array element types are compatible.  */
2989       if (TREE_CODE (expr) == ARRAY_REF
2990           && !useless_type_conversion_p (TREE_TYPE (expr),
2991                                          TREE_TYPE (TREE_TYPE (op))))
2992         {
2993           error ("type mismatch in array reference");
2994           debug_generic_stmt (TREE_TYPE (expr));
2995           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2996           return true;
2997         }
2998       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2999           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3000                                          TREE_TYPE (TREE_TYPE (op))))
3001         {
3002           error ("type mismatch in array range reference");
3003           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3004           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3005           return true;
3006         }
3007
3008       if ((TREE_CODE (expr) == REALPART_EXPR
3009            || TREE_CODE (expr) == IMAGPART_EXPR)
3010           && !useless_type_conversion_p (TREE_TYPE (expr),
3011                                          TREE_TYPE (TREE_TYPE (op))))
3012         {
3013           error ("type mismatch in real/imagpart reference");
3014           debug_generic_stmt (TREE_TYPE (expr));
3015           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3016           return true;
3017         }
3018
3019       if (TREE_CODE (expr) == COMPONENT_REF
3020           && !useless_type_conversion_p (TREE_TYPE (expr),
3021                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3022         {
3023           error ("type mismatch in component reference");
3024           debug_generic_stmt (TREE_TYPE (expr));
3025           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3026           return true;
3027         }
3028
3029       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3030         {
3031           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3032              that their operand is not an SSA name or an invariant when
3033              requiring an lvalue (this usually means there is a SRA or IPA-SRA
3034              bug).  Otherwise there is nothing to verify, gross mismatches at
3035              most invoke undefined behavior.  */
3036           if (require_lvalue
3037               && (TREE_CODE (op) == SSA_NAME
3038                   || is_gimple_min_invariant (op)))
3039             {
3040               error ("conversion of an SSA_NAME on the left hand side");
3041               debug_generic_stmt (expr);
3042               return true;
3043             }
3044           else if (TREE_CODE (op) == SSA_NAME
3045                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3046             {
3047               error ("conversion of register to a different size");
3048               debug_generic_stmt (expr);
3049               return true;
3050             }
3051           else if (!handled_component_p (op))
3052             return false;
3053         }
3054
3055       expr = op;
3056     }
3057
3058   if (TREE_CODE (expr) == MEM_REF)
3059     {
3060       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3061         {
3062           error ("invalid address operand in MEM_REF");
3063           debug_generic_stmt (expr);
3064           return true;
3065         }
3066       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3067           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3068         {
3069           error ("invalid offset operand in MEM_REF");
3070           debug_generic_stmt (expr);
3071           return true;
3072         }
3073     }
3074   else if (TREE_CODE (expr) == TARGET_MEM_REF)
3075     {
3076       if (!TMR_BASE (expr)
3077           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3078         {
3079           error ("invalid address operand in TARGET_MEM_REF");
3080           return true;
3081         }
3082       if (!TMR_OFFSET (expr)
3083           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3084           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3085         {
3086           error ("invalid offset operand in TARGET_MEM_REF");
3087           debug_generic_stmt (expr);
3088           return true;
3089         }
3090     }
3091
3092   return ((require_lvalue || !is_gimple_min_invariant (expr))
3093           && verify_types_in_gimple_min_lval (expr));
3094 }
3095
3096 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3097    list of pointer-to types that is trivially convertible to DEST.  */
3098
3099 static bool
3100 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3101 {
3102   tree src;
3103
3104   if (!TYPE_POINTER_TO (src_obj))
3105     return true;
3106
3107   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3108     if (useless_type_conversion_p (dest, src))
3109       return true;
3110
3111   return false;
3112 }
3113
3114 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3115    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3116
3117 static bool
3118 valid_fixed_convert_types_p (tree type1, tree type2)
3119 {
3120   return (FIXED_POINT_TYPE_P (type1)
3121           && (INTEGRAL_TYPE_P (type2)
3122               || SCALAR_FLOAT_TYPE_P (type2)
3123               || FIXED_POINT_TYPE_P (type2)));
3124 }
3125
3126 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3127    is a problem, otherwise false.  */
3128
3129 static bool
3130 verify_gimple_call (gimple stmt)
3131 {
3132   tree fn = gimple_call_fn (stmt);
3133   tree fntype, fndecl;
3134   unsigned i;
3135
3136   if (gimple_call_internal_p (stmt))
3137     {
3138       if (fn)
3139         {
3140           error ("gimple call has two targets");
3141           debug_generic_stmt (fn);
3142           return true;
3143         }
3144     }
3145   else
3146     {
3147       if (!fn)
3148         {
3149           error ("gimple call has no target");
3150           return true;
3151         }
3152     }
3153
3154   if (fn && !is_gimple_call_addr (fn))
3155     {
3156       error ("invalid function in gimple call");
3157       debug_generic_stmt (fn);
3158       return true;
3159     }
3160
3161   if (fn
3162       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3163           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3164               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3165     {
3166       error ("non-function in gimple call");
3167       return true;
3168     }
3169
3170    fndecl = gimple_call_fndecl (stmt);
3171    if (fndecl
3172        && TREE_CODE (fndecl) == FUNCTION_DECL
3173        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3174        && !DECL_PURE_P (fndecl)
3175        && !TREE_READONLY (fndecl))
3176      {
3177        error ("invalid pure const state for function");
3178        return true;
3179      }
3180
3181   if (gimple_call_lhs (stmt)
3182       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3183           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3184     {
3185       error ("invalid LHS in gimple call");
3186       return true;
3187     }
3188
3189   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3190     {
3191       error ("LHS in noreturn call");
3192       return true;
3193     }
3194
3195   fntype = gimple_call_fntype (stmt);
3196   if (fntype
3197       && gimple_call_lhs (stmt)
3198       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3199                                      TREE_TYPE (fntype))
3200       /* ???  At least C++ misses conversions at assignments from
3201          void * call results.
3202          ???  Java is completely off.  Especially with functions
3203          returning java.lang.Object.
3204          For now simply allow arbitrary pointer type conversions.  */
3205       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3206            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3207     {
3208       error ("invalid conversion in gimple call");
3209       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3210       debug_generic_stmt (TREE_TYPE (fntype));
3211       return true;
3212     }
3213
3214   if (gimple_call_chain (stmt)
3215       && !is_gimple_val (gimple_call_chain (stmt)))
3216     {
3217       error ("invalid static chain in gimple call");
3218       debug_generic_stmt (gimple_call_chain (stmt));
3219       return true;
3220     }
3221
3222   /* If there is a static chain argument, this should not be an indirect
3223      call, and the decl should have DECL_STATIC_CHAIN set.  */
3224   if (gimple_call_chain (stmt))
3225     {
3226       if (!gimple_call_fndecl (stmt))
3227         {
3228           error ("static chain in indirect gimple call");
3229           return true;
3230         }
3231       fn = TREE_OPERAND (fn, 0);
3232
3233       if (!DECL_STATIC_CHAIN (fn))
3234         {
3235           error ("static chain with function that doesn%'t use one");
3236           return true;
3237         }
3238     }
3239
3240   /* ???  The C frontend passes unpromoted arguments in case it
3241      didn't see a function declaration before the call.  So for now
3242      leave the call arguments mostly unverified.  Once we gimplify
3243      unit-at-a-time we have a chance to fix this.  */
3244
3245   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3246     {
3247       tree arg = gimple_call_arg (stmt, i);
3248       if ((is_gimple_reg_type (TREE_TYPE (arg))
3249            && !is_gimple_val (arg))
3250           || (!is_gimple_reg_type (TREE_TYPE (arg))
3251               && !is_gimple_lvalue (arg)))
3252         {
3253           error ("invalid argument to gimple call");
3254           debug_generic_expr (arg);
3255           return true;
3256         }
3257     }
3258
3259   return false;
3260 }
3261
3262 /* Verifies the gimple comparison with the result type TYPE and
3263    the operands OP0 and OP1.  */
3264
3265 static bool
3266 verify_gimple_comparison (tree type, tree op0, tree op1)
3267 {
3268   tree op0_type = TREE_TYPE (op0);
3269   tree op1_type = TREE_TYPE (op1);
3270
3271   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3272     {
3273       error ("invalid operands in gimple comparison");
3274       return true;
3275     }
3276
3277   /* For comparisons we do not have the operations type as the
3278      effective type the comparison is carried out in.  Instead
3279      we require that either the first operand is trivially
3280      convertible into the second, or the other way around.
3281      Because we special-case pointers to void we allow
3282      comparisons of pointers with the same mode as well.  */
3283   if (!useless_type_conversion_p (op0_type, op1_type)
3284       && !useless_type_conversion_p (op1_type, op0_type)
3285       && (!POINTER_TYPE_P (op0_type)
3286           || !POINTER_TYPE_P (op1_type)
3287           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3288     {
3289       error ("mismatching comparison operand types");
3290       debug_generic_expr (op0_type);
3291       debug_generic_expr (op1_type);
3292       return true;
3293     }
3294
3295   /* The resulting type of a comparison may be an effective boolean type.  */
3296   if (INTEGRAL_TYPE_P (type)
3297       && (TREE_CODE (type) == BOOLEAN_TYPE
3298           || TYPE_PRECISION (type) == 1))
3299     ;
3300   /* Or an integer vector type with the same size and element count
3301      as the comparison operand types.  */
3302   else if (TREE_CODE (type) == VECTOR_TYPE
3303            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3304     {
3305       if (TREE_CODE (op0_type) != VECTOR_TYPE
3306           || TREE_CODE (op1_type) != VECTOR_TYPE)
3307         {
3308           error ("non-vector operands in vector comparison");
3309           debug_generic_expr (op0_type);
3310           debug_generic_expr (op1_type);
3311           return true;
3312         }
3313
3314       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3315           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3316               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3317         {
3318           error ("invalid vector comparison resulting type");
3319           debug_generic_expr (type);
3320           return true;
3321         }
3322     }
3323   else
3324     {
3325       error ("bogus comparison result type");
3326       debug_generic_expr (type);
3327       return true;
3328     }
3329
3330   return false;
3331 }
3332
3333 /* Verify a gimple assignment statement STMT with an unary rhs.
3334    Returns true if anything is wrong.  */
3335
3336 static bool
3337 verify_gimple_assign_unary (gimple stmt)
3338 {
3339   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3340   tree lhs = gimple_assign_lhs (stmt);
3341   tree lhs_type = TREE_TYPE (lhs);
3342   tree rhs1 = gimple_assign_rhs1 (stmt);
3343   tree rhs1_type = TREE_TYPE (rhs1);
3344
3345   if (!is_gimple_reg (lhs))
3346     {
3347       error ("non-register as LHS of unary operation");
3348       return true;
3349     }
3350
3351   if (!is_gimple_val (rhs1))
3352     {
3353       error ("invalid operand in unary operation");
3354       return true;
3355     }
3356
3357   /* First handle conversions.  */
3358   switch (rhs_code)
3359     {
3360     CASE_CONVERT:
3361       {
3362         /* Allow conversions from pointer type to integral type only if
3363            there is no sign or zero extension involved.
3364            For targets were the precision of ptrofftype doesn't match that
3365            of pointers we need to allow arbitrary conversions to ptrofftype.  */
3366         if ((POINTER_TYPE_P (lhs_type)
3367              && INTEGRAL_TYPE_P (rhs1_type))
3368             || (POINTER_TYPE_P (rhs1_type)
3369                 && INTEGRAL_TYPE_P (lhs_type)
3370                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3371                     || ptrofftype_p (sizetype))))
3372           return false;
3373
3374         /* Allow conversion from integral to offset type and vice versa.  */
3375         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3376              && INTEGRAL_TYPE_P (rhs1_type))
3377             || (INTEGRAL_TYPE_P (lhs_type)
3378                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3379           return false;
3380
3381         /* Otherwise assert we are converting between types of the
3382            same kind.  */
3383         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3384           {
3385             error ("invalid types in nop conversion");
3386             debug_generic_expr (lhs_type);
3387             debug_generic_expr (rhs1_type);
3388             return true;
3389           }
3390
3391         return false;
3392       }
3393
3394     case ADDR_SPACE_CONVERT_EXPR:
3395       {
3396         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3397             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3398                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3399           {
3400             error ("invalid types in address space conversion");
3401             debug_generic_expr (lhs_type);
3402             debug_generic_expr (rhs1_type);
3403             return true;
3404           }
3405
3406         return false;
3407       }
3408
3409     case FIXED_CONVERT_EXPR:
3410       {
3411         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3412             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3413           {
3414             error ("invalid types in fixed-point conversion");
3415             debug_generic_expr (lhs_type);
3416             debug_generic_expr (rhs1_type);
3417             return true;
3418           }
3419
3420         return false;
3421       }
3422
3423     case FLOAT_EXPR:
3424       {
3425         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3426             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3427                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3428           {
3429             error ("invalid types in conversion to floating point");
3430             debug_generic_expr (lhs_type);
3431             debug_generic_expr (rhs1_type);
3432             return true;
3433           }
3434
3435         return false;
3436       }
3437
3438     case FIX_TRUNC_EXPR:
3439       {
3440         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3441             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3442                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3443           {
3444             error ("invalid types in conversion to integer");
3445             debug_generic_expr (lhs_type);
3446             debug_generic_expr (rhs1_type);
3447             return true;
3448           }
3449
3450         return false;
3451       }
3452
3453     case VEC_UNPACK_HI_EXPR:
3454     case VEC_UNPACK_LO_EXPR:
3455     case REDUC_MAX_EXPR:
3456     case REDUC_MIN_EXPR:
3457     case REDUC_PLUS_EXPR:
3458     case VEC_UNPACK_FLOAT_HI_EXPR:
3459     case VEC_UNPACK_FLOAT_LO_EXPR:
3460       /* FIXME.  */
3461       return false;
3462
3463     case NEGATE_EXPR:
3464     case ABS_EXPR:
3465     case BIT_NOT_EXPR:
3466     case PAREN_EXPR:
3467     case NON_LVALUE_EXPR:
3468     case CONJ_EXPR:
3469       break;
3470
3471     default:
3472       gcc_unreachable ();
3473     }
3474
3475   /* For the remaining codes assert there is no conversion involved.  */
3476   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3477     {
3478       error ("non-trivial conversion in unary operation");
3479       debug_generic_expr (lhs_type);
3480       debug_generic_expr (rhs1_type);
3481       return true;
3482     }
3483
3484   return false;
3485 }
3486
3487 /* Verify a gimple assignment statement STMT with a binary rhs.
3488    Returns true if anything is wrong.  */
3489
3490 static bool
3491 verify_gimple_assign_binary (gimple stmt)
3492 {
3493   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3494   tree lhs = gimple_assign_lhs (stmt);
3495   tree lhs_type = TREE_TYPE (lhs);
3496   tree rhs1 = gimple_assign_rhs1 (stmt);
3497   tree rhs1_type = TREE_TYPE (rhs1);
3498   tree rhs2 = gimple_assign_rhs2 (stmt);
3499   tree rhs2_type = TREE_TYPE (rhs2);
3500
3501   if (!is_gimple_reg (lhs))
3502     {
3503       error ("non-register as LHS of binary operation");
3504       return true;
3505     }
3506
3507   if (!is_gimple_val (rhs1)
3508       || !is_gimple_val (rhs2))
3509     {
3510       error ("invalid operands in binary operation");
3511       return true;
3512     }
3513
3514   /* First handle operations that involve different types.  */
3515   switch (rhs_code)
3516     {
3517     case COMPLEX_EXPR:
3518       {
3519         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3520             || !(INTEGRAL_TYPE_P (rhs1_type)
3521                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3522             || !(INTEGRAL_TYPE_P (rhs2_type)
3523                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3524           {
3525             error ("type mismatch in complex expression");
3526             debug_generic_expr (lhs_type);
3527             debug_generic_expr (rhs1_type);
3528             debug_generic_expr (rhs2_type);
3529             return true;
3530           }
3531
3532         return false;
3533       }
3534
3535     case LSHIFT_EXPR:
3536     case RSHIFT_EXPR:
3537     case LROTATE_EXPR:
3538     case RROTATE_EXPR:
3539       {
3540         /* Shifts and rotates are ok on integral types, fixed point
3541            types and integer vector types.  */
3542         if ((!INTEGRAL_TYPE_P (rhs1_type)
3543              && !FIXED_POINT_TYPE_P (rhs1_type)
3544              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3545                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3546             || (!INTEGRAL_TYPE_P (rhs2_type)
3547                 /* Vector shifts of vectors are also ok.  */
3548                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3549                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3550                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3551                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3552             || !useless_type_conversion_p (lhs_type, rhs1_type))
3553           {
3554             error ("type mismatch in shift expression");
3555             debug_generic_expr (lhs_type);
3556             debug_generic_expr (rhs1_type);
3557             debug_generic_expr (rhs2_type);
3558             return true;
3559           }
3560
3561         return false;
3562       }
3563
3564     case VEC_LSHIFT_EXPR:
3565     case VEC_RSHIFT_EXPR:
3566       {
3567         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3568             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3569                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3570                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3571                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3572             || (!INTEGRAL_TYPE_P (rhs2_type)
3573                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3574                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3575             || !useless_type_conversion_p (lhs_type, rhs1_type))
3576           {
3577             error ("type mismatch in vector shift expression");
3578             debug_generic_expr (lhs_type);
3579             debug_generic_expr (rhs1_type);
3580             debug_generic_expr (rhs2_type);
3581             return true;
3582           }
3583         /* For shifting a vector of non-integral components we
3584            only allow shifting by a constant multiple of the element size.  */
3585         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3586             && (TREE_CODE (rhs2) != INTEGER_CST
3587                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3588                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3589           {
3590             error ("non-element sized vector shift of floating point vector");
3591             return true;
3592           }
3593
3594         return false;
3595       }
3596
3597     case WIDEN_LSHIFT_EXPR:
3598       {
3599         if (!INTEGRAL_TYPE_P (lhs_type)
3600             || !INTEGRAL_TYPE_P (rhs1_type)
3601             || TREE_CODE (rhs2) != INTEGER_CST
3602             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3603           {
3604             error ("type mismatch in widening vector shift expression");
3605             debug_generic_expr (lhs_type);
3606             debug_generic_expr (rhs1_type);
3607             debug_generic_expr (rhs2_type);
3608             return true;
3609           }
3610
3611         return false;
3612       }
3613
3614     case VEC_WIDEN_LSHIFT_HI_EXPR:
3615     case VEC_WIDEN_LSHIFT_LO_EXPR:
3616       {
3617         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3618             || TREE_CODE (lhs_type) != VECTOR_TYPE
3619             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3620             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3621             || TREE_CODE (rhs2) != INTEGER_CST
3622             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3623                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3624           {
3625             error ("type mismatch in widening vector shift expression");
3626             debug_generic_expr (lhs_type);
3627             debug_generic_expr (rhs1_type);
3628             debug_generic_expr (rhs2_type);
3629             return true;
3630           }
3631
3632         return false;
3633       }
3634
3635     case PLUS_EXPR:
3636     case MINUS_EXPR:
3637       {
3638         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3639            ???  This just makes the checker happy and may not be what is
3640            intended.  */
3641         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3642             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3643           {
3644             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3645                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3646               {
3647                 error ("invalid non-vector operands to vector valued plus");
3648                 return true;
3649               }
3650             lhs_type = TREE_TYPE (lhs_type);
3651             rhs1_type = TREE_TYPE (rhs1_type);
3652             rhs2_type = TREE_TYPE (rhs2_type);
3653             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3654                the pointer to 2nd place.  */
3655             if (POINTER_TYPE_P (rhs2_type))
3656               {
3657                 tree tem = rhs1_type;
3658                 rhs1_type = rhs2_type;
3659                 rhs2_type = tem;
3660               }
3661             goto do_pointer_plus_expr_check;
3662           }
3663         if (POINTER_TYPE_P (lhs_type)
3664             || POINTER_TYPE_P (rhs1_type)
3665             || POINTER_TYPE_P (rhs2_type))
3666           {
3667             error ("invalid (pointer) operands to plus/minus");
3668             return true;
3669           }
3670
3671         /* Continue with generic binary expression handling.  */
3672         break;
3673       }
3674
3675     case POINTER_PLUS_EXPR:
3676       {
3677 do_pointer_plus_expr_check:
3678         if (!POINTER_TYPE_P (rhs1_type)
3679             || !useless_type_conversion_p (lhs_type, rhs1_type)
3680             || !ptrofftype_p (rhs2_type))
3681           {
3682             error ("type mismatch in pointer plus expression");
3683             debug_generic_stmt (lhs_type);
3684             debug_generic_stmt (rhs1_type);
3685             debug_generic_stmt (rhs2_type);
3686             return true;
3687           }
3688
3689         return false;
3690       }
3691
3692     case TRUTH_ANDIF_EXPR:
3693     case TRUTH_ORIF_EXPR:
3694     case TRUTH_AND_EXPR:
3695     case TRUTH_OR_EXPR:
3696     case TRUTH_XOR_EXPR:
3697
3698       gcc_unreachable ();
3699
3700     case LT_EXPR:
3701     case LE_EXPR:
3702     case GT_EXPR:
3703     case GE_EXPR:
3704     case EQ_EXPR:
3705     case NE_EXPR:
3706     case UNORDERED_EXPR:
3707     case ORDERED_EXPR:
3708     case UNLT_EXPR:
3709     case UNLE_EXPR:
3710     case UNGT_EXPR:
3711     case UNGE_EXPR:
3712     case UNEQ_EXPR:
3713     case LTGT_EXPR:
3714       /* Comparisons are also binary, but the result type is not
3715          connected to the operand types.  */
3716       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3717
3718     case WIDEN_MULT_EXPR:
3719       if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3720         return true;
3721       return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3722               || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3723
3724     case WIDEN_SUM_EXPR:
3725     case VEC_WIDEN_MULT_HI_EXPR:
3726     case VEC_WIDEN_MULT_LO_EXPR:
3727     case VEC_PACK_TRUNC_EXPR:
3728     case VEC_PACK_SAT_EXPR:
3729     case VEC_PACK_FIX_TRUNC_EXPR:
3730       /* FIXME.  */
3731       return false;
3732
3733     case MULT_EXPR:
3734     case MULT_HIGHPART_EXPR:
3735     case TRUNC_DIV_EXPR:
3736     case CEIL_DIV_EXPR:
3737     case FLOOR_DIV_EXPR:
3738     case ROUND_DIV_EXPR:
3739     case TRUNC_MOD_EXPR:
3740     case CEIL_MOD_EXPR:
3741     case FLOOR_MOD_EXPR:
3742     case ROUND_MOD_EXPR:
3743     case RDIV_EXPR:
3744     case EXACT_DIV_EXPR:
3745     case MIN_EXPR:
3746     case MAX_EXPR:
3747     case BIT_IOR_EXPR:
3748     case BIT_XOR_EXPR:
3749     case BIT_AND_EXPR:
3750       /* Continue with generic binary expression handling.  */
3751       break;
3752
3753     default:
3754       gcc_unreachable ();
3755     }
3756
3757   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3758       || !useless_type_conversion_p (lhs_type, rhs2_type))
3759     {
3760       error ("type mismatch in binary expression");
3761       debug_generic_stmt (lhs_type);
3762       debug_generic_stmt (rhs1_type);
3763       debug_generic_stmt (rhs2_type);
3764       return true;
3765     }
3766
3767   return false;
3768 }
3769
3770 /* Verify a gimple assignment statement STMT with a ternary rhs.
3771    Returns true if anything is wrong.  */
3772
3773 static bool
3774 verify_gimple_assign_ternary (gimple stmt)
3775 {
3776   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3777   tree lhs = gimple_assign_lhs (stmt);
3778   tree lhs_type = TREE_TYPE (lhs);
3779   tree rhs1 = gimple_assign_rhs1 (stmt);
3780   tree rhs1_type = TREE_TYPE (rhs1);
3781   tree rhs2 = gimple_assign_rhs2 (stmt);
3782   tree rhs2_type = TREE_TYPE (rhs2);
3783   tree rhs3 = gimple_assign_rhs3 (stmt);
3784   tree rhs3_type = TREE_TYPE (rhs3);
3785
3786   if (!is_gimple_reg (lhs))
3787     {
3788       error ("non-register as LHS of ternary operation");
3789       return true;
3790     }
3791
3792   if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3793        ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3794       || !is_gimple_val (rhs2)
3795       || !is_gimple_val (rhs3))
3796     {
3797       error ("invalid operands in ternary operation");
3798       return true;
3799     }
3800
3801   /* First handle operations that involve different types.  */
3802   switch (rhs_code)
3803     {
3804     case WIDEN_MULT_PLUS_EXPR:
3805     case WIDEN_MULT_MINUS_EXPR:
3806       if ((!INTEGRAL_TYPE_P (rhs1_type)
3807            && !FIXED_POINT_TYPE_P (rhs1_type))
3808           || !useless_type_conversion_p (rhs1_type, rhs2_type)
3809           || !useless_type_conversion_p (lhs_type, rhs3_type)
3810           || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3811           || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3812         {
3813           error ("type mismatch in widening multiply-accumulate expression");
3814           debug_generic_expr (lhs_type);
3815           debug_generic_expr (rhs1_type);
3816           debug_generic_expr (rhs2_type);
3817           debug_generic_expr (rhs3_type);
3818           return true;
3819         }
3820       break;
3821
3822     case FMA_EXPR:
3823       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3824           || !useless_type_conversion_p (lhs_type, rhs2_type)
3825           || !useless_type_conversion_p (lhs_type, rhs3_type))
3826         {
3827           error ("type mismatch in fused multiply-add expression");
3828           debug_generic_expr (lhs_type);
3829           debug_generic_expr (rhs1_type);
3830           debug_generic_expr (rhs2_type);
3831           debug_generic_expr (rhs3_type);
3832           return true;
3833         }
3834       break;
3835
3836     case COND_EXPR:
3837     case VEC_COND_EXPR:
3838       if (!useless_type_conversion_p (lhs_type, rhs2_type)
3839           || !useless_type_conversion_p (lhs_type, rhs3_type))
3840         {
3841           error ("type mismatch in conditional expression");
3842           debug_generic_expr (lhs_type);
3843           debug_generic_expr (rhs2_type);
3844           debug_generic_expr (rhs3_type);
3845           return true;
3846         }
3847       break;
3848
3849     case VEC_PERM_EXPR:
3850       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3851           || !useless_type_conversion_p (lhs_type, rhs2_type))
3852         {
3853           error ("type mismatch in vector permute expression");
3854           debug_generic_expr (lhs_type);
3855           debug_generic_expr (rhs1_type);
3856           debug_generic_expr (rhs2_type);
3857           debug_generic_expr (rhs3_type);
3858           return true;
3859         }
3860
3861       if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3862           || TREE_CODE (rhs2_type) != VECTOR_TYPE
3863           || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3864         {
3865           error ("vector types expected in vector permute expression");
3866           debug_generic_expr (lhs_type);
3867           debug_generic_expr (rhs1_type);
3868           debug_generic_expr (rhs2_type);
3869           debug_generic_expr (rhs3_type);
3870           return true;
3871         }
3872
3873       if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3874           || TYPE_VECTOR_SUBPARTS (rhs2_type)
3875              != TYPE_VECTOR_SUBPARTS (rhs3_type)
3876           || TYPE_VECTOR_SUBPARTS (rhs3_type)
3877              != TYPE_VECTOR_SUBPARTS (lhs_type))
3878         {
3879           error ("vectors with different element number found "
3880                  "in vector permute expression");
3881           debug_generic_expr (lhs_type);
3882           debug_generic_expr (rhs1_type);
3883           debug_generic_expr (rhs2_type);
3884           debug_generic_expr (rhs3_type);
3885           return true;
3886         }
3887
3888       if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3889           || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3890              != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3891         {
3892           error ("invalid mask type in vector permute expression");
3893           debug_generic_expr (lhs_type);
3894           debug_generic_expr (rhs1_type);
3895           debug_generic_expr (rhs2_type);
3896           debug_generic_expr (rhs3_type);
3897           return true;
3898         }
3899
3900       return false;
3901
3902     case DOT_PROD_EXPR:
3903     case REALIGN_LOAD_EXPR:
3904       /* FIXME.  */
3905       return false;
3906
3907     default:
3908       gcc_unreachable ();
3909     }
3910   return false;
3911 }
3912
3913 /* Verify a gimple assignment statement STMT with a single rhs.
3914    Returns true if anything is wrong.  */
3915
3916 static bool
3917 verify_gimple_assign_single (gimple stmt)
3918 {
3919   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3920   tree lhs = gimple_assign_lhs (stmt);
3921   tree lhs_type = TREE_TYPE (lhs);
3922   tree rhs1 = gimple_assign_rhs1 (stmt);
3923   tree rhs1_type = TREE_TYPE (rhs1);
3924   bool res = false;
3925
3926   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3927     {
3928       error ("non-trivial conversion at assignment");
3929       debug_generic_expr (lhs_type);
3930       debug_generic_expr (rhs1_type);
3931       return true;
3932     }
3933
3934   if (handled_component_p (lhs))
3935     res |= verify_types_in_gimple_reference (lhs, true);
3936
3937   /* Special codes we cannot handle via their class.  */
3938   switch (rhs_code)
3939     {
3940     case ADDR_EXPR:
3941       {
3942         tree op = TREE_OPERAND (rhs1, 0);
3943         if (!is_gimple_addressable (op))
3944           {
3945             error ("invalid operand in unary expression");
3946             return true;
3947           }
3948
3949         /* Technically there is no longer a need for matching types, but
3950            gimple hygiene asks for this check.  In LTO we can end up
3951            combining incompatible units and thus end up with addresses
3952            of globals that change their type to a common one.  */
3953         if (!in_lto_p
3954             && !types_compatible_p (TREE_TYPE (op),
3955                                     TREE_TYPE (TREE_TYPE (rhs1)))
3956             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3957                                                           TREE_TYPE (op)))
3958           {
3959             error ("type mismatch in address expression");
3960             debug_generic_stmt (TREE_TYPE (rhs1));
3961             debug_generic_stmt (TREE_TYPE (op));
3962             return true;
3963           }
3964
3965         return verify_types_in_gimple_reference (op, true);
3966       }
3967
3968     /* tcc_reference  */
3969     case INDIRECT_REF:
3970       error ("INDIRECT_REF in gimple IL");
3971       return true;
3972
3973     case COMPONENT_REF:
3974     case BIT_FIELD_REF:
3975     case ARRAY_REF:
3976     case ARRAY_RANGE_REF:
3977     case VIEW_CONVERT_EXPR:
3978     case REALPART_EXPR:
3979     case IMAGPART_EXPR:
3980     case TARGET_MEM_REF:
3981     case MEM_REF:
3982       if (!is_gimple_reg (lhs)
3983           && is_gimple_reg_type (TREE_TYPE (lhs)))
3984         {
3985           error ("invalid rhs for gimple memory store");
3986           debug_generic_stmt (lhs);
3987           debug_generic_stmt (rhs1);
3988           return true;
3989         }
3990       return res || verify_types_in_gimple_reference (rhs1, false);
3991
3992     /* tcc_constant  */
3993     case SSA_NAME:
3994     case INTEGER_CST:
3995     case REAL_CST:
3996     case FIXED_CST:
3997     case COMPLEX_CST:
3998     case VECTOR_CST:
3999     case STRING_CST:
4000       return res;
4001
4002     /* tcc_declaration  */
4003     case CONST_DECL:
4004       return res;
4005     case VAR_DECL:
4006     case PARM_DECL:
4007       if (!is_gimple_reg (lhs)
4008           && !is_gimple_reg (rhs1)
4009           && is_gimple_reg_type (TREE_TYPE (lhs)))
4010         {
4011           error ("invalid rhs for gimple memory store");
4012           debug_generic_stmt (lhs);
4013           debug_generic_stmt (rhs1);
4014           return true;
4015         }
4016       return res;
4017
4018     case CONSTRUCTOR:
4019     case OBJ_TYPE_REF:
4020     case ASSERT_EXPR:
4021     case WITH_SIZE_EXPR:
4022       /* FIXME.  */
4023       return res;
4024
4025     default:;
4026     }
4027
4028   return res;
4029 }
4030
4031 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
4032    is a problem, otherwise false.  */
4033
4034 static bool
4035 verify_gimple_assign (gimple stmt)
4036 {
4037   switch (gimple_assign_rhs_class (stmt))
4038     {
4039     case GIMPLE_SINGLE_RHS:
4040       return verify_gimple_assign_single (stmt);
4041
4042     case GIMPLE_UNARY_RHS:
4043       return verify_gimple_assign_unary (stmt);
4044
4045     case GIMPLE_BINARY_RHS:
4046       return verify_gimple_assign_binary (stmt);
4047
4048     case GIMPLE_TERNARY_RHS:
4049       return verify_gimple_assign_ternary (stmt);
4050
4051     default:
4052       gcc_unreachable ();
4053     }
4054 }
4055
4056 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
4057    is a problem, otherwise false.  */
4058
4059 static bool
4060 verify_gimple_return (gimple stmt)
4061 {
4062   tree op = gimple_return_retval (stmt);
4063   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4064
4065   /* We cannot test for present return values as we do not fix up missing
4066      return values from the original source.  */
4067   if (op == NULL)
4068     return false;
4069
4070   if (!is_gimple_val (op)
4071       && TREE_CODE (op) != RESULT_DECL)
4072     {
4073       error ("invalid operand in return statement");
4074       debug_generic_stmt (op);
4075       return true;
4076     }
4077
4078   if ((TREE_CODE (op) == RESULT_DECL
4079        && DECL_BY_REFERENCE (op))
4080       || (TREE_CODE (op) == SSA_NAME
4081           && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4082           && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4083     op = TREE_TYPE (op);
4084
4085   if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4086     {
4087       error ("invalid conversion in return statement");
4088       debug_generic_stmt (restype);
4089       debug_generic_stmt (TREE_TYPE (op));
4090       return true;
4091     }
4092
4093   return false;
4094 }
4095
4096
4097 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4098    is a problem, otherwise false.  */
4099
4100 static bool
4101 verify_gimple_goto (gimple stmt)
4102 {
4103   tree dest = gimple_goto_dest (stmt);
4104
4105   /* ???  We have two canonical forms of direct goto destinations, a
4106      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4107   if (TREE_CODE (dest) != LABEL_DECL
4108       && (!is_gimple_val (dest)
4109           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4110     {
4111       error ("goto destination is neither a label nor a pointer");
4112       return true;
4113     }
4114
4115   return false;
4116 }
4117
4118 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4119    is a problem, otherwise false.  */
4120
4121 static bool
4122 verify_gimple_switch (gimple stmt)
4123 {
4124   unsigned int i, n;
4125   tree elt, prev_upper_bound = NULL_TREE;
4126   tree index_type, elt_type = NULL_TREE;
4127
4128   if (!is_gimple_val (gimple_switch_index (stmt)))
4129     {
4130       error ("invalid operand to switch statement");
4131       debug_generic_stmt (gimple_switch_index (stmt));
4132       return true;
4133     }
4134
4135   index_type = TREE_TYPE (gimple_switch_index (stmt));
4136   if (! INTEGRAL_TYPE_P (index_type))
4137     {
4138       error ("non-integral type switch statement");
4139       debug_generic_expr (index_type);
4140       return true;
4141     }
4142
4143   elt = gimple_switch_default_label (stmt);
4144   if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4145     {
4146       error ("invalid default case label in switch statement");
4147       debug_generic_expr (elt);
4148       return true;
4149     }
4150
4151   n = gimple_switch_num_labels (stmt);
4152   for (i = 1; i < n; i++)
4153     {
4154       elt = gimple_switch_label (stmt, i);
4155
4156       if (! CASE_LOW (elt))
4157         {
4158           error ("invalid case label in switch statement");
4159           debug_generic_expr (elt);
4160           return true;
4161         }
4162       if (CASE_HIGH (elt)
4163           && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4164         {
4165           error ("invalid case range in switch statement");
4166           debug_generic_expr (elt);
4167           return true;
4168         }
4169
4170       if (elt_type)
4171         {
4172           if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4173               || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4174             {
4175               error ("type mismatch for case label in switch statement");
4176               debug_generic_expr (elt);
4177               return true;
4178             }
4179         }
4180       else
4181         {
4182           elt_type = TREE_TYPE (CASE_LOW (elt));
4183           if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4184             {
4185               error ("type precision mismatch in switch statement");
4186               return true;
4187             }
4188         }
4189
4190       if (prev_upper_bound)
4191         {
4192           if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4193             {
4194               error ("case labels not sorted in switch statement");
4195               return true;
4196             }
4197         }
4198
4199       prev_upper_bound = CASE_HIGH (elt);
4200       if (! prev_upper_bound)
4201         prev_upper_bound = CASE_LOW (elt);
4202     }
4203
4204   return false;
4205 }
4206
4207 /* Verify a gimple debug statement STMT.
4208    Returns true if anything is wrong.  */
4209
4210 static bool
4211 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4212 {
4213   /* There isn't much that could be wrong in a gimple debug stmt.  A
4214      gimple debug bind stmt, for example, maps a tree, that's usually
4215      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4216      component or member of an aggregate type, to another tree, that
4217      can be an arbitrary expression.  These stmts expand into debug
4218      insns, and are converted to debug notes by var-tracking.c.  */
4219   return false;
4220 }
4221
4222 /* Verify a gimple label statement STMT.
4223    Returns true if anything is wrong.  */
4224
4225 static bool
4226 verify_gimple_label (gimple stmt)
4227 {
4228   tree decl = gimple_label_label (stmt);
4229   int uid;
4230   bool err = false;
4231
4232   if (TREE_CODE (decl) != LABEL_DECL)
4233     return true;
4234
4235   uid = LABEL_DECL_UID (decl);
4236   if (cfun->cfg
4237       && (uid == -1
4238           || VEC_index (basic_block,
4239                         label_to_block_map, uid) != gimple_bb (stmt)))
4240     {
4241       error ("incorrect entry in label_to_block_map");
4242       err |= true;
4243     }
4244
4245   uid = EH_LANDING_PAD_NR (decl);
4246   if (uid)
4247     {
4248       eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4249       if (decl != lp->post_landing_pad)
4250         {
4251           error ("incorrect setting of landing pad number");
4252           err |= true;
4253         }
4254     }
4255
4256   return err;
4257 }
4258
4259 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4260    error, otherwise false.  */
4261
4262 static bool
4263 verify_gimple_stmt (gimple stmt)
4264 {
4265   switch (gimple_code (stmt))
4266     {
4267     case GIMPLE_ASSIGN:
4268       return verify_gimple_assign (stmt);
4269
4270     case GIMPLE_LABEL:
4271       return verify_gimple_label (stmt);
4272
4273     case GIMPLE_CALL:
4274       return verify_gimple_call (stmt);
4275
4276     case GIMPLE_COND:
4277       if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4278         {
4279           error ("invalid comparison code in gimple cond");
4280           return true;
4281         }
4282       if (!(!gimple_cond_true_label (stmt)
4283             || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4284           || !(!gimple_cond_false_label (stmt)
4285                || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4286         {
4287           error ("invalid labels in gimple cond");
4288           return true;
4289         }
4290
4291       return verify_gimple_comparison (boolean_type_node,
4292                                        gimple_cond_lhs (stmt),
4293                                        gimple_cond_rhs (stmt));
4294
4295     case GIMPLE_GOTO:
4296       return verify_gimple_goto (stmt);
4297
4298     case GIMPLE_SWITCH:
4299       return verify_gimple_switch (stmt);
4300
4301     case GIMPLE_RETURN:
4302       return verify_gimple_return (stmt);
4303
4304     case GIMPLE_ASM:
4305       return false;
4306
4307     case GIMPLE_TRANSACTION:
4308       return verify_gimple_transaction (stmt);
4309
4310     /* Tuples that do not have tree operands.  */
4311     case GIMPLE_NOP:
4312     case GIMPLE_PREDICT:
4313     case GIMPLE_RESX:
4314     case GIMPLE_EH_DISPATCH:
4315     case GIMPLE_EH_MUST_NOT_THROW:
4316       return false;
4317
4318     CASE_GIMPLE_OMP:
4319       /* OpenMP directives are validated by the FE and never operated
4320          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4321          non-gimple expressions when the main index variable has had
4322          its address taken.  This does not affect the loop itself
4323          because the header of an GIMPLE_OMP_FOR is merely used to determine
4324          how to setup the parallel iteration.  */
4325       return false;
4326
4327     case GIMPLE_DEBUG:
4328       return verify_gimple_debug (stmt);
4329
4330     default:
4331       gcc_unreachable ();
4332     }
4333 }
4334
4335 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4336    and false otherwise.  */
4337
4338 static bool
4339 verify_gimple_phi (gimple phi)
4340 {
4341   bool err = false;
4342   unsigned i;
4343   tree phi_result = gimple_phi_result (phi);
4344   bool virtual_p;
4345
4346   if (!phi_result)
4347     {
4348       error ("invalid PHI result");
4349       return true;
4350     }
4351
4352   virtual_p = !is_gimple_reg (phi_result);
4353   if (TREE_CODE (phi_result) != SSA_NAME
4354       || (virtual_p
4355           && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4356     {
4357       error ("invalid PHI result");
4358       err = true;
4359     }
4360
4361   for (i = 0; i < gimple_phi_num_args (phi); i++)
4362     {
4363       tree t = gimple_phi_arg_def (phi, i);
4364
4365       if (!t)
4366         {
4367           error ("missing PHI def");
4368           err |= true;
4369           continue;
4370         }
4371       /* Addressable variables do have SSA_NAMEs but they
4372          are not considered gimple values.  */
4373       else if ((TREE_CODE (t) == SSA_NAME
4374                 && virtual_p != !is_gimple_reg (t))
4375                || (virtual_p
4376                    && (TREE_CODE (t) != SSA_NAME
4377                        || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4378                || (!virtual_p
4379                    && !is_gimple_val (t)))
4380         {
4381           error ("invalid PHI argument");
4382           debug_generic_expr (t);
4383           err |= true;
4384         }
4385 #ifdef ENABLE_TYPES_CHECKING
4386       if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4387         {
4388           error ("incompatible types in PHI argument %u", i);
4389           debug_generic_stmt (TREE_TYPE (phi_result));
4390           debug_generic_stmt (TREE_TYPE (t));
4391           err |= true;
4392         }
4393 #endif
4394     }
4395
4396   return err;
4397 }
4398
4399 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4400
4401 static bool
4402 verify_gimple_in_seq_2 (gimple_seq stmts)
4403 {
4404   gimple_stmt_iterator ittr;
4405   bool err = false;
4406
4407   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4408     {
4409       gimple stmt = gsi_stmt (ittr);
4410
4411       switch (gimple_code (stmt))
4412         {
4413         case GIMPLE_BIND:
4414           err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4415           break;
4416
4417         case GIMPLE_TRY:
4418           err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4419           err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4420           break;
4421
4422         case GIMPLE_EH_FILTER:
4423           err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4424           break;
4425
4426         case GIMPLE_EH_ELSE:
4427           err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4428           err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4429           break;
4430
4431         case GIMPLE_CATCH:
4432           err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4433           break;
4434
4435         case GIMPLE_TRANSACTION:
4436           err |= verify_gimple_transaction (stmt);
4437           break;
4438
4439         default:
4440           {
4441             bool err2 = verify_gimple_stmt (stmt);
4442             if (err2)
4443               debug_gimple_stmt (stmt);
4444             err |= err2;
4445           }
4446         }
4447     }
4448
4449   return err;
4450 }
4451
4452 /* Verify the contents of a GIMPLE_TRANSACTION.  Returns true if there
4453    is a problem, otherwise false.  */
4454
4455 static bool
4456 verify_gimple_transaction (gimple stmt)
4457 {
4458   tree lab = gimple_transaction_label (stmt);
4459   if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4460     return true;
4461   return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4462 }
4463
4464
4465 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4466
4467 DEBUG_FUNCTION void
4468 verify_gimple_in_seq (gimple_seq stmts)
4469 {
4470   timevar_push (TV_TREE_STMT_VERIFY);
4471   if (verify_gimple_in_seq_2 (stmts))
4472     internal_error ("verify_gimple failed");
4473   timevar_pop (TV_TREE_STMT_VERIFY);
4474 }
4475
4476 /* Return true when the T can be shared.  */
4477
4478 bool
4479 tree_node_can_be_shared (tree t)
4480 {
4481   if (IS_TYPE_OR_DECL_P (t)
4482       || is_gimple_min_invariant (t)
4483       || TREE_CODE (t) == SSA_NAME
4484       || t == error_mark_node
4485       || TREE_CODE (t) == IDENTIFIER_NODE)
4486     return true;
4487
4488   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4489     return true;
4490
4491   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4492            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4493          || TREE_CODE (t) == COMPONENT_REF
4494          || TREE_CODE (t) == REALPART_EXPR
4495          || TREE_CODE (t) == IMAGPART_EXPR)
4496     t = TREE_OPERAND (t, 0);
4497
4498   if (DECL_P (t))
4499     return true;
4500
4501   return false;
4502 }
4503
4504 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4505
4506 static tree
4507 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4508 {
4509   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4510   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4511
4512   if (tree_node_can_be_shared (*tp))
4513     {
4514       *walk_subtrees = false;
4515       return NULL;
4516     }
4517
4518   if (pointer_set_insert (visited, *tp))
4519     return *tp;
4520
4521   return NULL;
4522 }
4523
4524 static bool eh_error_found;
4525 static int
4526 verify_eh_throw_stmt_node (void **slot, void *data)
4527 {
4528   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4529   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4530
4531   if (!pointer_set_contains (visited, node->stmt))
4532     {
4533       error ("dead STMT in EH table");
4534       debug_gimple_stmt (node->stmt);
4535       eh_error_found = true;
4536     }
4537   return 1;
4538 }
4539
4540 /* Verify the GIMPLE statements in the CFG of FN.  */
4541
4542 DEBUG_FUNCTION void
4543 verify_gimple_in_cfg (struct function *fn)
4544 {
4545   basic_block bb;
4546   bool err = false;
4547   struct pointer_set_t *visited, *visited_stmts;
4548
4549   timevar_push (TV_TREE_STMT_VERIFY);
4550   visited = pointer_set_create ();
4551   visited_stmts = pointer_set_create ();
4552
4553   FOR_EACH_BB_FN (bb, fn)
4554     {
4555       gimple_stmt_iterator gsi;
4556
4557       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4558         {
4559           gimple phi = gsi_stmt (gsi);
4560           bool err2 = false;
4561           unsigned i;
4562
4563           pointer_set_insert (visited_stmts, phi);
4564
4565           if (gimple_bb (phi) != bb)
4566             {
4567               error ("gimple_bb (phi) is set to a wrong basic block");
4568               err2 = true;
4569             }
4570
4571           err2 |= verify_gimple_phi (phi);
4572
4573           for (i = 0; i < gimple_phi_num_args (phi); i++)
4574             {
4575               tree arg = gimple_phi_arg_def (phi, i);
4576               tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL);
4577               if (addr)
4578                 {
4579                   error ("incorrect sharing of tree nodes");
4580                   debug_generic_expr (addr);
4581                   err2 |= true;
4582                 }
4583             }
4584
4585           if (err2)
4586             debug_gimple_stmt (phi);
4587           err |= err2;
4588         }
4589
4590       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4591         {
4592           gimple stmt = gsi_stmt (gsi);
4593           bool err2 = false;
4594           struct walk_stmt_info wi;
4595           tree addr;
4596           int lp_nr;
4597
4598           pointer_set_insert (visited_stmts, stmt);
4599
4600           if (gimple_bb (stmt) != bb)
4601             {
4602               error ("gimple_bb (stmt) is set to a wrong basic block");
4603               err2 = true;
4604             }
4605
4606           err2 |= verify_gimple_stmt (stmt);
4607
4608           memset (&wi, 0, sizeof (wi));
4609           wi.info = (void *) visited;
4610           addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4611           if (addr)
4612             {
4613               error ("incorrect sharing of tree nodes");
4614               debug_generic_expr (addr);
4615               err2 |= true;
4616             }
4617
4618           /* ???  Instead of not checking these stmts at all the walker
4619              should know its context via wi.  */
4620           if (!is_gimple_debug (stmt)
4621               && !is_gimple_omp (stmt))
4622             {
4623               memset (&wi, 0, sizeof (wi));
4624               addr = walk_gimple_op (stmt, verify_expr, &wi);
4625               if (addr)
4626                 {
4627                   debug_generic_expr (addr);
4628                   inform (gimple_location (stmt), "in statement");
4629                   err2 |= true;
4630                 }
4631             }
4632
4633           /* If the statement is marked as part of an EH region, then it is
4634              expected that the statement could throw.  Verify that when we
4635              have optimizations that simplify statements such that we prove
4636              that they cannot throw, that we update other data structures
4637              to match.  */
4638           lp_nr = lookup_stmt_eh_lp (stmt);
4639           if (lp_nr != 0)
4640             {
4641               if (!stmt_could_throw_p (stmt))
4642                 {
4643                   error ("statement marked for throw, but doesn%'t");
4644                   err2 |= true;
4645                 }
4646               else if (lp_nr > 0
4647                        && !gsi_one_before_end_p (gsi)
4648                        && stmt_can_throw_internal (stmt))
4649                 {
4650                   error ("statement marked for throw in middle of block");
4651                   err2 |= true;
4652                 }
4653             }
4654
4655           if (err2)
4656             debug_gimple_stmt (stmt);
4657           err |= err2;
4658         }
4659     }
4660
4661   eh_error_found = false;
4662   if (get_eh_throw_stmt_table (cfun))
4663     htab_traverse (get_eh_throw_stmt_table (cfun),
4664                    verify_eh_throw_stmt_node,
4665                    visited_stmts);
4666
4667   if (err || eh_error_found)
4668     internal_error ("verify_gimple failed");
4669
4670   pointer_set_destroy (visited);
4671   pointer_set_destroy (visited_stmts);
4672   verify_histograms ();
4673   timevar_pop (TV_TREE_STMT_VERIFY);
4674 }
4675
4676
4677 /* Verifies that the flow information is OK.  */
4678
4679 static int
4680 gimple_verify_flow_info (void)
4681 {
4682   int err = 0;
4683   basic_block bb;
4684   gimple_stmt_iterator gsi;
4685   gimple stmt;
4686   edge e;
4687   edge_iterator ei;
4688
4689   if (ENTRY_BLOCK_PTR->il.gimple.seq || ENTRY_BLOCK_PTR->il.gimple.phi_nodes)
4690     {
4691       error ("ENTRY_BLOCK has IL associated with it");
4692       err = 1;
4693     }
4694
4695   if (EXIT_BLOCK_PTR->il.gimple.seq || EXIT_BLOCK_PTR->il.gimple.phi_nodes)
4696     {
4697       error ("EXIT_BLOCK has IL associated with it");
4698       err = 1;
4699     }
4700
4701   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4702     if (e->flags & EDGE_FALLTHRU)
4703       {
4704         error ("fallthru to exit from bb %d", e->src->index);
4705         err = 1;
4706       }
4707
4708   FOR_EACH_BB (bb)
4709     {
4710       bool found_ctrl_stmt = false;
4711
4712       stmt = NULL;
4713
4714       /* Skip labels on the start of basic block.  */
4715       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4716         {
4717           tree label;
4718           gimple prev_stmt = stmt;
4719
4720           stmt = gsi_stmt (gsi);
4721
4722           if (gimple_code (stmt) != GIMPLE_LABEL)
4723             break;
4724
4725           label = gimple_label_label (stmt);
4726           if (prev_stmt && DECL_NONLOCAL (label))
4727             {
4728               error ("nonlocal label ");
4729               print_generic_expr (stderr, label, 0);
4730               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4731                        bb->index);
4732               err = 1;
4733             }
4734
4735           if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4736             {
4737               error ("EH landing pad label ");
4738               print_generic_expr (stderr, label, 0);
4739               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4740                        bb->index);
4741               err = 1;
4742             }
4743
4744           if (label_to_block (label) != bb)
4745             {
4746               error ("label ");
4747               print_generic_expr (stderr, label, 0);
4748               fprintf (stderr, " to block does not match in bb %d",
4749                        bb->index);
4750               err = 1;
4751             }
4752
4753           if (decl_function_context (label) != current_function_decl)
4754             {
4755               error ("label ");
4756               print_generic_expr (stderr, label, 0);
4757               fprintf (stderr, " has incorrect context in bb %d",
4758                        bb->index);
4759               err = 1;
4760             }
4761         }
4762
4763       /* Verify that body of basic block BB is free of control flow.  */
4764       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4765         {
4766           gimple stmt = gsi_stmt (gsi);
4767
4768           if (found_ctrl_stmt)
4769             {
4770               error ("control flow in the middle of basic block %d",
4771                      bb->index);
4772               err = 1;
4773             }
4774
4775           if (stmt_ends_bb_p (stmt))
4776             found_ctrl_stmt = true;
4777
4778           if (gimple_code (stmt) == GIMPLE_LABEL)
4779             {
4780               error ("label ");
4781               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4782               fprintf (stderr, " in the middle of basic block %d", bb->index);
4783               err = 1;
4784             }
4785         }
4786
4787       gsi = gsi_last_bb (bb);
4788       if (gsi_end_p (gsi))
4789         continue;
4790
4791       stmt = gsi_stmt (gsi);
4792
4793       if (gimple_code (stmt) == GIMPLE_LABEL)
4794         continue;
4795
4796       err |= verify_eh_edges (stmt);
4797
4798       if (is_ctrl_stmt (stmt))
4799         {
4800           FOR_EACH_EDGE (e, ei, bb->succs)
4801             if (e->flags & EDGE_FALLTHRU)
4802               {
4803                 error ("fallthru edge after a control statement in bb %d",
4804                        bb->index);
4805                 err = 1;
4806               }
4807         }
4808
4809       if (gimple_code (stmt) != GIMPLE_COND)
4810         {
4811           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4812              after anything else but if statement.  */
4813           FOR_EACH_EDGE (e, ei, bb->succs)
4814             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4815               {
4816                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4817                        bb->index);
4818                 err = 1;
4819               }
4820         }
4821
4822       switch (gimple_code (stmt))
4823         {
4824         case GIMPLE_COND:
4825           {
4826             edge true_edge;
4827             edge false_edge;
4828
4829             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4830
4831             if (!true_edge
4832                 || !false_edge
4833                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4834                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4835                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4836                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4837                 || EDGE_COUNT (bb->succs) >= 3)
4838               {
4839                 error ("wrong outgoing edge flags at end of bb %d",
4840                        bb->index);
4841                 err = 1;
4842               }
4843           }
4844           break;
4845
4846         case GIMPLE_GOTO:
4847           if (simple_goto_p (stmt))
4848             {
4849               error ("explicit goto at end of bb %d", bb->index);
4850               err = 1;
4851             }
4852           else
4853             {
4854               /* FIXME.  We should double check that the labels in the
4855                  destination blocks have their address taken.  */
4856               FOR_EACH_EDGE (e, ei, bb->succs)
4857                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4858                                  | EDGE_FALSE_VALUE))
4859                     || !(e->flags & EDGE_ABNORMAL))
4860                   {
4861                     error ("wrong outgoing edge flags at end of bb %d",
4862                            bb->index);
4863                     err = 1;
4864                   }
4865             }
4866           break;
4867
4868         case GIMPLE_CALL:
4869           if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4870             break;
4871           /* ... fallthru ... */
4872         case GIMPLE_RETURN:
4873           if (!single_succ_p (bb)
4874               || (single_succ_edge (bb)->flags
4875                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4876                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4877             {
4878               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4879               err = 1;
4880             }
4881           if (single_succ (bb) != EXIT_BLOCK_PTR)
4882             {
4883               error ("return edge does not point to exit in bb %d",
4884                      bb->index);
4885               err = 1;
4886             }
4887           break;
4888
4889         case GIMPLE_SWITCH:
4890           {
4891             tree prev;
4892             edge e;
4893             size_t i, n;
4894
4895             n = gimple_switch_num_labels (stmt);
4896
4897             /* Mark all the destination basic blocks.  */
4898             for (i = 0; i < n; ++i)
4899               {
4900                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4901                 basic_block label_bb = label_to_block (lab);
4902                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4903                 label_bb->aux = (void *)1;
4904               }
4905
4906             /* Verify that the case labels are sorted.  */
4907             prev = gimple_switch_label (stmt, 0);
4908             for (i = 1; i < n; ++i)
4909               {
4910                 tree c = gimple_switch_label (stmt, i);
4911                 if (!CASE_LOW (c))
4912                   {
4913                     error ("found default case not at the start of "
4914                            "case vector");
4915                     err = 1;
4916                     continue;
4917                   }
4918                 if (CASE_LOW (prev)
4919                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4920                   {
4921                     error ("case labels not sorted: ");
4922                     print_generic_expr (stderr, prev, 0);
4923                     fprintf (stderr," is greater than ");
4924                     print_generic_expr (stderr, c, 0);
4925                     fprintf (stderr," but comes before it.\n");
4926                     err = 1;
4927                   }
4928                 prev = c;
4929               }
4930             /* VRP will remove the default case if it can prove it will
4931                never be executed.  So do not verify there always exists
4932                a default case here.  */
4933
4934             FOR_EACH_EDGE (e, ei, bb->succs)
4935               {
4936                 if (!e->dest->aux)
4937                   {
4938                     error ("extra outgoing edge %d->%d",
4939                            bb->index, e->dest->index);
4940                     err = 1;
4941                   }
4942
4943                 e->dest->aux = (void *)2;
4944                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4945                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4946                   {
4947                     error ("wrong outgoing edge flags at end of bb %d",
4948                            bb->index);
4949                     err = 1;
4950                   }
4951               }
4952
4953             /* Check that we have all of them.  */
4954             for (i = 0; i < n; ++i)
4955               {
4956                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4957                 basic_block label_bb = label_to_block (lab);
4958
4959                 if (label_bb->aux != (void *)2)
4960                   {
4961                     error ("missing edge %i->%i", bb->index, label_bb->index);
4962                     err = 1;
4963                   }
4964               }
4965
4966             FOR_EACH_EDGE (e, ei, bb->succs)
4967               e->dest->aux = (void *)0;
4968           }
4969           break;
4970
4971         case GIMPLE_EH_DISPATCH:
4972           err |= verify_eh_dispatch_edge (stmt);
4973           break;
4974
4975         default:
4976           break;
4977         }
4978     }
4979
4980   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4981     verify_dominators (CDI_DOMINATORS);
4982
4983   return err;
4984 }
4985
4986
4987 /* Updates phi nodes after creating a forwarder block joined
4988    by edge FALLTHRU.  */
4989
4990 static void
4991 gimple_make_forwarder_block (edge fallthru)
4992 {
4993   edge e;
4994   edge_iterator ei;
4995   basic_block dummy, bb;
4996   tree var;
4997   gimple_stmt_iterator gsi;
4998
4999   dummy = fallthru->src;
5000   bb = fallthru->dest;
5001
5002   if (single_pred_p (bb))
5003     return;
5004
5005   /* If we redirected a branch we must create new PHI nodes at the
5006      start of BB.  */
5007   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5008     {
5009       gimple phi, new_phi;
5010
5011       phi = gsi_stmt (gsi);
5012       var = gimple_phi_result (phi);
5013       new_phi = create_phi_node (var, bb);
5014       SSA_NAME_DEF_STMT (var) = new_phi;
5015       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
5016       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5017                    UNKNOWN_LOCATION, NULL);
5018     }
5019
5020   /* Add the arguments we have stored on edges.  */
5021   FOR_EACH_EDGE (e, ei, bb->preds)
5022     {
5023       if (e == fallthru)
5024         continue;
5025
5026       flush_pending_stmts (e);
5027     }
5028 }
5029
5030
5031 /* Return a non-special label in the head of basic block BLOCK.
5032    Create one if it doesn't exist.  */
5033
5034 tree
5035 gimple_block_label (basic_block bb)
5036 {
5037   gimple_stmt_iterator i, s = gsi_start_bb (bb);
5038   bool first = true;
5039   tree label;
5040   gimple stmt;
5041
5042   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5043     {
5044       stmt = gsi_stmt (i);
5045       if (gimple_code (stmt) != GIMPLE_LABEL)
5046         break;
5047       label = gimple_label_label (stmt);
5048       if (!DECL_NONLOCAL (label))
5049         {
5050           if (!first)
5051             gsi_move_before (&i, &s);
5052           return label;
5053         }
5054     }
5055
5056   label = create_artificial_label (UNKNOWN_LOCATION);
5057   stmt = gimple_build_label (label);
5058   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5059   return label;
5060 }
5061
5062
5063 /* Attempt to perform edge redirection by replacing a possibly complex
5064    jump instruction by a goto or by removing the jump completely.
5065    This can apply only if all edges now point to the same block.  The
5066    parameters and return values are equivalent to
5067    redirect_edge_and_branch.  */
5068
5069 static edge
5070 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5071 {
5072   basic_block src = e->src;
5073   gimple_stmt_iterator i;
5074   gimple stmt;
5075
5076   /* We can replace or remove a complex jump only when we have exactly
5077      two edges.  */
5078   if (EDGE_COUNT (src->succs) != 2
5079       /* Verify that all targets will be TARGET.  Specifically, the
5080          edge that is not E must also go to TARGET.  */
5081       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5082     return NULL;
5083
5084   i = gsi_last_bb (src);
5085   if (gsi_end_p (i))
5086     return NULL;
5087
5088   stmt = gsi_stmt (i);
5089
5090   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5091     {
5092       gsi_remove (&i, true);
5093       e = ssa_redirect_edge (e, target);
5094       e->flags = EDGE_FALLTHRU;
5095       return e;
5096     }
5097
5098   return NULL;
5099 }
5100
5101
5102 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
5103    edge representing the redirected branch.  */
5104
5105 static edge
5106 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5107 {
5108   basic_block bb = e->src;
5109   gimple_stmt_iterator gsi;
5110   edge ret;
5111   gimple stmt;
5112
5113   if (e->flags & EDGE_ABNORMAL)
5114     return NULL;
5115
5116   if (e->dest == dest)
5117     return NULL;
5118
5119   if (e->flags & EDGE_EH)
5120     return redirect_eh_edge (e, dest);
5121
5122   if (e->src != ENTRY_BLOCK_PTR)
5123     {
5124       ret = gimple_try_redirect_by_replacing_jump (e, dest);
5125       if (ret)
5126         return ret;
5127     }
5128
5129   gsi = gsi_last_bb (bb);
5130   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5131
5132   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5133     {
5134     case GIMPLE_COND:
5135       /* For COND_EXPR, we only need to redirect the edge.  */
5136       break;
5137
5138     case GIMPLE_GOTO:
5139       /* No non-abnormal edges should lead from a non-simple goto, and
5140          simple ones should be represented implicitly.  */
5141       gcc_unreachable ();
5142
5143     case GIMPLE_SWITCH:
5144       {
5145         tree label = gimple_block_label (dest);
5146         tree cases = get_cases_for_edge (e, stmt);
5147
5148         /* If we have a list of cases associated with E, then use it
5149            as it's a lot faster than walking the entire case vector.  */
5150         if (cases)
5151           {
5152             edge e2 = find_edge (e->src, dest);
5153             tree last, first;
5154
5155             first = cases;
5156             while (cases)
5157               {
5158                 last = cases;
5159                 CASE_LABEL (cases) = label;
5160                 cases = CASE_CHAIN (cases);
5161               }
5162
5163             /* If there was already an edge in the CFG, then we need
5164                to move all the cases associated with E to E2.  */
5165             if (e2)
5166               {
5167                 tree cases2 = get_cases_for_edge (e2, stmt);
5168
5169                 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5170                 CASE_CHAIN (cases2) = first;
5171               }
5172             bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5173           }
5174         else
5175           {
5176             size_t i, n = gimple_switch_num_labels (stmt);
5177
5178             for (i = 0; i < n; i++)
5179               {
5180                 tree elt = gimple_switch_label (stmt, i);
5181                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5182                   CASE_LABEL (elt) = label;
5183               }
5184           }
5185       }
5186       break;
5187
5188     case GIMPLE_ASM:
5189       {
5190         int i, n = gimple_asm_nlabels (stmt);
5191         tree label = NULL;
5192
5193         for (i = 0; i < n; ++i)
5194           {
5195             tree cons = gimple_asm_label_op (stmt, i);
5196             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5197               {
5198                 if (!label)
5199                   label = gimple_block_label (dest);
5200                 TREE_VALUE (cons) = label;
5201               }
5202           }
5203
5204         /* If we didn't find any label matching the former edge in the
5205            asm labels, we must be redirecting the fallthrough
5206            edge.  */
5207         gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5208       }
5209       break;
5210
5211     case GIMPLE_RETURN:
5212       gsi_remove (&gsi, true);
5213       e->flags |= EDGE_FALLTHRU;
5214       break;
5215
5216     case GIMPLE_OMP_RETURN:
5217     case GIMPLE_OMP_CONTINUE:
5218     case GIMPLE_OMP_SECTIONS_SWITCH:
5219     case GIMPLE_OMP_FOR:
5220       /* The edges from OMP constructs can be simply redirected.  */
5221       break;
5222
5223     case GIMPLE_EH_DISPATCH:
5224       if (!(e->flags & EDGE_FALLTHRU))
5225         redirect_eh_dispatch_edge (stmt, e, dest);
5226       break;
5227
5228     case GIMPLE_TRANSACTION:
5229       /* The ABORT edge has a stored label associated with it, otherwise
5230          the edges are simply redirectable.  */
5231       if (e->flags == 0)
5232         gimple_transaction_set_label (stmt, gimple_block_label (dest));
5233       break;
5234
5235     default:
5236       /* Otherwise it must be a fallthru edge, and we don't need to
5237          do anything besides redirecting it.  */
5238       gcc_assert (e->flags & EDGE_FALLTHRU);
5239       break;
5240     }
5241
5242   /* Update/insert PHI nodes as necessary.  */
5243
5244   /* Now update the edges in the CFG.  */
5245   e = ssa_redirect_edge (e, dest);
5246
5247   return e;
5248 }
5249
5250 /* Returns true if it is possible to remove edge E by redirecting
5251    it to the destination of the other edge from E->src.  */
5252
5253 static bool
5254 gimple_can_remove_branch_p (const_edge e)
5255 {
5256   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5257     return false;
5258
5259   return true;
5260 }
5261
5262 /* Simple wrapper, as we can always redirect fallthru edges.  */
5263
5264 static basic_block
5265 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5266 {
5267   e = gimple_redirect_edge_and_branch (e, dest);
5268   gcc_assert (e);
5269
5270   return NULL;
5271 }
5272
5273
5274 /* Splits basic block BB after statement STMT (but at least after the
5275    labels).  If STMT is NULL, BB is split just after the labels.  */
5276
5277 static basic_block
5278 gimple_split_block (basic_block bb, void *stmt)
5279 {
5280   gimple_stmt_iterator gsi;
5281   gimple_stmt_iterator gsi_tgt;
5282   gimple act;
5283   gimple_seq list;
5284   basic_block new_bb;
5285   edge e;
5286   edge_iterator ei;
5287
5288   new_bb = create_empty_bb (bb);
5289
5290   /* Redirect the outgoing edges.  */
5291   new_bb->succs = bb->succs;
5292   bb->succs = NULL;
5293   FOR_EACH_EDGE (e, ei, new_bb->succs)
5294     e->src = new_bb;
5295
5296   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5297     stmt = NULL;
5298
5299   /* Move everything from GSI to the new basic block.  */
5300   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5301     {
5302       act = gsi_stmt (gsi);
5303       if (gimple_code (act) == GIMPLE_LABEL)
5304         continue;
5305
5306       if (!stmt)
5307         break;
5308
5309       if (stmt == act)
5310         {
5311           gsi_next (&gsi);
5312           break;
5313         }
5314     }
5315
5316   if (gsi_end_p (gsi))
5317     return new_bb;
5318
5319   /* Split the statement list - avoid re-creating new containers as this
5320      brings ugly quadratic memory consumption in the inliner.
5321      (We are still quadratic since we need to update stmt BB pointers,
5322      sadly.)  */
5323   gsi_split_seq_before (&gsi, &list);
5324   set_bb_seq (new_bb, list);
5325   for (gsi_tgt = gsi_start (list);
5326        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5327     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5328
5329   return new_bb;
5330 }
5331
5332
5333 /* Moves basic block BB after block AFTER.  */
5334
5335 static bool
5336 gimple_move_block_after (basic_block bb, basic_block after)
5337 {
5338   if (bb->prev_bb == after)
5339     return true;
5340
5341   unlink_block (bb);
5342   link_block (bb, after);
5343
5344   return true;
5345 }
5346
5347
5348 /* Return true if basic_block can be duplicated.  */
5349
5350 static bool
5351 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5352 {
5353   return true;
5354 }
5355
5356 /* Create a duplicate of the basic block BB.  NOTE: This does not
5357    preserve SSA form.  */
5358
5359 static basic_block
5360 gimple_duplicate_bb (basic_block bb)
5361 {
5362   basic_block new_bb;
5363   gimple_stmt_iterator gsi, gsi_tgt;
5364   gimple_seq phis = phi_nodes (bb);
5365   gimple phi, stmt, copy;
5366
5367   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5368
5369   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5370      the incoming edges have not been setup yet.  */
5371   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5372     {
5373       phi = gsi_stmt (gsi);
5374       copy = create_phi_node (gimple_phi_result (phi), new_bb);
5375       create_new_def_for (gimple_phi_result (copy), copy,
5376                           gimple_phi_result_ptr (copy));
5377     }
5378
5379   gsi_tgt = gsi_start_bb (new_bb);
5380   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5381     {
5382       def_operand_p def_p;
5383       ssa_op_iter op_iter;
5384       tree lhs;
5385
5386       stmt = gsi_stmt (gsi);
5387       if (gimple_code (stmt) == GIMPLE_LABEL)
5388         continue;
5389
5390       /* Don't duplicate label debug stmts.  */
5391       if (gimple_debug_bind_p (stmt)
5392           && TREE_CODE (gimple_debug_bind_get_var (stmt))
5393              == LABEL_DECL)
5394         continue;
5395
5396       /* Create a new copy of STMT and duplicate STMT's virtual
5397          operands.  */
5398       copy = gimple_copy (stmt);
5399       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5400
5401       maybe_duplicate_eh_stmt (copy, stmt);
5402       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5403
5404       /* When copying around a stmt writing into a local non-user
5405          aggregate, make sure it won't share stack slot with other
5406          vars.  */
5407       lhs = gimple_get_lhs (stmt);
5408       if (lhs && TREE_CODE (lhs) != SSA_NAME)
5409         {
5410           tree base = get_base_address (lhs);
5411           if (base
5412               && (TREE_CODE (base) == VAR_DECL
5413                   || TREE_CODE (base) == RESULT_DECL)
5414               && DECL_IGNORED_P (base)
5415               && !TREE_STATIC (base)
5416               && !DECL_EXTERNAL (base)
5417               && (TREE_CODE (base) != VAR_DECL
5418                   || !DECL_HAS_VALUE_EXPR_P (base)))
5419             DECL_NONSHAREABLE (base) = 1;
5420         }
5421
5422       /* Create new names for all the definitions created by COPY and
5423          add replacement mappings for each new name.  */
5424       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5425         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5426     }
5427
5428   return new_bb;
5429 }
5430
5431 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5432
5433 static void
5434 add_phi_args_after_copy_edge (edge e_copy)
5435 {
5436   basic_block bb, bb_copy = e_copy->src, dest;
5437   edge e;
5438   edge_iterator ei;
5439   gimple phi, phi_copy;
5440   tree def;
5441   gimple_stmt_iterator psi, psi_copy;
5442
5443   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5444     return;
5445
5446   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5447
5448   if (e_copy->dest->flags & BB_DUPLICATED)
5449     dest = get_bb_original (e_copy->dest);
5450   else
5451     dest = e_copy->dest;
5452
5453   e = find_edge (bb, dest);
5454   if (!e)
5455     {
5456       /* During loop unrolling the target of the latch edge is copied.
5457          In this case we are not looking for edge to dest, but to
5458          duplicated block whose original was dest.  */
5459       FOR_EACH_EDGE (e, ei, bb->succs)
5460         {
5461           if ((e->dest->flags & BB_DUPLICATED)
5462               && get_bb_original (e->dest) == dest)
5463             break;
5464         }
5465
5466       gcc_assert (e != NULL);
5467     }
5468
5469   for (psi = gsi_start_phis (e->dest),
5470        psi_copy = gsi_start_phis (e_copy->dest);
5471        !gsi_end_p (psi);
5472        gsi_next (&psi), gsi_next (&psi_copy))
5473     {
5474       phi = gsi_stmt (psi);
5475       phi_copy = gsi_stmt (psi_copy);
5476       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5477       add_phi_arg (phi_copy, def, e_copy,
5478                    gimple_phi_arg_location_from_edge (phi, e),
5479                    gimple_phi_arg_block_from_edge (phi, e));
5480     }
5481 }
5482
5483
5484 /* Basic block BB_COPY was created by code duplication.  Add phi node
5485    arguments for edges going out of BB_COPY.  The blocks that were
5486    duplicated have BB_DUPLICATED set.  */
5487
5488 void
5489 add_phi_args_after_copy_bb (basic_block bb_copy)
5490 {
5491   edge e_copy;
5492   edge_iterator ei;
5493
5494   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5495     {
5496       add_phi_args_after_copy_edge (e_copy);
5497     }
5498 }
5499
5500 /* Blocks in REGION_COPY array of length N_REGION were created by
5501    duplication of basic blocks.  Add phi node arguments for edges
5502    going from these blocks.  If E_COPY is not NULL, also add
5503    phi node arguments for its destination.*/
5504
5505 void
5506 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5507                          edge e_copy)
5508 {
5509   unsigned i;
5510
5511   for (i = 0; i < n_region; i++)
5512     region_copy[i]->flags |= BB_DUPLICATED;
5513
5514   for (i = 0; i < n_region; i++)
5515     add_phi_args_after_copy_bb (region_copy[i]);
5516   if (e_copy)
5517     add_phi_args_after_copy_edge (e_copy);
5518
5519   for (i = 0; i < n_region; i++)
5520     region_copy[i]->flags &= ~BB_DUPLICATED;
5521 }
5522
5523 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5524    important exit edge EXIT.  By important we mean that no SSA name defined
5525    inside region is live over the other exit edges of the region.  All entry
5526    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5527    to the duplicate of the region.  SSA form, dominance and loop information
5528    is updated.  The new basic blocks are stored to REGION_COPY in the same
5529    order as they had in REGION, provided that REGION_COPY is not NULL.
5530    The function returns false if it is unable to copy the region,
5531    true otherwise.  */
5532
5533 bool
5534 gimple_duplicate_sese_region (edge entry, edge exit,
5535                             basic_block *region, unsigned n_region,
5536                             basic_block *region_copy)
5537 {
5538   unsigned i;
5539   bool free_region_copy = false, copying_header = false;
5540   struct loop *loop = entry->dest->loop_father;
5541   edge exit_copy;
5542   VEC (basic_block, heap) *doms;
5543   edge redirected;
5544   int total_freq = 0, entry_freq = 0;
5545   gcov_type total_count = 0, entry_count = 0;
5546
5547   if (!can_copy_bbs_p (region, n_region))
5548     return false;
5549
5550   /* Some sanity checking.  Note that we do not check for all possible
5551      missuses of the functions.  I.e. if you ask to copy something weird,
5552      it will work, but the state of structures probably will not be
5553      correct.  */
5554   for (i = 0; i < n_region; i++)
5555     {
5556       /* We do not handle subloops, i.e. all the blocks must belong to the
5557          same loop.  */
5558       if (region[i]->loop_father != loop)
5559         return false;
5560
5561       if (region[i] != entry->dest
5562           && region[i] == loop->header)
5563         return false;
5564     }
5565
5566   set_loop_copy (loop, loop);
5567
5568   /* In case the function is used for loop header copying (which is the primary
5569      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5570   if (loop->header == entry->dest)
5571     {
5572       copying_header = true;
5573       set_loop_copy (loop, loop_outer (loop));
5574
5575       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5576         return false;
5577
5578       for (i = 0; i < n_region; i++)
5579         if (region[i] != exit->src
5580             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5581           return false;
5582     }
5583
5584   if (!region_copy)
5585     {
5586       region_copy = XNEWVEC (basic_block, n_region);
5587       free_region_copy = true;
5588     }
5589
5590   gcc_assert (!need_ssa_update_p (cfun));
5591
5592   /* Record blocks outside the region that are dominated by something
5593      inside.  */
5594   doms = NULL;
5595   initialize_original_copy_tables ();
5596
5597   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5598
5599   if (entry->dest->count)
5600     {
5601       total_count = entry->dest->count;
5602       entry_count = entry->count;
5603       /* Fix up corner cases, to avoid division by zero or creation of negative
5604          frequencies.  */
5605       if (entry_count > total_count)
5606         entry_count = total_count;
5607     }
5608   else
5609     {
5610       total_freq = entry->dest->frequency;
5611       entry_freq = EDGE_FREQUENCY (entry);
5612       /* Fix up corner cases, to avoid division by zero or creation of negative
5613          frequencies.  */
5614       if (total_freq == 0)
5615         total_freq = 1;
5616       else if (entry_freq > total_freq)
5617         entry_freq = total_freq;
5618     }
5619
5620   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5621             split_edge_bb_loc (entry));
5622   if (total_count)
5623     {
5624       scale_bbs_frequencies_gcov_type (region, n_region,
5625                                        total_count - entry_count,
5626                                        total_count);
5627       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5628                                        total_count);
5629     }
5630   else
5631     {
5632       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5633                                  total_freq);
5634       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5635     }
5636
5637   if (copying_header)
5638     {
5639       loop->header = exit->dest;
5640       loop->latch = exit->src;
5641     }
5642
5643   /* Redirect the entry and add the phi node arguments.  */
5644   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5645   gcc_assert (redirected != NULL);
5646   flush_pending_stmts (entry);
5647
5648   /* Concerning updating of dominators:  We must recount dominators
5649      for entry block and its copy.  Anything that is outside of the
5650      region, but was dominated by something inside needs recounting as
5651      well.  */
5652   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5653   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5654   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5655   VEC_free (basic_block, heap, doms);
5656
5657   /* Add the other PHI node arguments.  */
5658   add_phi_args_after_copy (region_copy, n_region, NULL);
5659
5660   /* Update the SSA web.  */
5661   update_ssa (TODO_update_ssa);
5662
5663   if (free_region_copy)
5664     free (region_copy);
5665
5666   free_original_copy_tables ();
5667   return true;
5668 }
5669
5670 /* Checks if BB is part of the region defined by N_REGION BBS.  */
5671 static bool
5672 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
5673 {
5674   unsigned int n;
5675
5676   for (n = 0; n < n_region; n++)
5677     {
5678      if (bb == bbs[n])
5679        return true;
5680     }
5681   return false;
5682 }
5683
5684 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5685    are stored to REGION_COPY in the same order in that they appear
5686    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5687    the region, EXIT an exit from it.  The condition guarding EXIT
5688    is moved to ENTRY.  Returns true if duplication succeeds, false
5689    otherwise.
5690
5691    For example,
5692
5693    some_code;
5694    if (cond)
5695      A;
5696    else
5697      B;
5698
5699    is transformed to
5700
5701    if (cond)
5702      {
5703        some_code;
5704        A;
5705      }
5706    else
5707      {
5708        some_code;
5709        B;
5710      }
5711 */
5712
5713 bool
5714 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5715                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5716                           basic_block *region_copy ATTRIBUTE_UNUSED)
5717 {
5718   unsigned i;
5719   bool free_region_copy = false;
5720   struct loop *loop = exit->dest->loop_father;
5721   struct loop *orig_loop = entry->dest->loop_father;
5722   basic_block switch_bb, entry_bb, nentry_bb;
5723   VEC (basic_block, heap) *doms;
5724   int total_freq = 0, exit_freq = 0;
5725   gcov_type total_count = 0, exit_count = 0;
5726   edge exits[2], nexits[2], e;
5727   gimple_stmt_iterator gsi;
5728   gimple cond_stmt;
5729   edge sorig, snew;
5730   basic_block exit_bb;
5731   gimple_stmt_iterator psi;
5732   gimple phi;
5733   tree def;
5734   struct loop *target, *aloop, *cloop;
5735
5736   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5737   exits[0] = exit;
5738   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5739
5740   if (!can_copy_bbs_p (region, n_region))
5741     return false;
5742
5743   initialize_original_copy_tables ();
5744   set_loop_copy (orig_loop, loop);
5745
5746   target= loop;
5747   for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
5748     {
5749       if (bb_part_of_region_p (aloop->header, region, n_region))
5750         {
5751           cloop = duplicate_loop (aloop, target);
5752           duplicate_subloops (aloop, cloop);
5753         }
5754     }
5755
5756   if (!region_copy)
5757     {
5758       region_copy = XNEWVEC (basic_block, n_region);
5759       free_region_copy = true;
5760     }
5761
5762   gcc_assert (!need_ssa_update_p (cfun));
5763
5764   /* Record blocks outside the region that are dominated by something
5765      inside.  */
5766   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5767
5768   if (exit->src->count)
5769     {
5770       total_count = exit->src->count;
5771       exit_count = exit->count;
5772       /* Fix up corner cases, to avoid division by zero or creation of negative
5773          frequencies.  */
5774       if (exit_count > total_count)
5775         exit_count = total_count;
5776     }
5777   else
5778     {
5779       total_freq = exit->src->frequency;
5780       exit_freq = EDGE_FREQUENCY (exit);
5781       /* Fix up corner cases, to avoid division by zero or creation of negative
5782          frequencies.  */
5783       if (total_freq == 0)
5784         total_freq = 1;
5785       if (exit_freq > total_freq)
5786         exit_freq = total_freq;
5787     }
5788
5789   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5790             split_edge_bb_loc (exit));
5791   if (total_count)
5792     {
5793       scale_bbs_frequencies_gcov_type (region, n_region,
5794                                        total_count - exit_count,
5795                                        total_count);
5796       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5797                                        total_count);
5798     }
5799   else
5800     {
5801       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5802                                  total_freq);
5803       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5804     }
5805
5806   /* Create the switch block, and put the exit condition to it.  */
5807   entry_bb = entry->dest;
5808   nentry_bb = get_bb_copy (entry_bb);
5809   if (!last_stmt (entry->src)
5810       || !stmt_ends_bb_p (last_stmt (entry->src)))
5811     switch_bb = entry->src;
5812   else
5813     switch_bb = split_edge (entry);
5814   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5815
5816   gsi = gsi_last_bb (switch_bb);
5817   cond_stmt = last_stmt (exit->src);
5818   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5819   cond_stmt = gimple_copy (cond_stmt);
5820
5821   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5822
5823   sorig = single_succ_edge (switch_bb);
5824   sorig->flags = exits[1]->flags;
5825   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5826
5827   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5828   rescan_loop_exit (snew, true, false);
5829
5830   /* Add the PHI node arguments.  */
5831   add_phi_args_after_copy (region_copy, n_region, snew);
5832
5833   /* Get rid of now superfluous conditions and associated edges (and phi node
5834      arguments).  */
5835   exit_bb = exit->dest;
5836
5837   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5838   PENDING_STMT (e) = NULL;
5839
5840   /* The latch of ORIG_LOOP was copied, and so was the backedge
5841      to the original header.  We redirect this backedge to EXIT_BB.  */
5842   for (i = 0; i < n_region; i++)
5843     if (get_bb_original (region_copy[i]) == orig_loop->latch)
5844       {
5845         gcc_assert (single_succ_edge (region_copy[i]));
5846         e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5847         PENDING_STMT (e) = NULL;
5848         for (psi = gsi_start_phis (exit_bb);
5849              !gsi_end_p (psi);
5850              gsi_next (&psi))
5851           {
5852             phi = gsi_stmt (psi);
5853             def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5854             add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e),
5855                          gimple_phi_arg_block_from_edge (phi, e));
5856           }
5857       }
5858   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5859   PENDING_STMT (e) = NULL;
5860
5861   /* Anything that is outside of the region, but was dominated by something
5862      inside needs to update dominance info.  */
5863   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5864   VEC_free (basic_block, heap, doms);
5865   /* Update the SSA web.  */
5866   update_ssa (TODO_update_ssa);
5867
5868   if (free_region_copy)
5869     free (region_copy);
5870
5871   free_original_copy_tables ();
5872   return true;
5873 }
5874
5875 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5876    adding blocks when the dominator traversal reaches EXIT.  This
5877    function silently assumes that ENTRY strictly dominates EXIT.  */
5878
5879 void
5880 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5881                               VEC(basic_block,heap) **bbs_p)
5882 {
5883   basic_block son;
5884
5885   for (son = first_dom_son (CDI_DOMINATORS, entry);
5886        son;
5887        son = next_dom_son (CDI_DOMINATORS, son))
5888     {
5889       VEC_safe_push (basic_block, heap, *bbs_p, son);
5890       if (son != exit)
5891         gather_blocks_in_sese_region (son, exit, bbs_p);
5892     }
5893 }
5894
5895 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5896    The duplicates are recorded in VARS_MAP.  */
5897
5898 static void
5899 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5900                            tree to_context)
5901 {
5902   tree t = *tp, new_t;
5903   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5904   void **loc;
5905
5906   if (DECL_CONTEXT (t) == to_context)
5907     return;
5908
5909   loc = pointer_map_contains (vars_map, t);
5910
5911   if (!loc)
5912     {
5913       loc = pointer_map_insert (vars_map, t);
5914
5915       if (SSA_VAR_P (t))
5916         {
5917           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5918           add_local_decl (f, new_t);
5919         }
5920       else
5921         {
5922           gcc_assert (TREE_CODE (t) == CONST_DECL);
5923           new_t = copy_node (t);
5924         }
5925       DECL_CONTEXT (new_t) = to_context;
5926
5927       *loc = new_t;
5928     }
5929   else
5930     new_t = (tree) *loc;
5931
5932   *tp = new_t;
5933 }
5934
5935
5936 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5937    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5938
5939 static tree
5940 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5941                   tree to_context)
5942 {
5943   void **loc;
5944   tree new_name, decl = SSA_NAME_VAR (name);
5945
5946   gcc_assert (is_gimple_reg (name));
5947
5948   loc = pointer_map_contains (vars_map, name);
5949
5950   if (!loc)
5951     {
5952       replace_by_duplicate_decl (&decl, vars_map, to_context);
5953
5954       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5955       if (gimple_in_ssa_p (cfun))
5956         add_referenced_var (decl);
5957
5958       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5959       if (SSA_NAME_IS_DEFAULT_DEF (name))
5960         set_default_def (decl, new_name);
5961       pop_cfun ();
5962
5963       loc = pointer_map_insert (vars_map, name);
5964       *loc = new_name;
5965     }
5966   else
5967     new_name = (tree) *loc;
5968
5969   return new_name;
5970 }
5971
5972 struct move_stmt_d
5973 {
5974   tree orig_block;
5975   tree new_block;
5976   tree from_context;
5977   tree to_context;
5978   struct pointer_map_t *vars_map;
5979   htab_t new_label_map;
5980   struct pointer_map_t *eh_map;
5981   bool remap_decls_p;
5982 };
5983
5984 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5985    contained in *TP if it has been ORIG_BLOCK previously and change the
5986    DECL_CONTEXT of every local variable referenced in *TP.  */
5987
5988 static tree
5989 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5990 {
5991   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5992   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5993   tree t = *tp;
5994
5995   if (EXPR_P (t))
5996     /* We should never have TREE_BLOCK set on non-statements.  */
5997     gcc_assert (!TREE_BLOCK (t));
5998
5999   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
6000     {
6001       if (TREE_CODE (t) == SSA_NAME)
6002         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
6003       else if (TREE_CODE (t) == LABEL_DECL)
6004         {
6005           if (p->new_label_map)
6006             {
6007               struct tree_map in, *out;
6008               in.base.from = t;
6009               out = (struct tree_map *)
6010                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6011               if (out)
6012                 *tp = t = out->to;
6013             }
6014
6015           DECL_CONTEXT (t) = p->to_context;
6016         }
6017       else if (p->remap_decls_p)
6018         {
6019           /* Replace T with its duplicate.  T should no longer appear in the
6020              parent function, so this looks wasteful; however, it may appear
6021              in referenced_vars, and more importantly, as virtual operands of
6022              statements, and in alias lists of other variables.  It would be
6023              quite difficult to expunge it from all those places.  ??? It might
6024              suffice to do this for addressable variables.  */
6025           if ((TREE_CODE (t) == VAR_DECL
6026                && !is_global_var (t))
6027               || TREE_CODE (t) == CONST_DECL)
6028             {
6029               struct function *to_fn = DECL_STRUCT_FUNCTION (p->to_context);
6030               replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6031               if (gimple_referenced_vars (to_fn))
6032                 add_referenced_var_1 (*tp, to_fn);
6033             }
6034         }
6035       *walk_subtrees = 0;
6036     }
6037   else if (TYPE_P (t))
6038     *walk_subtrees = 0;
6039
6040   return NULL_TREE;
6041 }
6042
6043 /* Helper for move_stmt_r.  Given an EH region number for the source
6044    function, map that to the duplicate EH regio number in the dest.  */
6045
6046 static int
6047 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6048 {
6049   eh_region old_r, new_r;
6050   void **slot;
6051
6052   old_r = get_eh_region_from_number (old_nr);
6053   slot = pointer_map_contains (p->eh_map, old_r);
6054   new_r = (eh_region) *slot;
6055
6056   return new_r->index;
6057 }
6058
6059 /* Similar, but operate on INTEGER_CSTs.  */
6060
6061 static tree
6062 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6063 {
6064   int old_nr, new_nr;
6065
6066   old_nr = tree_low_cst (old_t_nr, 0);
6067   new_nr = move_stmt_eh_region_nr (old_nr, p);
6068
6069   return build_int_cst (integer_type_node, new_nr);
6070 }
6071
6072 /* Like move_stmt_op, but for gimple statements.
6073
6074    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
6075    contained in the current statement in *GSI_P and change the
6076    DECL_CONTEXT of every local variable referenced in the current
6077    statement.  */
6078
6079 static tree
6080 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6081              struct walk_stmt_info *wi)
6082 {
6083   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6084   gimple stmt = gsi_stmt (*gsi_p);
6085   tree block = gimple_block (stmt);
6086
6087   if (p->orig_block == NULL_TREE
6088       || block == p->orig_block
6089       || block == NULL_TREE)
6090     gimple_set_block (stmt, p->new_block);
6091 #ifdef ENABLE_CHECKING
6092   else if (block != p->new_block)
6093     {
6094       while (block && block != p->orig_block)
6095         block = BLOCK_SUPERCONTEXT (block);
6096       gcc_assert (block);
6097     }
6098 #endif
6099
6100   switch (gimple_code (stmt))
6101     {
6102     case GIMPLE_CALL:
6103       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
6104       {
6105         tree r, fndecl = gimple_call_fndecl (stmt);
6106         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6107           switch (DECL_FUNCTION_CODE (fndecl))
6108             {
6109             case BUILT_IN_EH_COPY_VALUES:
6110               r = gimple_call_arg (stmt, 1);
6111               r = move_stmt_eh_region_tree_nr (r, p);
6112               gimple_call_set_arg (stmt, 1, r);
6113               /* FALLTHRU */
6114
6115             case BUILT_IN_EH_POINTER:
6116             case BUILT_IN_EH_FILTER:
6117               r = gimple_call_arg (stmt, 0);
6118               r = move_stmt_eh_region_tree_nr (r, p);
6119               gimple_call_set_arg (stmt, 0, r);
6120               break;
6121
6122             default:
6123               break;
6124             }
6125       }
6126       break;
6127
6128     case GIMPLE_RESX:
6129       {
6130         int r = gimple_resx_region (stmt);
6131         r = move_stmt_eh_region_nr (r, p);
6132         gimple_resx_set_region (stmt, r);
6133       }
6134       break;
6135
6136     case GIMPLE_EH_DISPATCH:
6137       {
6138         int r = gimple_eh_dispatch_region (stmt);
6139         r = move_stmt_eh_region_nr (r, p);
6140         gimple_eh_dispatch_set_region (stmt, r);
6141       }
6142       break;
6143
6144     case GIMPLE_OMP_RETURN:
6145     case GIMPLE_OMP_CONTINUE:
6146       break;
6147     default:
6148       if (is_gimple_omp (stmt))
6149         {
6150           /* Do not remap variables inside OMP directives.  Variables
6151              referenced in clauses and directive header belong to the
6152              parent function and should not be moved into the child
6153              function.  */
6154           bool save_remap_decls_p = p->remap_decls_p;
6155           p->remap_decls_p = false;
6156           *handled_ops_p = true;
6157
6158           walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6159                                move_stmt_op, wi);
6160
6161           p->remap_decls_p = save_remap_decls_p;
6162         }
6163       break;
6164     }
6165
6166   return NULL_TREE;
6167 }
6168
6169 /* Move basic block BB from function CFUN to function DEST_FN.  The
6170    block is moved out of the original linked list and placed after
6171    block AFTER in the new list.  Also, the block is removed from the
6172    original array of blocks and placed in DEST_FN's array of blocks.
6173    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6174    updated to reflect the moved edges.
6175
6176    The local variables are remapped to new instances, VARS_MAP is used
6177    to record the mapping.  */
6178
6179 static void
6180 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6181                   basic_block after, bool update_edge_count_p,
6182                   struct move_stmt_d *d)
6183 {
6184   struct control_flow_graph *cfg;
6185   edge_iterator ei;
6186   edge e;
6187   gimple_stmt_iterator si;
6188   unsigned old_len, new_len;
6189
6190   /* Remove BB from dominance structures.  */
6191   delete_from_dominance_info (CDI_DOMINATORS, bb);
6192   if (current_loops)
6193     remove_bb_from_loops (bb);
6194
6195   /* Link BB to the new linked list.  */
6196   move_block_after (bb, after);
6197
6198   /* Update the edge count in the corresponding flowgraphs.  */
6199   if (update_edge_count_p)
6200     FOR_EACH_EDGE (e, ei, bb->succs)
6201       {
6202         cfun->cfg->x_n_edges--;
6203         dest_cfun->cfg->x_n_edges++;
6204       }
6205
6206   /* Remove BB from the original basic block array.  */
6207   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
6208   cfun->cfg->x_n_basic_blocks--;
6209
6210   /* Grow DEST_CFUN's basic block array if needed.  */
6211   cfg = dest_cfun->cfg;
6212   cfg->x_n_basic_blocks++;
6213   if (bb->index >= cfg->x_last_basic_block)
6214     cfg->x_last_basic_block = bb->index + 1;
6215
6216   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
6217   if ((unsigned) cfg->x_last_basic_block >= old_len)
6218     {
6219       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6220       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
6221                              new_len);
6222     }
6223
6224   VEC_replace (basic_block, cfg->x_basic_block_info,
6225                bb->index, bb);
6226
6227   /* Remap the variables in phi nodes.  */
6228   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6229     {
6230       gimple phi = gsi_stmt (si);
6231       use_operand_p use;
6232       tree op = PHI_RESULT (phi);
6233       ssa_op_iter oi;
6234
6235       if (!is_gimple_reg (op))
6236         {
6237           /* Remove the phi nodes for virtual operands (alias analysis will be
6238              run for the new function, anyway).  */
6239           remove_phi_node (&si, true);
6240           continue;
6241         }
6242
6243       SET_PHI_RESULT (phi,
6244                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6245       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6246         {
6247           op = USE_FROM_PTR (use);
6248           if (TREE_CODE (op) == SSA_NAME)
6249             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6250         }
6251
6252       gsi_next (&si);
6253     }
6254
6255   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6256     {
6257       gimple stmt = gsi_stmt (si);
6258       struct walk_stmt_info wi;
6259
6260       memset (&wi, 0, sizeof (wi));
6261       wi.info = d;
6262       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6263
6264       if (gimple_code (stmt) == GIMPLE_LABEL)
6265         {
6266           tree label = gimple_label_label (stmt);
6267           int uid = LABEL_DECL_UID (label);
6268
6269           gcc_assert (uid > -1);
6270
6271           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
6272           if (old_len <= (unsigned) uid)
6273             {
6274               new_len = 3 * uid / 2 + 1;
6275               VEC_safe_grow_cleared (basic_block, gc,
6276                                      cfg->x_label_to_block_map, new_len);
6277             }
6278
6279           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
6280           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
6281
6282           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6283
6284           if (uid >= dest_cfun->cfg->last_label_uid)
6285             dest_cfun->cfg->last_label_uid = uid + 1;
6286         }
6287
6288       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6289       remove_stmt_from_eh_lp_fn (cfun, stmt);
6290
6291       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6292       gimple_remove_stmt_histograms (cfun, stmt);
6293
6294       /* We cannot leave any operands allocated from the operand caches of
6295          the current function.  */
6296       free_stmt_operands (stmt);
6297       push_cfun (dest_cfun);
6298       update_stmt (stmt);
6299       pop_cfun ();
6300     }
6301
6302   FOR_EACH_EDGE (e, ei, bb->succs)
6303     if (e->goto_locus)
6304       {
6305         tree block = e->goto_block;
6306         if (d->orig_block == NULL_TREE
6307             || block == d->orig_block)
6308           e->goto_block = d->new_block;
6309 #ifdef ENABLE_CHECKING
6310         else if (block != d->new_block)
6311           {
6312             while (block && block != d->orig_block)
6313               block = BLOCK_SUPERCONTEXT (block);
6314             gcc_assert (block);
6315           }
6316 #endif
6317       }
6318 }
6319
6320 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6321    the outermost EH region.  Use REGION as the incoming base EH region.  */
6322
6323 static eh_region
6324 find_outermost_region_in_block (struct function *src_cfun,
6325                                 basic_block bb, eh_region region)
6326 {
6327   gimple_stmt_iterator si;
6328
6329   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6330     {
6331       gimple stmt = gsi_stmt (si);
6332       eh_region stmt_region;
6333       int lp_nr;
6334
6335       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6336       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6337       if (stmt_region)
6338         {
6339           if (region == NULL)
6340             region = stmt_region;
6341           else if (stmt_region != region)
6342             {
6343               region = eh_region_outermost (src_cfun, stmt_region, region);
6344               gcc_assert (region != NULL);
6345             }
6346         }
6347     }
6348
6349   return region;
6350 }
6351
6352 static tree
6353 new_label_mapper (tree decl, void *data)
6354 {
6355   htab_t hash = (htab_t) data;
6356   struct tree_map *m;
6357   void **slot;
6358
6359   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6360
6361   m = XNEW (struct tree_map);
6362   m->hash = DECL_UID (decl);
6363   m->base.from = decl;
6364   m->to = create_artificial_label (UNKNOWN_LOCATION);
6365   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6366   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6367     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6368
6369   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6370   gcc_assert (*slot == NULL);
6371
6372   *slot = m;
6373
6374   return m->to;
6375 }
6376
6377 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6378    subblocks.  */
6379
6380 static void
6381 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6382                                   tree to_context)
6383 {
6384   tree *tp, t;
6385
6386   for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6387     {
6388       t = *tp;
6389       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6390         continue;
6391       replace_by_duplicate_decl (&t, vars_map, to_context);
6392       if (t != *tp)
6393         {
6394           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6395             {
6396               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6397               DECL_HAS_VALUE_EXPR_P (t) = 1;
6398             }
6399           DECL_CHAIN (t) = DECL_CHAIN (*tp);
6400           *tp = t;
6401         }
6402     }
6403
6404   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6405     replace_block_vars_by_duplicates (block, vars_map, to_context);
6406 }
6407
6408 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6409    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6410    single basic block in the original CFG and the new basic block is
6411    returned.  DEST_CFUN must not have a CFG yet.
6412
6413    Note that the region need not be a pure SESE region.  Blocks inside
6414    the region may contain calls to abort/exit.  The only restriction
6415    is that ENTRY_BB should be the only entry point and it must
6416    dominate EXIT_BB.
6417
6418    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6419    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6420    to the new function.
6421
6422    All local variables referenced in the region are assumed to be in
6423    the corresponding BLOCK_VARS and unexpanded variable lists
6424    associated with DEST_CFUN.  */
6425
6426 basic_block
6427 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6428                         basic_block exit_bb, tree orig_block)
6429 {
6430   VEC(basic_block,heap) *bbs, *dom_bbs;
6431   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6432   basic_block after, bb, *entry_pred, *exit_succ, abb;
6433   struct function *saved_cfun = cfun;
6434   int *entry_flag, *exit_flag;
6435   unsigned *entry_prob, *exit_prob;
6436   unsigned i, num_entry_edges, num_exit_edges;
6437   edge e;
6438   edge_iterator ei;
6439   htab_t new_label_map;
6440   struct pointer_map_t *vars_map, *eh_map;
6441   struct loop *loop = entry_bb->loop_father;
6442   struct move_stmt_d d;
6443
6444   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6445      region.  */
6446   gcc_assert (entry_bb != exit_bb
6447               && (!exit_bb
6448                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6449
6450   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6451      because it won't be added by dfs_enumerate_from.  */
6452   bbs = NULL;
6453   VEC_safe_push (basic_block, heap, bbs, entry_bb);
6454   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6455
6456   /* The blocks that used to be dominated by something in BBS will now be
6457      dominated by the new block.  */
6458   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6459                                      VEC_address (basic_block, bbs),
6460                                      VEC_length (basic_block, bbs));
6461
6462   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6463      the predecessor edges to ENTRY_BB and the successor edges to
6464      EXIT_BB so that we can re-attach them to the new basic block that
6465      will replace the region.  */
6466   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6467   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6468   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6469   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6470   i = 0;
6471   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6472     {
6473       entry_prob[i] = e->probability;
6474       entry_flag[i] = e->flags;
6475       entry_pred[i++] = e->src;
6476       remove_edge (e);
6477     }
6478
6479   if (exit_bb)
6480     {
6481       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6482       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6483                                            sizeof (basic_block));
6484       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6485       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6486       i = 0;
6487       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6488         {
6489           exit_prob[i] = e->probability;
6490           exit_flag[i] = e->flags;
6491           exit_succ[i++] = e->dest;
6492           remove_edge (e);
6493         }
6494     }
6495   else
6496     {
6497       num_exit_edges = 0;
6498       exit_succ = NULL;
6499       exit_flag = NULL;
6500       exit_prob = NULL;
6501     }
6502
6503   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6504   gcc_assert (dest_cfun->cfg == NULL);
6505   push_cfun (dest_cfun);
6506
6507   init_empty_tree_cfg ();
6508
6509   /* Initialize EH information for the new function.  */
6510   eh_map = NULL;
6511   new_label_map = NULL;
6512   if (saved_cfun->eh)
6513     {
6514       eh_region region = NULL;
6515
6516       FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6517         region = find_outermost_region_in_block (saved_cfun, bb, region);
6518
6519       init_eh_for_function ();
6520       if (region != NULL)
6521         {
6522           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6523           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6524                                          new_label_mapper, new_label_map);
6525         }
6526     }
6527
6528   pop_cfun ();
6529
6530   /* Move blocks from BBS into DEST_CFUN.  */
6531   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6532   after = dest_cfun->cfg->x_entry_block_ptr;
6533   vars_map = pointer_map_create ();
6534
6535   memset (&d, 0, sizeof (d));
6536   d.orig_block = orig_block;
6537   d.new_block = DECL_INITIAL (dest_cfun->decl);
6538   d.from_context = cfun->decl;
6539   d.to_context = dest_cfun->decl;
6540   d.vars_map = vars_map;
6541   d.new_label_map = new_label_map;
6542   d.eh_map = eh_map;
6543   d.remap_decls_p = true;
6544
6545   FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6546     {
6547       /* No need to update edge counts on the last block.  It has
6548          already been updated earlier when we detached the region from
6549          the original CFG.  */
6550       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6551       after = bb;
6552     }
6553
6554   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6555   if (orig_block)
6556     {
6557       tree block;
6558       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6559                   == NULL_TREE);
6560       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6561         = BLOCK_SUBBLOCKS (orig_block);
6562       for (block = BLOCK_SUBBLOCKS (orig_block);
6563            block; block = BLOCK_CHAIN (block))
6564         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6565       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6566     }
6567
6568   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6569                                     vars_map, dest_cfun->decl);
6570
6571   if (new_label_map)
6572     htab_delete (new_label_map);
6573   if (eh_map)
6574     pointer_map_destroy (eh_map);
6575   pointer_map_destroy (vars_map);
6576
6577   /* Rewire the entry and exit blocks.  The successor to the entry
6578      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6579      the child function.  Similarly, the predecessor of DEST_FN's
6580      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6581      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6582      various CFG manipulation function get to the right CFG.
6583
6584      FIXME, this is silly.  The CFG ought to become a parameter to
6585      these helpers.  */
6586   push_cfun (dest_cfun);
6587   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6588   if (exit_bb)
6589     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6590   pop_cfun ();
6591
6592   /* Back in the original function, the SESE region has disappeared,
6593      create a new basic block in its place.  */
6594   bb = create_empty_bb (entry_pred[0]);
6595   if (current_loops)
6596     add_bb_to_loop (bb, loop);
6597   for (i = 0; i < num_entry_edges; i++)
6598     {
6599       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6600       e->probability = entry_prob[i];
6601     }
6602
6603   for (i = 0; i < num_exit_edges; i++)
6604     {
6605       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6606       e->probability = exit_prob[i];
6607     }
6608
6609   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6610   FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb)
6611     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6612   VEC_free (basic_block, heap, dom_bbs);
6613
6614   if (exit_bb)
6615     {
6616       free (exit_prob);
6617       free (exit_flag);
6618       free (exit_succ);
6619     }
6620   free (entry_prob);
6621   free (entry_flag);
6622   free (entry_pred);
6623   VEC_free (basic_block, heap, bbs);
6624
6625   return bb;
6626 }
6627
6628
6629 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6630    */
6631
6632 void
6633 dump_function_to_file (tree fn, FILE *file, int flags)
6634 {
6635   tree arg, var;
6636   struct function *dsf;
6637   bool ignore_topmost_bind = false, any_var = false;
6638   basic_block bb;
6639   tree chain;
6640   bool tmclone = TREE_CODE (fn) == FUNCTION_DECL && decl_is_tm_clone (fn);
6641
6642   fprintf (file, "%s %s(", lang_hooks.decl_printable_name (fn, 2),
6643            tmclone ? "[tm-clone] " : "");
6644
6645   arg = DECL_ARGUMENTS (fn);
6646   while (arg)
6647     {
6648       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6649       fprintf (file, " ");
6650       print_generic_expr (file, arg, dump_flags);
6651       if (flags & TDF_VERBOSE)
6652         print_node (file, "", arg, 4);
6653       if (DECL_CHAIN (arg))
6654         fprintf (file, ", ");
6655       arg = DECL_CHAIN (arg);
6656     }
6657   fprintf (file, ")\n");
6658
6659   if (flags & TDF_VERBOSE)
6660     print_node (file, "", fn, 2);
6661
6662   dsf = DECL_STRUCT_FUNCTION (fn);
6663   if (dsf && (flags & TDF_EH))
6664     dump_eh_tree (file, dsf);
6665
6666   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6667     {
6668       dump_node (fn, TDF_SLIM | flags, file);
6669       return;
6670     }
6671
6672   /* Switch CFUN to point to FN.  */
6673   push_cfun (DECL_STRUCT_FUNCTION (fn));
6674
6675   /* When GIMPLE is lowered, the variables are no longer available in
6676      BIND_EXPRs, so display them separately.  */
6677   if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls))
6678     {
6679       unsigned ix;
6680       ignore_topmost_bind = true;
6681
6682       fprintf (file, "{\n");
6683       FOR_EACH_LOCAL_DECL (cfun, ix, var)
6684         {
6685           print_generic_decl (file, var, flags);
6686           if (flags & TDF_VERBOSE)
6687             print_node (file, "", var, 4);
6688           fprintf (file, "\n");
6689
6690           any_var = true;
6691         }
6692     }
6693
6694   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6695     {
6696       /* If the CFG has been built, emit a CFG-based dump.  */
6697       check_bb_profile (ENTRY_BLOCK_PTR, file);
6698       if (!ignore_topmost_bind)
6699         fprintf (file, "{\n");
6700
6701       if (any_var && n_basic_blocks)
6702         fprintf (file, "\n");
6703
6704       FOR_EACH_BB (bb)
6705         gimple_dump_bb (bb, file, 2, flags);
6706
6707       fprintf (file, "}\n");
6708       check_bb_profile (EXIT_BLOCK_PTR, file);
6709     }
6710   else if (DECL_SAVED_TREE (fn) == NULL)
6711     {
6712       /* The function is now in GIMPLE form but the CFG has not been
6713          built yet.  Emit the single sequence of GIMPLE statements
6714          that make up its body.  */
6715       gimple_seq body = gimple_body (fn);
6716
6717       if (gimple_seq_first_stmt (body)
6718           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6719           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6720         print_gimple_seq (file, body, 0, flags);
6721       else
6722         {
6723           if (!ignore_topmost_bind)
6724             fprintf (file, "{\n");
6725
6726           if (any_var)
6727             fprintf (file, "\n");
6728
6729           print_gimple_seq (file, body, 2, flags);
6730           fprintf (file, "}\n");
6731         }
6732     }
6733   else
6734     {
6735       int indent;
6736
6737       /* Make a tree based dump.  */
6738       chain = DECL_SAVED_TREE (fn);
6739
6740       if (chain && TREE_CODE (chain) == BIND_EXPR)
6741         {
6742           if (ignore_topmost_bind)
6743             {
6744               chain = BIND_EXPR_BODY (chain);
6745               indent = 2;
6746             }
6747           else
6748             indent = 0;
6749         }
6750       else
6751         {
6752           if (!ignore_topmost_bind)
6753             fprintf (file, "{\n");
6754           indent = 2;
6755         }
6756
6757       if (any_var)
6758         fprintf (file, "\n");
6759
6760       print_generic_stmt_indented (file, chain, flags, indent);
6761       if (ignore_topmost_bind)
6762         fprintf (file, "}\n");
6763     }
6764
6765   if (flags & TDF_ENUMERATE_LOCALS)
6766     dump_enumerated_decls (file, flags);
6767   fprintf (file, "\n\n");
6768
6769   /* Restore CFUN.  */
6770   pop_cfun ();
6771 }
6772
6773
6774 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6775
6776 DEBUG_FUNCTION void
6777 debug_function (tree fn, int flags)
6778 {
6779   dump_function_to_file (fn, stderr, flags);
6780 }
6781
6782
6783 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6784
6785 static void
6786 print_pred_bbs (FILE *file, basic_block bb)
6787 {
6788   edge e;
6789   edge_iterator ei;
6790
6791   FOR_EACH_EDGE (e, ei, bb->preds)
6792     fprintf (file, "bb_%d ", e->src->index);
6793 }
6794
6795
6796 /* Print on FILE the indexes for the successors of basic_block BB.  */
6797
6798 static void
6799 print_succ_bbs (FILE *file, basic_block bb)
6800 {
6801   edge e;
6802   edge_iterator ei;
6803
6804   FOR_EACH_EDGE (e, ei, bb->succs)
6805     fprintf (file, "bb_%d ", e->dest->index);
6806 }
6807
6808 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6809
6810 void
6811 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6812 {
6813   char *s_indent = (char *) alloca ((size_t) indent + 1);
6814   memset ((void *) s_indent, ' ', (size_t) indent);
6815   s_indent[indent] = '\0';
6816
6817   /* Print basic_block's header.  */
6818   if (verbosity >= 2)
6819     {
6820       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6821       print_pred_bbs (file, bb);
6822       fprintf (file, "}, succs = {");
6823       print_succ_bbs (file, bb);
6824       fprintf (file, "})\n");
6825     }
6826
6827   /* Print basic_block's body.  */
6828   if (verbosity >= 3)
6829     {
6830       fprintf (file, "%s  {\n", s_indent);
6831       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6832       fprintf (file, "%s  }\n", s_indent);
6833     }
6834 }
6835
6836 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6837
6838 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6839    VERBOSITY level this outputs the contents of the loop, or just its
6840    structure.  */
6841
6842 static void
6843 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6844 {
6845   char *s_indent;
6846   basic_block bb;
6847
6848   if (loop == NULL)
6849     return;
6850
6851   s_indent = (char *) alloca ((size_t) indent + 1);
6852   memset ((void *) s_indent, ' ', (size_t) indent);
6853   s_indent[indent] = '\0';
6854
6855   /* Print loop's header.  */
6856   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6857            loop->num, loop->header->index, loop->latch->index);
6858   fprintf (file, ", niter = ");
6859   print_generic_expr (file, loop->nb_iterations, 0);
6860
6861   if (loop->any_upper_bound)
6862     {
6863       fprintf (file, ", upper_bound = ");
6864       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6865     }
6866
6867   if (loop->any_estimate)
6868     {
6869       fprintf (file, ", estimate = ");
6870       dump_double_int (file, loop->nb_iterations_estimate, true);
6871     }
6872   fprintf (file, ")\n");
6873
6874   /* Print loop's body.  */
6875   if (verbosity >= 1)
6876     {
6877       fprintf (file, "%s{\n", s_indent);
6878       FOR_EACH_BB (bb)
6879         if (bb->loop_father == loop)
6880           print_loops_bb (file, bb, indent, verbosity);
6881
6882       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6883       fprintf (file, "%s}\n", s_indent);
6884     }
6885 }
6886
6887 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6888    spaces.  Following VERBOSITY level this outputs the contents of the
6889    loop, or just its structure.  */
6890
6891 static void
6892 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6893 {
6894   if (loop == NULL)
6895     return;
6896
6897   print_loop (file, loop, indent, verbosity);
6898   print_loop_and_siblings (file, loop->next, indent, verbosity);
6899 }
6900
6901 /* Follow a CFG edge from the entry point of the program, and on entry
6902    of a loop, pretty print the loop structure on FILE.  */
6903
6904 void
6905 print_loops (FILE *file, int verbosity)
6906 {
6907   basic_block bb;
6908
6909   bb = ENTRY_BLOCK_PTR;
6910   if (bb && bb->loop_father)
6911     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6912 }
6913
6914
6915 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6916
6917 DEBUG_FUNCTION void
6918 debug_loops (int verbosity)
6919 {
6920   print_loops (stderr, verbosity);
6921 }
6922
6923 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6924
6925 DEBUG_FUNCTION void
6926 debug_loop (struct loop *loop, int verbosity)
6927 {
6928   print_loop (stderr, loop, 0, verbosity);
6929 }
6930
6931 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6932    level.  */
6933
6934 DEBUG_FUNCTION void
6935 debug_loop_num (unsigned num, int verbosity)
6936 {
6937   debug_loop (get_loop (num), verbosity);
6938 }
6939
6940 /* Return true if BB ends with a call, possibly followed by some
6941    instructions that must stay with the call.  Return false,
6942    otherwise.  */
6943
6944 static bool
6945 gimple_block_ends_with_call_p (basic_block bb)
6946 {
6947   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6948   return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
6949 }
6950
6951
6952 /* Return true if BB ends with a conditional branch.  Return false,
6953    otherwise.  */
6954
6955 static bool
6956 gimple_block_ends_with_condjump_p (const_basic_block bb)
6957 {
6958   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6959   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6960 }
6961
6962
6963 /* Return true if we need to add fake edge to exit at statement T.
6964    Helper function for gimple_flow_call_edges_add.  */
6965
6966 static bool
6967 need_fake_edge_p (gimple t)
6968 {
6969   tree fndecl = NULL_TREE;
6970   int call_flags = 0;
6971
6972   /* NORETURN and LONGJMP calls already have an edge to exit.
6973      CONST and PURE calls do not need one.
6974      We don't currently check for CONST and PURE here, although
6975      it would be a good idea, because those attributes are
6976      figured out from the RTL in mark_constant_function, and
6977      the counter incrementation code from -fprofile-arcs
6978      leads to different results from -fbranch-probabilities.  */
6979   if (is_gimple_call (t))
6980     {
6981       fndecl = gimple_call_fndecl (t);
6982       call_flags = gimple_call_flags (t);
6983     }
6984
6985   if (is_gimple_call (t)
6986       && fndecl
6987       && DECL_BUILT_IN (fndecl)
6988       && (call_flags & ECF_NOTHROW)
6989       && !(call_flags & ECF_RETURNS_TWICE)
6990       /* fork() doesn't really return twice, but the effect of
6991          wrapping it in __gcov_fork() which calls __gcov_flush()
6992          and clears the counters before forking has the same
6993          effect as returning twice.  Force a fake edge.  */
6994       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6995            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6996     return false;
6997
6998   if (is_gimple_call (t))
6999     {
7000       edge_iterator ei;
7001       edge e;
7002       basic_block bb;
7003
7004       if (!(call_flags & ECF_NORETURN))
7005         return true;
7006
7007       bb = gimple_bb (t);
7008       FOR_EACH_EDGE (e, ei, bb->succs)
7009         if ((e->flags & EDGE_FAKE) == 0)
7010           return true;
7011     }
7012
7013   if (gimple_code (t) == GIMPLE_ASM
7014        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7015     return true;
7016
7017   return false;
7018 }
7019
7020
7021 /* Add fake edges to the function exit for any non constant and non
7022    noreturn calls (or noreturn calls with EH/abnormal edges),
7023    volatile inline assembly in the bitmap of blocks specified by BLOCKS
7024    or to the whole CFG if BLOCKS is zero.  Return the number of blocks
7025    that were split.
7026
7027    The goal is to expose cases in which entering a basic block does
7028    not imply that all subsequent instructions must be executed.  */
7029
7030 static int
7031 gimple_flow_call_edges_add (sbitmap blocks)
7032 {
7033   int i;
7034   int blocks_split = 0;
7035   int last_bb = last_basic_block;
7036   bool check_last_block = false;
7037
7038   if (n_basic_blocks == NUM_FIXED_BLOCKS)
7039     return 0;
7040
7041   if (! blocks)
7042     check_last_block = true;
7043   else
7044     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
7045
7046   /* In the last basic block, before epilogue generation, there will be
7047      a fallthru edge to EXIT.  Special care is required if the last insn
7048      of the last basic block is a call because make_edge folds duplicate
7049      edges, which would result in the fallthru edge also being marked
7050      fake, which would result in the fallthru edge being removed by
7051      remove_fake_edges, which would result in an invalid CFG.
7052
7053      Moreover, we can't elide the outgoing fake edge, since the block
7054      profiler needs to take this into account in order to solve the minimal
7055      spanning tree in the case that the call doesn't return.
7056
7057      Handle this by adding a dummy instruction in a new last basic block.  */
7058   if (check_last_block)
7059     {
7060       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
7061       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7062       gimple t = NULL;
7063
7064       if (!gsi_end_p (gsi))
7065         t = gsi_stmt (gsi);
7066
7067       if (t && need_fake_edge_p (t))
7068         {
7069           edge e;
7070
7071           e = find_edge (bb, EXIT_BLOCK_PTR);
7072           if (e)
7073             {
7074               gsi_insert_on_edge (e, gimple_build_nop ());
7075               gsi_commit_edge_inserts ();
7076             }
7077         }
7078     }
7079
7080   /* Now add fake edges to the function exit for any non constant
7081      calls since there is no way that we can determine if they will
7082      return or not...  */
7083   for (i = 0; i < last_bb; i++)
7084     {
7085       basic_block bb = BASIC_BLOCK (i);
7086       gimple_stmt_iterator gsi;
7087       gimple stmt, last_stmt;
7088
7089       if (!bb)
7090         continue;
7091
7092       if (blocks && !TEST_BIT (blocks, i))
7093         continue;
7094
7095       gsi = gsi_last_nondebug_bb (bb);
7096       if (!gsi_end_p (gsi))
7097         {
7098           last_stmt = gsi_stmt (gsi);
7099           do
7100             {
7101               stmt = gsi_stmt (gsi);
7102               if (need_fake_edge_p (stmt))
7103                 {
7104                   edge e;
7105
7106                   /* The handling above of the final block before the
7107                      epilogue should be enough to verify that there is
7108                      no edge to the exit block in CFG already.
7109                      Calling make_edge in such case would cause us to
7110                      mark that edge as fake and remove it later.  */
7111 #ifdef ENABLE_CHECKING
7112                   if (stmt == last_stmt)
7113                     {
7114                       e = find_edge (bb, EXIT_BLOCK_PTR);
7115                       gcc_assert (e == NULL);
7116                     }
7117 #endif
7118
7119                   /* Note that the following may create a new basic block
7120                      and renumber the existing basic blocks.  */
7121                   if (stmt != last_stmt)
7122                     {
7123                       e = split_block (bb, stmt);
7124                       if (e)
7125                         blocks_split++;
7126                     }
7127                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
7128                 }
7129               gsi_prev (&gsi);
7130             }
7131           while (!gsi_end_p (gsi));
7132         }
7133     }
7134
7135   if (blocks_split)
7136     verify_flow_info ();
7137
7138   return blocks_split;
7139 }
7140
7141 /* Removes edge E and all the blocks dominated by it, and updates dominance
7142    information.  The IL in E->src needs to be updated separately.
7143    If dominance info is not available, only the edge E is removed.*/
7144
7145 void
7146 remove_edge_and_dominated_blocks (edge e)
7147 {
7148   VEC (basic_block, heap) *bbs_to_remove = NULL;
7149   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
7150   bitmap df, df_idom;
7151   edge f;
7152   edge_iterator ei;
7153   bool none_removed = false;
7154   unsigned i;
7155   basic_block bb, dbb;
7156   bitmap_iterator bi;
7157
7158   if (!dom_info_available_p (CDI_DOMINATORS))
7159     {
7160       remove_edge (e);
7161       return;
7162     }
7163
7164   /* No updating is needed for edges to exit.  */
7165   if (e->dest == EXIT_BLOCK_PTR)
7166     {
7167       if (cfgcleanup_altered_bbs)
7168         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7169       remove_edge (e);
7170       return;
7171     }
7172
7173   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
7174      that is not dominated by E->dest, then this set is empty.  Otherwise,
7175      all the basic blocks dominated by E->dest are removed.
7176
7177      Also, to DF_IDOM we store the immediate dominators of the blocks in
7178      the dominance frontier of E (i.e., of the successors of the
7179      removed blocks, if there are any, and of E->dest otherwise).  */
7180   FOR_EACH_EDGE (f, ei, e->dest->preds)
7181     {
7182       if (f == e)
7183         continue;
7184
7185       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7186         {
7187           none_removed = true;
7188           break;
7189         }
7190     }
7191
7192   df = BITMAP_ALLOC (NULL);
7193   df_idom = BITMAP_ALLOC (NULL);
7194
7195   if (none_removed)
7196     bitmap_set_bit (df_idom,
7197                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7198   else
7199     {
7200       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7201       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
7202         {
7203           FOR_EACH_EDGE (f, ei, bb->succs)
7204             {
7205               if (f->dest != EXIT_BLOCK_PTR)
7206                 bitmap_set_bit (df, f->dest->index);
7207             }
7208         }
7209       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
7210         bitmap_clear_bit (df, bb->index);
7211
7212       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7213         {
7214           bb = BASIC_BLOCK (i);
7215           bitmap_set_bit (df_idom,
7216                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7217         }
7218     }
7219
7220   if (cfgcleanup_altered_bbs)
7221     {
7222       /* Record the set of the altered basic blocks.  */
7223       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7224       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7225     }
7226
7227   /* Remove E and the cancelled blocks.  */
7228   if (none_removed)
7229     remove_edge (e);
7230   else
7231     {
7232       /* Walk backwards so as to get a chance to substitute all
7233          released DEFs into debug stmts.  See
7234          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7235          details.  */
7236       for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
7237         delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
7238     }
7239
7240   /* Update the dominance information.  The immediate dominator may change only
7241      for blocks whose immediate dominator belongs to DF_IDOM:
7242
7243      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7244      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7245      Z dominates X after the removal.  Before removal, there exists a path P
7246      from Y to X that avoids Z.  Let F be the last edge on P that is
7247      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7248      dominates W, and because of P, Z does not dominate W), and W belongs to
7249      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7250   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7251     {
7252       bb = BASIC_BLOCK (i);
7253       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7254            dbb;
7255            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7256         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
7257     }
7258
7259   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7260
7261   BITMAP_FREE (df);
7262   BITMAP_FREE (df_idom);
7263   VEC_free (basic_block, heap, bbs_to_remove);
7264   VEC_free (basic_block, heap, bbs_to_fix_dom);
7265 }
7266
7267 /* Purge dead EH edges from basic block BB.  */
7268
7269 bool
7270 gimple_purge_dead_eh_edges (basic_block bb)
7271 {
7272   bool changed = false;
7273   edge e;
7274   edge_iterator ei;
7275   gimple stmt = last_stmt (bb);
7276
7277   if (stmt && stmt_can_throw_internal (stmt))
7278     return false;
7279
7280   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7281     {
7282       if (e->flags & EDGE_EH)
7283         {
7284           remove_edge_and_dominated_blocks (e);
7285           changed = true;
7286         }
7287       else
7288         ei_next (&ei);
7289     }
7290
7291   return changed;
7292 }
7293
7294 /* Purge dead EH edges from basic block listed in BLOCKS.  */
7295
7296 bool
7297 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7298 {
7299   bool changed = false;
7300   unsigned i;
7301   bitmap_iterator bi;
7302
7303   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7304     {
7305       basic_block bb = BASIC_BLOCK (i);
7306
7307       /* Earlier gimple_purge_dead_eh_edges could have removed
7308          this basic block already.  */
7309       gcc_assert (bb || changed);
7310       if (bb != NULL)
7311         changed |= gimple_purge_dead_eh_edges (bb);
7312     }
7313
7314   return changed;
7315 }
7316
7317 /* Purge dead abnormal call edges from basic block BB.  */
7318
7319 bool
7320 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7321 {
7322   bool changed = false;
7323   edge e;
7324   edge_iterator ei;
7325   gimple stmt = last_stmt (bb);
7326
7327   if (!cfun->has_nonlocal_label)
7328     return false;
7329
7330   if (stmt && stmt_can_make_abnormal_goto (stmt))
7331     return false;
7332
7333   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7334     {
7335       if (e->flags & EDGE_ABNORMAL)
7336         {
7337           remove_edge_and_dominated_blocks (e);
7338           changed = true;
7339         }
7340       else
7341         ei_next (&ei);
7342     }
7343
7344   return changed;
7345 }
7346
7347 /* Purge dead abnormal call edges from basic block listed in BLOCKS.  */
7348
7349 bool
7350 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7351 {
7352   bool changed = false;
7353   unsigned i;
7354   bitmap_iterator bi;
7355
7356   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7357     {
7358       basic_block bb = BASIC_BLOCK (i);
7359
7360       /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7361          this basic block already.  */
7362       gcc_assert (bb || changed);
7363       if (bb != NULL)
7364         changed |= gimple_purge_dead_abnormal_call_edges (bb);
7365     }
7366
7367   return changed;
7368 }
7369
7370 /* This function is called whenever a new edge is created or
7371    redirected.  */
7372
7373 static void
7374 gimple_execute_on_growing_pred (edge e)
7375 {
7376   basic_block bb = e->dest;
7377
7378   if (!gimple_seq_empty_p (phi_nodes (bb)))
7379     reserve_phi_args_for_new_edge (bb);
7380 }
7381
7382 /* This function is called immediately before edge E is removed from
7383    the edge vector E->dest->preds.  */
7384
7385 static void
7386 gimple_execute_on_shrinking_pred (edge e)
7387 {
7388   if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7389     remove_phi_args (e);
7390 }
7391
7392 /*---------------------------------------------------------------------------
7393   Helper functions for Loop versioning
7394   ---------------------------------------------------------------------------*/
7395
7396 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7397    of 'first'. Both of them are dominated by 'new_head' basic block. When
7398    'new_head' was created by 'second's incoming edge it received phi arguments
7399    on the edge by split_edge(). Later, additional edge 'e' was created to
7400    connect 'new_head' and 'first'. Now this routine adds phi args on this
7401    additional edge 'e' that new_head to second edge received as part of edge
7402    splitting.  */
7403
7404 static void
7405 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7406                                   basic_block new_head, edge e)
7407 {
7408   gimple phi1, phi2;
7409   gimple_stmt_iterator psi1, psi2;
7410   tree def;
7411   edge e2 = find_edge (new_head, second);
7412
7413   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7414      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7415   gcc_assert (e2 != NULL);
7416
7417   /* Browse all 'second' basic block phi nodes and add phi args to
7418      edge 'e' for 'first' head. PHI args are always in correct order.  */
7419
7420   for (psi2 = gsi_start_phis (second),
7421        psi1 = gsi_start_phis (first);
7422        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7423        gsi_next (&psi2),  gsi_next (&psi1))
7424     {
7425       phi1 = gsi_stmt (psi1);
7426       phi2 = gsi_stmt (psi2);
7427       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7428       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2),
7429                    gimple_phi_arg_block_from_edge (phi2, e2));
7430     }
7431 }
7432
7433
7434 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7435    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7436    the destination of the ELSE part.  */
7437
7438 static void
7439 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7440                                basic_block second_head ATTRIBUTE_UNUSED,
7441                                basic_block cond_bb, void *cond_e)
7442 {
7443   gimple_stmt_iterator gsi;
7444   gimple new_cond_expr;
7445   tree cond_expr = (tree) cond_e;
7446   edge e0;
7447
7448   /* Build new conditional expr */
7449   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7450                                                NULL_TREE, NULL_TREE);
7451
7452   /* Add new cond in cond_bb.  */
7453   gsi = gsi_last_bb (cond_bb);
7454   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7455
7456   /* Adjust edges appropriately to connect new head with first head
7457      as well as second head.  */
7458   e0 = single_succ_edge (cond_bb);
7459   e0->flags &= ~EDGE_FALLTHRU;
7460   e0->flags |= EDGE_FALSE_VALUE;
7461 }
7462
7463 struct cfg_hooks gimple_cfg_hooks = {
7464   "gimple",
7465   gimple_verify_flow_info,
7466   gimple_dump_bb,               /* dump_bb  */
7467   create_bb,                    /* create_basic_block  */
7468   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7469   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7470   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7471   remove_bb,                    /* delete_basic_block  */
7472   gimple_split_block,           /* split_block  */
7473   gimple_move_block_after,      /* move_block_after  */
7474   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7475   gimple_merge_blocks,          /* merge_blocks  */
7476   gimple_predict_edge,          /* predict_edge  */
7477   gimple_predicted_by_p,        /* predicted_by_p  */
7478   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7479   gimple_duplicate_bb,          /* duplicate_block  */
7480   gimple_split_edge,            /* split_edge  */
7481   gimple_make_forwarder_block,  /* make_forward_block  */
7482   NULL,                         /* tidy_fallthru_edge  */
7483   NULL,                         /* force_nonfallthru */
7484   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7485   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7486   gimple_flow_call_edges_add,   /* flow_call_edges_add */
7487   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7488   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7489   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7490   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7491   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7492   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7493   flush_pending_stmts           /* flush_pending_stmts */
7494 };
7495
7496
7497 /* Split all critical edges.  */
7498
7499 static unsigned int
7500 split_critical_edges (void)
7501 {
7502   basic_block bb;
7503   edge e;
7504   edge_iterator ei;
7505
7506   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7507      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7508      mappings around the calls to split_edge.  */
7509   start_recording_case_labels ();
7510   FOR_ALL_BB (bb)
7511     {
7512       FOR_EACH_EDGE (e, ei, bb->succs)
7513         {
7514           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7515             split_edge (e);
7516           /* PRE inserts statements to edges and expects that
7517              since split_critical_edges was done beforehand, committing edge
7518              insertions will not split more edges.  In addition to critical
7519              edges we must split edges that have multiple successors and
7520              end by control flow statements, such as RESX.
7521              Go ahead and split them too.  This matches the logic in
7522              gimple_find_edge_insert_loc.  */
7523           else if ((!single_pred_p (e->dest)
7524                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7525                     || e->dest == EXIT_BLOCK_PTR)
7526                    && e->src != ENTRY_BLOCK_PTR
7527                    && !(e->flags & EDGE_ABNORMAL))
7528             {
7529               gimple_stmt_iterator gsi;
7530
7531               gsi = gsi_last_bb (e->src);
7532               if (!gsi_end_p (gsi)
7533                   && stmt_ends_bb_p (gsi_stmt (gsi))
7534                   && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7535                       && !gimple_call_builtin_p (gsi_stmt (gsi),
7536                                                  BUILT_IN_RETURN)))
7537                 split_edge (e);
7538             }
7539         }
7540     }
7541   end_recording_case_labels ();
7542   return 0;
7543 }
7544
7545 struct gimple_opt_pass pass_split_crit_edges =
7546 {
7547  {
7548   GIMPLE_PASS,
7549   "crited",                          /* name */
7550   NULL,                          /* gate */
7551   split_critical_edges,          /* execute */
7552   NULL,                          /* sub */
7553   NULL,                          /* next */
7554   0,                             /* static_pass_number */
7555   TV_TREE_SPLIT_EDGES,           /* tv_id */
7556   PROP_cfg,                      /* properties required */
7557   PROP_no_crit_edges,            /* properties_provided */
7558   0,                             /* properties_destroyed */
7559   0,                             /* todo_flags_start */
7560   TODO_verify_flow               /* todo_flags_finish */
7561  }
7562 };
7563
7564
7565 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7566    Return the gimple_val holding the result.  */
7567
7568 tree
7569 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7570                  tree type, tree a, tree b, tree c)
7571 {
7572   tree ret;
7573   location_t loc = gimple_location (gsi_stmt (*gsi));
7574
7575   ret = fold_build3_loc (loc, code, type, a, b, c);
7576   STRIP_NOPS (ret);
7577
7578   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7579                                    GSI_SAME_STMT);
7580 }
7581
7582 /* Build a binary operation and gimplify it.  Emit code before GSI.
7583    Return the gimple_val holding the result.  */
7584
7585 tree
7586 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7587                  tree type, tree a, tree b)
7588 {
7589   tree ret;
7590
7591   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7592   STRIP_NOPS (ret);
7593
7594   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7595                                    GSI_SAME_STMT);
7596 }
7597
7598 /* Build a unary operation and gimplify it.  Emit code before GSI.
7599    Return the gimple_val holding the result.  */
7600
7601 tree
7602 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7603                  tree a)
7604 {
7605   tree ret;
7606
7607   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7608   STRIP_NOPS (ret);
7609
7610   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7611                                    GSI_SAME_STMT);
7612 }
7613
7614
7615 \f
7616 /* Emit return warnings.  */
7617
7618 static unsigned int
7619 execute_warn_function_return (void)
7620 {
7621   source_location location;
7622   gimple last;
7623   edge e;
7624   edge_iterator ei;
7625
7626   /* If we have a path to EXIT, then we do return.  */
7627   if (TREE_THIS_VOLATILE (cfun->decl)
7628       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7629     {
7630       location = UNKNOWN_LOCATION;
7631       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7632         {
7633           last = last_stmt (e->src);
7634           if ((gimple_code (last) == GIMPLE_RETURN
7635                || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7636               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7637             break;
7638         }
7639       if (location == UNKNOWN_LOCATION)
7640         location = cfun->function_end_locus;
7641       warning_at (location, 0, "%<noreturn%> function does return");
7642     }
7643
7644   /* If we see "return;" in some basic block, then we do reach the end
7645      without returning a value.  */
7646   else if (warn_return_type
7647            && !TREE_NO_WARNING (cfun->decl)
7648            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7649            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7650     {
7651       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7652         {
7653           gimple last = last_stmt (e->src);
7654           if (gimple_code (last) == GIMPLE_RETURN
7655               && gimple_return_retval (last) == NULL
7656               && !gimple_no_warning_p (last))
7657             {
7658               location = gimple_location (last);
7659               if (location == UNKNOWN_LOCATION)
7660                   location = cfun->function_end_locus;
7661               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7662               TREE_NO_WARNING (cfun->decl) = 1;
7663               break;
7664             }
7665         }
7666     }
7667   return 0;
7668 }
7669
7670
7671 /* Given a basic block B which ends with a conditional and has
7672    precisely two successors, determine which of the edges is taken if
7673    the conditional is true and which is taken if the conditional is
7674    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7675
7676 void
7677 extract_true_false_edges_from_block (basic_block b,
7678                                      edge *true_edge,
7679                                      edge *false_edge)
7680 {
7681   edge e = EDGE_SUCC (b, 0);
7682
7683   if (e->flags & EDGE_TRUE_VALUE)
7684     {
7685       *true_edge = e;
7686       *false_edge = EDGE_SUCC (b, 1);
7687     }
7688   else
7689     {
7690       *false_edge = e;
7691       *true_edge = EDGE_SUCC (b, 1);
7692     }
7693 }
7694
7695 struct gimple_opt_pass pass_warn_function_return =
7696 {
7697  {
7698   GIMPLE_PASS,
7699   "*warn_function_return",              /* name */
7700   NULL,                                 /* gate */
7701   execute_warn_function_return,         /* execute */
7702   NULL,                                 /* sub */
7703   NULL,                                 /* next */
7704   0,                                    /* static_pass_number */
7705   TV_NONE,                              /* tv_id */
7706   PROP_cfg,                             /* properties_required */
7707   0,                                    /* properties_provided */
7708   0,                                    /* properties_destroyed */
7709   0,                                    /* todo_flags_start */
7710   0                                     /* todo_flags_finish */
7711  }
7712 };
7713
7714 /* Emit noreturn warnings.  */
7715
7716 static unsigned int
7717 execute_warn_function_noreturn (void)
7718 {
7719   if (!TREE_THIS_VOLATILE (current_function_decl)
7720       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7721     warn_function_noreturn (current_function_decl);
7722   return 0;
7723 }
7724
7725 static bool
7726 gate_warn_function_noreturn (void)
7727 {
7728   return warn_suggest_attribute_noreturn;
7729 }
7730
7731 struct gimple_opt_pass pass_warn_function_noreturn =
7732 {
7733  {
7734   GIMPLE_PASS,
7735   "*warn_function_noreturn",            /* name */
7736   gate_warn_function_noreturn,          /* gate */
7737   execute_warn_function_noreturn,       /* execute */
7738   NULL,                                 /* sub */
7739   NULL,                                 /* next */
7740   0,                                    /* static_pass_number */
7741   TV_NONE,                              /* tv_id */
7742   PROP_cfg,                             /* properties_required */
7743   0,                                    /* properties_provided */
7744   0,                                    /* properties_destroyed */
7745   0,                                    /* todo_flags_start */
7746   0                                     /* todo_flags_finish */
7747  }
7748 };
7749
7750
7751 /* Walk a gimplified function and warn for functions whose return value is
7752    ignored and attribute((warn_unused_result)) is set.  This is done before
7753    inlining, so we don't have to worry about that.  */
7754
7755 static void
7756 do_warn_unused_result (gimple_seq seq)
7757 {
7758   tree fdecl, ftype;
7759   gimple_stmt_iterator i;
7760
7761   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7762     {
7763       gimple g = gsi_stmt (i);
7764
7765       switch (gimple_code (g))
7766         {
7767         case GIMPLE_BIND:
7768           do_warn_unused_result (gimple_bind_body (g));
7769           break;
7770         case GIMPLE_TRY:
7771           do_warn_unused_result (gimple_try_eval (g));
7772           do_warn_unused_result (gimple_try_cleanup (g));
7773           break;
7774         case GIMPLE_CATCH:
7775           do_warn_unused_result (gimple_catch_handler (g));
7776           break;
7777         case GIMPLE_EH_FILTER:
7778           do_warn_unused_result (gimple_eh_filter_failure (g));
7779           break;
7780
7781         case GIMPLE_CALL:
7782           if (gimple_call_lhs (g))
7783             break;
7784           if (gimple_call_internal_p (g))
7785             break;
7786
7787           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7788              LHS.  All calls whose value is ignored should be
7789              represented like this.  Look for the attribute.  */
7790           fdecl = gimple_call_fndecl (g);
7791           ftype = gimple_call_fntype (g);
7792
7793           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7794             {
7795               location_t loc = gimple_location (g);
7796
7797               if (fdecl)
7798                 warning_at (loc, OPT_Wunused_result,
7799                             "ignoring return value of %qD, "
7800                             "declared with attribute warn_unused_result",
7801                             fdecl);
7802               else
7803                 warning_at (loc, OPT_Wunused_result,
7804                             "ignoring return value of function "
7805                             "declared with attribute warn_unused_result");
7806             }
7807           break;
7808
7809         default:
7810           /* Not a container, not a call, or a call whose value is used.  */
7811           break;
7812         }
7813     }
7814 }
7815
7816 static unsigned int
7817 run_warn_unused_result (void)
7818 {
7819   do_warn_unused_result (gimple_body (current_function_decl));
7820   return 0;
7821 }
7822
7823 static bool
7824 gate_warn_unused_result (void)
7825 {
7826   return flag_warn_unused_result;
7827 }
7828
7829 struct gimple_opt_pass pass_warn_unused_result =
7830 {
7831   {
7832     GIMPLE_PASS,
7833     "*warn_unused_result",              /* name */
7834     gate_warn_unused_result,            /* gate */
7835     run_warn_unused_result,             /* execute */
7836     NULL,                               /* sub */
7837     NULL,                               /* next */
7838     0,                                  /* static_pass_number */
7839     TV_NONE,                            /* tv_id */
7840     PROP_gimple_any,                    /* properties_required */
7841     0,                                  /* properties_provided */
7842     0,                                  /* properties_destroyed */
7843     0,                                  /* todo_flags_start */
7844     0,                                  /* todo_flags_finish */
7845   }
7846 };