gcc/tree-cfg.c

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