gcc/tree-cfg.c

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