gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
   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 2, 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 COPYING.  If not, write to
  20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  21 Boston, MA 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "flags.h"
  34 #include "function.h"
  35 #include "expr.h"
  36 #include "ggc.h"
  37 #include "langhooks.h"
  38 #include "diagnostic.h"
  39 #include "tree-flow.h"
  40 #include "timevar.h"
  41 #include "tree-dump.h"
  42 #include "tree-pass.h"
  43 #include "toplev.h"
  44 #include "except.h"
  45 #include "cfgloop.h"
  46 #include "cfglayout.h"
  47 #include "hashtab.h"
  48 #include "tree-ssa-propagate.h"
  49
  50 /* This file contains functions for building the Control Flow Graph (CFG)
  51    for a function tree.  */
  52
  53 /* Local declarations.  */
  54
  55 /* Initial capacity for the basic block array.  */
  56 static const int initial_cfg_capacity = 20;
  57
  58 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  59    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  60    via their TREE_CHAIN field, which we clear after we're done with the
  61    hash table to prevent problems with duplication of SWITCH_EXPRs.
  62
  63    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  64    update the case vector in response to edge redirections.
  65
  66    Right now this table is set up and torn down at key points in the
  67    compilation process.  It would be nice if we could make the table
  68    more persistent.  The key is getting notification of changes to
  69    the CFG (particularly edge removal, creation and redirection).  */
  70
  71 struct edge_to_cases_elt
  72 {
  73   /* The edge itself.  Necessary for hashing and equality tests.  */
  74   edge e;
  75
  76   /* The case labels associated with this edge.  We link these up via
  77      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
  78      when we destroy the hash table.  This prevents problems when copying
  79      SWITCH_EXPRs.  */
  80   tree case_labels;
  81 };
  82
  83 static htab_t edge_to_cases;
  84
  85 /* CFG statistics.  */
  86 struct cfg_stats_d
  87 {
  88   long num_merged_labels;
  89 };
  90
  91 static struct cfg_stats_d cfg_stats;
  92
  93 /* Nonzero if we found a computed goto while building basic blocks.  */
  94 static bool found_computed_goto;
  95
  96 /* Basic blocks and flowgraphs.  */
  97 static basic_block create_bb (void *, void *, basic_block);
  98 static void make_blocks (tree);
  99 static void factor_computed_gotos (void);
 100
 101 /* Edges.  */
 102 static void make_edges (void);
 103 static void make_cond_expr_edges (basic_block);
 104 static void make_switch_expr_edges (basic_block);
 105 static void make_goto_expr_edges (basic_block);
 106 static edge tree_redirect_edge_and_branch (edge, basic_block);
 107 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
 108 static unsigned int split_critical_edges (void);
 109
 110 /* Various helpers.  */
 111 static inline bool stmt_starts_bb_p (tree, tree);
 112 static int tree_verify_flow_info (void);
 113 static void tree_make_forwarder_block (edge);
 114 static void tree_cfg2vcg (FILE *);
 115 static inline void change_bb_for_stmt (tree t, basic_block bb);
 116
 117 /* Flowgraph optimization and cleanup.  */
 118 static void tree_merge_blocks (basic_block, basic_block);
 119 static bool tree_can_merge_blocks_p (basic_block, basic_block);
 120 static void remove_bb (basic_block);
 121 static edge find_taken_edge_computed_goto (basic_block, tree);
 122 static edge find_taken_edge_cond_expr (basic_block, tree);
 123 static edge find_taken_edge_switch_expr (basic_block, tree);
 124 static tree find_case_label_for_value (tree, tree);
 125
 126 void
 127 init_empty_tree_cfg (void)
 128 {
 129   /* Initialize the basic block array.  */
 130   init_flow ();
 131   profile_status = PROFILE_ABSENT;
 132   n_basic_blocks = NUM_FIXED_BLOCKS;
 133   last_basic_block = NUM_FIXED_BLOCKS;
 134   basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 135   VEC_safe_grow (basic_block, gc, basic_block_info, initial_cfg_capacity);
 136   memset (VEC_address (basic_block, basic_block_info), 0,
 137           sizeof (basic_block) * initial_cfg_capacity);
 138
 139   /* Build a mapping of labels to their associated blocks.  */
 140   label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 141   VEC_safe_grow (basic_block, gc, label_to_block_map, initial_cfg_capacity);
 142   memset (VEC_address (basic_block, label_to_block_map),
 143           0, sizeof (basic_block) * initial_cfg_capacity);
 144
 145   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
 146   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
 147   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 148   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 149 }
 150
 151 /*---------------------------------------------------------------------------
 152                               Create basic blocks
 153 ---------------------------------------------------------------------------*/
 154
 155 /* Entry point to the CFG builder for trees.  TP points to the list of
 156    statements to be added to the flowgraph.  */
 157
 158 static void
 159 build_tree_cfg (tree *tp)
 160 {
 161   /* Register specific tree functions.  */
 162   tree_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 (*tp);
 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     {
 186       size_t old_size = VEC_length (basic_block, basic_block_info);
 187       basic_block *p;
 188       VEC_safe_grow (basic_block, gc, basic_block_info, n_basic_blocks);
 189       p = VEC_address (basic_block, basic_block_info);
 190       memset (&p[old_size], 0,
 191               sizeof (basic_block) * (n_basic_blocks - old_size));
 192     }
 193
 194   /* To speed up statement iterator walks, we first purge dead labels.  */
 195   cleanup_dead_labels ();
 196
 197   /* Group case nodes to reduce the number of edges.
 198      We do this after cleaning up dead labels because otherwise we miss
 199      a lot of obvious case merging opportunities.  */
 200   group_case_labels ();
 201
 202   /* Create the edges of the flowgraph.  */
 203   make_edges ();
 204
 205   /* Debugging dumps.  */
 206
 207   /* Write the flowgraph to a VCG file.  */
 208   {
 209     int local_dump_flags;
 210     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 211     if (vcg_file)
 212       {
 213         tree_cfg2vcg (vcg_file);
 214         dump_end (TDI_vcg, vcg_file);
 215       }
 216   }
 217
 218 #ifdef ENABLE_CHECKING
 219   verify_stmts ();
 220 #endif
 221
 222   /* Dump a textual representation of the flowgraph.  */
 223   if (dump_file)
 224     dump_tree_cfg (dump_file, dump_flags);
 225 }
 226
 227 static unsigned int
 228 execute_build_cfg (void)
 229 {
 230   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
 231   return 0;
 232 }
 233
 234 struct tree_opt_pass pass_build_cfg =
 235 {
 236   "cfg",                                /* name */
 237   NULL,                                 /* gate */
 238   execute_build_cfg,                    /* execute */
 239   NULL,                                 /* sub */
 240   NULL,                                 /* next */
 241   0,                                    /* static_pass_number */
 242   TV_TREE_CFG,                          /* tv_id */
 243   PROP_gimple_leh,                      /* properties_required */
 244   PROP_cfg,                             /* properties_provided */
 245   0,                                    /* properties_destroyed */
 246   0,                                    /* todo_flags_start */
 247   TODO_verify_stmts,                    /* todo_flags_finish */
 248   0                                     /* letter */
 249 };
 250
 251 /* Search the CFG for any computed gotos.  If found, factor them to a
 252    common computed goto site.  Also record the location of that site so
 253    that we can un-factor the gotos after we have converted back to
 254    normal form.  */
 255
 256 static void
 257 factor_computed_gotos (void)
 258 {
 259   basic_block bb;
 260   tree factored_label_decl = NULL;
 261   tree var = NULL;
 262   tree factored_computed_goto_label = NULL;
 263   tree factored_computed_goto = NULL;
 264
 265   /* We know there are one or more computed gotos in this function.
 266      Examine the last statement in each basic block to see if the block
 267      ends with a computed goto.  */
 268
 269   FOR_EACH_BB (bb)
 270     {
 271       block_stmt_iterator bsi = bsi_last (bb);
 272       tree last;
 273
 274       if (bsi_end_p (bsi))
 275         continue;
 276       last = bsi_stmt (bsi);
 277
 278       /* Ignore the computed goto we create when we factor the original
 279          computed gotos.  */
 280       if (last == factored_computed_goto)
 281         continue;
 282
 283       /* If the last statement is a computed goto, factor it.  */
 284       if (computed_goto_p (last))
 285         {
 286           tree assignment;
 287
 288           /* The first time we find a computed goto we need to create
 289              the factored goto block and the variable each original
 290              computed goto will use for their goto destination.  */
 291           if (! factored_computed_goto)
 292             {
 293               basic_block new_bb = create_empty_bb (bb);
 294               block_stmt_iterator new_bsi = bsi_start (new_bb);
 295
 296               /* Create the destination of the factored goto.  Each original
 297                  computed goto will put its desired destination into this
 298                  variable and jump to the label we create immediately
 299                  below.  */
 300               var = create_tmp_var (ptr_type_node, "gotovar");
 301
 302               /* Build a label for the new block which will contain the
 303                  factored computed goto.  */
 304               factored_label_decl = create_artificial_label ();
 305               factored_computed_goto_label
 306                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
 307               bsi_insert_after (&new_bsi, factored_computed_goto_label,
 308                                 BSI_NEW_STMT);
 309
 310               /* Build our new computed goto.  */
 311               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
 312               bsi_insert_after (&new_bsi, factored_computed_goto,
 313                                 BSI_NEW_STMT);
 314             }
 315
 316           /* Copy the original computed goto's destination into VAR.  */
 317           assignment = build2 (MODIFY_EXPR, ptr_type_node,
 318                                var, GOTO_DESTINATION (last));
 319           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
 320
 321           /* And re-vector the computed goto to the new destination.  */
 322           GOTO_DESTINATION (last) = factored_label_decl;
 323         }
 324     }
 325 }
 326
 327
 328 /* Build a flowgraph for the statement_list STMT_LIST.  */
 329
 330 static void
 331 make_blocks (tree stmt_list)
 332 {
 333   tree_stmt_iterator i = tsi_start (stmt_list);
 334   tree stmt = NULL;
 335   bool start_new_block = true;
 336   bool first_stmt_of_list = true;
 337   basic_block bb = ENTRY_BLOCK_PTR;
 338
 339   while (!tsi_end_p (i))
 340     {
 341       tree prev_stmt;
 342
 343       prev_stmt = stmt;
 344       stmt = tsi_stmt (i);
 345
 346       /* If the statement starts a new basic block or if we have determined
 347          in a previous pass that we need to create a new block for STMT, do
 348          so now.  */
 349       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 350         {
 351           if (!first_stmt_of_list)
 352             stmt_list = tsi_split_statement_list_before (&i);
 353           bb = create_basic_block (stmt_list, NULL, bb);
 354           start_new_block = false;
 355         }
 356
 357       /* Now add STMT to BB and create the subgraphs for special statement
 358          codes.  */
 359       set_bb_for_stmt (stmt, bb);
 360
 361       if (computed_goto_p (stmt))
 362         found_computed_goto = true;
 363
 364       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 365          next iteration.  */
 366       if (stmt_ends_bb_p (stmt))
 367         start_new_block = true;
 368
 369       tsi_next (&i);
 370       first_stmt_of_list = false;
 371     }
 372 }
 373
 374
 375 /* Create and return a new empty basic block after bb AFTER.  */
 376
 377 static basic_block
 378 create_bb (void *h, void *e, basic_block after)
 379 {
 380   basic_block bb;
 381
 382   gcc_assert (!e);
 383
 384   /* Create and initialize a new basic block.  Since alloc_block uses
 385      ggc_alloc_cleared to allocate a basic block, we do not have to
 386      clear the newly allocated basic block here.  */
 387   bb = alloc_block ();
 388
 389   bb->index = last_basic_block;
 390   bb->flags = BB_NEW;
 391   bb->stmt_list = h ? (tree) h : alloc_stmt_list ();
 392
 393   /* Add the new block to the linked list of blocks.  */
 394   link_block (bb, after);
 395
 396   /* Grow the basic block array if needed.  */
 397   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 398     {
 399       size_t old_size = VEC_length (basic_block, basic_block_info);
 400       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 401       basic_block *p;
 402       VEC_safe_grow (basic_block, gc, basic_block_info, new_size);
 403       p = VEC_address (basic_block, basic_block_info);
 404       memset (&p[old_size], 0, sizeof (basic_block) * (new_size - old_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       tree stmt = last_stmt (bb);
 431
 432       if (stmt
 433           && TREE_CODE (stmt) == COND_EXPR)
 434         {
 435           tree cond = fold (COND_EXPR_COND (stmt));
 436           if (integer_zerop (cond))
 437             COND_EXPR_COND (stmt) = boolean_false_node;
 438           else if (integer_onep (cond))
 439             COND_EXPR_COND (stmt) = boolean_true_node;
 440         }
 441     }
 442 }
 443
 444 /* Join all the blocks in the flowgraph.  */
 445
 446 static void
 447 make_edges (void)
 448 {
 449   basic_block bb;
 450   struct omp_region *cur_region = NULL;
 451
 452   /* Create an edge from entry to the first block with executable
 453      statements in it.  */
 454   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 455
 456   /* Traverse the basic block array placing edges.  */
 457   FOR_EACH_BB (bb)
 458     {
 459       tree last = last_stmt (bb);
 460       bool fallthru;
 461
 462       if (last)
 463         {
 464           enum tree_code code = TREE_CODE (last);
 465           switch (code)
 466             {
 467             case GOTO_EXPR:
 468               make_goto_expr_edges (bb);
 469               fallthru = false;
 470               break;
 471             case RETURN_EXPR:
 472               make_edge (bb, EXIT_BLOCK_PTR, 0);
 473               fallthru = false;
 474               break;
 475             case COND_EXPR:
 476               make_cond_expr_edges (bb);
 477               fallthru = false;
 478               break;
 479             case SWITCH_EXPR:
 480               make_switch_expr_edges (bb);
 481               fallthru = false;
 482               break;
 483             case RESX_EXPR:
 484               make_eh_edges (last);
 485               fallthru = false;
 486               break;
 487
 488             case CALL_EXPR:
 489               /* If this function receives a nonlocal goto, then we need to
 490                  make edges from this call site to all the nonlocal goto
 491                  handlers.  */
 492               if (TREE_SIDE_EFFECTS (last)
 493                   && current_function_has_nonlocal_label)
 494                 make_goto_expr_edges (bb);
 495
 496               /* If this statement has reachable exception handlers, then
 497                  create abnormal edges to them.  */
 498               make_eh_edges (last);
 499
 500               /* Some calls are known not to return.  */
 501               fallthru = !(call_expr_flags (last) & ECF_NORETURN);
 502               break;
 503
 504             case MODIFY_EXPR:
 505               if (is_ctrl_altering_stmt (last))
 506                 {
 507                   /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the
 508                      CALL_EXPR may have an abnormal edge.  Search the RHS for
 509                      this case and create any required edges.  */
 510                   tree op = get_call_expr_in (last);
 511                   if (op && TREE_SIDE_EFFECTS (op)
 512                       && current_function_has_nonlocal_label)
 513                     make_goto_expr_edges (bb);
 514
 515                   make_eh_edges (last);
 516                 }
 517               fallthru = true;
 518               break;
 519
 520             case OMP_PARALLEL:
 521             case OMP_FOR:
 522             case OMP_SINGLE:
 523             case OMP_MASTER:
 524             case OMP_ORDERED:
 525             case OMP_CRITICAL:
 526             case OMP_SECTION:
 527               cur_region = new_omp_region (bb, code, cur_region);
 528               fallthru = true;
 529               break;
 530
 531             case OMP_SECTIONS:
 532               cur_region = new_omp_region (bb, code, cur_region);
 533               fallthru = false;
 534               break;
 535
 536             case OMP_RETURN:
 537               /* In the case of an OMP_SECTION, the edge will go somewhere
 538                  other than the next block.  This will be created later.  */
 539               cur_region->exit = bb;
 540               fallthru = cur_region->type != OMP_SECTION;
 541               cur_region = cur_region->outer;
 542               break;
 543
 544             case OMP_CONTINUE:
 545               cur_region->cont = bb;
 546               switch (cur_region->type)
 547                 {
 548                 case OMP_FOR:
 549                   /* ??? Technically there should be a some sort of loopback
 550                      edge here, but it goes to a block that doesn't exist yet,
 551                      and without it, updating the ssa form would be a real
 552                      bear.  Fortunately, we don't yet do ssa before expanding
 553                      these nodes.  */
 554                   break;
 555
 556                 case OMP_SECTIONS:
 557                   /* Wire up the edges into and out of the nested sections.  */
 558                   /* ??? Similarly wrt loopback.  */
 559                   {
 560                     struct omp_region *i;
 561                     for (i = cur_region->inner; i ; i = i->next)
 562                       {
 563                         gcc_assert (i->type == OMP_SECTION);
 564                         make_edge (cur_region->entry, i->entry, 0);
 565                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 566                       }
 567                   }
 568                   break;
 569
 570                 default:
 571                   gcc_unreachable ();
 572                 }
 573               fallthru = true;
 574               break;
 575
 576             default:
 577               gcc_assert (!stmt_ends_bb_p (last));
 578               fallthru = true;
 579             }
 580         }
 581       else
 582         fallthru = true;
 583
 584       if (fallthru)
 585         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 586     }
 587
 588   if (root_omp_region)
 589     free_omp_regions ();
 590
 591   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 592   fold_cond_expr_cond ();
 593
 594   /* Clean up the graph and warn for unreachable code.  */
 595   cleanup_tree_cfg ();
 596 }
 597
 598
 599 /* Create the edges for a COND_EXPR starting at block BB.
 600    At this point, both clauses must contain only simple gotos.  */
 601
 602 static void
 603 make_cond_expr_edges (basic_block bb)
 604 {
 605   tree entry = last_stmt (bb);
 606   basic_block then_bb, else_bb;
 607   tree then_label, else_label;
 608   edge e;
 609
 610   gcc_assert (entry);
 611   gcc_assert (TREE_CODE (entry) == COND_EXPR);
 612
 613   /* Entry basic blocks for each component.  */
 614   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
 615   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
 616   then_bb = label_to_block (then_label);
 617   else_bb = label_to_block (else_label);
 618
 619   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 620 #ifdef USE_MAPPED_LOCATION
 621   e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
 622 #else
 623   e->goto_locus = EXPR_LOCUS (COND_EXPR_THEN (entry));
 624 #endif
 625   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 626   if (e)
 627     {
 628 #ifdef USE_MAPPED_LOCATION
 629       e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
 630 #else
 631       e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
 632 #endif
 633     }
 634 }
 635
 636 /* Hashing routine for EDGE_TO_CASES.  */
 637
 638 static hashval_t
 639 edge_to_cases_hash (const void *p)
 640 {
 641   edge e = ((struct edge_to_cases_elt *)p)->e;
 642
 643   /* Hash on the edge itself (which is a pointer).  */
 644   return htab_hash_pointer (e);
 645 }
 646
 647 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
 648    for equality is just a pointer comparison.  */
 649
 650 static int
 651 edge_to_cases_eq (const void *p1, const void *p2)
 652 {
 653   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
 654   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
 655
 656   return e1 == e2;
 657 }
 658
 659 /* Called for each element in the hash table (P) as we delete the
 660    edge to cases hash table.
 661
 662    Clear all the TREE_CHAINs to prevent problems with copying of
 663    SWITCH_EXPRs and structure sharing rules, then free the hash table
 664    element.  */
 665
 666 static void
 667 edge_to_cases_cleanup (void *p)
 668 {
 669   struct edge_to_cases_elt *elt = (struct edge_to_cases_elt *) p;
 670   tree t, next;
 671
 672   for (t = elt->case_labels; t; t = next)
 673     {
 674       next = TREE_CHAIN (t);
 675       TREE_CHAIN (t) = NULL;
 676     }
 677   free (p);
 678 }
 679
 680 /* Start recording information mapping edges to case labels.  */
 681
 682 void
 683 start_recording_case_labels (void)
 684 {
 685   gcc_assert (edge_to_cases == NULL);
 686
 687   edge_to_cases = htab_create (37,
 688                                edge_to_cases_hash,
 689                                edge_to_cases_eq,
 690                                edge_to_cases_cleanup);
 691 }
 692
 693 /* Return nonzero if we are recording information for case labels.  */
 694
 695 static bool
 696 recording_case_labels_p (void)
 697 {
 698   return (edge_to_cases != NULL);
 699 }
 700
 701 /* Stop recording information mapping edges to case labels and
 702    remove any information we have recorded.  */
 703 void
 704 end_recording_case_labels (void)
 705 {
 706   htab_delete (edge_to_cases);
 707   edge_to_cases = NULL;
 708 }
 709
 710 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
 711
 712 static void
 713 record_switch_edge (edge e, tree case_label)
 714 {
 715   struct edge_to_cases_elt *elt;
 716   void **slot;
 717
 718   /* Build a hash table element so we can see if E is already
 719      in the table.  */
 720   elt = XNEW (struct edge_to_cases_elt);
 721   elt->e = e;
 722   elt->case_labels = case_label;
 723
 724   slot = htab_find_slot (edge_to_cases, elt, INSERT);
 725
 726   if (*slot == NULL)
 727     {
 728       /* E was not in the hash table.  Install E into the hash table.  */
 729       *slot = (void *)elt;
 730     }
 731   else
 732     {
 733       /* E was already in the hash table.  Free ELT as we do not need it
 734          anymore.  */
 735       free (elt);
 736
 737       /* Get the entry stored in the hash table.  */
 738       elt = (struct edge_to_cases_elt *) *slot;
 739
 740       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
 741       TREE_CHAIN (case_label) = elt->case_labels;
 742       elt->case_labels = case_label;
 743     }
 744 }
 745
 746 /* If we are inside a {start,end}_recording_cases block, then return
 747    a chain of CASE_LABEL_EXPRs from T which reference E.
 748
 749    Otherwise return NULL.  */
 750
 751 static tree
 752 get_cases_for_edge (edge e, tree t)
 753 {
 754   struct edge_to_cases_elt elt, *elt_p;
 755   void **slot;
 756   size_t i, n;
 757   tree vec;
 758
 759   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 760      chains available.  Return NULL so the caller can detect this case.  */
 761   if (!recording_case_labels_p ())
 762     return NULL;
 763
 764 restart:
 765   elt.e = e;
 766   elt.case_labels = NULL;
 767   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
 768
 769   if (slot)
 770     {
 771       elt_p = (struct edge_to_cases_elt *)*slot;
 772       return elt_p->case_labels;
 773     }
 774
 775   /* If we did not find E in the hash table, then this must be the first
 776      time we have been queried for information about E & T.  Add all the
 777      elements from T to the hash table then perform the query again.  */
 778
 779   vec = SWITCH_LABELS (t);
 780   n = TREE_VEC_LENGTH (vec);
 781   for (i = 0; i < n; i++)
 782     {
 783       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 784       basic_block label_bb = label_to_block (lab);
 785       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
 786     }
 787   goto restart;
 788 }
 789
 790 /* Create the edges for a SWITCH_EXPR starting at block BB.
 791    At this point, the switch body has been lowered and the
 792    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
 793
 794 static void
 795 make_switch_expr_edges (basic_block bb)
 796 {
 797   tree entry = last_stmt (bb);
 798   size_t i, n;
 799   tree vec;
 800
 801   vec = SWITCH_LABELS (entry);
 802   n = TREE_VEC_LENGTH (vec);
 803
 804   for (i = 0; i < n; ++i)
 805     {
 806       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 807       basic_block label_bb = label_to_block (lab);
 808       make_edge (bb, label_bb, 0);
 809     }
 810 }
 811
 812
 813 /* Return the basic block holding label DEST.  */
 814
 815 basic_block
 816 label_to_block_fn (struct function *ifun, tree dest)
 817 {
 818   int uid = LABEL_DECL_UID (dest);
 819
 820   /* We would die hard when faced by an undefined label.  Emit a label to
 821      the very first basic block.  This will hopefully make even the dataflow
 822      and undefined variable warnings quite right.  */
 823   if ((errorcount || sorrycount) && uid < 0)
 824     {
 825       block_stmt_iterator bsi =
 826         bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 827       tree stmt;
 828
 829       stmt = build1 (LABEL_EXPR, void_type_node, dest);
 830       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 831       uid = LABEL_DECL_UID (dest);
 832     }
 833   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 834       <= (unsigned int) uid)
 835     return NULL;
 836   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 837 }
 838
 839 /* Create edges for a goto statement at block BB.  */
 840
 841 static void
 842 make_goto_expr_edges (basic_block bb)
 843 {
 844   tree goto_t;
 845   basic_block target_bb;
 846   bool for_call;
 847   block_stmt_iterator last = bsi_last (bb);
 848
 849   goto_t = bsi_stmt (last);
 850
 851   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
 852      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
 853      from a nonlocal goto.  */
 854   if (TREE_CODE (goto_t) != GOTO_EXPR)
 855     for_call = true;
 856   else
 857     {
 858       tree dest = GOTO_DESTINATION (goto_t);
 859       for_call = false;
 860
 861       /* A GOTO to a local label creates normal edges.  */
 862       if (simple_goto_p (goto_t))
 863         {
 864           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
 865 #ifdef USE_MAPPED_LOCATION
 866           e->goto_locus = EXPR_LOCATION (goto_t);
 867 #else
 868           e->goto_locus = EXPR_LOCUS (goto_t);
 869 #endif
 870           bsi_remove (&last, true);
 871           return;
 872         }
 873
 874       /* Nothing more to do for nonlocal gotos.  */
 875       if (TREE_CODE (dest) == LABEL_DECL)
 876         return;
 877
 878       /* Computed gotos remain.  */
 879     }
 880
 881   /* Look for the block starting with the destination label.  In the
 882      case of a computed goto, make an edge to any label block we find
 883      in the CFG.  */
 884   FOR_EACH_BB (target_bb)
 885     {
 886       block_stmt_iterator bsi;
 887
 888       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
 889         {
 890           tree target = bsi_stmt (bsi);
 891
 892           if (TREE_CODE (target) != LABEL_EXPR)
 893             break;
 894
 895           if (
 896               /* Computed GOTOs.  Make an edge to every label block that has
 897                  been marked as a potential target for a computed goto.  */
 898               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && !for_call)
 899               /* Nonlocal GOTO target.  Make an edge to every label block
 900                  that has been marked as a potential target for a nonlocal
 901                  goto.  */
 902               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call))
 903             {
 904               make_edge (bb, target_bb, EDGE_ABNORMAL);
 905               break;
 906             }
 907         }
 908     }
 909 }
 910
 911
 912 /*---------------------------------------------------------------------------
 913                                Flowgraph analysis
 914 ---------------------------------------------------------------------------*/
 915
 916 /* Cleanup useless labels in basic blocks.  This is something we wish
 917    to do early because it allows us to group case labels before creating
 918    the edges for the CFG, and it speeds up block statement iterators in
 919    all passes later on.
 920    We only run this pass once, running it more than once is probably not
 921    profitable.  */
 922
 923 /* A map from basic block index to the leading label of that block.  */
 924 static tree *label_for_bb;
 925
 926 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
 927 static void
 928 update_eh_label (struct eh_region *region)
 929 {
 930   tree old_label = get_eh_region_tree_label (region);
 931   if (old_label)
 932     {
 933       tree new_label;
 934       basic_block bb = label_to_block (old_label);
 935
 936       /* ??? After optimizing, there may be EH regions with labels
 937          that have already been removed from the function body, so
 938          there is no basic block for them.  */
 939       if (! bb)
 940         return;
 941
 942       new_label = label_for_bb[bb->index];
 943       set_eh_region_tree_label (region, new_label);
 944     }
 945 }
 946
 947 /* Given LABEL return the first label in the same basic block.  */
 948 static tree
 949 main_block_label (tree label)
 950 {
 951   basic_block bb = label_to_block (label);
 952
 953   /* label_to_block possibly inserted undefined label into the chain.  */
 954   if (!label_for_bb[bb->index])
 955     label_for_bb[bb->index] = label;
 956   return label_for_bb[bb->index];
 957 }
 958
 959 /* Cleanup redundant labels.  This is a three-step process:
 960      1) Find the leading label for each block.
 961      2) Redirect all references to labels to the leading labels.
 962      3) Cleanup all useless labels.  */
 963
 964 void
 965 cleanup_dead_labels (void)
 966 {
 967   basic_block bb;
 968   label_for_bb = XCNEWVEC (tree, last_basic_block);
 969
 970   /* Find a suitable label for each block.  We use the first user-defined
 971      label if there is one, or otherwise just the first label we see.  */
 972   FOR_EACH_BB (bb)
 973     {
 974       block_stmt_iterator i;
 975
 976       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 977         {
 978           tree label, stmt = bsi_stmt (i);
 979
 980           if (TREE_CODE (stmt) != LABEL_EXPR)
 981             break;
 982
 983           label = LABEL_EXPR_LABEL (stmt);
 984
 985           /* If we have not yet seen a label for the current block,
 986              remember this one and see if there are more labels.  */
 987           if (! label_for_bb[bb->index])
 988             {
 989               label_for_bb[bb->index] = label;
 990               continue;
 991             }
 992
 993           /* If we did see a label for the current block already, but it
 994              is an artificially created label, replace it if the current
 995              label is a user defined label.  */
 996           if (! DECL_ARTIFICIAL (label)
 997               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
 998             {
 999               label_for_bb[bb->index] = label;
1000               break;
1001             }
1002         }
1003     }
1004
1005   /* Now redirect all jumps/branches to the selected label.
1006      First do so for each block ending in a control statement.  */
1007   FOR_EACH_BB (bb)
1008     {
1009       tree stmt = last_stmt (bb);
1010       if (!stmt)
1011         continue;
1012
1013       switch (TREE_CODE (stmt))
1014         {
1015         case COND_EXPR:
1016           {
1017             tree true_branch, false_branch;
1018
1019             true_branch = COND_EXPR_THEN (stmt);
1020             false_branch = COND_EXPR_ELSE (stmt);
1021
1022             GOTO_DESTINATION (true_branch)
1023               = main_block_label (GOTO_DESTINATION (true_branch));
1024             GOTO_DESTINATION (false_branch)
1025               = main_block_label (GOTO_DESTINATION (false_branch));
1026
1027             break;
1028           }
1029
1030         case SWITCH_EXPR:
1031           {
1032             size_t i;
1033             tree vec = SWITCH_LABELS (stmt);
1034             size_t n = TREE_VEC_LENGTH (vec);
1035
1036             /* Replace all destination labels.  */
1037             for (i = 0; i < n; ++i)
1038               {
1039                 tree elt = TREE_VEC_ELT (vec, i);
1040                 tree label = main_block_label (CASE_LABEL (elt));
1041                 CASE_LABEL (elt) = label;
1042               }
1043             break;
1044           }
1045
1046         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1047            remove them until after we've created the CFG edges.  */
1048         case GOTO_EXPR:
1049           if (! computed_goto_p (stmt))
1050             {
1051               GOTO_DESTINATION (stmt)
1052                 = main_block_label (GOTO_DESTINATION (stmt));
1053               break;
1054             }
1055
1056         default:
1057           break;
1058       }
1059     }
1060
1061   for_each_eh_region (update_eh_label);
1062
1063   /* Finally, purge dead labels.  All user-defined labels and labels that
1064      can be the target of non-local gotos and labels which have their
1065      address taken are preserved.  */
1066   FOR_EACH_BB (bb)
1067     {
1068       block_stmt_iterator i;
1069       tree label_for_this_bb = label_for_bb[bb->index];
1070
1071       if (! label_for_this_bb)
1072         continue;
1073
1074       for (i = bsi_start (bb); !bsi_end_p (i); )
1075         {
1076           tree label, stmt = bsi_stmt (i);
1077
1078           if (TREE_CODE (stmt) != LABEL_EXPR)
1079             break;
1080
1081           label = LABEL_EXPR_LABEL (stmt);
1082
1083           if (label == label_for_this_bb
1084               || ! DECL_ARTIFICIAL (label)
1085               || DECL_NONLOCAL (label)
1086               || FORCED_LABEL (label))
1087             bsi_next (&i);
1088           else
1089             bsi_remove (&i, true);
1090         }
1091     }
1092
1093   free (label_for_bb);
1094 }
1095
1096 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1097    and scan the sorted vector of cases.  Combine the ones jumping to the
1098    same label.
1099    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1100
1101 void
1102 group_case_labels (void)
1103 {
1104   basic_block bb;
1105
1106   FOR_EACH_BB (bb)
1107     {
1108       tree stmt = last_stmt (bb);
1109       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1110         {
1111           tree labels = SWITCH_LABELS (stmt);
1112           int old_size = TREE_VEC_LENGTH (labels);
1113           int i, j, new_size = old_size;
1114           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1115           tree default_label;
1116
1117           /* The default label is always the last case in a switch
1118              statement after gimplification.  */
1119           default_label = CASE_LABEL (default_case);
1120
1121           /* Look for possible opportunities to merge cases.
1122              Ignore the last element of the label vector because it
1123              must be the default case.  */
1124           i = 0;
1125           while (i < old_size - 1)
1126             {
1127               tree base_case, base_label, base_high;
1128               base_case = TREE_VEC_ELT (labels, i);
1129
1130               gcc_assert (base_case);
1131               base_label = CASE_LABEL (base_case);
1132
1133               /* Discard cases that have the same destination as the
1134                  default case.  */
1135               if (base_label == default_label)
1136                 {
1137                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1138                   i++;
1139                   new_size--;
1140                   continue;
1141                 }
1142
1143               base_high = CASE_HIGH (base_case) ?
1144                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1145               i++;
1146               /* Try to merge case labels.  Break out when we reach the end
1147                  of the label vector or when we cannot merge the next case
1148                  label with the current one.  */
1149               while (i < old_size - 1)
1150                 {
1151                   tree merge_case = TREE_VEC_ELT (labels, i);
1152                   tree merge_label = CASE_LABEL (merge_case);
1153                   tree t = int_const_binop (PLUS_EXPR, base_high,
1154                                             integer_one_node, 1);
1155
1156                   /* Merge the cases if they jump to the same place,
1157                      and their ranges are consecutive.  */
1158                   if (merge_label == base_label
1159                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1160                     {
1161                       base_high = CASE_HIGH (merge_case) ?
1162                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1163                       CASE_HIGH (base_case) = base_high;
1164                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1165                       new_size--;
1166                       i++;
1167                     }
1168                   else
1169                     break;
1170                 }
1171             }
1172
1173           /* Compress the case labels in the label vector, and adjust the
1174              length of the vector.  */
1175           for (i = 0, j = 0; i < new_size; i++)
1176             {
1177               while (! TREE_VEC_ELT (labels, j))
1178                 j++;
1179               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1180             }
1181           TREE_VEC_LENGTH (labels) = new_size;
1182         }
1183     }
1184 }
1185
1186 /* Checks whether we can merge block B into block A.  */
1187
1188 static bool
1189 tree_can_merge_blocks_p (basic_block a, basic_block b)
1190 {
1191   tree stmt;
1192   block_stmt_iterator bsi;
1193   tree phi;
1194
1195   if (!single_succ_p (a))
1196     return false;
1197
1198   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1199     return false;
1200
1201   if (single_succ (a) != b)
1202     return false;
1203
1204   if (!single_pred_p (b))
1205     return false;
1206
1207   if (b == EXIT_BLOCK_PTR)
1208     return false;
1209
1210   /* If A ends by a statement causing exceptions or something similar, we
1211      cannot merge the blocks.  */
1212   stmt = last_stmt (a);
1213   if (stmt && stmt_ends_bb_p (stmt))
1214     return false;
1215
1216   /* Do not allow a block with only a non-local label to be merged.  */
1217   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1218       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1219     return false;
1220
1221   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1222      is not up-to-date, we cannot eliminate any phis.  */
1223   phi = phi_nodes (b);
1224   if (phi)
1225     {
1226       if (need_ssa_update_p ())
1227         return false;
1228
1229       for (; phi; phi = PHI_CHAIN (phi))
1230         if (!is_gimple_reg (PHI_RESULT (phi))
1231             && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1232           return false;
1233     }
1234
1235   /* Do not remove user labels.  */
1236   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1237     {
1238       stmt = bsi_stmt (bsi);
1239       if (TREE_CODE (stmt) != LABEL_EXPR)
1240         break;
1241       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1242         return false;
1243     }
1244
1245   /* Protect the loop latches.  */
1246   if (current_loops
1247       && b->loop_father->latch == b)
1248     return false;
1249
1250   return true;
1251 }
1252
1253 /* Replaces all uses of NAME by VAL.  */
1254
1255 void
1256 replace_uses_by (tree name, tree val)
1257 {
1258   imm_use_iterator imm_iter;
1259   use_operand_p use;
1260   tree stmt;
1261   edge e;
1262   unsigned i;
1263
1264
1265   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1266     {
1267       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1268         {
1269           replace_exp (use, val);
1270
1271           if (TREE_CODE (stmt) == PHI_NODE)
1272             {
1273               e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1274               if (e->flags & EDGE_ABNORMAL)
1275                 {
1276                   /* This can only occur for virtual operands, since
1277                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1278                      would prevent replacement.  */
1279                   gcc_assert (!is_gimple_reg (name));
1280                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1281                 }
1282             }
1283         }
1284       if (TREE_CODE (stmt) != PHI_NODE)
1285         {
1286           tree rhs;
1287
1288           fold_stmt_inplace (stmt);
1289           rhs = get_rhs (stmt);
1290           if (TREE_CODE (rhs) == ADDR_EXPR)
1291             recompute_tree_invariant_for_addr_expr (rhs);
1292
1293           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1294           mark_new_vars_to_rename (stmt);
1295         }
1296     }
1297
1298   gcc_assert (num_imm_uses (name) == 0);
1299
1300   /* Also update the trees stored in loop structures.  */
1301   if (current_loops)
1302     {
1303       struct loop *loop;
1304
1305       for (i = 0; i < current_loops->num; i++)
1306         {
1307           loop = current_loops->parray[i];
1308           if (loop)
1309             substitute_in_loop_info (loop, name, val);
1310         }
1311     }
1312 }
1313
1314 /* Merge block B into block A.  */
1315
1316 static void
1317 tree_merge_blocks (basic_block a, basic_block b)
1318 {
1319   block_stmt_iterator bsi;
1320   tree_stmt_iterator last;
1321   tree phi;
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   bsi = bsi_last (a);
1329   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1330     {
1331       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1332       tree copy;
1333       bool may_replace_uses = may_propagate_copy (def, use);
1334
1335       /* In case we have loops to care about, do not propagate arguments of
1336          loop closed ssa phi nodes.  */
1337       if (current_loops
1338           && is_gimple_reg (def)
1339           && TREE_CODE (use) == SSA_NAME
1340           && a->loop_father != b->loop_father)
1341         may_replace_uses = false;
1342
1343       if (!may_replace_uses)
1344         {
1345           gcc_assert (is_gimple_reg (def));
1346
1347           /* Note that just emitting the copies is fine -- there is no problem
1348              with ordering of phi nodes.  This is because A is the single
1349              predecessor of B, therefore results of the phi nodes cannot
1350              appear as arguments of the phi nodes.  */
1351           copy = build2 (MODIFY_EXPR, void_type_node, def, use);
1352           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1353           SET_PHI_RESULT (phi, NULL_TREE);
1354           SSA_NAME_DEF_STMT (def) = copy;
1355         }
1356       else
1357         replace_uses_by (def, use);
1358
1359       remove_phi_node (phi, NULL);
1360     }
1361
1362   /* Ensure that B follows A.  */
1363   move_block_after (b, a);
1364
1365   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1366   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1367
1368   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1369   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1370     {
1371       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1372         {
1373           tree label = bsi_stmt (bsi);
1374
1375           bsi_remove (&bsi, false);
1376           /* Now that we can thread computed gotos, we might have
1377              a situation where we have a forced label in block B
1378              However, the label at the start of block B might still be
1379              used in other ways (think about the runtime checking for
1380              Fortran assigned gotos).  So we can not just delete the
1381              label.  Instead we move the label to the start of block A.  */
1382           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1383             {
1384               block_stmt_iterator dest_bsi = bsi_start (a);
1385               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1386             }
1387         }
1388       else
1389         {
1390           change_bb_for_stmt (bsi_stmt (bsi), a);
1391           bsi_next (&bsi);
1392         }
1393     }
1394
1395   /* Merge the chains.  */
1396   last = tsi_last (a->stmt_list);
1397   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1398   b->stmt_list = NULL;
1399 }
1400
1401
1402 /* Return the one of two successors of BB that is not reachable by a
1403    reached by a complex edge, if there is one.  Else, return BB.  We use
1404    this in optimizations that use post-dominators for their heuristics,
1405    to catch the cases in C++ where function calls are involved.  */
1406
1407 basic_block
1408 single_noncomplex_succ (basic_block bb)
1409 {
1410   edge e0, e1;
1411   if (EDGE_COUNT (bb->succs) != 2)
1412     return bb;
1413
1414   e0 = EDGE_SUCC (bb, 0);
1415   e1 = EDGE_SUCC (bb, 1);
1416   if (e0->flags & EDGE_COMPLEX)
1417     return e1->dest;
1418   if (e1->flags & EDGE_COMPLEX)
1419     return e0->dest;
1420
1421   return bb;
1422 }
1423
1424
1425 /* Walk the function tree removing unnecessary statements.
1426
1427      * Empty statement nodes are removed
1428
1429      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1430
1431      * Unnecessary COND_EXPRs are removed
1432
1433      * Some unnecessary BIND_EXPRs are removed
1434
1435    Clearly more work could be done.  The trick is doing the analysis
1436    and removal fast enough to be a net improvement in compile times.
1437
1438    Note that when we remove a control structure such as a COND_EXPR
1439    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1440    to ensure we eliminate all the useless code.  */
1441
1442 struct rus_data
1443 {
1444   tree *last_goto;
1445   bool repeat;
1446   bool may_throw;
1447   bool may_branch;
1448   bool has_label;
1449 };
1450
1451 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1452
1453 static bool
1454 remove_useless_stmts_warn_notreached (tree stmt)
1455 {
1456   if (EXPR_HAS_LOCATION (stmt))
1457     {
1458       location_t loc = EXPR_LOCATION (stmt);
1459       if (LOCATION_LINE (loc) > 0)
1460         {
1461           warning (0, "%Hwill never be executed", &loc);
1462           return true;
1463         }
1464     }
1465
1466   switch (TREE_CODE (stmt))
1467     {
1468     case STATEMENT_LIST:
1469       {
1470         tree_stmt_iterator i;
1471         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1472           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1473             return true;
1474       }
1475       break;
1476
1477     case COND_EXPR:
1478       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1479         return true;
1480       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1481         return true;
1482       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1483         return true;
1484       break;
1485
1486     case TRY_FINALLY_EXPR:
1487     case TRY_CATCH_EXPR:
1488       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1489         return true;
1490       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1491         return true;
1492       break;
1493
1494     case CATCH_EXPR:
1495       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1496     case EH_FILTER_EXPR:
1497       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1498     case BIND_EXPR:
1499       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1500
1501     default:
1502       /* Not a live container.  */
1503       break;
1504     }
1505
1506   return false;
1507 }
1508
1509 static void
1510 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1511 {
1512   tree then_clause, else_clause, cond;
1513   bool save_has_label, then_has_label, else_has_label;
1514
1515   save_has_label = data->has_label;
1516   data->has_label = false;
1517   data->last_goto = NULL;
1518
1519   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1520
1521   then_has_label = data->has_label;
1522   data->has_label = false;
1523   data->last_goto = NULL;
1524
1525   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1526
1527   else_has_label = data->has_label;
1528   data->has_label = save_has_label | then_has_label | else_has_label;
1529
1530   then_clause = COND_EXPR_THEN (*stmt_p);
1531   else_clause = COND_EXPR_ELSE (*stmt_p);
1532   cond = fold (COND_EXPR_COND (*stmt_p));
1533
1534   /* If neither arm does anything at all, we can remove the whole IF.  */
1535   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1536     {
1537       *stmt_p = build_empty_stmt ();
1538       data->repeat = true;
1539     }
1540
1541   /* If there are no reachable statements in an arm, then we can
1542      zap the entire conditional.  */
1543   else if (integer_nonzerop (cond) && !else_has_label)
1544     {
1545       if (warn_notreached)
1546         remove_useless_stmts_warn_notreached (else_clause);
1547       *stmt_p = then_clause;
1548       data->repeat = true;
1549     }
1550   else if (integer_zerop (cond) && !then_has_label)
1551     {
1552       if (warn_notreached)
1553         remove_useless_stmts_warn_notreached (then_clause);
1554       *stmt_p = else_clause;
1555       data->repeat = true;
1556     }
1557
1558   /* Check a couple of simple things on then/else with single stmts.  */
1559   else
1560     {
1561       tree then_stmt = expr_only (then_clause);
1562       tree else_stmt = expr_only (else_clause);
1563
1564       /* Notice branches to a common destination.  */
1565       if (then_stmt && else_stmt
1566           && TREE_CODE (then_stmt) == GOTO_EXPR
1567           && TREE_CODE (else_stmt) == GOTO_EXPR
1568           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1569         {
1570           *stmt_p = then_stmt;
1571           data->repeat = true;
1572         }
1573
1574       /* If the THEN/ELSE clause merely assigns a value to a variable or
1575          parameter which is already known to contain that value, then
1576          remove the useless THEN/ELSE clause.  */
1577       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1578         {
1579           if (else_stmt
1580               && TREE_CODE (else_stmt) == MODIFY_EXPR
1581               && TREE_OPERAND (else_stmt, 0) == cond
1582               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1583             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1584         }
1585       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1586                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1587                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1588                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1589         {
1590           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1591                        ? then_stmt : else_stmt);
1592           tree *location = (TREE_CODE (cond) == EQ_EXPR
1593                             ? &COND_EXPR_THEN (*stmt_p)
1594                             : &COND_EXPR_ELSE (*stmt_p));
1595
1596           if (stmt
1597               && TREE_CODE (stmt) == MODIFY_EXPR
1598               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1599               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1600             *location = alloc_stmt_list ();
1601         }
1602     }
1603
1604   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1605      would be re-introduced during lowering.  */
1606   data->last_goto = NULL;
1607 }
1608
1609
1610 static void
1611 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1612 {
1613   bool save_may_branch, save_may_throw;
1614   bool this_may_branch, this_may_throw;
1615
1616   /* Collect may_branch and may_throw information for the body only.  */
1617   save_may_branch = data->may_branch;
1618   save_may_throw = data->may_throw;
1619   data->may_branch = false;
1620   data->may_throw = false;
1621   data->last_goto = NULL;
1622
1623   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1624
1625   this_may_branch = data->may_branch;
1626   this_may_throw = data->may_throw;
1627   data->may_branch |= save_may_branch;
1628   data->may_throw |= save_may_throw;
1629   data->last_goto = NULL;
1630
1631   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1632
1633   /* If the body is empty, then we can emit the FINALLY block without
1634      the enclosing TRY_FINALLY_EXPR.  */
1635   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1636     {
1637       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1638       data->repeat = true;
1639     }
1640
1641   /* If the handler is empty, then we can emit the TRY block without
1642      the enclosing TRY_FINALLY_EXPR.  */
1643   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1644     {
1645       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1646       data->repeat = true;
1647     }
1648
1649   /* If the body neither throws, nor branches, then we can safely
1650      string the TRY and FINALLY blocks together.  */
1651   else if (!this_may_branch && !this_may_throw)
1652     {
1653       tree stmt = *stmt_p;
1654       *stmt_p = TREE_OPERAND (stmt, 0);
1655       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1656       data->repeat = true;
1657     }
1658 }
1659
1660
1661 static void
1662 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1663 {
1664   bool save_may_throw, this_may_throw;
1665   tree_stmt_iterator i;
1666   tree stmt;
1667
1668   /* Collect may_throw information for the body only.  */
1669   save_may_throw = data->may_throw;
1670   data->may_throw = false;
1671   data->last_goto = NULL;
1672
1673   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1674
1675   this_may_throw = data->may_throw;
1676   data->may_throw = save_may_throw;
1677
1678   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1679   if (!this_may_throw)
1680     {
1681       if (warn_notreached)
1682         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1683       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1684       data->repeat = true;
1685       return;
1686     }
1687
1688   /* Process the catch clause specially.  We may be able to tell that
1689      no exceptions propagate past this point.  */
1690
1691   this_may_throw = true;
1692   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1693   stmt = tsi_stmt (i);
1694   data->last_goto = NULL;
1695
1696   switch (TREE_CODE (stmt))
1697     {
1698     case CATCH_EXPR:
1699       for (; !tsi_end_p (i); tsi_next (&i))
1700         {
1701           stmt = tsi_stmt (i);
1702           /* If we catch all exceptions, then the body does not
1703              propagate exceptions past this point.  */
1704           if (CATCH_TYPES (stmt) == NULL)
1705             this_may_throw = false;
1706           data->last_goto = NULL;
1707           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1708         }
1709       break;
1710
1711     case EH_FILTER_EXPR:
1712       if (EH_FILTER_MUST_NOT_THROW (stmt))
1713         this_may_throw = false;
1714       else if (EH_FILTER_TYPES (stmt) == NULL)
1715         this_may_throw = false;
1716       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1717       break;
1718
1719     default:
1720       /* Otherwise this is a cleanup.  */
1721       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1722
1723       /* If the cleanup is empty, then we can emit the TRY block without
1724          the enclosing TRY_CATCH_EXPR.  */
1725       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1726         {
1727           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1728           data->repeat = true;
1729         }
1730       break;
1731     }
1732   data->may_throw |= this_may_throw;
1733 }
1734
1735
1736 static void
1737 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1738 {
1739   tree block;
1740
1741   /* First remove anything underneath the BIND_EXPR.  */
1742   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1743
1744   /* If the BIND_EXPR has no variables, then we can pull everything
1745      up one level and remove the BIND_EXPR, unless this is the toplevel
1746      BIND_EXPR for the current function or an inlined function.
1747
1748      When this situation occurs we will want to apply this
1749      optimization again.  */
1750   block = BIND_EXPR_BLOCK (*stmt_p);
1751   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1752       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1753       && (! block
1754           || ! BLOCK_ABSTRACT_ORIGIN (block)
1755           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1756               != FUNCTION_DECL)))
1757     {
1758       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1759       data->repeat = true;
1760     }
1761 }
1762
1763
1764 static void
1765 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1766 {
1767   tree dest = GOTO_DESTINATION (*stmt_p);
1768
1769   data->may_branch = true;
1770   data->last_goto = NULL;
1771
1772   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1773   if (TREE_CODE (dest) == LABEL_DECL)
1774     data->last_goto = stmt_p;
1775 }
1776
1777
1778 static void
1779 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1780 {
1781   tree label = LABEL_EXPR_LABEL (*stmt_p);
1782
1783   data->has_label = true;
1784
1785   /* We do want to jump across non-local label receiver code.  */
1786   if (DECL_NONLOCAL (label))
1787     data->last_goto = NULL;
1788
1789   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1790     {
1791       *data->last_goto = build_empty_stmt ();
1792       data->repeat = true;
1793     }
1794
1795   /* ??? Add something here to delete unused labels.  */
1796 }
1797
1798
1799 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1800    decl.  This allows us to eliminate redundant or useless
1801    calls to "const" functions.
1802
1803    Gimplifier already does the same operation, but we may notice functions
1804    being const and pure once their calls has been gimplified, so we need
1805    to update the flag.  */
1806
1807 static void
1808 update_call_expr_flags (tree call)
1809 {
1810   tree decl = get_callee_fndecl (call);
1811   if (!decl)
1812     return;
1813   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1814     TREE_SIDE_EFFECTS (call) = 0;
1815   if (TREE_NOTHROW (decl))
1816     TREE_NOTHROW (call) = 1;
1817 }
1818
1819
1820 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1821
1822 void
1823 notice_special_calls (tree t)
1824 {
1825   int flags = call_expr_flags (t);
1826
1827   if (flags & ECF_MAY_BE_ALLOCA)
1828     current_function_calls_alloca = true;
1829   if (flags & ECF_RETURNS_TWICE)
1830     current_function_calls_setjmp = true;
1831 }
1832
1833
1834 /* Clear flags set by notice_special_calls.  Used by dead code removal
1835    to update the flags.  */
1836
1837 void
1838 clear_special_calls (void)
1839 {
1840   current_function_calls_alloca = false;
1841   current_function_calls_setjmp = false;
1842 }
1843
1844
1845 static void
1846 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1847 {
1848   tree t = *tp, op;
1849
1850   switch (TREE_CODE (t))
1851     {
1852     case COND_EXPR:
1853       remove_useless_stmts_cond (tp, data);
1854       break;
1855
1856     case TRY_FINALLY_EXPR:
1857       remove_useless_stmts_tf (tp, data);
1858       break;
1859
1860     case TRY_CATCH_EXPR:
1861       remove_useless_stmts_tc (tp, data);
1862       break;
1863
1864     case BIND_EXPR:
1865       remove_useless_stmts_bind (tp, data);
1866       break;
1867
1868     case GOTO_EXPR:
1869       remove_useless_stmts_goto (tp, data);
1870       break;
1871
1872     case LABEL_EXPR:
1873       remove_useless_stmts_label (tp, data);
1874       break;
1875
1876     case RETURN_EXPR:
1877       fold_stmt (tp);
1878       data->last_goto = NULL;
1879       data->may_branch = true;
1880       break;
1881
1882     case CALL_EXPR:
1883       fold_stmt (tp);
1884       data->last_goto = NULL;
1885       notice_special_calls (t);
1886       update_call_expr_flags (t);
1887       if (tree_could_throw_p (t))
1888         data->may_throw = true;
1889       break;
1890
1891     case MODIFY_EXPR:
1892       data->last_goto = NULL;
1893       fold_stmt (tp);
1894       op = get_call_expr_in (t);
1895       if (op)
1896         {
1897           update_call_expr_flags (op);
1898           notice_special_calls (op);
1899         }
1900       if (tree_could_throw_p (t))
1901         data->may_throw = true;
1902       break;
1903
1904     case STATEMENT_LIST:
1905       {
1906         tree_stmt_iterator i = tsi_start (t);
1907         while (!tsi_end_p (i))
1908           {
1909             t = tsi_stmt (i);
1910             if (IS_EMPTY_STMT (t))
1911               {
1912                 tsi_delink (&i);
1913                 continue;
1914               }
1915
1916             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1917
1918             t = tsi_stmt (i);
1919             if (TREE_CODE (t) == STATEMENT_LIST)
1920               {
1921                 tsi_link_before (&i, t, TSI_SAME_STMT);
1922                 tsi_delink (&i);
1923               }
1924             else
1925               tsi_next (&i);
1926           }
1927       }
1928       break;
1929     case ASM_EXPR:
1930       fold_stmt (tp);
1931       data->last_goto = NULL;
1932       break;
1933
1934     default:
1935       data->last_goto = NULL;
1936       break;
1937     }
1938 }
1939
1940 static unsigned int
1941 remove_useless_stmts (void)
1942 {
1943   struct rus_data data;
1944
1945   clear_special_calls ();
1946
1947   do
1948     {
1949       memset (&data, 0, sizeof (data));
1950       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1951     }
1952   while (data.repeat);
1953   return 0;
1954 }
1955
1956
1957 struct tree_opt_pass pass_remove_useless_stmts =
1958 {
1959   "useless",                            /* name */
1960   NULL,                                 /* gate */
1961   remove_useless_stmts,                 /* execute */
1962   NULL,                                 /* sub */
1963   NULL,                                 /* next */
1964   0,                                    /* static_pass_number */
1965   0,                                    /* tv_id */
1966   PROP_gimple_any,                      /* properties_required */
1967   0,                                    /* properties_provided */
1968   0,                                    /* properties_destroyed */
1969   0,                                    /* todo_flags_start */
1970   TODO_dump_func,                       /* todo_flags_finish */
1971   0                                     /* letter */
1972 };
1973
1974 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1975
1976 static void
1977 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1978 {
1979   tree phi;
1980
1981   /* Since this block is no longer reachable, we can just delete all
1982      of its PHI nodes.  */
1983   phi = phi_nodes (bb);
1984   while (phi)
1985     {
1986       tree next = PHI_CHAIN (phi);
1987       remove_phi_node (phi, NULL_TREE);
1988       phi = next;
1989     }
1990
1991   /* Remove edges to BB's successors.  */
1992   while (EDGE_COUNT (bb->succs) > 0)
1993     remove_edge (EDGE_SUCC (bb, 0));
1994 }
1995
1996
1997 /* Remove statements of basic block BB.  */
1998
1999 static void
2000 remove_bb (basic_block bb)
2001 {
2002   block_stmt_iterator i;
2003 #ifdef USE_MAPPED_LOCATION
2004   source_location loc = UNKNOWN_LOCATION;
2005 #else
2006   source_locus loc = 0;
2007 #endif
2008
2009   if (dump_file)
2010     {
2011       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2012       if (dump_flags & TDF_DETAILS)
2013         {
2014           dump_bb (bb, dump_file, 0);
2015           fprintf (dump_file, "\n");
2016         }
2017     }
2018
2019   /* If we remove the header or the latch of a loop, mark the loop for
2020      removal by setting its header and latch to NULL.  */
2021   if (current_loops)
2022     {
2023       struct loop *loop = bb->loop_father;
2024
2025       if (loop->latch == bb
2026           || loop->header == bb)
2027         {
2028           loop->latch = NULL;
2029           loop->header = NULL;
2030
2031           /* Also clean up the information associated with the loop.  Updating
2032              it would waste time. More importantly, it may refer to ssa
2033              names that were defined in other removed basic block -- these
2034              ssa names are now removed and invalid.  */
2035           free_numbers_of_iterations_estimates_loop (loop);
2036         }
2037     }
2038
2039   /* Remove all the instructions in the block.  */
2040   for (i = bsi_start (bb); !bsi_end_p (i);)
2041     {
2042       tree stmt = bsi_stmt (i);
2043       if (TREE_CODE (stmt) == LABEL_EXPR
2044           && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2045               || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2046         {
2047           basic_block new_bb;
2048           block_stmt_iterator new_bsi;
2049
2050           /* A non-reachable non-local label may still be referenced.
2051              But it no longer needs to carry the extra semantics of
2052              non-locality.  */
2053           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2054             {
2055               DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2056               FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2057             }
2058
2059           new_bb = bb->prev_bb;
2060           new_bsi = bsi_start (new_bb);
2061           bsi_remove (&i, false);
2062           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2063         }
2064       else
2065         {
2066           /* Release SSA definitions if we are in SSA.  Note that we
2067              may be called when not in SSA.  For example,
2068              final_cleanup calls this function via
2069              cleanup_tree_cfg.  */
2070           if (in_ssa_p)
2071             release_defs (stmt);
2072
2073           bsi_remove (&i, true);
2074         }
2075
2076       /* Don't warn for removed gotos.  Gotos are often removed due to
2077          jump threading, thus resulting in bogus warnings.  Not great,
2078          since this way we lose warnings for gotos in the original
2079          program that are indeed unreachable.  */
2080       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2081         {
2082 #ifdef USE_MAPPED_LOCATION
2083           if (EXPR_HAS_LOCATION (stmt))
2084             loc = EXPR_LOCATION (stmt);
2085 #else
2086           source_locus t;
2087           t = EXPR_LOCUS (stmt);
2088           if (t && LOCATION_LINE (*t) > 0)
2089             loc = t;
2090 #endif
2091         }
2092     }
2093
2094   /* If requested, give a warning that the first statement in the
2095      block is unreachable.  We walk statements backwards in the
2096      loop above, so the last statement we process is the first statement
2097      in the block.  */
2098 #ifdef USE_MAPPED_LOCATION
2099   if (loc > BUILTINS_LOCATION)
2100     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2101 #else
2102   if (loc)
2103     warning (OPT_Wunreachable_code, "%Hwill never be executed", loc);
2104 #endif
2105
2106   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2107 }
2108
2109
2110 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2111    predicate VAL, return the edge that will be taken out of the block.
2112    If VAL does not match a unique edge, NULL is returned.  */
2113
2114 edge
2115 find_taken_edge (basic_block bb, tree val)
2116 {
2117   tree stmt;
2118
2119   stmt = last_stmt (bb);
2120
2121   gcc_assert (stmt);
2122   gcc_assert (is_ctrl_stmt (stmt));
2123   gcc_assert (val);
2124
2125   if (! is_gimple_min_invariant (val))
2126     return NULL;
2127
2128   if (TREE_CODE (stmt) == COND_EXPR)
2129     return find_taken_edge_cond_expr (bb, val);
2130
2131   if (TREE_CODE (stmt) == SWITCH_EXPR)
2132     return find_taken_edge_switch_expr (bb, val);
2133
2134   if (computed_goto_p (stmt))
2135     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2136
2137   gcc_unreachable ();
2138 }
2139
2140 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2141    statement, determine which of the outgoing edges will be taken out of the
2142    block.  Return NULL if either edge may be taken.  */
2143
2144 static edge
2145 find_taken_edge_computed_goto (basic_block bb, tree val)
2146 {
2147   basic_block dest;
2148   edge e = NULL;
2149
2150   dest = label_to_block (val);
2151   if (dest)
2152     {
2153       e = find_edge (bb, dest);
2154       gcc_assert (e != NULL);
2155     }
2156
2157   return e;
2158 }
2159
2160 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2161    statement, determine which of the two edges will be taken out of the
2162    block.  Return NULL if either edge may be taken.  */
2163
2164 static edge
2165 find_taken_edge_cond_expr (basic_block bb, tree val)
2166 {
2167   edge true_edge, false_edge;
2168
2169   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2170
2171   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2172   return (zero_p (val) ? false_edge : true_edge);
2173 }
2174
2175 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2176    statement, determine which edge will be taken out of the block.  Return
2177    NULL if any edge may be taken.  */
2178
2179 static edge
2180 find_taken_edge_switch_expr (basic_block bb, tree val)
2181 {
2182   tree switch_expr, taken_case;
2183   basic_block dest_bb;
2184   edge e;
2185
2186   switch_expr = last_stmt (bb);
2187   taken_case = find_case_label_for_value (switch_expr, val);
2188   dest_bb = label_to_block (CASE_LABEL (taken_case));
2189
2190   e = find_edge (bb, dest_bb);
2191   gcc_assert (e);
2192   return e;
2193 }
2194
2195
2196 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2197    We can make optimal use here of the fact that the case labels are
2198    sorted: We can do a binary search for a case matching VAL.  */
2199
2200 static tree
2201 find_case_label_for_value (tree switch_expr, tree val)
2202 {
2203   tree vec = SWITCH_LABELS (switch_expr);
2204   size_t low, high, n = TREE_VEC_LENGTH (vec);
2205   tree default_case = TREE_VEC_ELT (vec, n - 1);
2206
2207   for (low = -1, high = n - 1; high - low > 1; )
2208     {
2209       size_t i = (high + low) / 2;
2210       tree t = TREE_VEC_ELT (vec, i);
2211       int cmp;
2212
2213       /* Cache the result of comparing CASE_LOW and val.  */
2214       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2215
2216       if (cmp > 0)
2217         high = i;
2218       else
2219         low = i;
2220
2221       if (CASE_HIGH (t) == NULL)
2222         {
2223           /* A singe-valued case label.  */
2224           if (cmp == 0)
2225             return t;
2226         }
2227       else
2228         {
2229           /* A case range.  We can only handle integer ranges.  */
2230           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2231             return t;
2232         }
2233     }
2234
2235   return default_case;
2236 }
2237
2238
2239
2240
2241 /*---------------------------------------------------------------------------
2242                               Debugging functions
2243 ---------------------------------------------------------------------------*/
2244
2245 /* Dump tree-specific information of block BB to file OUTF.  */
2246
2247 void
2248 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2249 {
2250   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2251 }
2252
2253
2254 /* Dump a basic block on stderr.  */
2255
2256 void
2257 debug_tree_bb (basic_block bb)
2258 {
2259   dump_bb (bb, stderr, 0);
2260 }
2261
2262
2263 /* Dump basic block with index N on stderr.  */
2264
2265 basic_block
2266 debug_tree_bb_n (int n)
2267 {
2268   debug_tree_bb (BASIC_BLOCK (n));
2269   return BASIC_BLOCK (n);
2270 }
2271
2272
2273 /* Dump the CFG on stderr.
2274
2275    FLAGS are the same used by the tree dumping functions
2276    (see TDF_* in tree-pass.h).  */
2277
2278 void
2279 debug_tree_cfg (int flags)
2280 {
2281   dump_tree_cfg (stderr, flags);
2282 }
2283
2284
2285 /* Dump the program showing basic block boundaries on the given FILE.
2286
2287    FLAGS are the same used by the tree dumping functions (see TDF_* in
2288    tree.h).  */
2289
2290 void
2291 dump_tree_cfg (FILE *file, int flags)
2292 {
2293   if (flags & TDF_DETAILS)
2294     {
2295       const char *funcname
2296         = lang_hooks.decl_printable_name (current_function_decl, 2);
2297
2298       fputc ('\n', file);
2299       fprintf (file, ";; Function %s\n\n", funcname);
2300       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2301                n_basic_blocks, n_edges, last_basic_block);
2302
2303       brief_dump_cfg (file);
2304       fprintf (file, "\n");
2305     }
2306
2307   if (flags & TDF_STATS)
2308     dump_cfg_stats (file);
2309
2310   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2311 }
2312
2313
2314 /* Dump CFG statistics on FILE.  */
2315
2316 void
2317 dump_cfg_stats (FILE *file)
2318 {
2319   static long max_num_merged_labels = 0;
2320   unsigned long size, total = 0;
2321   long num_edges;
2322   basic_block bb;
2323   const char * const fmt_str   = "%-30s%-13s%12s\n";
2324   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2325   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2326   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2327   const char *funcname
2328     = lang_hooks.decl_printable_name (current_function_decl, 2);
2329
2330
2331   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2332
2333   fprintf (file, "---------------------------------------------------------\n");
2334   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2335   fprintf (file, fmt_str, "", "  instances  ", "used ");
2336   fprintf (file, "---------------------------------------------------------\n");
2337
2338   size = n_basic_blocks * sizeof (struct basic_block_def);
2339   total += size;
2340   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2341            SCALE (size), LABEL (size));
2342
2343   num_edges = 0;
2344   FOR_EACH_BB (bb)
2345     num_edges += EDGE_COUNT (bb->succs);
2346   size = num_edges * sizeof (struct edge_def);
2347   total += size;
2348   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2349
2350   fprintf (file, "---------------------------------------------------------\n");
2351   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2352            LABEL (total));
2353   fprintf (file, "---------------------------------------------------------\n");
2354   fprintf (file, "\n");
2355
2356   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2357     max_num_merged_labels = cfg_stats.num_merged_labels;
2358
2359   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2360            cfg_stats.num_merged_labels, max_num_merged_labels);
2361
2362   fprintf (file, "\n");
2363 }
2364
2365
2366 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2367    linked in the final executable.  */
2368
2369 void
2370 debug_cfg_stats (void)
2371 {
2372   dump_cfg_stats (stderr);
2373 }
2374
2375
2376 /* Dump the flowgraph to a .vcg FILE.  */
2377
2378 static void
2379 tree_cfg2vcg (FILE *file)
2380 {
2381   edge e;
2382   edge_iterator ei;
2383   basic_block bb;
2384   const char *funcname
2385     = lang_hooks.decl_printable_name (current_function_decl, 2);
2386
2387   /* Write the file header.  */
2388   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2389   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2390   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2391
2392   /* Write blocks and edges.  */
2393   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2394     {
2395       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2396                e->dest->index);
2397
2398       if (e->flags & EDGE_FAKE)
2399         fprintf (file, " linestyle: dotted priority: 10");
2400       else
2401         fprintf (file, " linestyle: solid priority: 100");
2402
2403       fprintf (file, " }\n");
2404     }
2405   fputc ('\n', file);
2406
2407   FOR_EACH_BB (bb)
2408     {
2409       enum tree_code head_code, end_code;
2410       const char *head_name, *end_name;
2411       int head_line = 0;
2412       int end_line = 0;
2413       tree first = first_stmt (bb);
2414       tree last = last_stmt (bb);
2415
2416       if (first)
2417         {
2418           head_code = TREE_CODE (first);
2419           head_name = tree_code_name[head_code];
2420           head_line = get_lineno (first);
2421         }
2422       else
2423         head_name = "no-statement";
2424
2425       if (last)
2426         {
2427           end_code = TREE_CODE (last);
2428           end_name = tree_code_name[end_code];
2429           end_line = get_lineno (last);
2430         }
2431       else
2432         end_name = "no-statement";
2433
2434       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2435                bb->index, bb->index, head_name, head_line, end_name,
2436                end_line);
2437
2438       FOR_EACH_EDGE (e, ei, bb->succs)
2439         {
2440           if (e->dest == EXIT_BLOCK_PTR)
2441             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2442           else
2443             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2444
2445           if (e->flags & EDGE_FAKE)
2446             fprintf (file, " priority: 10 linestyle: dotted");
2447           else
2448             fprintf (file, " priority: 100 linestyle: solid");
2449
2450           fprintf (file, " }\n");
2451         }
2452
2453       if (bb->next_bb != EXIT_BLOCK_PTR)
2454         fputc ('\n', file);
2455     }
2456
2457   fputs ("}\n\n", file);
2458 }
2459
2460
2461
2462 /*---------------------------------------------------------------------------
2463                              Miscellaneous helpers
2464 ---------------------------------------------------------------------------*/
2465
2466 /* Return true if T represents a stmt that always transfers control.  */
2467
2468 bool
2469 is_ctrl_stmt (tree t)
2470 {
2471   return (TREE_CODE (t) == COND_EXPR
2472           || TREE_CODE (t) == SWITCH_EXPR
2473           || TREE_CODE (t) == GOTO_EXPR
2474           || TREE_CODE (t) == RETURN_EXPR
2475           || TREE_CODE (t) == RESX_EXPR);
2476 }
2477
2478
2479 /* Return true if T is a statement that may alter the flow of control
2480    (e.g., a call to a non-returning function).  */
2481
2482 bool
2483 is_ctrl_altering_stmt (tree t)
2484 {
2485   tree call;
2486
2487   gcc_assert (t);
2488   call = get_call_expr_in (t);
2489   if (call)
2490     {
2491       /* A non-pure/const CALL_EXPR alters flow control if the current
2492          function has nonlocal labels.  */
2493       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2494         return true;
2495
2496       /* A CALL_EXPR also alters control flow if it does not return.  */
2497       if (call_expr_flags (call) & ECF_NORETURN)
2498         return true;
2499     }
2500
2501   /* OpenMP directives alter control flow.  */
2502   if (OMP_DIRECTIVE_P (t))
2503     return true;
2504
2505   /* If a statement can throw, it alters control flow.  */
2506   return tree_can_throw_internal (t);
2507 }
2508
2509
2510 /* Return true if T is a computed goto.  */
2511
2512 bool
2513 computed_goto_p (tree t)
2514 {
2515   return (TREE_CODE (t) == GOTO_EXPR
2516           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2517 }
2518
2519
2520 /* Checks whether EXPR is a simple local goto.  */
2521
2522 bool
2523 simple_goto_p (tree expr)
2524 {
2525   return (TREE_CODE (expr) == GOTO_EXPR
2526           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2527 }
2528
2529
2530 /* Return true if T should start a new basic block.  PREV_T is the
2531    statement preceding T.  It is used when T is a label or a case label.
2532    Labels should only start a new basic block if their previous statement
2533    wasn't a label.  Otherwise, sequence of labels would generate
2534    unnecessary basic blocks that only contain a single label.  */
2535
2536 static inline bool
2537 stmt_starts_bb_p (tree t, tree prev_t)
2538 {
2539   if (t == NULL_TREE)
2540     return false;
2541
2542   /* LABEL_EXPRs start a new basic block only if the preceding
2543      statement wasn't a label of the same type.  This prevents the
2544      creation of consecutive blocks that have nothing but a single
2545      label.  */
2546   if (TREE_CODE (t) == LABEL_EXPR)
2547     {
2548       /* Nonlocal and computed GOTO targets always start a new block.  */
2549       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2550           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2551         return true;
2552
2553       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2554         {
2555           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2556             return true;
2557
2558           cfg_stats.num_merged_labels++;
2559           return false;
2560         }
2561       else
2562         return true;
2563     }
2564
2565   return false;
2566 }
2567
2568
2569 /* Return true if T should end a basic block.  */
2570
2571 bool
2572 stmt_ends_bb_p (tree t)
2573 {
2574   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2575 }
2576
2577
2578 /* Add gotos that used to be represented implicitly in the CFG.  */
2579
2580 void
2581 disband_implicit_edges (void)
2582 {
2583   basic_block bb;
2584   block_stmt_iterator last;
2585   edge e;
2586   edge_iterator ei;
2587   tree stmt, label;
2588
2589   FOR_EACH_BB (bb)
2590     {
2591       last = bsi_last (bb);
2592       stmt = last_stmt (bb);
2593
2594       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2595         {
2596           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2597              from cfg_remove_useless_stmts here since it violates the
2598              invariants for tree--cfg correspondence and thus fits better
2599              here where we do it anyway.  */
2600           e = find_edge (bb, bb->next_bb);
2601           if (e)
2602             {
2603               if (e->flags & EDGE_TRUE_VALUE)
2604                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2605               else if (e->flags & EDGE_FALSE_VALUE)
2606                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2607               else
2608                 gcc_unreachable ();
2609               e->flags |= EDGE_FALLTHRU;
2610             }
2611
2612           continue;
2613         }
2614
2615       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2616         {
2617           /* Remove the RETURN_EXPR if we may fall though to the exit
2618              instead.  */
2619           gcc_assert (single_succ_p (bb));
2620           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2621
2622           if (bb->next_bb == EXIT_BLOCK_PTR
2623               && !TREE_OPERAND (stmt, 0))
2624             {
2625               bsi_remove (&last, true);
2626               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2627             }
2628           continue;
2629         }
2630
2631       /* There can be no fallthru edge if the last statement is a control
2632          one.  */
2633       if (stmt && is_ctrl_stmt (stmt))
2634         continue;
2635
2636       /* Find a fallthru edge and emit the goto if necessary.  */
2637       FOR_EACH_EDGE (e, ei, bb->succs)
2638         if (e->flags & EDGE_FALLTHRU)
2639           break;
2640
2641       if (!e || e->dest == bb->next_bb)
2642         continue;
2643
2644       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2645       label = tree_block_label (e->dest);
2646
2647       stmt = build1 (GOTO_EXPR, void_type_node, label);
2648 #ifdef USE_MAPPED_LOCATION
2649       SET_EXPR_LOCATION (stmt, e->goto_locus);
2650 #else
2651       SET_EXPR_LOCUS (stmt, e->goto_locus);
2652 #endif
2653       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2654       e->flags &= ~EDGE_FALLTHRU;
2655     }
2656 }
2657
2658 /* Remove block annotations and other datastructures.  */
2659
2660 void
2661 delete_tree_cfg_annotations (void)
2662 {
2663   label_to_block_map = NULL;
2664 }
2665
2666
2667 /* Return the first statement in basic block BB.  */
2668
2669 tree
2670 first_stmt (basic_block bb)
2671 {
2672   block_stmt_iterator i = bsi_start (bb);
2673   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2674 }
2675
2676
2677 /* Return the last statement in basic block BB.  */
2678
2679 tree
2680 last_stmt (basic_block bb)
2681 {
2682   block_stmt_iterator b = bsi_last (bb);
2683   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2684 }
2685
2686
2687 /* Return a pointer to the last statement in block BB.  */
2688
2689 tree *
2690 last_stmt_ptr (basic_block bb)
2691 {
2692   block_stmt_iterator last = bsi_last (bb);
2693   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2694 }
2695
2696
2697 /* Return the last statement of an otherwise empty block.  Return NULL
2698    if the block is totally empty, or if it contains more than one
2699    statement.  */
2700
2701 tree
2702 last_and_only_stmt (basic_block bb)
2703 {
2704   block_stmt_iterator i = bsi_last (bb);
2705   tree last, prev;
2706
2707   if (bsi_end_p (i))
2708     return NULL_TREE;
2709
2710   last = bsi_stmt (i);
2711   bsi_prev (&i);
2712   if (bsi_end_p (i))
2713     return last;
2714
2715   /* Empty statements should no longer appear in the instruction stream.
2716      Everything that might have appeared before should be deleted by
2717      remove_useless_stmts, and the optimizers should just bsi_remove
2718      instead of smashing with build_empty_stmt.
2719
2720      Thus the only thing that should appear here in a block containing
2721      one executable statement is a label.  */
2722   prev = bsi_stmt (i);
2723   if (TREE_CODE (prev) == LABEL_EXPR)
2724     return last;
2725   else
2726     return NULL_TREE;
2727 }
2728
2729
2730 /* Mark BB as the basic block holding statement T.  */
2731
2732 void
2733 set_bb_for_stmt (tree t, basic_block bb)
2734 {
2735   if (TREE_CODE (t) == PHI_NODE)
2736     PHI_BB (t) = bb;
2737   else if (TREE_CODE (t) == STATEMENT_LIST)
2738     {
2739       tree_stmt_iterator i;
2740       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2741         set_bb_for_stmt (tsi_stmt (i), bb);
2742     }
2743   else
2744     {
2745       stmt_ann_t ann = get_stmt_ann (t);
2746       ann->bb = bb;
2747
2748       /* If the statement is a label, add the label to block-to-labels map
2749         so that we can speed up edge creation for GOTO_EXPRs.  */
2750       if (TREE_CODE (t) == LABEL_EXPR)
2751         {
2752           int uid;
2753
2754           t = LABEL_EXPR_LABEL (t);
2755           uid = LABEL_DECL_UID (t);
2756           if (uid == -1)
2757             {
2758               unsigned old_len = VEC_length (basic_block, label_to_block_map);
2759               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2760               if (old_len <= (unsigned) uid)
2761                 {
2762                   basic_block *addr;
2763                   unsigned new_len = 3 * uid / 2;
2764
2765                   VEC_safe_grow (basic_block, gc, label_to_block_map,
2766                                  new_len);
2767                   addr = VEC_address (basic_block, label_to_block_map);
2768                   memset (&addr[old_len],
2769                           0, sizeof (basic_block) * (new_len - old_len));
2770                 }
2771             }
2772           else
2773             /* We're moving an existing label.  Make sure that we've
2774                 removed it from the old block.  */
2775             gcc_assert (!bb
2776                         || !VEC_index (basic_block, label_to_block_map, uid));
2777           VEC_replace (basic_block, label_to_block_map, uid, bb);
2778         }
2779     }
2780 }
2781
2782 /* Faster version of set_bb_for_stmt that assume that statement is being moved
2783    from one basic block to another.
2784    For BB splitting we can run into quadratic case, so performance is quite
2785    important and knowing that the tables are big enough, change_bb_for_stmt
2786    can inline as leaf function.  */
2787 static inline void
2788 change_bb_for_stmt (tree t, basic_block bb)
2789 {
2790   get_stmt_ann (t)->bb = bb;
2791   if (TREE_CODE (t) == LABEL_EXPR)
2792     VEC_replace (basic_block, label_to_block_map,
2793                  LABEL_DECL_UID (LABEL_EXPR_LABEL (t)), bb);
2794 }
2795
2796 /* Finds iterator for STMT.  */
2797
2798 extern block_stmt_iterator
2799 bsi_for_stmt (tree stmt)
2800 {
2801   block_stmt_iterator bsi;
2802
2803   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2804     if (bsi_stmt (bsi) == stmt)
2805       return bsi;
2806
2807   gcc_unreachable ();
2808 }
2809
2810 /* Mark statement T as modified, and update it.  */
2811 static inline void
2812 update_modified_stmts (tree t)
2813 {
2814   if (TREE_CODE (t) == STATEMENT_LIST)
2815     {
2816       tree_stmt_iterator i;
2817       tree stmt;
2818       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2819         {
2820           stmt = tsi_stmt (i);
2821           update_stmt_if_modified (stmt);
2822         }
2823     }
2824   else
2825     update_stmt_if_modified (t);
2826 }
2827
2828 /* Insert statement (or statement list) T before the statement
2829    pointed-to by iterator I.  M specifies how to update iterator I
2830    after insertion (see enum bsi_iterator_update).  */
2831
2832 void
2833 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2834 {
2835   set_bb_for_stmt (t, i->bb);
2836   update_modified_stmts (t);
2837   tsi_link_before (&i->tsi, t, m);
2838 }
2839
2840
2841 /* Insert statement (or statement list) T after the statement
2842    pointed-to by iterator I.  M specifies how to update iterator I
2843    after insertion (see enum bsi_iterator_update).  */
2844
2845 void
2846 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2847 {
2848   set_bb_for_stmt (t, i->bb);
2849   update_modified_stmts (t);
2850   tsi_link_after (&i->tsi, t, m);
2851 }
2852
2853
2854 /* Remove the statement pointed to by iterator I.  The iterator is updated
2855    to the next statement.
2856
2857    When REMOVE_EH_INFO is true we remove the statement pointed to by
2858    iterator I from the EH tables.  Otherwise we do not modify the EH
2859    tables.
2860
2861    Generally, REMOVE_EH_INFO should be true when the statement is going to
2862    be removed from the IL and not reinserted elsewhere.  */
2863
2864 void
2865 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2866 {
2867   tree t = bsi_stmt (*i);
2868   set_bb_for_stmt (t, NULL);
2869   delink_stmt_imm_use (t);
2870   tsi_delink (&i->tsi);
2871   mark_stmt_modified (t);
2872   if (remove_eh_info)
2873     remove_stmt_from_eh_region (t);
2874 }
2875
2876
2877 /* Move the statement at FROM so it comes right after the statement at TO.  */
2878
2879 void
2880 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2881 {
2882   tree stmt = bsi_stmt (*from);
2883   bsi_remove (from, false);
2884   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2885 }
2886
2887
2888 /* Move the statement at FROM so it comes right before the statement at TO.  */
2889
2890 void
2891 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2892 {
2893   tree stmt = bsi_stmt (*from);
2894   bsi_remove (from, false);
2895   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2896 }
2897
2898
2899 /* Move the statement at FROM to the end of basic block BB.  */
2900
2901 void
2902 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2903 {
2904   block_stmt_iterator last = bsi_last (bb);
2905
2906   /* Have to check bsi_end_p because it could be an empty block.  */
2907   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2908     bsi_move_before (from, &last);
2909   else
2910     bsi_move_after (from, &last);
2911 }
2912
2913
2914 /* Replace the contents of the statement pointed to by iterator BSI
2915    with STMT.  If UPDATE_EH_INFO is true, the exception handling
2916    information of the original statement is moved to the new statement.  */
2917
2918 void
2919 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2920 {
2921   int eh_region;
2922   tree orig_stmt = bsi_stmt (*bsi);
2923
2924   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2925   set_bb_for_stmt (stmt, bsi->bb);
2926
2927   /* Preserve EH region information from the original statement, if
2928      requested by the caller.  */
2929   if (update_eh_info)
2930     {
2931       eh_region = lookup_stmt_eh_region (orig_stmt);
2932       if (eh_region >= 0)
2933         {
2934           remove_stmt_from_eh_region (orig_stmt);
2935           add_stmt_to_eh_region (stmt, eh_region);
2936         }
2937     }
2938
2939   delink_stmt_imm_use (orig_stmt);
2940   *bsi_stmt_ptr (*bsi) = stmt;
2941   mark_stmt_modified (stmt);
2942   update_modified_stmts (stmt);
2943 }
2944
2945
2946 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2947    is made to place the statement in an existing basic block, but
2948    sometimes that isn't possible.  When it isn't possible, the edge is
2949    split and the statement is added to the new block.
2950
2951    In all cases, the returned *BSI points to the correct location.  The
2952    return value is true if insertion should be done after the location,
2953    or false if it should be done before the location.  If new basic block
2954    has to be created, it is stored in *NEW_BB.  */
2955
2956 static bool
2957 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2958                            basic_block *new_bb)
2959 {
2960   basic_block dest, src;
2961   tree tmp;
2962
2963   dest = e->dest;
2964  restart:
2965
2966   /* If the destination has one predecessor which has no PHI nodes,
2967      insert there.  Except for the exit block.
2968
2969      The requirement for no PHI nodes could be relaxed.  Basically we
2970      would have to examine the PHIs to prove that none of them used
2971      the value set by the statement we want to insert on E.  That
2972      hardly seems worth the effort.  */
2973   if (single_pred_p (dest)
2974       && ! phi_nodes (dest)
2975       && dest != EXIT_BLOCK_PTR)
2976     {
2977       *bsi = bsi_start (dest);
2978       if (bsi_end_p (*bsi))
2979         return true;
2980
2981       /* Make sure we insert after any leading labels.  */
2982       tmp = bsi_stmt (*bsi);
2983       while (TREE_CODE (tmp) == LABEL_EXPR)
2984         {
2985           bsi_next (bsi);
2986           if (bsi_end_p (*bsi))
2987             break;
2988           tmp = bsi_stmt (*bsi);
2989         }
2990
2991       if (bsi_end_p (*bsi))
2992         {
2993           *bsi = bsi_last (dest);
2994           return true;
2995         }
2996       else
2997         return false;
2998     }
2999
3000   /* If the source has one successor, the edge is not abnormal and
3001      the last statement does not end a basic block, insert there.
3002      Except for the entry block.  */
3003   src = e->src;
3004   if ((e->flags & EDGE_ABNORMAL) == 0
3005       && single_succ_p (src)
3006       && src != ENTRY_BLOCK_PTR)
3007     {
3008       *bsi = bsi_last (src);
3009       if (bsi_end_p (*bsi))
3010         return true;
3011
3012       tmp = bsi_stmt (*bsi);
3013       if (!stmt_ends_bb_p (tmp))
3014         return true;
3015
3016       /* Insert code just before returning the value.  We may need to decompose
3017          the return in the case it contains non-trivial operand.  */
3018       if (TREE_CODE (tmp) == RETURN_EXPR)
3019         {
3020           tree op = TREE_OPERAND (tmp, 0);
3021           if (op && !is_gimple_val (op))
3022             {
3023               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3024               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3025               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3026             }
3027           bsi_prev (bsi);
3028           return true;
3029         }
3030     }
3031
3032   /* Otherwise, create a new basic block, and split this edge.  */
3033   dest = split_edge (e);
3034   if (new_bb)
3035     *new_bb = dest;
3036   e = single_pred_edge (dest);
3037   goto restart;
3038 }
3039
3040
3041 /* This routine will commit all pending edge insertions, creating any new
3042    basic blocks which are necessary.  */
3043
3044 void
3045 bsi_commit_edge_inserts (void)
3046 {
3047   basic_block bb;
3048   edge e;
3049   edge_iterator ei;
3050
3051   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3052
3053   FOR_EACH_BB (bb)
3054     FOR_EACH_EDGE (e, ei, bb->succs)
3055       bsi_commit_one_edge_insert (e, NULL);
3056 }
3057
3058
3059 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3060    to this block, otherwise set it to NULL.  */
3061
3062 void
3063 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3064 {
3065   if (new_bb)
3066     *new_bb = NULL;
3067   if (PENDING_STMT (e))
3068     {
3069       block_stmt_iterator bsi;
3070       tree stmt = PENDING_STMT (e);
3071
3072       PENDING_STMT (e) = NULL_TREE;
3073
3074       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3075         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3076       else
3077         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3078     }
3079 }
3080
3081
3082 /* Add STMT to the pending list of edge E.  No actual insertion is
3083    made until a call to bsi_commit_edge_inserts () is made.  */
3084
3085 void
3086 bsi_insert_on_edge (edge e, tree stmt)
3087 {
3088   append_to_statement_list (stmt, &PENDING_STMT (e));
3089 }
3090
3091 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3092    block has to be created, it is returned.  */
3093
3094 basic_block
3095 bsi_insert_on_edge_immediate (edge e, tree stmt)
3096 {
3097   block_stmt_iterator bsi;
3098   basic_block new_bb = NULL;
3099
3100   gcc_assert (!PENDING_STMT (e));
3101
3102   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3103     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3104   else
3105     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3106
3107   return new_bb;
3108 }
3109
3110 /*---------------------------------------------------------------------------
3111              Tree specific functions for CFG manipulation
3112 ---------------------------------------------------------------------------*/
3113
3114 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3115
3116 static void
3117 reinstall_phi_args (edge new_edge, edge old_edge)
3118 {
3119   tree var, phi;
3120
3121   if (!PENDING_STMT (old_edge))
3122     return;
3123
3124   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3125        var && phi;
3126        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3127     {
3128       tree result = TREE_PURPOSE (var);
3129       tree arg = TREE_VALUE (var);
3130
3131       gcc_assert (result == PHI_RESULT (phi));
3132
3133       add_phi_arg (phi, arg, new_edge);
3134     }
3135
3136   PENDING_STMT (old_edge) = NULL;
3137 }
3138
3139 /* Returns the basic block after which the new basic block created
3140    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
3141    near its "logical" location.  This is of most help to humans looking
3142    at debugging dumps.  */
3143
3144 static basic_block
3145 split_edge_bb_loc (edge edge_in)
3146 {
3147   basic_block dest = edge_in->dest;
3148
3149   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3150     return edge_in->src;
3151   else
3152     return dest->prev_bb;
3153 }
3154
3155 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3156    Abort on abnormal edges.  */
3157
3158 static basic_block
3159 tree_split_edge (edge edge_in)
3160 {
3161   basic_block new_bb, after_bb, dest;
3162   edge new_edge, e;
3163
3164   /* Abnormal edges cannot be split.  */
3165   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3166
3167   dest = edge_in->dest;
3168
3169   after_bb = split_edge_bb_loc (edge_in);
3170
3171   new_bb = create_empty_bb (after_bb);
3172   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3173   new_bb->count = edge_in->count;
3174   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3175   new_edge->probability = REG_BR_PROB_BASE;
3176   new_edge->count = edge_in->count;
3177
3178   e = redirect_edge_and_branch (edge_in, new_bb);
3179   gcc_assert (e);
3180   reinstall_phi_args (new_edge, e);
3181
3182   return new_bb;
3183 }
3184
3185
3186 /* Return true when BB has label LABEL in it.  */
3187
3188 static bool
3189 has_label_p (basic_block bb, tree label)
3190 {
3191   block_stmt_iterator bsi;
3192
3193   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3194     {
3195       tree stmt = bsi_stmt (bsi);
3196
3197       if (TREE_CODE (stmt) != LABEL_EXPR)
3198         return false;
3199       if (LABEL_EXPR_LABEL (stmt) == label)
3200         return true;
3201     }
3202   return false;
3203 }
3204
3205
3206 /* Callback for walk_tree, check that all elements with address taken are
3207    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3208    inside a PHI node.  */
3209
3210 static tree
3211 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3212 {
3213   tree t = *tp, x;
3214   bool in_phi = (data != NULL);
3215
3216   if (TYPE_P (t))
3217     *walk_subtrees = 0;
3218
3219   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3220 #define CHECK_OP(N, MSG) \
3221   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3222        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3223
3224   switch (TREE_CODE (t))
3225     {
3226     case SSA_NAME:
3227       if (SSA_NAME_IN_FREE_LIST (t))
3228         {
3229           error ("SSA name in freelist but still referenced");
3230           return *tp;
3231         }
3232       break;
3233
3234     case ASSERT_EXPR:
3235       x = fold (ASSERT_EXPR_COND (t));
3236       if (x == boolean_false_node)
3237         {
3238           error ("ASSERT_EXPR with an always-false condition");
3239           return *tp;
3240         }
3241       break;
3242
3243     case MODIFY_EXPR:
3244       x = TREE_OPERAND (t, 0);
3245       if (TREE_CODE (x) == BIT_FIELD_REF
3246           && is_gimple_reg (TREE_OPERAND (x, 0)))
3247         {
3248           error ("GIMPLE register modified with BIT_FIELD_REF");
3249           return t;
3250         }
3251       break;
3252
3253     case ADDR_EXPR:
3254       {
3255         bool old_invariant;
3256         bool old_constant;
3257         bool old_side_effects;
3258         bool new_invariant;
3259         bool new_constant;
3260         bool new_side_effects;
3261
3262         /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3263            dead PHIs that take the address of something.  But if the PHI
3264            result is dead, the fact that it takes the address of anything
3265            is irrelevant.  Because we can not tell from here if a PHI result
3266            is dead, we just skip this check for PHIs altogether.  This means
3267            we may be missing "valid" checks, but what can you do?
3268            This was PR19217.  */
3269         if (in_phi)
3270           break;
3271
3272         old_invariant = TREE_INVARIANT (t);
3273         old_constant = TREE_CONSTANT (t);
3274         old_side_effects = TREE_SIDE_EFFECTS (t);
3275
3276         recompute_tree_invariant_for_addr_expr (t);
3277         new_invariant = TREE_INVARIANT (t);
3278         new_side_effects = TREE_SIDE_EFFECTS (t);
3279         new_constant = TREE_CONSTANT (t);
3280
3281         if (old_invariant != new_invariant)
3282           {
3283             error ("invariant not recomputed when ADDR_EXPR changed");
3284             return t;
3285           }
3286
3287         if (old_constant != new_constant)
3288           {
3289             error ("constant not recomputed when ADDR_EXPR changed");
3290             return t;
3291           }
3292         if (old_side_effects != new_side_effects)
3293           {
3294             error ("side effects not recomputed when ADDR_EXPR changed");
3295             return t;
3296           }
3297
3298         /* Skip any references (they will be checked when we recurse down the
3299            tree) and ensure that any variable used as a prefix is marked
3300            addressable.  */
3301         for (x = TREE_OPERAND (t, 0);
3302              handled_component_p (x);
3303              x = TREE_OPERAND (x, 0))
3304           ;
3305
3306         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3307           return NULL;
3308         if (!TREE_ADDRESSABLE (x))
3309           {
3310             error ("address taken, but ADDRESSABLE bit not set");
3311             return x;
3312           }
3313         break;
3314       }
3315
3316     case COND_EXPR:
3317       x = COND_EXPR_COND (t);
3318       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3319         {
3320           error ("non-boolean used in condition");
3321           return x;
3322         }
3323       if (!is_gimple_condexpr (x))
3324         {
3325           error ("invalid conditional operand");
3326           return x;
3327         }
3328       break;
3329
3330     case NOP_EXPR:
3331     case CONVERT_EXPR:
3332     case FIX_TRUNC_EXPR:
3333     case FIX_CEIL_EXPR:
3334     case FIX_FLOOR_EXPR:
3335     case FIX_ROUND_EXPR:
3336     case FLOAT_EXPR:
3337     case NEGATE_EXPR:
3338     case ABS_EXPR:
3339     case BIT_NOT_EXPR:
3340     case NON_LVALUE_EXPR:
3341     case TRUTH_NOT_EXPR:
3342       CHECK_OP (0, "invalid operand to unary operator");
3343       break;
3344
3345     case REALPART_EXPR:
3346     case IMAGPART_EXPR:
3347     case COMPONENT_REF:
3348     case ARRAY_REF:
3349     case ARRAY_RANGE_REF:
3350     case BIT_FIELD_REF:
3351     case VIEW_CONVERT_EXPR:
3352       /* We have a nest of references.  Verify that each of the operands
3353          that determine where to reference is either a constant or a variable,
3354          verify that the base is valid, and then show we've already checked
3355          the subtrees.  */
3356       while (handled_component_p (t))
3357         {
3358           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3359             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3360           else if (TREE_CODE (t) == ARRAY_REF
3361                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3362             {
3363               CHECK_OP (1, "invalid array index");
3364               if (TREE_OPERAND (t, 2))
3365                 CHECK_OP (2, "invalid array lower bound");
3366               if (TREE_OPERAND (t, 3))
3367                 CHECK_OP (3, "invalid array stride");
3368             }
3369           else if (TREE_CODE (t) == BIT_FIELD_REF)
3370             {
3371               CHECK_OP (1, "invalid operand to BIT_FIELD_REF");
3372               CHECK_OP (2, "invalid operand to BIT_FIELD_REF");
3373             }
3374
3375           t = TREE_OPERAND (t, 0);
3376         }
3377
3378       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3379         {
3380           error ("invalid reference prefix");
3381           return t;
3382         }
3383       *walk_subtrees = 0;
3384       break;
3385
3386     case LT_EXPR:
3387     case LE_EXPR:
3388     case GT_EXPR:
3389     case GE_EXPR:
3390     case EQ_EXPR:
3391     case NE_EXPR:
3392     case UNORDERED_EXPR:
3393     case ORDERED_EXPR:
3394     case UNLT_EXPR:
3395     case UNLE_EXPR:
3396     case UNGT_EXPR:
3397     case UNGE_EXPR:
3398     case UNEQ_EXPR:
3399     case LTGT_EXPR:
3400     case PLUS_EXPR:
3401     case MINUS_EXPR:
3402     case MULT_EXPR:
3403     case TRUNC_DIV_EXPR:
3404     case CEIL_DIV_EXPR:
3405     case FLOOR_DIV_EXPR:
3406     case ROUND_DIV_EXPR:
3407     case TRUNC_MOD_EXPR:
3408     case CEIL_MOD_EXPR:
3409     case FLOOR_MOD_EXPR:
3410     case ROUND_MOD_EXPR:
3411     case RDIV_EXPR:
3412     case EXACT_DIV_EXPR:
3413     case MIN_EXPR:
3414     case MAX_EXPR:
3415     case LSHIFT_EXPR:
3416     case RSHIFT_EXPR:
3417     case LROTATE_EXPR:
3418     case RROTATE_EXPR:
3419     case BIT_IOR_EXPR:
3420     case BIT_XOR_EXPR:
3421     case BIT_AND_EXPR:
3422       CHECK_OP (0, "invalid operand to binary operator");
3423       CHECK_OP (1, "invalid operand to binary operator");
3424       break;
3425
3426     default:
3427       break;
3428     }
3429   return NULL;
3430
3431 #undef CHECK_OP
3432 }
3433
3434
3435 /* Verify STMT, return true if STMT is not in GIMPLE form.
3436    TODO: Implement type checking.  */
3437
3438 static bool
3439 verify_stmt (tree stmt, bool last_in_block)
3440 {
3441   tree addr;
3442
3443   if (OMP_DIRECTIVE_P (stmt))
3444     {
3445       /* OpenMP directives are validated by the FE and never operated
3446          on by the optimizers.  Furthermore, OMP_FOR may contain
3447          non-gimple expressions when the main index variable has had
3448          its address taken.  This does not affect the loop itself
3449          because the header of an OMP_FOR is merely used to determine
3450          how to setup the parallel iteration.  */
3451       return false;
3452     }
3453
3454   if (!is_gimple_stmt (stmt))
3455     {
3456       error ("is not a valid GIMPLE statement");
3457       goto fail;
3458     }
3459
3460   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3461   if (addr)
3462     {
3463       debug_generic_stmt (addr);
3464       return true;
3465     }
3466
3467   /* If the statement is marked as part of an EH region, then it is
3468      expected that the statement could throw.  Verify that when we
3469      have optimizations that simplify statements such that we prove
3470      that they cannot throw, that we update other data structures
3471      to match.  */
3472   if (lookup_stmt_eh_region (stmt) >= 0)
3473     {
3474       if (!tree_could_throw_p (stmt))
3475         {
3476           error ("statement marked for throw, but doesn%'t");
3477           goto fail;
3478         }
3479       if (!last_in_block && tree_can_throw_internal (stmt))
3480         {
3481           error ("statement marked for throw in middle of block");
3482           goto fail;
3483         }
3484     }
3485
3486   return false;
3487
3488  fail:
3489   debug_generic_stmt (stmt);
3490   return true;
3491 }
3492
3493
3494 /* Return true when the T can be shared.  */
3495
3496 static bool
3497 tree_node_can_be_shared (tree t)
3498 {
3499   if (IS_TYPE_OR_DECL_P (t)
3500       || is_gimple_min_invariant (t)
3501       || TREE_CODE (t) == SSA_NAME
3502       || t == error_mark_node
3503       || TREE_CODE (t) == IDENTIFIER_NODE)
3504     return true;
3505
3506   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3507     return true;
3508
3509   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3510            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
3511          || TREE_CODE (t) == COMPONENT_REF
3512          || TREE_CODE (t) == REALPART_EXPR
3513          || TREE_CODE (t) == IMAGPART_EXPR)
3514     t = TREE_OPERAND (t, 0);
3515
3516   if (DECL_P (t))
3517     return true;
3518
3519   return false;
3520 }
3521
3522
3523 /* Called via walk_trees.  Verify tree sharing.  */
3524
3525 static tree
3526 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3527 {
3528   htab_t htab = (htab_t) data;
3529   void **slot;
3530
3531   if (tree_node_can_be_shared (*tp))
3532     {
3533       *walk_subtrees = false;
3534       return NULL;
3535     }
3536
3537   slot = htab_find_slot (htab, *tp, INSERT);
3538   if (*slot)
3539     return (tree) *slot;
3540   *slot = *tp;
3541
3542   return NULL;
3543 }
3544
3545
3546 /* Verify the GIMPLE statement chain.  */
3547
3548 void
3549 verify_stmts (void)
3550 {
3551   basic_block bb;
3552   block_stmt_iterator bsi;
3553   bool err = false;
3554   htab_t htab;
3555   tree addr;
3556
3557   timevar_push (TV_TREE_STMT_VERIFY);
3558   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3559
3560   FOR_EACH_BB (bb)
3561     {
3562       tree phi;
3563       int i;
3564
3565       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3566         {
3567           int phi_num_args = PHI_NUM_ARGS (phi);
3568
3569           if (bb_for_stmt (phi) != bb)
3570             {
3571               error ("bb_for_stmt (phi) is set to a wrong basic block");
3572               err |= true;
3573             }
3574
3575           for (i = 0; i < phi_num_args; i++)
3576             {
3577               tree t = PHI_ARG_DEF (phi, i);
3578               tree addr;
3579
3580               /* Addressable variables do have SSA_NAMEs but they
3581                  are not considered gimple values.  */
3582               if (TREE_CODE (t) != SSA_NAME
3583                   && TREE_CODE (t) != FUNCTION_DECL
3584                   && !is_gimple_val (t))
3585                 {
3586                   error ("PHI def is not a GIMPLE value");
3587                   debug_generic_stmt (phi);
3588                   debug_generic_stmt (t);
3589                   err |= true;
3590                 }
3591
3592               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3593               if (addr)
3594                 {
3595                   debug_generic_stmt (addr);
3596                   err |= true;
3597                 }
3598
3599               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3600               if (addr)
3601                 {
3602                   error ("incorrect sharing of tree nodes");
3603                   debug_generic_stmt (phi);
3604                   debug_generic_stmt (addr);
3605                   err |= true;
3606                 }
3607             }
3608         }
3609
3610       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3611         {
3612           tree stmt = bsi_stmt (bsi);
3613
3614           if (bb_for_stmt (stmt) != bb)
3615             {
3616               error ("bb_for_stmt (stmt) is set to a wrong basic block");
3617               err |= true;
3618             }
3619
3620           bsi_next (&bsi);
3621           err |= verify_stmt (stmt, bsi_end_p (bsi));
3622           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3623           if (addr)
3624             {
3625               error ("incorrect sharing of tree nodes");
3626               debug_generic_stmt (stmt);
3627               debug_generic_stmt (addr);
3628               err |= true;
3629             }
3630         }
3631     }
3632
3633   if (err)
3634     internal_error ("verify_stmts failed");
3635
3636   htab_delete (htab);
3637   timevar_pop (TV_TREE_STMT_VERIFY);
3638 }
3639
3640
3641 /* Verifies that the flow information is OK.  */
3642
3643 static int
3644 tree_verify_flow_info (void)
3645 {
3646   int err = 0;
3647   basic_block bb;
3648   block_stmt_iterator bsi;
3649   tree stmt;
3650   edge e;
3651   edge_iterator ei;
3652
3653   if (ENTRY_BLOCK_PTR->stmt_list)
3654     {
3655       error ("ENTRY_BLOCK has a statement list associated with it");
3656       err = 1;
3657     }
3658
3659   if (EXIT_BLOCK_PTR->stmt_list)
3660     {
3661       error ("EXIT_BLOCK has a statement list associated with it");
3662       err = 1;
3663     }
3664
3665   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3666     if (e->flags & EDGE_FALLTHRU)
3667       {
3668         error ("fallthru to exit from bb %d", e->src->index);
3669         err = 1;
3670       }
3671
3672   FOR_EACH_BB (bb)
3673     {
3674       bool found_ctrl_stmt = false;
3675
3676       stmt = NULL_TREE;
3677
3678       /* Skip labels on the start of basic block.  */
3679       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3680         {
3681           tree prev_stmt = stmt;
3682
3683           stmt = bsi_stmt (bsi);
3684
3685           if (TREE_CODE (stmt) != LABEL_EXPR)
3686             break;
3687
3688           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3689             {
3690               error ("nonlocal label ");
3691               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3692               fprintf (stderr, " is not first in a sequence of labels in bb %d",
3693                        bb->index);
3694               err = 1;
3695             }
3696
3697           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3698             {
3699               error ("label ");
3700               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3701               fprintf (stderr, " to block does not match in bb %d",
3702                        bb->index);
3703               err = 1;
3704             }
3705
3706           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3707               != current_function_decl)
3708             {
3709               error ("label ");
3710               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3711               fprintf (stderr, " has incorrect context in bb %d",
3712                        bb->index);
3713               err = 1;
3714             }
3715         }
3716
3717       /* Verify that body of basic block BB is free of control flow.  */
3718       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3719         {
3720           tree stmt = bsi_stmt (bsi);
3721
3722           if (found_ctrl_stmt)
3723             {
3724               error ("control flow in the middle of basic block %d",
3725                      bb->index);
3726               err = 1;
3727             }
3728
3729           if (stmt_ends_bb_p (stmt))
3730             found_ctrl_stmt = true;
3731
3732           if (TREE_CODE (stmt) == LABEL_EXPR)
3733             {
3734               error ("label ");
3735               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3736               fprintf (stderr, " in the middle of basic block %d", bb->index);
3737               err = 1;
3738             }
3739         }
3740
3741       bsi = bsi_last (bb);
3742       if (bsi_end_p (bsi))
3743         continue;
3744
3745       stmt = bsi_stmt (bsi);
3746
3747       err |= verify_eh_edges (stmt);
3748
3749       if (is_ctrl_stmt (stmt))
3750         {
3751           FOR_EACH_EDGE (e, ei, bb->succs)
3752             if (e->flags & EDGE_FALLTHRU)
3753               {
3754                 error ("fallthru edge after a control statement in bb %d",
3755                        bb->index);
3756                 err = 1;
3757               }
3758         }
3759
3760       switch (TREE_CODE (stmt))
3761         {
3762         case COND_EXPR:
3763           {
3764             edge true_edge;
3765             edge false_edge;
3766             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3767                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3768               {
3769                 error ("structured COND_EXPR at the end of bb %d", bb->index);
3770                 err = 1;
3771               }
3772
3773             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3774
3775             if (!true_edge || !false_edge
3776                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3777                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3778                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3779                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3780                 || EDGE_COUNT (bb->succs) >= 3)
3781               {
3782                 error ("wrong outgoing edge flags at end of bb %d",
3783                        bb->index);
3784                 err = 1;
3785               }
3786
3787             if (!has_label_p (true_edge->dest,
3788                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3789               {
3790                 error ("%<then%> label does not match edge at end of bb %d",
3791                        bb->index);
3792                 err = 1;
3793               }
3794
3795             if (!has_label_p (false_edge->dest,
3796                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3797               {
3798                 error ("%<else%> label does not match edge at end of bb %d",
3799                        bb->index);
3800                 err = 1;
3801               }
3802           }
3803           break;
3804
3805         case GOTO_EXPR:
3806           if (simple_goto_p (stmt))
3807             {
3808               error ("explicit goto at end of bb %d", bb->index);
3809               err = 1;
3810             }
3811           else
3812             {
3813               /* FIXME.  We should double check that the labels in the
3814                  destination blocks have their address taken.  */
3815               FOR_EACH_EDGE (e, ei, bb->succs)
3816                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3817                                  | EDGE_FALSE_VALUE))
3818                     || !(e->flags & EDGE_ABNORMAL))
3819                   {
3820                     error ("wrong outgoing edge flags at end of bb %d",
3821                            bb->index);
3822                     err = 1;
3823                   }
3824             }
3825           break;
3826
3827         case RETURN_EXPR:
3828           if (!single_succ_p (bb)
3829               || (single_succ_edge (bb)->flags
3830                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3831                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3832             {
3833               error ("wrong outgoing edge flags at end of bb %d", bb->index);
3834               err = 1;
3835             }
3836           if (single_succ (bb) != EXIT_BLOCK_PTR)
3837             {
3838               error ("return edge does not point to exit in bb %d",
3839                      bb->index);
3840               err = 1;
3841             }
3842           break;
3843
3844         case SWITCH_EXPR:
3845           {
3846             tree prev;
3847             edge e;
3848             size_t i, n;
3849             tree vec;
3850
3851             vec = SWITCH_LABELS (stmt);
3852             n = TREE_VEC_LENGTH (vec);
3853
3854             /* Mark all the destination basic blocks.  */
3855             for (i = 0; i < n; ++i)
3856               {
3857                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3858                 basic_block label_bb = label_to_block (lab);
3859
3860                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3861                 label_bb->aux = (void *)1;
3862               }
3863
3864             /* Verify that the case labels are sorted.  */
3865             prev = TREE_VEC_ELT (vec, 0);
3866             for (i = 1; i < n - 1; ++i)
3867               {
3868                 tree c = TREE_VEC_ELT (vec, i);
3869                 if (! CASE_LOW (c))
3870                   {
3871                     error ("found default case not at end of case vector");
3872                     err = 1;
3873                     continue;
3874                   }
3875                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3876                   {
3877                     error ("case labels not sorted: ");
3878                     print_generic_expr (stderr, prev, 0);
3879                     fprintf (stderr," is greater than ");
3880                     print_generic_expr (stderr, c, 0);
3881                     fprintf (stderr," but comes before it.\n");
3882                     err = 1;
3883                   }
3884                 prev = c;
3885               }
3886             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3887               {
3888                 error ("no default case found at end of case vector");
3889                 err = 1;
3890               }
3891
3892             FOR_EACH_EDGE (e, ei, bb->succs)
3893               {
3894                 if (!e->dest->aux)
3895                   {
3896                     error ("extra outgoing edge %d->%d",
3897                            bb->index, e->dest->index);
3898                     err = 1;
3899                   }
3900                 e->dest->aux = (void *)2;
3901                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3902                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3903                   {
3904                     error ("wrong outgoing edge flags at end of bb %d",
3905                            bb->index);
3906                     err = 1;
3907                   }
3908               }
3909
3910             /* Check that we have all of them.  */
3911             for (i = 0; i < n; ++i)
3912               {
3913                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3914                 basic_block label_bb = label_to_block (lab);
3915
3916                 if (label_bb->aux != (void *)2)
3917                   {
3918                     error ("missing edge %i->%i",
3919                            bb->index, label_bb->index);
3920                     err = 1;
3921                   }
3922               }
3923
3924             FOR_EACH_EDGE (e, ei, bb->succs)
3925               e->dest->aux = (void *)0;
3926           }
3927
3928         default: ;
3929         }
3930     }
3931
3932   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3933     verify_dominators (CDI_DOMINATORS);
3934
3935   return err;
3936 }
3937
3938
3939 /* Updates phi nodes after creating a forwarder block joined
3940    by edge FALLTHRU.  */
3941
3942 static void
3943 tree_make_forwarder_block (edge fallthru)
3944 {
3945   edge e;
3946   edge_iterator ei;
3947   basic_block dummy, bb;
3948   tree phi, new_phi, var;
3949
3950   dummy = fallthru->src;
3951   bb = fallthru->dest;
3952
3953   if (single_pred_p (bb))
3954     return;
3955
3956   /* If we redirected a branch we must create new phi nodes at the
3957      start of BB.  */
3958   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3959     {
3960       var = PHI_RESULT (phi);
3961       new_phi = create_phi_node (var, bb);
3962       SSA_NAME_DEF_STMT (var) = new_phi;
3963       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3964       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3965     }
3966
3967   /* Ensure that the PHI node chain is in the same order.  */
3968   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3969
3970   /* Add the arguments we have stored on edges.  */
3971   FOR_EACH_EDGE (e, ei, bb->preds)
3972     {
3973       if (e == fallthru)
3974         continue;
3975
3976       flush_pending_stmts (e);
3977     }
3978 }
3979
3980
3981 /* Return a non-special label in the head of basic block BLOCK.
3982    Create one if it doesn't exist.  */
3983
3984 tree
3985 tree_block_label (basic_block bb)
3986 {
3987   block_stmt_iterator i, s = bsi_start (bb);
3988   bool first = true;
3989   tree label, stmt;
3990
3991   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3992     {
3993       stmt = bsi_stmt (i);
3994       if (TREE_CODE (stmt) != LABEL_EXPR)
3995         break;
3996       label = LABEL_EXPR_LABEL (stmt);
3997       if (!DECL_NONLOCAL (label))
3998         {
3999           if (!first)
4000             bsi_move_before (&i, &s);
4001           return label;
4002         }
4003     }
4004
4005   label = create_artificial_label ();
4006   stmt = build1 (LABEL_EXPR, void_type_node, label);
4007   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4008   return label;
4009 }
4010
4011
4012 /* Attempt to perform edge redirection by replacing a possibly complex
4013    jump instruction by a goto or by removing the jump completely.
4014    This can apply only if all edges now point to the same block.  The
4015    parameters and return values are equivalent to
4016    redirect_edge_and_branch.  */
4017
4018 static edge
4019 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4020 {
4021   basic_block src = e->src;
4022   block_stmt_iterator b;
4023   tree stmt;
4024
4025   /* We can replace or remove a complex jump only when we have exactly
4026      two edges.  */
4027   if (EDGE_COUNT (src->succs) != 2
4028       /* Verify that all targets will be TARGET.  Specifically, the
4029          edge that is not E must also go to TARGET.  */
4030       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4031     return NULL;
4032
4033   b = bsi_last (src);
4034   if (bsi_end_p (b))
4035     return NULL;
4036   stmt = bsi_stmt (b);
4037
4038   if (TREE_CODE (stmt) == COND_EXPR
4039       || TREE_CODE (stmt) == SWITCH_EXPR)
4040     {
4041       bsi_remove (&b, true);
4042       e = ssa_redirect_edge (e, target);
4043       e->flags = EDGE_FALLTHRU;
4044       return e;
4045     }
4046
4047   return NULL;
4048 }
4049
4050
4051 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4052    edge representing the redirected branch.  */
4053
4054 static edge
4055 tree_redirect_edge_and_branch (edge e, basic_block dest)
4056 {
4057   basic_block bb = e->src;
4058   block_stmt_iterator bsi;
4059   edge ret;
4060   tree label, stmt;
4061
4062   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4063     return NULL;
4064
4065   if (e->src != ENTRY_BLOCK_PTR
4066       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4067     return ret;
4068
4069   if (e->dest == dest)
4070     return NULL;
4071
4072   label = tree_block_label (dest);
4073
4074   bsi = bsi_last (bb);
4075   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4076
4077   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4078     {
4079     case COND_EXPR:
4080       stmt = (e->flags & EDGE_TRUE_VALUE
4081               ? COND_EXPR_THEN (stmt)
4082               : COND_EXPR_ELSE (stmt));
4083       GOTO_DESTINATION (stmt) = label;
4084       break;
4085
4086     case GOTO_EXPR:
4087       /* No non-abnormal edges should lead from a non-simple goto, and
4088          simple ones should be represented implicitly.  */
4089       gcc_unreachable ();
4090
4091     case SWITCH_EXPR:
4092       {
4093         tree cases = get_cases_for_edge (e, stmt);
4094
4095         /* If we have a list of cases associated with E, then use it
4096            as it's a lot faster than walking the entire case vector.  */
4097         if (cases)
4098           {
4099             edge e2 = find_edge (e->src, dest);
4100             tree last, first;
4101
4102             first = cases;
4103             while (cases)
4104               {
4105                 last = cases;
4106                 CASE_LABEL (cases) = label;
4107                 cases = TREE_CHAIN (cases);
4108               }
4109
4110             /* If there was already an edge in the CFG, then we need
4111                to move all the cases associated with E to E2.  */
4112             if (e2)
4113               {
4114                 tree cases2 = get_cases_for_edge (e2, stmt);
4115
4116                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4117                 TREE_CHAIN (cases2) = first;
4118               }
4119           }
4120         else
4121           {
4122             tree vec = SWITCH_LABELS (stmt);
4123             size_t i, n = TREE_VEC_LENGTH (vec);
4124
4125             for (i = 0; i < n; i++)
4126               {
4127                 tree elt = TREE_VEC_ELT (vec, i);
4128
4129                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4130                   CASE_LABEL (elt) = label;
4131               }
4132           }
4133
4134         break;
4135       }
4136
4137     case RETURN_EXPR:
4138       bsi_remove (&bsi, true);
4139       e->flags |= EDGE_FALLTHRU;
4140       break;
4141
4142     default:
4143       /* Otherwise it must be a fallthru edge, and we don't need to
4144          do anything besides redirecting it.  */
4145       gcc_assert (e->flags & EDGE_FALLTHRU);
4146       break;
4147     }
4148
4149   /* Update/insert PHI nodes as necessary.  */
4150
4151   /* Now update the edges in the CFG.  */
4152   e = ssa_redirect_edge (e, dest);
4153
4154   return e;
4155 }
4156
4157
4158 /* Simple wrapper, as we can always redirect fallthru edges.  */
4159
4160 static basic_block
4161 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4162 {
4163   e = tree_redirect_edge_and_branch (e, dest);
4164   gcc_assert (e);
4165
4166   return NULL;
4167 }
4168
4169
4170 /* Splits basic block BB after statement STMT (but at least after the
4171    labels).  If STMT is NULL, BB is split just after the labels.  */
4172
4173 static basic_block
4174 tree_split_block (basic_block bb, void *stmt)
4175 {
4176   block_stmt_iterator bsi;
4177   tree_stmt_iterator tsi_tgt;
4178   tree act;
4179   basic_block new_bb;
4180   edge e;
4181   edge_iterator ei;
4182
4183   new_bb = create_empty_bb (bb);
4184
4185   /* Redirect the outgoing edges.  */
4186   new_bb->succs = bb->succs;
4187   bb->succs = NULL;
4188   FOR_EACH_EDGE (e, ei, new_bb->succs)
4189     e->src = new_bb;
4190
4191   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4192     stmt = NULL;
4193
4194   /* Move everything from BSI to the new basic block.  */
4195   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4196     {
4197       act = bsi_stmt (bsi);
4198       if (TREE_CODE (act) == LABEL_EXPR)
4199         continue;
4200
4201       if (!stmt)
4202         break;
4203
4204       if (stmt == act)
4205         {
4206           bsi_next (&bsi);
4207           break;
4208         }
4209     }
4210
4211   if (bsi_end_p (bsi))
4212     return new_bb;
4213
4214   /* Split the statement list - avoid re-creating new containers as this
4215      brings ugly quadratic memory consumption in the inliner.
4216      (We are still quadratic since we need to update stmt BB pointers,
4217      sadly.)  */
4218   new_bb->stmt_list = tsi_split_statement_list_before (&bsi.tsi);
4219   for (tsi_tgt = tsi_start (new_bb->stmt_list);
4220        !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
4221     change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
4222
4223   return new_bb;
4224 }
4225
4226
4227 /* Moves basic block BB after block AFTER.  */
4228
4229 static bool
4230 tree_move_block_after (basic_block bb, basic_block after)
4231 {
4232   if (bb->prev_bb == after)
4233     return true;
4234
4235   unlink_block (bb);
4236   link_block (bb, after);
4237
4238   return true;
4239 }
4240
4241
4242 /* Return true if basic_block can be duplicated.  */
4243
4244 static bool
4245 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4246 {
4247   return true;
4248 }
4249
4250
4251 /* Create a duplicate of the basic block BB.  NOTE: This does not
4252    preserve SSA form.  */
4253
4254 static basic_block
4255 tree_duplicate_bb (basic_block bb)
4256 {
4257   basic_block new_bb;
4258   block_stmt_iterator bsi, bsi_tgt;
4259   tree phi;
4260
4261   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4262
4263   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4264      the incoming edges have not been setup yet.  */
4265   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4266     {
4267       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4268       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4269     }
4270
4271   /* Keep the chain of PHI nodes in the same order so that they can be
4272      updated by ssa_redirect_edge.  */
4273   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4274
4275   bsi_tgt = bsi_start (new_bb);
4276   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4277     {
4278       def_operand_p def_p;
4279       ssa_op_iter op_iter;
4280       tree stmt, copy;
4281       int region;
4282
4283       stmt = bsi_stmt (bsi);
4284       if (TREE_CODE (stmt) == LABEL_EXPR)
4285         continue;
4286
4287       /* Create a new copy of STMT and duplicate STMT's virtual
4288          operands.  */
4289       copy = unshare_expr (stmt);
4290       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4291       copy_virtual_operands (copy, stmt);
4292       region = lookup_stmt_eh_region (stmt);
4293       if (region >= 0)
4294         add_stmt_to_eh_region (copy, region);
4295
4296       /* Create new names for all the definitions created by COPY and
4297          add replacement mappings for each new name.  */
4298       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4299         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4300     }
4301
4302   return new_bb;
4303 }
4304
4305
4306 /* Basic block BB_COPY was created by code duplication.  Add phi node
4307    arguments for edges going out of BB_COPY.  The blocks that were
4308    duplicated have BB_DUPLICATED set.  */
4309
4310 void
4311 add_phi_args_after_copy_bb (basic_block bb_copy)
4312 {
4313   basic_block bb, dest;
4314   edge e, e_copy;
4315   edge_iterator ei;
4316   tree phi, phi_copy, phi_next, def;
4317
4318   bb = get_bb_original (bb_copy);
4319
4320   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4321     {
4322       if (!phi_nodes (e_copy->dest))
4323         continue;
4324
4325       if (e_copy->dest->flags & BB_DUPLICATED)
4326         dest = get_bb_original (e_copy->dest);
4327       else
4328         dest = e_copy->dest;
4329
4330       e = find_edge (bb, dest);
4331       if (!e)
4332         {
4333           /* During loop unrolling the target of the latch edge is copied.
4334              In this case we are not looking for edge to dest, but to
4335              duplicated block whose original was dest.  */
4336           FOR_EACH_EDGE (e, ei, bb->succs)
4337             if ((e->dest->flags & BB_DUPLICATED)
4338                 && get_bb_original (e->dest) == dest)
4339               break;
4340
4341           gcc_assert (e != NULL);
4342         }
4343
4344       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4345            phi;
4346            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4347         {
4348           phi_next = PHI_CHAIN (phi);
4349           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4350           add_phi_arg (phi_copy, def, e_copy);
4351         }
4352     }
4353 }
4354
4355 /* Blocks in REGION_COPY array of length N_REGION were created by
4356    duplication of basic blocks.  Add phi node arguments for edges
4357    going from these blocks.  */
4358
4359 void
4360 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4361 {
4362   unsigned i;
4363
4364   for (i = 0; i < n_region; i++)
4365     region_copy[i]->flags |= BB_DUPLICATED;
4366
4367   for (i = 0; i < n_region; i++)
4368     add_phi_args_after_copy_bb (region_copy[i]);
4369
4370   for (i = 0; i < n_region; i++)
4371     region_copy[i]->flags &= ~BB_DUPLICATED;
4372 }
4373
4374 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4375    important exit edge EXIT.  By important we mean that no SSA name defined
4376    inside region is live over the other exit edges of the region.  All entry
4377    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4378    to the duplicate of the region.  SSA form, dominance and loop information
4379    is updated.  The new basic blocks are stored to REGION_COPY in the same
4380    order as they had in REGION, provided that REGION_COPY is not NULL.
4381    The function returns false if it is unable to copy the region,
4382    true otherwise.  */
4383
4384 bool
4385 tree_duplicate_sese_region (edge entry, edge exit,
4386                             basic_block *region, unsigned n_region,
4387                             basic_block *region_copy)
4388 {
4389   unsigned i, n_doms;
4390   bool free_region_copy = false, copying_header = false;
4391   struct loop *loop = entry->dest->loop_father;
4392   edge exit_copy;
4393   basic_block *doms;
4394   edge redirected;
4395   int total_freq = 0, entry_freq = 0;
4396   gcov_type total_count = 0, entry_count = 0;
4397
4398   if (!can_copy_bbs_p (region, n_region))
4399     return false;
4400
4401   /* Some sanity checking.  Note that we do not check for all possible
4402      missuses of the functions.  I.e. if you ask to copy something weird,
4403      it will work, but the state of structures probably will not be
4404      correct.  */
4405   for (i = 0; i < n_region; i++)
4406     {
4407       /* We do not handle subloops, i.e. all the blocks must belong to the
4408          same loop.  */
4409       if (region[i]->loop_father != loop)
4410         return false;
4411
4412       if (region[i] != entry->dest
4413           && region[i] == loop->header)
4414         return false;
4415     }
4416
4417   loop->copy = loop;
4418
4419   /* In case the function is used for loop header copying (which is the primary
4420      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4421   if (loop->header == entry->dest)
4422     {
4423       copying_header = true;
4424       loop->copy = loop->outer;
4425
4426       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4427         return false;
4428
4429       for (i = 0; i < n_region; i++)
4430         if (region[i] != exit->src
4431             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4432           return false;
4433     }
4434
4435   if (!region_copy)
4436     {
4437       region_copy = XNEWVEC (basic_block, n_region);
4438       free_region_copy = true;
4439     }
4440
4441   gcc_assert (!need_ssa_update_p ());
4442
4443   /* Record blocks outside the region that are dominated by something
4444      inside.  */
4445   doms = XNEWVEC (basic_block, n_basic_blocks);
4446   initialize_original_copy_tables ();
4447
4448   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4449
4450   if (entry->dest->count)
4451     {
4452       total_count = entry->dest->count;
4453       entry_count = entry->count;
4454       /* Fix up corner cases, to avoid division by zero or creation of negative
4455          frequencies.  */
4456       if (entry_count > total_count)
4457         entry_count = total_count;
4458     }
4459   else
4460     {
4461       total_freq = entry->dest->frequency;
4462       entry_freq = EDGE_FREQUENCY (entry);
4463       /* Fix up corner cases, to avoid division by zero or creation of negative
4464          frequencies.  */
4465       if (total_freq == 0)
4466         total_freq = 1;
4467       else if (entry_freq > total_freq)
4468         entry_freq = total_freq;
4469     }
4470
4471   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
4472             split_edge_bb_loc (entry));
4473   if (total_count)
4474     {
4475       scale_bbs_frequencies_gcov_type (region, n_region,
4476                                        total_count - entry_count,
4477                                        total_count);
4478       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4479                                        total_count);
4480     }
4481   else
4482     {
4483       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4484                                  total_freq);
4485       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4486     }
4487
4488   if (copying_header)
4489     {
4490       loop->header = exit->dest;
4491       loop->latch = exit->src;
4492     }
4493
4494   /* Redirect the entry and add the phi node arguments.  */
4495   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4496   gcc_assert (redirected != NULL);
4497   flush_pending_stmts (entry);
4498
4499   /* Concerning updating of dominators:  We must recount dominators
4500      for entry block and its copy.  Anything that is outside of the
4501      region, but was dominated by something inside needs recounting as
4502      well.  */
4503   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4504   doms[n_doms++] = get_bb_original (entry->dest);
4505   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4506   free (doms);
4507
4508   /* Add the other PHI node arguments.  */
4509   add_phi_args_after_copy (region_copy, n_region);
4510
4511   /* Update the SSA web.  */
4512   update_ssa (TODO_update_ssa);
4513
4514   if (free_region_copy)
4515     free (region_copy);
4516
4517   free_original_copy_tables ();
4518   return true;
4519 }
4520
4521 /*
4522 DEF_VEC_P(basic_block);
4523 DEF_VEC_ALLOC_P(basic_block,heap);
4524 */
4525
4526 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
4527    adding blocks when the dominator traversal reaches EXIT.  This
4528    function silently assumes that ENTRY strictly dominates EXIT.  */
4529
4530 static void
4531 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
4532                               VEC(basic_block,heap) **bbs_p)
4533 {
4534   basic_block son;
4535
4536   for (son = first_dom_son (CDI_DOMINATORS, entry);
4537        son;
4538        son = next_dom_son (CDI_DOMINATORS, son))
4539     {
4540       VEC_safe_push (basic_block, heap, *bbs_p, son);
4541       if (son != exit)
4542         gather_blocks_in_sese_region (son, exit, bbs_p);
4543     }
4544 }
4545
4546
4547 struct move_stmt_d
4548 {
4549   tree block;
4550   tree from_context;
4551   tree to_context;
4552   bitmap vars_to_remove;
4553   htab_t new_label_map;
4554   bool remap_decls_p;
4555 };
4556
4557 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
4558    contained in *TP and change the DECL_CONTEXT of every local
4559    variable referenced in *TP.  */
4560
4561 static tree
4562 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
4563 {
4564   struct move_stmt_d *p = (struct move_stmt_d *) data;
4565   tree t = *tp;
4566
4567   if (p->block && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (t))))
4568     TREE_BLOCK (t) = p->block;
4569
4570   if (OMP_DIRECTIVE_P (t)
4571       && TREE_CODE (t) != OMP_RETURN
4572       && TREE_CODE (t) != OMP_CONTINUE)
4573     {
4574       /* Do not remap variables inside OMP directives.  Variables
4575          referenced in clauses and directive header belong to the
4576          parent function and should not be moved into the child
4577          function.  */
4578       bool save_remap_decls_p = p->remap_decls_p;
4579       p->remap_decls_p = false;
4580       *walk_subtrees = 0;
4581
4582       walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
4583
4584       p->remap_decls_p = save_remap_decls_p;
4585     }
4586   else if (DECL_P (t) && DECL_CONTEXT (t) == p->from_context)
4587     {
4588       if (TREE_CODE (t) == LABEL_DECL)
4589         {
4590           if (p->new_label_map)
4591             {
4592               struct tree_map in, *out;
4593               in.from = t;
4594               out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
4595               if (out)
4596                 *tp = t = out->to;
4597             }
4598
4599           DECL_CONTEXT (t) = p->to_context;
4600         }
4601       else if (p->remap_decls_p)
4602         {
4603           DECL_CONTEXT (t) = p->to_context;
4604
4605           if (TREE_CODE (t) == VAR_DECL)
4606             {
4607               struct function *f = DECL_STRUCT_FUNCTION (p->to_context);
4608               f->unexpanded_var_list
4609                 = tree_cons (0, t, f->unexpanded_var_list);
4610
4611               /* Mark T to be removed from the original function,
4612                  otherwise it will be given a DECL_RTL when the
4613                  original function is expanded.  */
4614               bitmap_set_bit (p->vars_to_remove, DECL_UID (t));
4615             }
4616         }
4617     }
4618   else if (TYPE_P (t))
4619     *walk_subtrees = 0;
4620
4621   return NULL_TREE;
4622 }
4623
4624
4625 /* Move basic block BB from function CFUN to function DEST_FN.  The
4626    block is moved out of the original linked list and placed after
4627    block AFTER in the new list.  Also, the block is removed from the
4628    original array of blocks and placed in DEST_FN's array of blocks.
4629    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
4630    updated to reflect the moved edges.
4631
4632    On exit, local variables that need to be removed from
4633    CFUN->UNEXPANDED_VAR_LIST will have been added to VARS_TO_REMOVE.  */
4634
4635 static void
4636 move_block_to_fn (struct function *dest_cfun, basic_block bb,
4637                   basic_block after, bool update_edge_count_p,
4638                   bitmap vars_to_remove, htab_t new_label_map, int eh_offset)
4639 {
4640   struct control_flow_graph *cfg;
4641   edge_iterator ei;
4642   edge e;
4643   block_stmt_iterator si;
4644   struct move_stmt_d d;
4645   unsigned old_len, new_len;
4646   basic_block *addr;
4647
4648   /* Link BB to the new linked list.  */
4649   move_block_after (bb, after);
4650
4651   /* Update the edge count in the corresponding flowgraphs.  */
4652   if (update_edge_count_p)
4653     FOR_EACH_EDGE (e, ei, bb->succs)
4654       {
4655         cfun->cfg->x_n_edges--;
4656         dest_cfun->cfg->x_n_edges++;
4657       }
4658
4659   /* Remove BB from the original basic block array.  */
4660   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
4661   cfun->cfg->x_n_basic_blocks--;
4662
4663   /* Grow DEST_CFUN's basic block array if needed.  */
4664   cfg = dest_cfun->cfg;
4665   cfg->x_n_basic_blocks++;
4666   if (bb->index > cfg->x_last_basic_block)
4667     cfg->x_last_basic_block = bb->index;
4668
4669   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
4670   if ((unsigned) cfg->x_last_basic_block >= old_len)
4671     {
4672       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
4673       VEC_safe_grow (basic_block, gc, cfg->x_basic_block_info, new_len);
4674       addr = VEC_address (basic_block, cfg->x_basic_block_info);
4675       memset (&addr[old_len], 0, sizeof (basic_block) * (new_len - old_len));
4676     }
4677
4678   VEC_replace (basic_block, cfg->x_basic_block_info,
4679                cfg->x_last_basic_block, bb);
4680
4681   /* The statements in BB need to be associated with a new TREE_BLOCK.
4682      Labels need to be associated with a new label-to-block map.  */
4683   memset (&d, 0, sizeof (d));
4684   d.vars_to_remove = vars_to_remove;
4685
4686   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4687     {
4688       tree stmt = bsi_stmt (si);
4689       int region;
4690
4691       d.from_context = cfun->decl;
4692       d.to_context = dest_cfun->decl;
4693       d.remap_decls_p = true;
4694       d.new_label_map = new_label_map;
4695       if (TREE_BLOCK (stmt))
4696         d.block = DECL_INITIAL (dest_cfun->decl);
4697
4698       walk_tree (&stmt, move_stmt_r, &d, NULL);
4699
4700       if (TREE_CODE (stmt) == LABEL_EXPR)
4701         {
4702           tree label = LABEL_EXPR_LABEL (stmt);
4703           int uid = LABEL_DECL_UID (label);
4704
4705           gcc_assert (uid > -1);
4706
4707           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
4708           if (old_len <= (unsigned) uid)
4709             {
4710               new_len = 3 * uid / 2;
4711               VEC_safe_grow (basic_block, gc, cfg->x_label_to_block_map,
4712                              new_len);
4713               addr = VEC_address (basic_block, cfg->x_label_to_block_map);
4714               memset (&addr[old_len], 0,
4715                       sizeof (basic_block) * (new_len - old_len));
4716             }
4717
4718           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
4719           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
4720
4721           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
4722
4723           if (uid >= dest_cfun->last_label_uid)
4724             dest_cfun->last_label_uid = uid + 1;
4725         }
4726       else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
4727         TREE_OPERAND (stmt, 0) =
4728           build_int_cst (NULL_TREE,
4729                          TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
4730                          + eh_offset);
4731
4732       region = lookup_stmt_eh_region (stmt);
4733       if (region >= 0)
4734         {
4735           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
4736           remove_stmt_from_eh_region (stmt);
4737         }
4738     }
4739 }
4740
4741 /* Examine the statements in BB (which is in SRC_CFUN); find and return
4742    the outermost EH region.  Use REGION as the incoming base EH region.  */
4743
4744 static int
4745 find_outermost_region_in_block (struct function *src_cfun,
4746                                 basic_block bb, int region)
4747 {
4748   block_stmt_iterator si;
4749
4750   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4751     {
4752       tree stmt = bsi_stmt (si);
4753       int stmt_region;
4754
4755       if (TREE_CODE (stmt) == RESX_EXPR)
4756         stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
4757       else
4758         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
4759       if (stmt_region > 0)
4760         {
4761           if (region < 0)
4762             region = stmt_region;
4763           else if (stmt_region != region)
4764             {
4765               region = eh_region_outermost (src_cfun, stmt_region, region);
4766               gcc_assert (region != -1);
4767             }
4768         }
4769     }
4770
4771   return region;
4772 }
4773
4774 static tree
4775 new_label_mapper (tree decl, void *data)
4776 {
4777   htab_t hash = (htab_t) data;
4778   struct tree_map *m;
4779   void **slot;
4780
4781   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
4782
4783   m = xmalloc (sizeof (struct tree_map));
4784   m->hash = DECL_UID (decl);
4785   m->from = decl;
4786   m->to = create_artificial_label ();
4787   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
4788
4789   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
4790   gcc_assert (*slot == NULL);
4791
4792   *slot = m;
4793
4794   return m->to;
4795 }
4796
4797 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
4798    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
4799    single basic block in the original CFG and the new basic block is
4800    returned.  DEST_CFUN must not have a CFG yet.
4801
4802    Note that the region need not be a pure SESE region.  Blocks inside
4803    the region may contain calls to abort/exit.  The only restriction
4804    is that ENTRY_BB should be the only entry point and it must
4805    dominate EXIT_BB.
4806
4807    All local variables referenced in the region are assumed to be in
4808    the corresponding BLOCK_VARS and unexpanded variable lists
4809    associated with DEST_CFUN.  */
4810
4811 basic_block
4812 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
4813                         basic_block exit_bb)
4814 {
4815   VEC(basic_block,heap) *bbs;
4816   basic_block after, bb, *entry_pred, *exit_succ;
4817   struct function *saved_cfun;
4818   int *entry_flag, *exit_flag, eh_offset;
4819   unsigned i, num_entry_edges, num_exit_edges;
4820   edge e;
4821   edge_iterator ei;
4822   bitmap vars_to_remove;
4823   htab_t new_label_map;
4824
4825   saved_cfun = cfun;
4826
4827   /* Collect all the blocks in the region.  Manually add ENTRY_BB
4828      because it won't be added by dfs_enumerate_from.  */
4829   calculate_dominance_info (CDI_DOMINATORS);
4830
4831   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
4832      region.  */
4833   gcc_assert (entry_bb != exit_bb
4834               && (!exit_bb
4835                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
4836
4837   bbs = NULL;
4838   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4839   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4840
4841   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
4842      the predecessor edges to ENTRY_BB and the successor edges to
4843      EXIT_BB so that we can re-attach them to the new basic block that
4844      will replace the region.  */
4845   num_entry_edges = EDGE_COUNT (entry_bb->preds);
4846   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
4847   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
4848   i = 0;
4849   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
4850     {
4851       entry_flag[i] = e->flags;
4852       entry_pred[i++] = e->src;
4853       remove_edge (e);
4854     }
4855
4856   if (exit_bb)
4857     {
4858       num_exit_edges = EDGE_COUNT (exit_bb->succs);
4859       exit_succ = (basic_block *) xcalloc (num_exit_edges,
4860                                            sizeof (basic_block));
4861       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
4862       i = 0;
4863       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
4864         {
4865           exit_flag[i] = e->flags;
4866           exit_succ[i++] = e->dest;
4867           remove_edge (e);
4868         }
4869     }
4870   else
4871     {
4872       num_exit_edges = 0;
4873       exit_succ = NULL;
4874       exit_flag = NULL;
4875     }
4876
4877   /* Switch context to the child function to initialize DEST_FN's CFG.  */
4878   gcc_assert (dest_cfun->cfg == NULL);
4879   cfun = dest_cfun;
4880
4881   init_empty_tree_cfg ();
4882
4883   /* Initialize EH information for the new function.  */
4884   eh_offset = 0;
4885   new_label_map = NULL;
4886   if (saved_cfun->eh)
4887     {
4888       int region = -1;
4889
4890       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4891         region = find_outermost_region_in_block (saved_cfun, bb, region);
4892
4893       init_eh_for_function ();
4894       if (region != -1)
4895         {
4896           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
4897           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
4898                                             new_label_map, region, 0);
4899         }
4900     }
4901
4902   cfun = saved_cfun;
4903
4904   /* Move blocks from BBS into DEST_CFUN.  */
4905   gcc_assert (VEC_length (basic_block, bbs) >= 2);
4906   after = dest_cfun->cfg->x_entry_block_ptr;
4907   vars_to_remove = BITMAP_ALLOC (NULL);
4908   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4909     {
4910       /* No need to update edge counts on the last block.  It has
4911          already been updated earlier when we detached the region from
4912          the original CFG.  */
4913       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_to_remove,
4914                         new_label_map, eh_offset);
4915       after = bb;
4916     }
4917
4918   if (new_label_map)
4919     htab_delete (new_label_map);
4920
4921   /* Remove the variables marked in VARS_TO_REMOVE from
4922      CFUN->UNEXPANDED_VAR_LIST.  Otherwise, they will be given a
4923      DECL_RTL in the context of CFUN.  */
4924   if (!bitmap_empty_p (vars_to_remove))
4925     {
4926       tree *p;
4927
4928       for (p = &cfun->unexpanded_var_list; *p; )
4929         {
4930           tree var = TREE_VALUE (*p);
4931           if (bitmap_bit_p (vars_to_remove, DECL_UID (var)))
4932             {
4933               *p = TREE_CHAIN (*p);
4934               continue;
4935             }
4936
4937           p = &TREE_CHAIN (*p);
4938         }
4939     }
4940
4941   BITMAP_FREE (vars_to_remove);
4942
4943   /* Rewire the entry and exit blocks.  The successor to the entry
4944      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
4945      the child function.  Similarly, the predecessor of DEST_FN's
4946      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
4947      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
4948      various CFG manipulation function get to the right CFG.
4949
4950      FIXME, this is silly.  The CFG ought to become a parameter to
4951      these helpers.  */
4952   cfun = dest_cfun;
4953   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
4954   if (exit_bb)
4955     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
4956   cfun = saved_cfun;
4957
4958   /* Back in the original function, the SESE region has disappeared,
4959      create a new basic block in its place.  */
4960   bb = create_empty_bb (entry_pred[0]);
4961   for (i = 0; i < num_entry_edges; i++)
4962     make_edge (entry_pred[i], bb, entry_flag[i]);
4963
4964   for (i = 0; i < num_exit_edges; i++)
4965     make_edge (bb, exit_succ[i], exit_flag[i]);
4966
4967   if (exit_bb)
4968     {
4969       free (exit_flag);
4970       free (exit_succ);
4971     }
4972   free (entry_flag);
4973   free (entry_pred);
4974   free_dominance_info (CDI_DOMINATORS);
4975   free_dominance_info (CDI_POST_DOMINATORS);
4976   VEC_free (basic_block, heap, bbs);
4977
4978   return bb;
4979 }
4980
4981
4982 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4983
4984 void
4985 dump_function_to_file (tree fn, FILE *file, int flags)
4986 {
4987   tree arg, vars, var;
4988   bool ignore_topmost_bind = false, any_var = false;
4989   basic_block bb;
4990   tree chain;
4991   struct function *saved_cfun;
4992
4993   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4994
4995   arg = DECL_ARGUMENTS (fn);
4996   while (arg)
4997     {
4998       print_generic_expr (file, arg, dump_flags);
4999       if (TREE_CHAIN (arg))
5000         fprintf (file, ", ");
5001       arg = TREE_CHAIN (arg);
5002     }
5003   fprintf (file, ")\n");
5004
5005   if (flags & TDF_DETAILS)
5006     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
5007   if (flags & TDF_RAW)
5008     {
5009       dump_node (fn, TDF_SLIM | flags, file);
5010       return;
5011     }
5012
5013   /* Switch CFUN to point to FN.  */
5014   saved_cfun = cfun;
5015   cfun = DECL_STRUCT_FUNCTION (fn);
5016
5017   /* When GIMPLE is lowered, the variables are no longer available in
5018      BIND_EXPRs, so display them separately.  */
5019   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
5020     {
5021       ignore_topmost_bind = true;
5022
5023       fprintf (file, "{\n");
5024       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
5025         {
5026           var = TREE_VALUE (vars);
5027
5028           print_generic_decl (file, var, flags);
5029           fprintf (file, "\n");
5030
5031           any_var = true;
5032         }
5033     }
5034
5035   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5036     {
5037       /* Make a CFG based dump.  */
5038       check_bb_profile (ENTRY_BLOCK_PTR, file);
5039       if (!ignore_topmost_bind)
5040         fprintf (file, "{\n");
5041
5042       if (any_var && n_basic_blocks)
5043         fprintf (file, "\n");
5044
5045       FOR_EACH_BB (bb)
5046         dump_generic_bb (file, bb, 2, flags);
5047
5048       fprintf (file, "}\n");
5049       check_bb_profile (EXIT_BLOCK_PTR, file);
5050     }
5051   else
5052     {
5053       int indent;
5054
5055       /* Make a tree based dump.  */
5056       chain = DECL_SAVED_TREE (fn);
5057
5058       if (chain && TREE_CODE (chain) == BIND_EXPR)
5059         {
5060           if (ignore_topmost_bind)
5061             {
5062               chain = BIND_EXPR_BODY (chain);
5063               indent = 2;
5064             }
5065           else
5066             indent = 0;
5067         }
5068       else
5069         {
5070           if (!ignore_topmost_bind)
5071             fprintf (file, "{\n");
5072           indent = 2;
5073         }
5074
5075       if (any_var)
5076         fprintf (file, "\n");
5077
5078       print_generic_stmt_indented (file, chain, flags, indent);
5079       if (ignore_topmost_bind)
5080         fprintf (file, "}\n");
5081     }
5082
5083   fprintf (file, "\n\n");
5084
5085   /* Restore CFUN.  */
5086   cfun = saved_cfun;
5087 }
5088
5089
5090 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5091
5092 void
5093 debug_function (tree fn, int flags)
5094 {
5095   dump_function_to_file (fn, stderr, flags);
5096 }
5097
5098
5099 /* Pretty print of the loops intermediate representation.  */
5100 static void print_loop (FILE *, struct loop *, int);
5101 static void print_pred_bbs (FILE *, basic_block bb);
5102 static void print_succ_bbs (FILE *, basic_block bb);
5103
5104
5105 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5106
5107 static void
5108 print_pred_bbs (FILE *file, basic_block bb)
5109 {
5110   edge e;
5111   edge_iterator ei;
5112
5113   FOR_EACH_EDGE (e, ei, bb->preds)
5114     fprintf (file, "bb_%d ", e->src->index);
5115 }
5116
5117
5118 /* Print on FILE the indexes for the successors of basic_block BB.  */
5119
5120 static void
5121 print_succ_bbs (FILE *file, basic_block bb)
5122 {
5123   edge e;
5124   edge_iterator ei;
5125
5126   FOR_EACH_EDGE (e, ei, bb->succs)
5127     fprintf (file, "bb_%d ", e->dest->index);
5128 }
5129
5130
5131 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5132
5133 static void
5134 print_loop (FILE *file, struct loop *loop, int indent)
5135 {
5136   char *s_indent;
5137   basic_block bb;
5138
5139   if (loop == NULL)
5140     return;
5141
5142   s_indent = (char *) alloca ((size_t) indent + 1);
5143   memset ((void *) s_indent, ' ', (size_t) indent);
5144   s_indent[indent] = '\0';
5145
5146   /* Print the loop's header.  */
5147   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5148
5149   /* Print the loop's body.  */
5150   fprintf (file, "%s{\n", s_indent);
5151   FOR_EACH_BB (bb)
5152     if (bb->loop_father == loop)
5153       {
5154         /* Print the basic_block's header.  */
5155         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5156         print_pred_bbs (file, bb);
5157         fprintf (file, "}, succs = {");
5158         print_succ_bbs (file, bb);
5159         fprintf (file, "})\n");
5160
5161         /* Print the basic_block's body.  */
5162         fprintf (file, "%s  {\n", s_indent);
5163         tree_dump_bb (bb, file, indent + 4);
5164         fprintf (file, "%s  }\n", s_indent);
5165       }
5166
5167   print_loop (file, loop->inner, indent + 2);
5168   fprintf (file, "%s}\n", s_indent);
5169   print_loop (file, loop->next, indent);
5170 }
5171
5172
5173 /* Follow a CFG edge from the entry point of the program, and on entry
5174    of a loop, pretty print the loop structure on FILE.  */
5175
5176 void
5177 print_loop_ir (FILE *file)
5178 {
5179   basic_block bb;
5180
5181   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
5182   if (bb && bb->loop_father)
5183     print_loop (file, bb->loop_father, 0);
5184 }
5185
5186
5187 /* Debugging loops structure at tree level.  */
5188
5189 void
5190 debug_loop_ir (void)
5191 {
5192   print_loop_ir (stderr);
5193 }
5194
5195
5196 /* Return true if BB ends with a call, possibly followed by some
5197    instructions that must stay with the call.  Return false,
5198    otherwise.  */
5199
5200 static bool
5201 tree_block_ends_with_call_p (basic_block bb)
5202 {
5203   block_stmt_iterator bsi = bsi_last (bb);
5204   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5205 }
5206
5207
5208 /* Return true if BB ends with a conditional branch.  Return false,
5209    otherwise.  */
5210
5211 static bool
5212 tree_block_ends_with_condjump_p (basic_block bb)
5213 {
5214   tree stmt = last_stmt (bb);
5215   return (stmt && TREE_CODE (stmt) == COND_EXPR);
5216 }
5217
5218
5219 /* Return true if we need to add fake edge to exit at statement T.
5220    Helper function for tree_flow_call_edges_add.  */
5221
5222 static bool
5223 need_fake_edge_p (tree t)
5224 {
5225   tree call;
5226
5227   /* NORETURN and LONGJMP calls already have an edge to exit.
5228      CONST and PURE calls do not need one.
5229      We don't currently check for CONST and PURE here, although
5230      it would be a good idea, because those attributes are
5231      figured out from the RTL in mark_constant_function, and
5232      the counter incrementation code from -fprofile-arcs
5233      leads to different results from -fbranch-probabilities.  */
5234   call = get_call_expr_in (t);
5235   if (call
5236       && !(call_expr_flags (call) & ECF_NORETURN))
5237     return true;
5238
5239   if (TREE_CODE (t) == ASM_EXPR
5240        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5241     return true;
5242
5243   return false;
5244 }
5245
5246
5247 /* Add fake edges to the function exit for any non constant and non
5248    noreturn calls, volatile inline assembly in the bitmap of blocks
5249    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5250    the number of blocks that were split.
5251
5252    The goal is to expose cases in which entering a basic block does
5253    not imply that all subsequent instructions must be executed.  */
5254
5255 static int
5256 tree_flow_call_edges_add (sbitmap blocks)
5257 {
5258   int i;
5259   int blocks_split = 0;
5260   int last_bb = last_basic_block;
5261   bool check_last_block = false;
5262
5263   if (n_basic_blocks == NUM_FIXED_BLOCKS)
5264     return 0;
5265
5266   if (! blocks)
5267     check_last_block = true;
5268   else
5269     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5270
5271   /* In the last basic block, before epilogue generation, there will be
5272      a fallthru edge to EXIT.  Special care is required if the last insn
5273      of the last basic block is a call because make_edge folds duplicate
5274      edges, which would result in the fallthru edge also being marked
5275      fake, which would result in the fallthru edge being removed by
5276      remove_fake_edges, which would result in an invalid CFG.
5277
5278      Moreover, we can't elide the outgoing fake edge, since the block
5279      profiler needs to take this into account in order to solve the minimal
5280      spanning tree in the case that the call doesn't return.
5281
5282      Handle this by adding a dummy instruction in a new last basic block.  */
5283   if (check_last_block)
5284     {
5285       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5286       block_stmt_iterator bsi = bsi_last (bb);
5287       tree t = NULL_TREE;
5288       if (!bsi_end_p (bsi))
5289         t = bsi_stmt (bsi);
5290
5291       if (t && need_fake_edge_p (t))
5292         {
5293           edge e;
5294
5295           e = find_edge (bb, EXIT_BLOCK_PTR);
5296           if (e)
5297             {
5298               bsi_insert_on_edge (e, build_empty_stmt ());
5299               bsi_commit_edge_inserts ();
5300             }
5301         }
5302     }
5303
5304   /* Now add fake edges to the function exit for any non constant
5305      calls since there is no way that we can determine if they will
5306      return or not...  */
5307   for (i = 0; i < last_bb; i++)
5308     {
5309       basic_block bb = BASIC_BLOCK (i);
5310       block_stmt_iterator bsi;
5311       tree stmt, last_stmt;
5312
5313       if (!bb)
5314         continue;
5315
5316       if (blocks && !TEST_BIT (blocks, i))
5317         continue;
5318
5319       bsi = bsi_last (bb);
5320       if (!bsi_end_p (bsi))
5321         {
5322           last_stmt = bsi_stmt (bsi);
5323           do
5324             {
5325               stmt = bsi_stmt (bsi);
5326               if (need_fake_edge_p (stmt))
5327                 {
5328                   edge e;
5329                   /* The handling above of the final block before the
5330                      epilogue should be enough to verify that there is
5331                      no edge to the exit block in CFG already.
5332                      Calling make_edge in such case would cause us to
5333                      mark that edge as fake and remove it later.  */
5334 #ifdef ENABLE_CHECKING
5335                   if (stmt == last_stmt)
5336                     {
5337                       e = find_edge (bb, EXIT_BLOCK_PTR);
5338                       gcc_assert (e == NULL);
5339                     }
5340 #endif
5341
5342                   /* Note that the following may create a new basic block
5343                      and renumber the existing basic blocks.  */
5344                   if (stmt != last_stmt)
5345                     {
5346                       e = split_block (bb, stmt);
5347                       if (e)
5348                         blocks_split++;
5349                     }
5350                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5351                 }
5352               bsi_prev (&bsi);
5353             }
5354           while (!bsi_end_p (bsi));
5355         }
5356     }
5357
5358   if (blocks_split)
5359     verify_flow_info ();
5360
5361   return blocks_split;
5362 }
5363
5364 bool
5365 tree_purge_dead_eh_edges (basic_block bb)
5366 {
5367   bool changed = false;
5368   edge e;
5369   edge_iterator ei;
5370   tree stmt = last_stmt (bb);
5371
5372   if (stmt && tree_can_throw_internal (stmt))
5373     return false;
5374
5375   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5376     {
5377       if (e->flags & EDGE_EH)
5378         {
5379           remove_edge (e);
5380           changed = true;
5381         }
5382       else
5383         ei_next (&ei);
5384     }
5385
5386   /* Removal of dead EH edges might change dominators of not
5387      just immediate successors.  E.g. when bb1 is changed so that
5388      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5389      eh edges purged by this function in:
5390            0
5391           / \
5392          v   v
5393          1-->2
5394         / \  |
5395        v   v |
5396        3-->4 |
5397         \    v
5398          --->5
5399              |
5400              -
5401      idom(bb5) must be recomputed.  For now just free the dominance
5402      info.  */
5403   if (changed)
5404     free_dominance_info (CDI_DOMINATORS);
5405
5406   return changed;
5407 }
5408
5409 bool
5410 tree_purge_all_dead_eh_edges (bitmap blocks)
5411 {
5412   bool changed = false;
5413   unsigned i;
5414   bitmap_iterator bi;
5415
5416   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5417     {
5418       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5419     }
5420
5421   return changed;
5422 }
5423
5424 /* This function is called whenever a new edge is created or
5425    redirected.  */
5426
5427 static void
5428 tree_execute_on_growing_pred (edge e)
5429 {
5430   basic_block bb = e->dest;
5431
5432   if (phi_nodes (bb))
5433     reserve_phi_args_for_new_edge (bb);
5434 }
5435
5436 /* This function is called immediately before edge E is removed from
5437    the edge vector E->dest->preds.  */
5438
5439 static void
5440 tree_execute_on_shrinking_pred (edge e)
5441 {
5442   if (phi_nodes (e->dest))
5443     remove_phi_args (e);
5444 }
5445
5446 /*---------------------------------------------------------------------------
5447   Helper functions for Loop versioning
5448   ---------------------------------------------------------------------------*/
5449
5450 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
5451    of 'first'. Both of them are dominated by 'new_head' basic block. When
5452    'new_head' was created by 'second's incoming edge it received phi arguments
5453    on the edge by split_edge(). Later, additional edge 'e' was created to
5454    connect 'new_head' and 'first'. Now this routine adds phi args on this
5455    additional edge 'e' that new_head to second edge received as part of edge
5456    splitting.
5457 */
5458
5459 static void
5460 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
5461                                 basic_block new_head, edge e)
5462 {
5463   tree phi1, phi2;
5464   edge e2 = find_edge (new_head, second);
5465
5466   /* Because NEW_HEAD has been created by splitting SECOND's incoming
5467      edge, we should always have an edge from NEW_HEAD to SECOND.  */
5468   gcc_assert (e2 != NULL);
5469
5470   /* Browse all 'second' basic block phi nodes and add phi args to
5471      edge 'e' for 'first' head. PHI args are always in correct order.  */
5472
5473   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
5474        phi2 && phi1;
5475        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
5476     {
5477       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
5478       add_phi_arg (phi1, def, e);
5479     }
5480 }
5481
5482 /* Adds a if else statement to COND_BB with condition COND_EXPR.
5483    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
5484    the destination of the ELSE part.  */
5485 static void
5486 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
5487                             basic_block cond_bb, void *cond_e)
5488 {
5489   block_stmt_iterator bsi;
5490   tree goto1 = NULL_TREE;
5491   tree goto2 = NULL_TREE;
5492   tree new_cond_expr = NULL_TREE;
5493   tree cond_expr = (tree) cond_e;
5494   edge e0;
5495
5496   /* Build new conditional expr */
5497   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
5498   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
5499   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
5500
5501   /* Add new cond in cond_bb.  */
5502   bsi = bsi_start (cond_bb);
5503   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
5504   /* Adjust edges appropriately to connect new head with first head
5505      as well as second head.  */
5506   e0 = single_succ_edge (cond_bb);
5507   e0->flags &= ~EDGE_FALLTHRU;
5508   e0->flags |= EDGE_FALSE_VALUE;
5509 }
5510
5511 struct cfg_hooks tree_cfg_hooks = {
5512   "tree",
5513   tree_verify_flow_info,
5514   tree_dump_bb,                 /* dump_bb  */
5515   create_bb,                    /* create_basic_block  */
5516   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5517   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5518   remove_bb,                    /* delete_basic_block  */
5519   tree_split_block,             /* split_block  */
5520   tree_move_block_after,        /* move_block_after  */
5521   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5522   tree_merge_blocks,            /* merge_blocks  */
5523   tree_predict_edge,            /* predict_edge  */
5524   tree_predicted_by_p,          /* predicted_by_p  */
5525   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5526   tree_duplicate_bb,            /* duplicate_block  */
5527   tree_split_edge,              /* split_edge  */
5528   tree_make_forwarder_block,    /* make_forward_block  */
5529   NULL,                         /* tidy_fallthru_edge  */
5530   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5531   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5532   tree_flow_call_edges_add,     /* flow_call_edges_add */
5533   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5534   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5535   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
5536   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5537   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
5538   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
5539   flush_pending_stmts           /* flush_pending_stmts */
5540 };
5541
5542
5543 /* Split all critical edges.  */
5544
5545 static unsigned int
5546 split_critical_edges (void)
5547 {
5548   basic_block bb;
5549   edge e;
5550   edge_iterator ei;
5551
5552   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5553      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5554      mappings around the calls to split_edge.  */
5555   start_recording_case_labels ();
5556   FOR_ALL_BB (bb)
5557     {
5558       FOR_EACH_EDGE (e, ei, bb->succs)
5559         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5560           {
5561             split_edge (e);
5562           }
5563     }
5564   end_recording_case_labels ();
5565   return 0;
5566 }
5567
5568 struct tree_opt_pass pass_split_crit_edges =
5569 {
5570   "crited",                          /* name */
5571   NULL,                          /* gate */
5572   split_critical_edges,          /* execute */
5573   NULL,                          /* sub */
5574   NULL,                          /* next */
5575   0,                             /* static_pass_number */
5576   TV_TREE_SPLIT_EDGES,           /* tv_id */
5577   PROP_cfg,                      /* properties required */
5578   PROP_no_crit_edges,            /* properties_provided */
5579   0,                             /* properties_destroyed */
5580   0,                             /* todo_flags_start */
5581   TODO_dump_func,                /* todo_flags_finish */
5582   0                              /* letter */
5583 };
5584
5585 \f
5586 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5587    a temporary, make sure and register it to be renamed if necessary,
5588    and finally return the temporary.  Put the statements to compute
5589    EXP before the current statement in BSI.  */
5590
5591 tree
5592 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5593 {
5594   tree t, new_stmt, orig_stmt;
5595
5596   if (is_gimple_val (exp))
5597     return exp;
5598
5599   t = make_rename_temp (type, NULL);
5600   new_stmt = build2 (MODIFY_EXPR, type, t, exp);
5601
5602   orig_stmt = bsi_stmt (*bsi);
5603   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5604   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5605
5606   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5607   if (in_ssa_p)
5608     mark_new_vars_to_rename (new_stmt);
5609
5610   return t;
5611 }
5612
5613 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5614    Return the gimple_val holding the result.  */
5615
5616 tree
5617 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5618                  tree type, tree a, tree b, tree c)
5619 {
5620   tree ret;
5621
5622   ret = fold_build3 (code, type, a, b, c);
5623   STRIP_NOPS (ret);
5624
5625   return gimplify_val (bsi, type, ret);
5626 }
5627
5628 /* Build a binary operation and gimplify it.  Emit code before BSI.
5629    Return the gimple_val holding the result.  */
5630
5631 tree
5632 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5633                  tree type, tree a, tree b)
5634 {
5635   tree ret;
5636
5637   ret = fold_build2 (code, type, a, b);
5638   STRIP_NOPS (ret);
5639
5640   return gimplify_val (bsi, type, ret);
5641 }
5642
5643 /* Build a unary operation and gimplify it.  Emit code before BSI.
5644    Return the gimple_val holding the result.  */
5645
5646 tree
5647 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5648                  tree a)
5649 {
5650   tree ret;
5651
5652   ret = fold_build1 (code, type, a);
5653   STRIP_NOPS (ret);
5654
5655   return gimplify_val (bsi, type, ret);
5656 }
5657
5658
5659 \f
5660 /* Emit return warnings.  */
5661
5662 static unsigned int
5663 execute_warn_function_return (void)
5664 {
5665 #ifdef USE_MAPPED_LOCATION
5666   source_location location;
5667 #else
5668   location_t *locus;
5669 #endif
5670   tree last;
5671   edge e;
5672   edge_iterator ei;
5673
5674   /* If we have a path to EXIT, then we do return.  */
5675   if (TREE_THIS_VOLATILE (cfun->decl)
5676       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5677     {
5678 #ifdef USE_MAPPED_LOCATION
5679       location = UNKNOWN_LOCATION;
5680 #else
5681       locus = NULL;
5682 #endif
5683       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5684         {
5685           last = last_stmt (e->src);
5686           if (TREE_CODE (last) == RETURN_EXPR
5687 #ifdef USE_MAPPED_LOCATION
5688               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5689 #else
5690               && (locus = EXPR_LOCUS (last)) != NULL)
5691 #endif
5692             break;
5693         }
5694 #ifdef USE_MAPPED_LOCATION
5695       if (location == UNKNOWN_LOCATION)
5696         location = cfun->function_end_locus;
5697       warning (0, "%H%<noreturn%> function does return", &location);
5698 #else
5699       if (!locus)
5700         locus = &cfun->function_end_locus;
5701       warning (0, "%H%<noreturn%> function does return", locus);
5702 #endif
5703     }
5704
5705   /* If we see "return;" in some basic block, then we do reach the end
5706      without returning a value.  */
5707   else if (warn_return_type
5708            && !TREE_NO_WARNING (cfun->decl)
5709            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5710            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5711     {
5712       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5713         {
5714           tree last = last_stmt (e->src);
5715           if (TREE_CODE (last) == RETURN_EXPR
5716               && TREE_OPERAND (last, 0) == NULL
5717               && !TREE_NO_WARNING (last))
5718             {
5719 #ifdef USE_MAPPED_LOCATION
5720               location = EXPR_LOCATION (last);
5721               if (location == UNKNOWN_LOCATION)
5722                   location = cfun->function_end_locus;
5723               warning (0, "%Hcontrol reaches end of non-void function", &location);
5724 #else
5725               locus = EXPR_LOCUS (last);
5726               if (!locus)
5727                 locus = &cfun->function_end_locus;
5728               warning (0, "%Hcontrol reaches end of non-void function", locus);
5729 #endif
5730               TREE_NO_WARNING (cfun->decl) = 1;
5731               break;
5732             }
5733         }
5734     }
5735   return 0;
5736 }
5737
5738
5739 /* Given a basic block B which ends with a conditional and has
5740    precisely two successors, determine which of the edges is taken if
5741    the conditional is true and which is taken if the conditional is
5742    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5743
5744 void
5745 extract_true_false_edges_from_block (basic_block b,
5746                                      edge *true_edge,
5747                                      edge *false_edge)
5748 {
5749   edge e = EDGE_SUCC (b, 0);
5750
5751   if (e->flags & EDGE_TRUE_VALUE)
5752     {
5753       *true_edge = e;
5754       *false_edge = EDGE_SUCC (b, 1);
5755     }
5756   else
5757     {
5758       *false_edge = e;
5759       *true_edge = EDGE_SUCC (b, 1);
5760     }
5761 }
5762
5763 struct tree_opt_pass pass_warn_function_return =
5764 {
5765   NULL,                                 /* name */
5766   NULL,                                 /* gate */
5767   execute_warn_function_return,         /* execute */
5768   NULL,                                 /* sub */
5769   NULL,                                 /* next */
5770   0,                                    /* static_pass_number */
5771   0,                                    /* tv_id */
5772   PROP_cfg,                             /* properties_required */
5773   0,                                    /* properties_provided */
5774   0,                                    /* properties_destroyed */
5775   0,                                    /* todo_flags_start */
5776   0,                                    /* todo_flags_finish */
5777   0                                     /* letter */
5778 };
5779
5780 /* Emit noreturn warnings.  */
5781
5782 static unsigned int
5783 execute_warn_function_noreturn (void)
5784 {
5785   if (warn_missing_noreturn
5786       && !TREE_THIS_VOLATILE (cfun->decl)
5787       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5788       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5789     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5790              "for attribute %<noreturn%>",
5791              cfun->decl);
5792   return 0;
5793 }
5794
5795 struct tree_opt_pass pass_warn_function_noreturn =
5796 {
5797   NULL,                                 /* name */
5798   NULL,                                 /* gate */
5799   execute_warn_function_noreturn,       /* execute */
5800   NULL,                                 /* sub */
5801   NULL,                                 /* next */
5802   0,                                    /* static_pass_number */
5803   0,                                    /* tv_id */
5804   PROP_cfg,                             /* properties_required */
5805   0,                                    /* properties_provided */
5806   0,                                    /* properties_destroyed */
5807   0,                                    /* todo_flags_start */
5808   0,                                    /* todo_flags_finish */
5809   0                                     /* letter */
5810 };