gcc/tree-cfg.c

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