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