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