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         {
4738           if (region < 0)
4739             region = stmt_region;
4740           else if (stmt_region != region)
4741             {
4742               region = eh_region_outermost (src_cfun, stmt_region, region);
4743               gcc_assert (region != -1);
4744             }
4745         }
4746     }
4747
4748   return region;
4749 }
4750
4751 static tree
4752 new_label_mapper (tree decl, void *data)
4753 {
4754   htab_t hash = (htab_t) data;
4755   struct tree_map *m;
4756   void **slot;
4757
4758   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
4759
4760   m = xmalloc (sizeof (struct tree_map));
4761   m->hash = DECL_UID (decl);
4762   m->from = decl;
4763   m->to = create_artificial_label ();
4764   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
4765
4766   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
4767   gcc_assert (*slot == NULL);
4768
4769   *slot = m;
4770
4771   return m->to;
4772 }
4773
4774 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
4775    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
4776    single basic block in the original CFG and the new basic block is
4777    returned.  DEST_CFUN must not have a CFG yet.
4778
4779    Note that the region need not be a pure SESE region.  Blocks inside
4780    the region may contain calls to abort/exit.  The only restriction
4781    is that ENTRY_BB should be the only entry point and it must
4782    dominate EXIT_BB.
4783
4784    All local variables referenced in the region are assumed to be in
4785    the corresponding BLOCK_VARS and unexpanded variable lists
4786    associated with DEST_CFUN.  */
4787
4788 basic_block
4789 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
4790                         basic_block exit_bb)
4791 {
4792   VEC(basic_block,heap) *bbs;
4793   basic_block after, bb, *entry_pred, *exit_succ;
4794   struct function *saved_cfun;
4795   int *entry_flag, *exit_flag, eh_offset;
4796   unsigned i, num_entry_edges, num_exit_edges;
4797   edge e;
4798   edge_iterator ei;
4799   bitmap vars_to_remove;
4800   htab_t new_label_map;
4801
4802   saved_cfun = cfun;
4803
4804   /* Collect all the blocks in the region.  Manually add ENTRY_BB
4805      because it won't be added by dfs_enumerate_from.  */
4806   calculate_dominance_info (CDI_DOMINATORS);
4807
4808   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
4809      region.  */
4810   gcc_assert (entry_bb != exit_bb
4811               && dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
4812
4813   bbs = NULL;
4814   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4815   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4816
4817   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
4818      the predecessor edges to ENTRY_BB and the successor edges to
4819      EXIT_BB so that we can re-attach them to the new basic block that
4820      will replace the region.  */
4821   num_entry_edges = EDGE_COUNT (entry_bb->preds);
4822   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
4823   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
4824   i = 0;
4825   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
4826     {
4827       entry_flag[i] = e->flags;
4828       entry_pred[i++] = e->src;
4829       remove_edge (e);
4830     }
4831
4832   num_exit_edges = EDGE_COUNT (exit_bb->succs);
4833   exit_succ = (basic_block *) xcalloc (num_exit_edges, sizeof (basic_block));
4834   exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
4835   i = 0;
4836   for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
4837     {
4838       exit_flag[i] = e->flags;
4839       exit_succ[i++] = e->dest;
4840       remove_edge (e);
4841     }
4842
4843   /* Switch context to the child function to initialize DEST_FN's CFG.  */
4844   gcc_assert (dest_cfun->cfg == NULL);
4845   cfun = dest_cfun;
4846
4847   init_empty_tree_cfg ();
4848
4849   /* Initialize EH information for the new function.  */
4850   eh_offset = 0;
4851   new_label_map = NULL;
4852   if (saved_cfun->eh)
4853     {
4854       int region = -1;
4855
4856       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4857         region = find_outermost_region_in_block (saved_cfun, bb, region);
4858
4859       init_eh_for_function ();
4860       if (region != -1)
4861         {
4862           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
4863           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
4864                                             new_label_map, region, 0);
4865         }
4866     }
4867
4868   cfun = saved_cfun;
4869
4870   /* Move blocks from BBS into DEST_CFUN.  */
4871   gcc_assert (VEC_length (basic_block, bbs) >= 2);
4872   after = dest_cfun->cfg->x_entry_block_ptr;
4873   vars_to_remove = BITMAP_ALLOC (NULL);
4874   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4875     {
4876       /* No need to update edge counts on the last block.  It has
4877          already been updated earlier when we detached the region from
4878          the original CFG.  */
4879       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_to_remove,
4880                         new_label_map, eh_offset);
4881       after = bb;
4882     }
4883
4884   if (new_label_map)
4885     htab_delete (new_label_map);
4886
4887   /* Remove the variables marked in VARS_TO_REMOVE from
4888      CFUN->UNEXPANDED_VAR_LIST.  Otherwise, they will be given a
4889      DECL_RTL in the context of CFUN.  */
4890   if (!bitmap_empty_p (vars_to_remove))
4891     {
4892       tree *p;
4893
4894       for (p = &cfun->unexpanded_var_list; *p; )
4895         {
4896           tree var = TREE_VALUE (*p);
4897           if (bitmap_bit_p (vars_to_remove, DECL_UID (var)))
4898             {
4899               *p = TREE_CHAIN (*p);
4900               continue;
4901             }
4902
4903           p = &TREE_CHAIN (*p);
4904         }
4905     }
4906
4907   BITMAP_FREE (vars_to_remove);
4908
4909   /* Rewire the entry and exit blocks.  The successor to the entry
4910      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
4911      the child function.  Similarly, the predecessor of DEST_FN's
4912      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
4913      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
4914      various CFG manipulation function get to the right CFG.
4915
4916      FIXME, this is silly.  The CFG ought to become a parameter to
4917      these helpers.  */
4918   cfun = dest_cfun;
4919   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
4920   make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
4921   cfun = saved_cfun;
4922
4923   /* Back in the original function, the SESE region has disappeared,
4924      create a new basic block in its place.  */
4925   bb = create_empty_bb (entry_pred[0]);
4926   for (i = 0; i < num_entry_edges; i++)
4927     make_edge (entry_pred[i], bb, entry_flag[i]);
4928
4929   for (i = 0; i < num_exit_edges; i++)
4930     make_edge (bb, exit_succ[i], exit_flag[i]);
4931
4932   free (exit_flag);
4933   free (entry_flag);
4934   free (entry_pred);
4935   free (exit_succ);
4936   free_dominance_info (CDI_DOMINATORS);
4937   free_dominance_info (CDI_POST_DOMINATORS);
4938   VEC_free (basic_block, heap, bbs);
4939
4940   return bb;
4941 }
4942
4943
4944 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4945
4946 void
4947 dump_function_to_file (tree fn, FILE *file, int flags)
4948 {
4949   tree arg, vars, var;
4950   bool ignore_topmost_bind = false, any_var = false;
4951   basic_block bb;
4952   tree chain;
4953   struct function *saved_cfun;
4954
4955   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4956
4957   arg = DECL_ARGUMENTS (fn);
4958   while (arg)
4959     {
4960       print_generic_expr (file, arg, dump_flags);
4961       if (TREE_CHAIN (arg))
4962         fprintf (file, ", ");
4963       arg = TREE_CHAIN (arg);
4964     }
4965   fprintf (file, ")\n");
4966
4967   if (flags & TDF_DETAILS)
4968     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4969   if (flags & TDF_RAW)
4970     {
4971       dump_node (fn, TDF_SLIM | flags, file);
4972       return;
4973     }
4974
4975   /* Switch CFUN to point to FN.  */
4976   saved_cfun = cfun;
4977   cfun = DECL_STRUCT_FUNCTION (fn);
4978
4979   /* When GIMPLE is lowered, the variables are no longer available in
4980      BIND_EXPRs, so display them separately.  */
4981   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
4982     {
4983       ignore_topmost_bind = true;
4984
4985       fprintf (file, "{\n");
4986       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4987         {
4988           var = TREE_VALUE (vars);
4989
4990           print_generic_decl (file, var, flags);
4991           fprintf (file, "\n");
4992
4993           any_var = true;
4994         }
4995     }
4996
4997   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
4998     {
4999       /* Make a CFG based dump.  */
5000       check_bb_profile (ENTRY_BLOCK_PTR, file);
5001       if (!ignore_topmost_bind)
5002         fprintf (file, "{\n");
5003
5004       if (any_var && n_basic_blocks)
5005         fprintf (file, "\n");
5006
5007       FOR_EACH_BB (bb)
5008         dump_generic_bb (file, bb, 2, flags);
5009
5010       fprintf (file, "}\n");
5011       check_bb_profile (EXIT_BLOCK_PTR, file);
5012     }
5013   else
5014     {
5015       int indent;
5016
5017       /* Make a tree based dump.  */
5018       chain = DECL_SAVED_TREE (fn);
5019
5020       if (chain && TREE_CODE (chain) == BIND_EXPR)
5021         {
5022           if (ignore_topmost_bind)
5023             {
5024               chain = BIND_EXPR_BODY (chain);
5025               indent = 2;
5026             }
5027           else
5028             indent = 0;
5029         }
5030       else
5031         {
5032           if (!ignore_topmost_bind)
5033             fprintf (file, "{\n");
5034           indent = 2;
5035         }
5036
5037       if (any_var)
5038         fprintf (file, "\n");
5039
5040       print_generic_stmt_indented (file, chain, flags, indent);
5041       if (ignore_topmost_bind)
5042         fprintf (file, "}\n");
5043     }
5044
5045   fprintf (file, "\n\n");
5046
5047   /* Restore CFUN.  */
5048   cfun = saved_cfun;
5049 }
5050
5051
5052 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5053
5054 void
5055 debug_function (tree fn, int flags)
5056 {
5057   dump_function_to_file (fn, stderr, flags);
5058 }
5059
5060
5061 /* Pretty print of the loops intermediate representation.  */
5062 static void print_loop (FILE *, struct loop *, int);
5063 static void print_pred_bbs (FILE *, basic_block bb);
5064 static void print_succ_bbs (FILE *, basic_block bb);
5065
5066
5067 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5068
5069 static void
5070 print_pred_bbs (FILE *file, basic_block bb)
5071 {
5072   edge e;
5073   edge_iterator ei;
5074
5075   FOR_EACH_EDGE (e, ei, bb->preds)
5076     fprintf (file, "bb_%d ", e->src->index);
5077 }
5078
5079
5080 /* Print on FILE the indexes for the successors of basic_block BB.  */
5081
5082 static void
5083 print_succ_bbs (FILE *file, basic_block bb)
5084 {
5085   edge e;
5086   edge_iterator ei;
5087
5088   FOR_EACH_EDGE (e, ei, bb->succs)
5089     fprintf (file, "bb_%d ", e->dest->index);
5090 }
5091
5092
5093 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5094
5095 static void
5096 print_loop (FILE *file, struct loop *loop, int indent)
5097 {
5098   char *s_indent;
5099   basic_block bb;
5100
5101   if (loop == NULL)
5102     return;
5103
5104   s_indent = (char *) alloca ((size_t) indent + 1);
5105   memset ((void *) s_indent, ' ', (size_t) indent);
5106   s_indent[indent] = '\0';
5107
5108   /* Print the loop's header.  */
5109   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5110
5111   /* Print the loop's body.  */
5112   fprintf (file, "%s{\n", s_indent);
5113   FOR_EACH_BB (bb)
5114     if (bb->loop_father == loop)
5115       {
5116         /* Print the basic_block's header.  */
5117         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5118         print_pred_bbs (file, bb);
5119         fprintf (file, "}, succs = {");
5120         print_succ_bbs (file, bb);
5121         fprintf (file, "})\n");
5122
5123         /* Print the basic_block's body.  */
5124         fprintf (file, "%s  {\n", s_indent);
5125         tree_dump_bb (bb, file, indent + 4);
5126         fprintf (file, "%s  }\n", s_indent);
5127       }
5128
5129   print_loop (file, loop->inner, indent + 2);
5130   fprintf (file, "%s}\n", s_indent);
5131   print_loop (file, loop->next, indent);
5132 }
5133
5134
5135 /* Follow a CFG edge from the entry point of the program, and on entry
5136    of a loop, pretty print the loop structure on FILE.  */
5137
5138 void
5139 print_loop_ir (FILE *file)
5140 {
5141   basic_block bb;
5142
5143   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
5144   if (bb && bb->loop_father)
5145     print_loop (file, bb->loop_father, 0);
5146 }
5147
5148
5149 /* Debugging loops structure at tree level.  */
5150
5151 void
5152 debug_loop_ir (void)
5153 {
5154   print_loop_ir (stderr);
5155 }
5156
5157
5158 /* Return true if BB ends with a call, possibly followed by some
5159    instructions that must stay with the call.  Return false,
5160    otherwise.  */
5161
5162 static bool
5163 tree_block_ends_with_call_p (basic_block bb)
5164 {
5165   block_stmt_iterator bsi = bsi_last (bb);
5166   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5167 }
5168
5169
5170 /* Return true if BB ends with a conditional branch.  Return false,
5171    otherwise.  */
5172
5173 static bool
5174 tree_block_ends_with_condjump_p (basic_block bb)
5175 {
5176   tree stmt = last_stmt (bb);
5177   return (stmt && TREE_CODE (stmt) == COND_EXPR);
5178 }
5179
5180
5181 /* Return true if we need to add fake edge to exit at statement T.
5182    Helper function for tree_flow_call_edges_add.  */
5183
5184 static bool
5185 need_fake_edge_p (tree t)
5186 {
5187   tree call;
5188
5189   /* NORETURN and LONGJMP calls already have an edge to exit.
5190      CONST and PURE calls do not need one.
5191      We don't currently check for CONST and PURE here, although
5192      it would be a good idea, because those attributes are
5193      figured out from the RTL in mark_constant_function, and
5194      the counter incrementation code from -fprofile-arcs
5195      leads to different results from -fbranch-probabilities.  */
5196   call = get_call_expr_in (t);
5197   if (call
5198       && !(call_expr_flags (call) & ECF_NORETURN))
5199     return true;
5200
5201   if (TREE_CODE (t) == ASM_EXPR
5202        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5203     return true;
5204
5205   return false;
5206 }
5207
5208
5209 /* Add fake edges to the function exit for any non constant and non
5210    noreturn calls, volatile inline assembly in the bitmap of blocks
5211    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5212    the number of blocks that were split.
5213
5214    The goal is to expose cases in which entering a basic block does
5215    not imply that all subsequent instructions must be executed.  */
5216
5217 static int
5218 tree_flow_call_edges_add (sbitmap blocks)
5219 {
5220   int i;
5221   int blocks_split = 0;
5222   int last_bb = last_basic_block;
5223   bool check_last_block = false;
5224
5225   if (n_basic_blocks == NUM_FIXED_BLOCKS)
5226     return 0;
5227
5228   if (! blocks)
5229     check_last_block = true;
5230   else
5231     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5232
5233   /* In the last basic block, before epilogue generation, there will be
5234      a fallthru edge to EXIT.  Special care is required if the last insn
5235      of the last basic block is a call because make_edge folds duplicate
5236      edges, which would result in the fallthru edge also being marked
5237      fake, which would result in the fallthru edge being removed by
5238      remove_fake_edges, which would result in an invalid CFG.
5239
5240      Moreover, we can't elide the outgoing fake edge, since the block
5241      profiler needs to take this into account in order to solve the minimal
5242      spanning tree in the case that the call doesn't return.
5243
5244      Handle this by adding a dummy instruction in a new last basic block.  */
5245   if (check_last_block)
5246     {
5247       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5248       block_stmt_iterator bsi = bsi_last (bb);
5249       tree t = NULL_TREE;
5250       if (!bsi_end_p (bsi))
5251         t = bsi_stmt (bsi);
5252
5253       if (t && need_fake_edge_p (t))
5254         {
5255           edge e;
5256
5257           e = find_edge (bb, EXIT_BLOCK_PTR);
5258           if (e)
5259             {
5260               bsi_insert_on_edge (e, build_empty_stmt ());
5261               bsi_commit_edge_inserts ();
5262             }
5263         }
5264     }
5265
5266   /* Now add fake edges to the function exit for any non constant
5267      calls since there is no way that we can determine if they will
5268      return or not...  */
5269   for (i = 0; i < last_bb; i++)
5270     {
5271       basic_block bb = BASIC_BLOCK (i);
5272       block_stmt_iterator bsi;
5273       tree stmt, last_stmt;
5274
5275       if (!bb)
5276         continue;
5277
5278       if (blocks && !TEST_BIT (blocks, i))
5279         continue;
5280
5281       bsi = bsi_last (bb);
5282       if (!bsi_end_p (bsi))
5283         {
5284           last_stmt = bsi_stmt (bsi);
5285           do
5286             {
5287               stmt = bsi_stmt (bsi);
5288               if (need_fake_edge_p (stmt))
5289                 {
5290                   edge e;
5291                   /* The handling above of the final block before the
5292                      epilogue should be enough to verify that there is
5293                      no edge to the exit block in CFG already.
5294                      Calling make_edge in such case would cause us to
5295                      mark that edge as fake and remove it later.  */
5296 #ifdef ENABLE_CHECKING
5297                   if (stmt == last_stmt)
5298                     {
5299                       e = find_edge (bb, EXIT_BLOCK_PTR);
5300                       gcc_assert (e == NULL);
5301                     }
5302 #endif
5303
5304                   /* Note that the following may create a new basic block
5305                      and renumber the existing basic blocks.  */
5306                   if (stmt != last_stmt)
5307                     {
5308                       e = split_block (bb, stmt);
5309                       if (e)
5310                         blocks_split++;
5311                     }
5312                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5313                 }
5314               bsi_prev (&bsi);
5315             }
5316           while (!bsi_end_p (bsi));
5317         }
5318     }
5319
5320   if (blocks_split)
5321     verify_flow_info ();
5322
5323   return blocks_split;
5324 }
5325
5326 bool
5327 tree_purge_dead_eh_edges (basic_block bb)
5328 {
5329   bool changed = false;
5330   edge e;
5331   edge_iterator ei;
5332   tree stmt = last_stmt (bb);
5333
5334   if (stmt && tree_can_throw_internal (stmt))
5335     return false;
5336
5337   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5338     {
5339       if (e->flags & EDGE_EH)
5340         {
5341           remove_edge (e);
5342           changed = true;
5343         }
5344       else
5345         ei_next (&ei);
5346     }
5347
5348   /* Removal of dead EH edges might change dominators of not
5349      just immediate successors.  E.g. when bb1 is changed so that
5350      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5351      eh edges purged by this function in:
5352            0
5353           / \
5354          v   v
5355          1-->2
5356         / \  |
5357        v   v |
5358        3-->4 |
5359         \    v
5360          --->5
5361              |
5362              -
5363      idom(bb5) must be recomputed.  For now just free the dominance
5364      info.  */
5365   if (changed)
5366     free_dominance_info (CDI_DOMINATORS);
5367
5368   return changed;
5369 }
5370
5371 bool
5372 tree_purge_all_dead_eh_edges (bitmap blocks)
5373 {
5374   bool changed = false;
5375   unsigned i;
5376   bitmap_iterator bi;
5377
5378   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5379     {
5380       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5381     }
5382
5383   return changed;
5384 }
5385
5386 /* This function is called whenever a new edge is created or
5387    redirected.  */
5388
5389 static void
5390 tree_execute_on_growing_pred (edge e)
5391 {
5392   basic_block bb = e->dest;
5393
5394   if (phi_nodes (bb))
5395     reserve_phi_args_for_new_edge (bb);
5396 }
5397
5398 /* This function is called immediately before edge E is removed from
5399    the edge vector E->dest->preds.  */
5400
5401 static void
5402 tree_execute_on_shrinking_pred (edge e)
5403 {
5404   if (phi_nodes (e->dest))
5405     remove_phi_args (e);
5406 }
5407
5408 /*---------------------------------------------------------------------------
5409   Helper functions for Loop versioning
5410   ---------------------------------------------------------------------------*/
5411
5412 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
5413    of 'first'. Both of them are dominated by 'new_head' basic block. When
5414    'new_head' was created by 'second's incoming edge it received phi arguments
5415    on the edge by split_edge(). Later, additional edge 'e' was created to
5416    connect 'new_head' and 'first'. Now this routine adds phi args on this
5417    additional edge 'e' that new_head to second edge received as part of edge
5418    splitting.
5419 */
5420
5421 static void
5422 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
5423                                 basic_block new_head, edge e)
5424 {
5425   tree phi1, phi2;
5426   edge e2 = find_edge (new_head, second);
5427
5428   /* Because NEW_HEAD has been created by splitting SECOND's incoming
5429      edge, we should always have an edge from NEW_HEAD to SECOND.  */
5430   gcc_assert (e2 != NULL);
5431
5432   /* Browse all 'second' basic block phi nodes and add phi args to
5433      edge 'e' for 'first' head. PHI args are always in correct order.  */
5434
5435   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
5436        phi2 && phi1;
5437        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
5438     {
5439       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
5440       add_phi_arg (phi1, def, e);
5441     }
5442 }
5443
5444 /* Adds a if else statement to COND_BB with condition COND_EXPR.
5445    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
5446    the destination of the ELSE part.  */
5447 static void
5448 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
5449                             basic_block cond_bb, void *cond_e)
5450 {
5451   block_stmt_iterator bsi;
5452   tree goto1 = NULL_TREE;
5453   tree goto2 = NULL_TREE;
5454   tree new_cond_expr = NULL_TREE;
5455   tree cond_expr = (tree) cond_e;
5456   edge e0;
5457
5458   /* Build new conditional expr */
5459   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
5460   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
5461   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
5462
5463   /* Add new cond in cond_bb.  */
5464   bsi = bsi_start (cond_bb);
5465   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
5466   /* Adjust edges appropriately to connect new head with first head
5467      as well as second head.  */
5468   e0 = single_succ_edge (cond_bb);
5469   e0->flags &= ~EDGE_FALLTHRU;
5470   e0->flags |= EDGE_FALSE_VALUE;
5471 }
5472
5473 struct cfg_hooks tree_cfg_hooks = {
5474   "tree",
5475   tree_verify_flow_info,
5476   tree_dump_bb,                 /* dump_bb  */
5477   create_bb,                    /* create_basic_block  */
5478   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5479   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5480   remove_bb,                    /* delete_basic_block  */
5481   tree_split_block,             /* split_block  */
5482   tree_move_block_after,        /* move_block_after  */
5483   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5484   tree_merge_blocks,            /* merge_blocks  */
5485   tree_predict_edge,            /* predict_edge  */
5486   tree_predicted_by_p,          /* predicted_by_p  */
5487   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5488   tree_duplicate_bb,            /* duplicate_block  */
5489   tree_split_edge,              /* split_edge  */
5490   tree_make_forwarder_block,    /* make_forward_block  */
5491   NULL,                         /* tidy_fallthru_edge  */
5492   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5493   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5494   tree_flow_call_edges_add,     /* flow_call_edges_add */
5495   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5496   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5497   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
5498   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5499   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
5500   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
5501   flush_pending_stmts           /* flush_pending_stmts */
5502 };
5503
5504
5505 /* Split all critical edges.  */
5506
5507 static unsigned int
5508 split_critical_edges (void)
5509 {
5510   basic_block bb;
5511   edge e;
5512   edge_iterator ei;
5513
5514   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5515      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5516      mappings around the calls to split_edge.  */
5517   start_recording_case_labels ();
5518   FOR_ALL_BB (bb)
5519     {
5520       FOR_EACH_EDGE (e, ei, bb->succs)
5521         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5522           {
5523             split_edge (e);
5524           }
5525     }
5526   end_recording_case_labels ();
5527   return 0;
5528 }
5529
5530 struct tree_opt_pass pass_split_crit_edges =
5531 {
5532   "crited",                          /* name */
5533   NULL,                          /* gate */
5534   split_critical_edges,          /* execute */
5535   NULL,                          /* sub */
5536   NULL,                          /* next */
5537   0,                             /* static_pass_number */
5538   TV_TREE_SPLIT_EDGES,           /* tv_id */
5539   PROP_cfg,                      /* properties required */
5540   PROP_no_crit_edges,            /* properties_provided */
5541   0,                             /* properties_destroyed */
5542   0,                             /* todo_flags_start */
5543   TODO_dump_func,                /* todo_flags_finish */
5544   0                              /* letter */
5545 };
5546
5547 \f
5548 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5549    a temporary, make sure and register it to be renamed if necessary,
5550    and finally return the temporary.  Put the statements to compute
5551    EXP before the current statement in BSI.  */
5552
5553 tree
5554 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5555 {
5556   tree t, new_stmt, orig_stmt;
5557
5558   if (is_gimple_val (exp))
5559     return exp;
5560
5561   t = make_rename_temp (type, NULL);
5562   new_stmt = build2 (MODIFY_EXPR, type, t, exp);
5563
5564   orig_stmt = bsi_stmt (*bsi);
5565   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5566   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5567
5568   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5569
5570   return t;
5571 }
5572
5573 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5574    Return the gimple_val holding the result.  */
5575
5576 tree
5577 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5578                  tree type, tree a, tree b, tree c)
5579 {
5580   tree ret;
5581
5582   ret = fold_build3 (code, type, a, b, c);
5583   STRIP_NOPS (ret);
5584
5585   return gimplify_val (bsi, type, ret);
5586 }
5587
5588 /* Build a binary operation and gimplify it.  Emit code before BSI.
5589    Return the gimple_val holding the result.  */
5590
5591 tree
5592 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5593                  tree type, tree a, tree b)
5594 {
5595   tree ret;
5596
5597   ret = fold_build2 (code, type, a, b);
5598   STRIP_NOPS (ret);
5599
5600   return gimplify_val (bsi, type, ret);
5601 }
5602
5603 /* Build a unary operation and gimplify it.  Emit code before BSI.
5604    Return the gimple_val holding the result.  */
5605
5606 tree
5607 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5608                  tree a)
5609 {
5610   tree ret;
5611
5612   ret = fold_build1 (code, type, a);
5613   STRIP_NOPS (ret);
5614
5615   return gimplify_val (bsi, type, ret);
5616 }
5617
5618
5619 \f
5620 /* Emit return warnings.  */
5621
5622 static unsigned int
5623 execute_warn_function_return (void)
5624 {
5625 #ifdef USE_MAPPED_LOCATION
5626   source_location location;
5627 #else
5628   location_t *locus;
5629 #endif
5630   tree last;
5631   edge e;
5632   edge_iterator ei;
5633
5634   /* If we have a path to EXIT, then we do return.  */
5635   if (TREE_THIS_VOLATILE (cfun->decl)
5636       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5637     {
5638 #ifdef USE_MAPPED_LOCATION
5639       location = UNKNOWN_LOCATION;
5640 #else
5641       locus = NULL;
5642 #endif
5643       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5644         {
5645           last = last_stmt (e->src);
5646           if (TREE_CODE (last) == RETURN_EXPR
5647 #ifdef USE_MAPPED_LOCATION
5648               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5649 #else
5650               && (locus = EXPR_LOCUS (last)) != NULL)
5651 #endif
5652             break;
5653         }
5654 #ifdef USE_MAPPED_LOCATION
5655       if (location == UNKNOWN_LOCATION)
5656         location = cfun->function_end_locus;
5657       warning (0, "%H%<noreturn%> function does return", &location);
5658 #else
5659       if (!locus)
5660         locus = &cfun->function_end_locus;
5661       warning (0, "%H%<noreturn%> function does return", locus);
5662 #endif
5663     }
5664
5665   /* If we see "return;" in some basic block, then we do reach the end
5666      without returning a value.  */
5667   else if (warn_return_type
5668            && !TREE_NO_WARNING (cfun->decl)
5669            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5670            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5671     {
5672       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5673         {
5674           tree last = last_stmt (e->src);
5675           if (TREE_CODE (last) == RETURN_EXPR
5676               && TREE_OPERAND (last, 0) == NULL
5677               && !TREE_NO_WARNING (last))
5678             {
5679 #ifdef USE_MAPPED_LOCATION
5680               location = EXPR_LOCATION (last);
5681               if (location == UNKNOWN_LOCATION)
5682                   location = cfun->function_end_locus;
5683               warning (0, "%Hcontrol reaches end of non-void function", &location);
5684 #else
5685               locus = EXPR_LOCUS (last);
5686               if (!locus)
5687                 locus = &cfun->function_end_locus;
5688               warning (0, "%Hcontrol reaches end of non-void function", locus);
5689 #endif
5690               TREE_NO_WARNING (cfun->decl) = 1;
5691               break;
5692             }
5693         }
5694     }
5695   return 0;
5696 }
5697
5698
5699 /* Given a basic block B which ends with a conditional and has
5700    precisely two successors, determine which of the edges is taken if
5701    the conditional is true and which is taken if the conditional is
5702    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5703
5704 void
5705 extract_true_false_edges_from_block (basic_block b,
5706                                      edge *true_edge,
5707                                      edge *false_edge)
5708 {
5709   edge e = EDGE_SUCC (b, 0);
5710
5711   if (e->flags & EDGE_TRUE_VALUE)
5712     {
5713       *true_edge = e;
5714       *false_edge = EDGE_SUCC (b, 1);
5715     }
5716   else
5717     {
5718       *false_edge = e;
5719       *true_edge = EDGE_SUCC (b, 1);
5720     }
5721 }
5722
5723 struct tree_opt_pass pass_warn_function_return =
5724 {
5725   NULL,                                 /* name */
5726   NULL,                                 /* gate */
5727   execute_warn_function_return,         /* execute */
5728   NULL,                                 /* sub */
5729   NULL,                                 /* next */
5730   0,                                    /* static_pass_number */
5731   0,                                    /* tv_id */
5732   PROP_cfg,                             /* properties_required */
5733   0,                                    /* properties_provided */
5734   0,                                    /* properties_destroyed */
5735   0,                                    /* todo_flags_start */
5736   0,                                    /* todo_flags_finish */
5737   0                                     /* letter */
5738 };
5739
5740 /* Emit noreturn warnings.  */
5741
5742 static unsigned int
5743 execute_warn_function_noreturn (void)
5744 {
5745   if (warn_missing_noreturn
5746       && !TREE_THIS_VOLATILE (cfun->decl)
5747       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5748       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5749     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5750              "for attribute %<noreturn%>",
5751              cfun->decl);
5752   return 0;
5753 }
5754
5755 struct tree_opt_pass pass_warn_function_noreturn =
5756 {
5757   NULL,                                 /* name */
5758   NULL,                                 /* gate */
5759   execute_warn_function_noreturn,       /* execute */
5760   NULL,                                 /* sub */
5761   NULL,                                 /* next */
5762   0,                                    /* static_pass_number */
5763   0,                                    /* tv_id */
5764   PROP_cfg,                             /* properties_required */
5765   0,                                    /* properties_provided */
5766   0,                                    /* properties_destroyed */
5767   0,                                    /* todo_flags_start */
5768   0,                                    /* todo_flags_finish */
5769   0                                     /* letter */
5770 };