gcc/tree-cfg.c

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