contrib/gcc/tree-cfg.c

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