gcc/tree-cfg.c

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