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 NOP_EXPR:
3256     case CONVERT_EXPR:
3257     case FIX_TRUNC_EXPR:
3258     case FLOAT_EXPR:
3259     case NEGATE_EXPR:
3260     case ABS_EXPR:
3261     case BIT_NOT_EXPR:
3262     case TRUTH_NOT_EXPR:
3263       CHECK_OP (0, "invalid operand to unary operator");
3264       break;
3265
3266     case REALPART_EXPR:
3267     case IMAGPART_EXPR:
3268     case COMPONENT_REF:
3269     case ARRAY_REF:
3270     case ARRAY_RANGE_REF:
3271     case BIT_FIELD_REF:
3272     case VIEW_CONVERT_EXPR:
3273       /* We have a nest of references.  Verify that each of the operands
3274          that determine where to reference is either a constant or a variable,
3275          verify that the base is valid, and then show we've already checked
3276          the subtrees.  */
3277       while (handled_component_p (t))
3278         {
3279           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3280             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3281           else if (TREE_CODE (t) == ARRAY_REF
3282                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3283             {
3284               CHECK_OP (1, "invalid array index");
3285               if (TREE_OPERAND (t, 2))
3286                 CHECK_OP (2, "invalid array lower bound");
3287               if (TREE_OPERAND (t, 3))
3288                 CHECK_OP (3, "invalid array stride");
3289             }
3290           else if (TREE_CODE (t) == BIT_FIELD_REF)
3291             {
3292               if (!host_integerp (TREE_OPERAND (t, 1), 1)
3293                   || !host_integerp (TREE_OPERAND (t, 2), 1))
3294                 {
3295                   error ("invalid position or size operand to BIT_FIELD_REF");
3296                   return t;
3297                 }
3298               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
3299                        && (TYPE_PRECISION (TREE_TYPE (t))
3300                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3301                 {
3302                   error ("integral result type precision does not match "
3303                          "field size of BIT_FIELD_REF");
3304                   return t;
3305                 }
3306               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
3307                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
3308                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3309                 {
3310                   error ("mode precision of non-integral result does not "
3311                          "match field size of BIT_FIELD_REF");
3312                   return t;
3313                 }
3314             }
3315
3316           t = TREE_OPERAND (t, 0);
3317         }
3318
3319       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
3320         {
3321           error ("invalid reference prefix");
3322           return t;
3323         }
3324       *walk_subtrees = 0;
3325       break;
3326     case PLUS_EXPR:
3327     case MINUS_EXPR:
3328       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3329          POINTER_PLUS_EXPR. */
3330       if (POINTER_TYPE_P (TREE_TYPE (t)))
3331         {
3332           error ("invalid operand to plus/minus, type is a pointer");
3333           return t;
3334         }
3335       CHECK_OP (0, "invalid operand to binary operator");
3336       CHECK_OP (1, "invalid operand to binary operator");
3337       break;
3338
3339     case POINTER_PLUS_EXPR:
3340       /* Check to make sure the first operand is a pointer or reference type. */
3341       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3342         {
3343           error ("invalid operand to pointer plus, first operand is not a pointer");
3344           return t;
3345         }
3346       /* Check to make sure the second operand is an integer with type of
3347          sizetype.  */
3348       if (!useless_type_conversion_p (sizetype,
3349                                      TREE_TYPE (TREE_OPERAND (t, 1))))
3350         {
3351           error ("invalid operand to pointer plus, second operand is not an "
3352                  "integer with type of sizetype.");
3353           return t;
3354         }
3355       /* FALLTHROUGH */
3356     case LT_EXPR:
3357     case LE_EXPR:
3358     case GT_EXPR:
3359     case GE_EXPR:
3360     case EQ_EXPR:
3361     case NE_EXPR:
3362     case UNORDERED_EXPR:
3363     case ORDERED_EXPR:
3364     case UNLT_EXPR:
3365     case UNLE_EXPR:
3366     case UNGT_EXPR:
3367     case UNGE_EXPR:
3368     case UNEQ_EXPR:
3369     case LTGT_EXPR:
3370     case MULT_EXPR:
3371     case TRUNC_DIV_EXPR:
3372     case CEIL_DIV_EXPR:
3373     case FLOOR_DIV_EXPR:
3374     case ROUND_DIV_EXPR:
3375     case TRUNC_MOD_EXPR:
3376     case CEIL_MOD_EXPR:
3377     case FLOOR_MOD_EXPR:
3378     case ROUND_MOD_EXPR:
3379     case RDIV_EXPR:
3380     case EXACT_DIV_EXPR:
3381     case MIN_EXPR:
3382     case MAX_EXPR:
3383     case LSHIFT_EXPR:
3384     case RSHIFT_EXPR:
3385     case LROTATE_EXPR:
3386     case RROTATE_EXPR:
3387     case BIT_IOR_EXPR:
3388     case BIT_XOR_EXPR:
3389     case BIT_AND_EXPR:
3390       CHECK_OP (0, "invalid operand to binary operator");
3391       CHECK_OP (1, "invalid operand to binary operator");
3392       break;
3393
3394     case CONSTRUCTOR:
3395       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3396         *walk_subtrees = 0;
3397       break;
3398
3399     default:
3400       break;
3401     }
3402   return NULL;
3403
3404 #undef CHECK_OP
3405 }
3406
3407 /* Verifies if EXPR is a valid GIMPLE unary expression.  Returns true
3408    if there is an error, otherwise false.  */
3409
3410 static bool
3411 verify_gimple_unary_expr (const_tree expr)
3412 {
3413   tree op = TREE_OPERAND (expr, 0);
3414   tree type = TREE_TYPE (expr);
3415
3416   if (!is_gimple_val (op))
3417     {
3418       error ("invalid operand in unary expression");
3419       return true;
3420     }
3421
3422   /* For general unary expressions we have the operations type
3423      as the effective type the operation is carried out on.  So all
3424      we need to require is that the operand is trivially convertible
3425      to that type.  */
3426   if (!useless_type_conversion_p (type, TREE_TYPE (op)))
3427     {
3428       error ("type mismatch in unary expression");
3429       debug_generic_expr (type);
3430       debug_generic_expr (TREE_TYPE (op));
3431       return true;
3432     }
3433
3434   return false;
3435 }
3436
3437 /* Verifies if EXPR is a valid GIMPLE binary expression.  Returns true
3438    if there is an error, otherwise false.  */
3439
3440 static bool
3441 verify_gimple_binary_expr (const_tree expr)
3442 {
3443   tree op0 = TREE_OPERAND (expr, 0);
3444   tree op1 = TREE_OPERAND (expr, 1);
3445   tree type = TREE_TYPE (expr);
3446
3447   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3448     {
3449       error ("invalid operands in binary expression");
3450       return true;
3451     }
3452
3453   /* For general binary expressions we have the operations type
3454      as the effective type the operation is carried out on.  So all
3455      we need to require is that both operands are trivially convertible
3456      to that type.  */
3457   if (!useless_type_conversion_p (type, TREE_TYPE (op0))
3458       || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3459     {
3460       error ("type mismatch in binary expression");
3461       debug_generic_stmt (type);
3462       debug_generic_stmt (TREE_TYPE (op0));
3463       debug_generic_stmt (TREE_TYPE (op1));
3464       return true;
3465     }
3466
3467   return false;
3468 }
3469
3470 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3471    Returns true if there is an error, otherwise false.  */
3472
3473 static bool
3474 verify_gimple_min_lval (tree expr)
3475 {
3476   tree op;
3477
3478   if (is_gimple_id (expr))
3479     return false;
3480
3481   if (TREE_CODE (expr) != INDIRECT_REF
3482       && TREE_CODE (expr) != ALIGN_INDIRECT_REF
3483       && TREE_CODE (expr) != MISALIGNED_INDIRECT_REF)
3484     {
3485       error ("invalid expression for min lvalue");
3486       return true;
3487     }
3488
3489   op = TREE_OPERAND (expr, 0);
3490   if (!is_gimple_val (op))
3491     {
3492       error ("invalid operand in indirect reference");
3493       debug_generic_stmt (op);
3494       return true;
3495     }
3496   if (!useless_type_conversion_p (TREE_TYPE (expr),
3497                                   TREE_TYPE (TREE_TYPE (op))))
3498     {
3499       error ("type mismatch in indirect reference");
3500       debug_generic_stmt (TREE_TYPE (expr));
3501       debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3502       return true;
3503     }
3504
3505   return false;
3506 }
3507
3508 /* Verify if EXPR is a valid GIMPLE reference expression.  Returns true
3509    if there is an error, otherwise false.  */
3510
3511 static bool
3512 verify_gimple_reference (tree expr)
3513 {
3514   while (handled_component_p (expr))
3515     {
3516       tree op = TREE_OPERAND (expr, 0);
3517
3518       if (TREE_CODE (expr) == ARRAY_REF
3519           || TREE_CODE (expr) == ARRAY_RANGE_REF)
3520         {
3521           if (!is_gimple_val (TREE_OPERAND (expr, 1))
3522               || (TREE_OPERAND (expr, 2)
3523                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
3524               || (TREE_OPERAND (expr, 3)
3525                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
3526             {
3527               error ("invalid operands to array reference");
3528               debug_generic_stmt (expr);
3529               return true;
3530             }
3531         }
3532
3533       /* Verify if the reference array element types are compatible.  */
3534       if (TREE_CODE (expr) == ARRAY_REF
3535           && !useless_type_conversion_p (TREE_TYPE (expr),
3536                                          TREE_TYPE (TREE_TYPE (op))))
3537         {
3538           error ("type mismatch in array reference");
3539           debug_generic_stmt (TREE_TYPE (expr));
3540           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3541           return true;
3542         }
3543       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3544           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3545                                          TREE_TYPE (TREE_TYPE (op))))
3546         {
3547           error ("type mismatch in array range reference");
3548           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3549           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3550           return true;
3551         }
3552
3553       if ((TREE_CODE (expr) == REALPART_EXPR
3554            || TREE_CODE (expr) == IMAGPART_EXPR)
3555           && !useless_type_conversion_p (TREE_TYPE (expr),
3556                                          TREE_TYPE (TREE_TYPE (op))))
3557         {
3558           error ("type mismatch in real/imagpart reference");
3559           debug_generic_stmt (TREE_TYPE (expr));
3560           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3561           return true;
3562         }
3563
3564       if (TREE_CODE (expr) == COMPONENT_REF
3565           && !useless_type_conversion_p (TREE_TYPE (expr),
3566                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3567         {
3568           error ("type mismatch in component reference");
3569           debug_generic_stmt (TREE_TYPE (expr));
3570           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3571           return true;
3572         }
3573
3574       /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3575          is nothing to verify.  Gross mismatches at most invoke
3576          undefined behavior.  */
3577
3578       expr = op;
3579     }
3580
3581   return verify_gimple_min_lval (expr);
3582 }
3583
3584 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3585    list of pointer-to types that is trivially convertible to DEST.  */
3586
3587 static bool
3588 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3589 {
3590   tree src;
3591
3592   if (!TYPE_POINTER_TO (src_obj))
3593     return true;
3594
3595   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3596     if (useless_type_conversion_p (dest, src))
3597       return true;
3598
3599   return false;
3600 }
3601
3602 /* Verify the GIMPLE expression EXPR.  Returns true if there is an
3603    error, otherwise false.  */
3604
3605 static bool
3606 verify_gimple_expr (tree expr)
3607 {
3608   tree type = TREE_TYPE (expr);
3609
3610   if (is_gimple_val (expr))
3611     return false;
3612
3613   /* Special codes we cannot handle via their class.  */
3614   switch (TREE_CODE (expr))
3615     {
3616     case NOP_EXPR:
3617     case CONVERT_EXPR:
3618       {
3619         tree op = TREE_OPERAND (expr, 0);
3620         if (!is_gimple_val (op))
3621           {
3622             error ("invalid operand in conversion");
3623             return true;
3624           }
3625
3626         /* Allow conversions between integral types and between
3627            pointer types.  */
3628         if ((INTEGRAL_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3629             || (POINTER_TYPE_P (type) && POINTER_TYPE_P (TREE_TYPE (op))))
3630           return false;
3631
3632         /* Allow conversions between integral types and pointers only if
3633            there is no sign or zero extension involved.  */
3634         if (((POINTER_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3635              || (POINTER_TYPE_P (TREE_TYPE (op)) && INTEGRAL_TYPE_P (type)))
3636             && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op)))
3637           return false;
3638
3639         /* Allow conversion from integer to offset type and vice versa.  */
3640         if ((TREE_CODE (type) == OFFSET_TYPE
3641              && TREE_CODE (TREE_TYPE (op)) == INTEGER_TYPE)
3642             || (TREE_CODE (type) == INTEGER_TYPE
3643                 && TREE_CODE (TREE_TYPE (op)) == OFFSET_TYPE))
3644           return false;
3645
3646         /* Otherwise assert we are converting between types of the
3647            same kind.  */
3648         if (TREE_CODE (type) != TREE_CODE (TREE_TYPE (op)))
3649           {
3650             error ("invalid types in nop conversion");
3651             debug_generic_expr (type);
3652             debug_generic_expr (TREE_TYPE (op));
3653             return true;
3654           }
3655
3656         return false;
3657       }
3658
3659     case FLOAT_EXPR:
3660       {
3661         tree op = TREE_OPERAND (expr, 0);
3662         if (!is_gimple_val (op))
3663           {
3664             error ("invalid operand in int to float conversion");
3665             return true;
3666           }
3667         if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3668             || !SCALAR_FLOAT_TYPE_P (type))
3669           {
3670             error ("invalid types in conversion to floating point");
3671             debug_generic_expr (type);
3672             debug_generic_expr (TREE_TYPE (op));
3673             return true;
3674           }
3675         return false;
3676       }
3677
3678     case FIX_TRUNC_EXPR:
3679       {
3680         tree op = TREE_OPERAND (expr, 0);
3681         if (!is_gimple_val (op))
3682           {
3683             error ("invalid operand in float to int conversion");
3684             return true;
3685           }
3686         if (!INTEGRAL_TYPE_P (type)
3687             || !SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
3688           {
3689             error ("invalid types in conversion to integer");
3690             debug_generic_expr (type);
3691             debug_generic_expr (TREE_TYPE (op));
3692             return true;
3693           }
3694         return false;
3695       }
3696
3697     case COMPLEX_EXPR:
3698       {
3699         tree op0 = TREE_OPERAND (expr, 0);
3700         tree op1 = TREE_OPERAND (expr, 1);
3701         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3702           {
3703             error ("invalid operands in complex expression");
3704             return true;
3705           }
3706         if (!TREE_CODE (type) == COMPLEX_TYPE
3707             || !(TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3708                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0)))
3709             || !(TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3710                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op1)))
3711             || !useless_type_conversion_p (TREE_TYPE (type),
3712                                            TREE_TYPE (op0))
3713             || !useless_type_conversion_p (TREE_TYPE (type),
3714                                            TREE_TYPE (op1)))
3715           {
3716             error ("type mismatch in complex expression");
3717             debug_generic_stmt (TREE_TYPE (expr));
3718             debug_generic_stmt (TREE_TYPE (op0));
3719             debug_generic_stmt (TREE_TYPE (op1));
3720             return true;
3721           }
3722         return false;
3723       }
3724
3725     case CONSTRUCTOR:
3726       {
3727         /* This is used like COMPLEX_EXPR but for vectors.  */
3728         if (TREE_CODE (type) != VECTOR_TYPE)
3729           {
3730             error ("constructor not allowed for non-vector types");
3731             debug_generic_stmt (type);
3732             return true;
3733           }
3734         /* FIXME: verify constructor arguments.  */
3735         return false;
3736       }
3737
3738     case LSHIFT_EXPR:
3739     case RSHIFT_EXPR:
3740     case LROTATE_EXPR:
3741     case RROTATE_EXPR:
3742       {
3743         tree op0 = TREE_OPERAND (expr, 0);
3744         tree op1 = TREE_OPERAND (expr, 1);
3745         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3746           {
3747             error ("invalid operands in shift expression");
3748             return true;
3749           }
3750         if (!TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3751             || !useless_type_conversion_p (type, TREE_TYPE (op0)))
3752           {
3753             error ("type mismatch in shift expression");
3754             debug_generic_stmt (TREE_TYPE (expr));
3755             debug_generic_stmt (TREE_TYPE (op0));
3756             debug_generic_stmt (TREE_TYPE (op1));
3757             return true;
3758           }
3759         return false;
3760       }
3761
3762     case PLUS_EXPR:
3763     case MINUS_EXPR:
3764       {
3765         tree op0 = TREE_OPERAND (expr, 0);
3766         tree op1 = TREE_OPERAND (expr, 1);
3767         if (POINTER_TYPE_P (type)
3768             || POINTER_TYPE_P (TREE_TYPE (op0))
3769             || POINTER_TYPE_P (TREE_TYPE (op1)))
3770           {
3771             error ("invalid (pointer) operands to plus/minus");
3772             return true;
3773           }
3774         /* Continue with generic binary expression handling.  */
3775         break;
3776       }
3777
3778     case POINTER_PLUS_EXPR:
3779       {
3780         tree op0 = TREE_OPERAND (expr, 0);
3781         tree op1 = TREE_OPERAND (expr, 1);
3782         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3783           {
3784             error ("invalid operands in pointer plus expression");
3785             return true;
3786           }
3787         if (!POINTER_TYPE_P (TREE_TYPE (op0))
3788             || !useless_type_conversion_p (type, TREE_TYPE (op0))
3789             || !useless_type_conversion_p (sizetype, TREE_TYPE (op1)))
3790           {
3791             error ("type mismatch in pointer plus expression");
3792             debug_generic_stmt (type);
3793             debug_generic_stmt (TREE_TYPE (op0));
3794             debug_generic_stmt (TREE_TYPE (op1));
3795             return true;
3796           }
3797         return false;
3798       }
3799
3800     case COND_EXPR:
3801       {
3802         tree op0 = TREE_OPERAND (expr, 0);
3803         tree op1 = TREE_OPERAND (expr, 1);
3804         tree op2 = TREE_OPERAND (expr, 2);
3805         if ((!is_gimple_val (op1)
3806              && TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE)
3807             || (!is_gimple_val (op2)
3808                 && TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE))
3809           {
3810             error ("invalid operands in conditional expression");
3811             return true;
3812           }
3813         if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3814             || (TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE
3815                 && !useless_type_conversion_p (type, TREE_TYPE (op1)))
3816             || (TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE
3817                 && !useless_type_conversion_p (type, TREE_TYPE (op2))))
3818           {
3819             error ("type mismatch in conditional expression");
3820             debug_generic_stmt (type);
3821             debug_generic_stmt (TREE_TYPE (op0));
3822             debug_generic_stmt (TREE_TYPE (op1));
3823             debug_generic_stmt (TREE_TYPE (op2));
3824             return true;
3825           }
3826         return verify_gimple_expr (op0);
3827       }
3828
3829     case ADDR_EXPR:
3830       {
3831         tree op = TREE_OPERAND (expr, 0);
3832         if (!is_gimple_addressable (op))
3833           {
3834             error ("invalid operand in unary expression");
3835             return true;
3836           }
3837         if (!one_pointer_to_useless_type_conversion_p (type, TREE_TYPE (op))
3838             /* FIXME: a longstanding wart, &a == &a[0].  */
3839             && (TREE_CODE (TREE_TYPE (op)) != ARRAY_TYPE
3840                 || !one_pointer_to_useless_type_conversion_p (type,
3841                       TREE_TYPE (TREE_TYPE (op)))))
3842           {
3843             error ("type mismatch in address expression");
3844             debug_generic_stmt (TREE_TYPE (expr));
3845             debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op)));
3846             return true;
3847           }
3848
3849         return verify_gimple_reference (op);
3850       }
3851
3852     case TRUTH_ANDIF_EXPR:
3853     case TRUTH_ORIF_EXPR:
3854       gcc_unreachable ();
3855
3856     case TRUTH_AND_EXPR:
3857     case TRUTH_OR_EXPR:
3858     case TRUTH_XOR_EXPR:
3859       {
3860         tree op0 = TREE_OPERAND (expr, 0);
3861         tree op1 = TREE_OPERAND (expr, 1);
3862
3863         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3864           {
3865             error ("invalid operands in truth expression");
3866             return true;
3867           }
3868
3869         /* We allow any kind of integral typed argument and result.  */
3870         if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3871             || !INTEGRAL_TYPE_P (TREE_TYPE (op1))
3872             || !INTEGRAL_TYPE_P (type))
3873           {
3874             error ("type mismatch in binary truth expression");
3875             debug_generic_stmt (type);
3876             debug_generic_stmt (TREE_TYPE (op0));
3877             debug_generic_stmt (TREE_TYPE (op1));
3878             return true;
3879           }
3880
3881         return false;
3882       }
3883
3884     case TRUTH_NOT_EXPR:
3885       {
3886         tree op = TREE_OPERAND (expr, 0);
3887
3888         if (!is_gimple_val (op))
3889           {
3890             error ("invalid operand in unary not");
3891             return true;
3892           }
3893
3894         /* For TRUTH_NOT_EXPR we can have any kind of integral
3895            typed arguments and results.  */
3896         if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3897             || !INTEGRAL_TYPE_P (type))
3898           {
3899             error ("type mismatch in not expression");
3900             debug_generic_expr (TREE_TYPE (expr));
3901             debug_generic_expr (TREE_TYPE (op));
3902             return true;
3903           }
3904
3905         return false;
3906       }
3907
3908     case CALL_EXPR:
3909       /* FIXME.  The C frontend passes unpromoted arguments in case it
3910          didn't see a function declaration before the call.  */
3911       {
3912         tree decl = CALL_EXPR_FN (expr);
3913
3914         if (TREE_CODE (decl) == FUNCTION_DECL
3915             && DECL_LOOPING_CONST_OR_PURE_P (decl)
3916             && (!DECL_PURE_P (decl))
3917             && (!TREE_READONLY (decl)))
3918           {
3919             error ("invalid pure const state for function");
3920             return true;
3921           }
3922         return false;
3923       }
3924
3925     case OBJ_TYPE_REF:
3926       /* FIXME.  */
3927       return false;
3928
3929     default:;
3930     }
3931
3932   /* Generic handling via classes.  */
3933   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3934     {
3935     case tcc_unary:
3936       return verify_gimple_unary_expr (expr);
3937
3938     case tcc_binary:
3939       return verify_gimple_binary_expr (expr);
3940
3941     case tcc_reference:
3942       return verify_gimple_reference (expr);
3943
3944     case tcc_comparison:
3945       {
3946         tree op0 = TREE_OPERAND (expr, 0);
3947         tree op1 = TREE_OPERAND (expr, 1);
3948         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3949           {
3950             error ("invalid operands in comparison expression");
3951             return true;
3952           }
3953         /* For comparisons we do not have the operations type as the
3954            effective type the comparison is carried out in.  Instead
3955            we require that either the first operand is trivially
3956            convertible into the second, or the other way around.
3957            The resulting type of a comparison may be any integral type.
3958            Because we special-case pointers to void we allow
3959            comparisons of pointers with the same mode as well.  */
3960         if ((!useless_type_conversion_p (TREE_TYPE (op0), TREE_TYPE (op1))
3961              && !useless_type_conversion_p (TREE_TYPE (op1), TREE_TYPE (op0))
3962              && (!POINTER_TYPE_P (TREE_TYPE (op0))
3963                  || !POINTER_TYPE_P (TREE_TYPE (op1))
3964                  || TYPE_MODE (TREE_TYPE (op0)) != TYPE_MODE (TREE_TYPE (op1))))
3965             || !INTEGRAL_TYPE_P (type))
3966           {
3967             error ("type mismatch in comparison expression");
3968             debug_generic_stmt (TREE_TYPE (expr));
3969             debug_generic_stmt (TREE_TYPE (op0));
3970             debug_generic_stmt (TREE_TYPE (op1));
3971             return true;
3972           }
3973         break;
3974       }
3975
3976     default:
3977       gcc_unreachable ();
3978     }
3979
3980   return false;
3981 }
3982
3983 /* Verify the GIMPLE assignment statement STMT.  Returns true if there
3984    is an error, otherwise false.  */
3985
3986 static bool
3987 verify_gimple_modify_stmt (const_tree stmt)
3988 {
3989   tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3990   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3991
3992   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3993
3994   if (!useless_type_conversion_p (TREE_TYPE (lhs),
3995                                   TREE_TYPE (rhs)))
3996     {
3997       error ("non-trivial conversion at assignment");
3998       debug_generic_expr (TREE_TYPE (lhs));
3999       debug_generic_expr (TREE_TYPE (rhs));
4000       return true;
4001     }
4002
4003   /* Loads/stores from/to a variable are ok.  */
4004   if ((is_gimple_val (lhs)
4005        && is_gimple_variable (rhs))
4006       || (is_gimple_val (rhs)
4007           && is_gimple_variable (lhs)))
4008     return false;
4009
4010   /* Aggregate copies are ok.  */
4011   if (!is_gimple_reg_type (TREE_TYPE (lhs))
4012       && !is_gimple_reg_type (TREE_TYPE (rhs)))
4013     return false;
4014
4015   /* We might get 'loads' from a parameter which is not a gimple value.  */
4016   if (TREE_CODE (rhs) == PARM_DECL)
4017     return verify_gimple_expr (lhs);
4018
4019   if (!is_gimple_variable (lhs)
4020       && verify_gimple_expr (lhs))
4021     return true;
4022
4023   if (!is_gimple_variable (rhs)
4024       && verify_gimple_expr (rhs))
4025     return true;
4026
4027   return false;
4028 }
4029
4030 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4031    error, otherwise false.  */
4032
4033 static bool
4034 verify_gimple_stmt (tree stmt)
4035 {
4036   if (!is_gimple_stmt (stmt))
4037     {
4038       error ("is not a valid GIMPLE statement");
4039       return true;
4040     }
4041
4042   if (OMP_DIRECTIVE_P (stmt))
4043     {
4044       /* OpenMP directives are validated by the FE and never operated
4045          on by the optimizers.  Furthermore, OMP_FOR may contain
4046          non-gimple expressions when the main index variable has had
4047          its address taken.  This does not affect the loop itself
4048          because the header of an OMP_FOR is merely used to determine
4049          how to setup the parallel iteration.  */
4050       return false;
4051     }
4052
4053   switch (TREE_CODE (stmt))
4054     {
4055     case GIMPLE_MODIFY_STMT:
4056       return verify_gimple_modify_stmt (stmt);
4057
4058     case GOTO_EXPR:
4059     case LABEL_EXPR:
4060       return false;
4061
4062     case SWITCH_EXPR:
4063       if (!is_gimple_val (TREE_OPERAND (stmt, 0)))
4064         {
4065           error ("invalid operand to switch statement");
4066           debug_generic_expr (TREE_OPERAND (stmt, 0));
4067         }
4068       return false;
4069
4070     case RETURN_EXPR:
4071       {
4072         tree op = TREE_OPERAND (stmt, 0);
4073
4074         if (TREE_CODE (TREE_TYPE (stmt)) != VOID_TYPE)
4075           {
4076             error ("type error in return expression");
4077             return true;
4078           }
4079
4080         if (op == NULL_TREE
4081             || TREE_CODE (op) == RESULT_DECL)
4082           return false;
4083
4084         return verify_gimple_modify_stmt (op);
4085       }
4086
4087     case CALL_EXPR:
4088     case COND_EXPR:
4089       return verify_gimple_expr (stmt);
4090
4091     case NOP_EXPR:
4092     case CHANGE_DYNAMIC_TYPE_EXPR:
4093     case ASM_EXPR:
4094     case PREDICT_EXPR:
4095       return false;
4096
4097     default:
4098       gcc_unreachable ();
4099     }
4100 }
4101
4102 /* Verify the GIMPLE statements inside the statement list STMTS.
4103    Returns true if there were any errors.  */
4104
4105 static bool
4106 verify_gimple_2 (tree stmts)
4107 {
4108   tree_stmt_iterator tsi;
4109   bool err = false;
4110
4111   for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
4112     {
4113       tree stmt = tsi_stmt (tsi);
4114
4115       switch (TREE_CODE (stmt))
4116         {
4117         case BIND_EXPR:
4118           err |= verify_gimple_2 (BIND_EXPR_BODY (stmt));
4119           break;
4120
4121         case TRY_CATCH_EXPR:
4122         case TRY_FINALLY_EXPR:
4123           err |= verify_gimple_2 (TREE_OPERAND (stmt, 0));
4124           err |= verify_gimple_2 (TREE_OPERAND (stmt, 1));
4125           break;
4126
4127         case CATCH_EXPR:
4128           err |= verify_gimple_2 (CATCH_BODY (stmt));
4129           break;
4130
4131         case EH_FILTER_EXPR:
4132           err |= verify_gimple_2 (EH_FILTER_FAILURE (stmt));
4133           break;
4134
4135         default:
4136           {
4137             bool err2 = verify_gimple_stmt (stmt);
4138             if (err2)
4139               debug_generic_expr (stmt);
4140             err |= err2;
4141           }
4142         }
4143     }
4144
4145   return err;
4146 }
4147
4148
4149 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4150
4151 void
4152 verify_gimple_1 (tree stmts)
4153 {
4154   if (verify_gimple_2 (stmts))
4155     internal_error ("verify_gimple failed");
4156 }
4157
4158 /* Verify the GIMPLE statements inside the current function.  */
4159
4160 void
4161 verify_gimple (void)
4162 {
4163   verify_gimple_1 (BIND_EXPR_BODY (DECL_SAVED_TREE (cfun->decl)));
4164 }
4165
4166 /* Verify STMT, return true if STMT is not in GIMPLE form.
4167    TODO: Implement type checking.  */
4168
4169 static bool
4170 verify_stmt (tree stmt, bool last_in_block)
4171 {
4172   tree addr;
4173
4174   if (OMP_DIRECTIVE_P (stmt))
4175     {
4176       /* OpenMP directives are validated by the FE and never operated
4177          on by the optimizers.  Furthermore, OMP_FOR may contain
4178          non-gimple expressions when the main index variable has had
4179          its address taken.  This does not affect the loop itself
4180          because the header of an OMP_FOR is merely used to determine
4181          how to setup the parallel iteration.  */
4182       return false;
4183     }
4184
4185   if (!is_gimple_stmt (stmt))
4186     {
4187       error ("is not a valid GIMPLE statement");
4188       goto fail;
4189     }
4190
4191   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
4192   if (addr)
4193     {
4194       debug_generic_stmt (addr);
4195       if (addr != stmt)
4196         {
4197           inform ("in statement");
4198           debug_generic_stmt (stmt);
4199         }
4200       return true;
4201     }
4202
4203   /* If the statement is marked as part of an EH region, then it is
4204      expected that the statement could throw.  Verify that when we
4205      have optimizations that simplify statements such that we prove
4206      that they cannot throw, that we update other data structures
4207      to match.  */
4208   if (lookup_stmt_eh_region (stmt) >= 0)
4209     {
4210       if (!tree_could_throw_p (stmt))
4211         {
4212           error ("statement marked for throw, but doesn%'t");
4213           goto fail;
4214         }
4215       if (!last_in_block && tree_can_throw_internal (stmt))
4216         {
4217           error ("statement marked for throw in middle of block");
4218           goto fail;
4219         }
4220     }
4221
4222   return false;
4223
4224  fail:
4225   debug_generic_stmt (stmt);
4226   return true;
4227 }
4228
4229
4230 /* Return true when the T can be shared.  */
4231
4232 static bool
4233 tree_node_can_be_shared (tree t)
4234 {
4235   if (IS_TYPE_OR_DECL_P (t)
4236       || is_gimple_min_invariant (t)
4237       || TREE_CODE (t) == SSA_NAME
4238       || t == error_mark_node
4239       || TREE_CODE (t) == IDENTIFIER_NODE)
4240     return true;
4241
4242   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4243     return true;
4244
4245   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4246            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4247          || TREE_CODE (t) == COMPONENT_REF
4248          || TREE_CODE (t) == REALPART_EXPR
4249          || TREE_CODE (t) == IMAGPART_EXPR)
4250     t = TREE_OPERAND (t, 0);
4251
4252   if (DECL_P (t))
4253     return true;
4254
4255   return false;
4256 }
4257
4258
4259 /* Called via walk_trees.  Verify tree sharing.  */
4260
4261 static tree
4262 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
4263 {
4264   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4265
4266   if (tree_node_can_be_shared (*tp))
4267     {
4268       *walk_subtrees = false;
4269       return NULL;
4270     }
4271
4272   if (pointer_set_insert (visited, *tp))
4273     return *tp;
4274
4275   return NULL;
4276 }
4277
4278
4279 /* Helper function for verify_gimple_tuples.  */
4280
4281 static tree
4282 verify_gimple_tuples_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
4283                          void *data ATTRIBUTE_UNUSED)
4284 {
4285   switch (TREE_CODE (*tp))
4286     {
4287     case MODIFY_EXPR:
4288       error ("unexpected non-tuple");
4289       debug_tree (*tp);
4290       gcc_unreachable ();
4291       return NULL_TREE;
4292
4293     default:
4294       return NULL_TREE;
4295     }
4296 }
4297
4298 /* Verify that there are no trees that should have been converted to
4299    gimple tuples.  Return true if T contains a node that should have
4300    been converted to a gimple tuple, but hasn't.  */
4301
4302 static bool
4303 verify_gimple_tuples (tree t)
4304 {
4305   return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
4306 }
4307
4308 static bool eh_error_found;
4309 static int
4310 verify_eh_throw_stmt_node (void **slot, void *data)
4311 {
4312   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4313   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4314
4315   if (!pointer_set_contains (visited, node->stmt))
4316     {
4317       error ("Dead STMT in EH table");
4318       debug_generic_stmt (node->stmt);
4319       eh_error_found = true;
4320     }
4321   return 0;
4322 }
4323
4324 /* Verify the GIMPLE statement chain.  */
4325
4326 void
4327 verify_stmts (void)
4328 {
4329   basic_block bb;
4330   block_stmt_iterator bsi;
4331   bool err = false;
4332   struct pointer_set_t *visited, *visited_stmts;
4333   tree addr;
4334
4335   timevar_push (TV_TREE_STMT_VERIFY);
4336   visited = pointer_set_create ();
4337   visited_stmts = pointer_set_create ();
4338
4339   FOR_EACH_BB (bb)
4340     {
4341       tree phi;
4342       int i;
4343
4344       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4345         {
4346           int phi_num_args = PHI_NUM_ARGS (phi);
4347
4348           pointer_set_insert (visited_stmts, phi);
4349           if (bb_for_stmt (phi) != bb)
4350             {
4351               error ("bb_for_stmt (phi) is set to a wrong basic block");
4352               err |= true;
4353             }
4354
4355           for (i = 0; i < phi_num_args; i++)
4356             {
4357               tree t = PHI_ARG_DEF (phi, i);
4358               tree addr;
4359
4360               if (!t)
4361                 {
4362                   error ("missing PHI def");
4363                   debug_generic_stmt (phi);
4364                   err |= true;
4365                   continue;
4366                 }
4367               /* Addressable variables do have SSA_NAMEs but they
4368                  are not considered gimple values.  */
4369               else if (TREE_CODE (t) != SSA_NAME
4370                        && TREE_CODE (t) != FUNCTION_DECL
4371                        && !is_gimple_min_invariant (t))
4372                 {
4373                   error ("PHI def is not a GIMPLE value");
4374                   debug_generic_stmt (phi);
4375                   debug_generic_stmt (t);
4376                   err |= true;
4377                 }
4378
4379               addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4380               if (addr)
4381                 {
4382                   error ("incorrect sharing of tree nodes");
4383                   debug_generic_stmt (phi);
4384                   debug_generic_stmt (addr);
4385                   err |= true;
4386                 }
4387             }
4388         }
4389
4390       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4391         {
4392           tree stmt = bsi_stmt (bsi);
4393
4394           pointer_set_insert (visited_stmts, stmt);
4395           err |= verify_gimple_tuples (stmt);
4396
4397           if (bb_for_stmt (stmt) != bb)
4398             {
4399               error ("bb_for_stmt (stmt) is set to a wrong basic block");
4400               err |= true;
4401             }
4402
4403           bsi_next (&bsi);
4404           err |= verify_stmt (stmt, bsi_end_p (bsi));
4405           addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
4406           if (addr)
4407             {
4408               error ("incorrect sharing of tree nodes");
4409               debug_generic_stmt (stmt);
4410               debug_generic_stmt (addr);
4411               err |= true;
4412             }
4413         }
4414     }
4415   eh_error_found = false;
4416   if (get_eh_throw_stmt_table (cfun))
4417     htab_traverse (get_eh_throw_stmt_table (cfun),
4418                    verify_eh_throw_stmt_node,
4419                    visited_stmts);
4420
4421   if (err | eh_error_found)
4422     internal_error ("verify_stmts failed");
4423
4424   pointer_set_destroy (visited);
4425   pointer_set_destroy (visited_stmts);
4426   verify_histograms ();
4427   timevar_pop (TV_TREE_STMT_VERIFY);
4428 }
4429
4430
4431 /* Verifies that the flow information is OK.  */
4432
4433 static int
4434 tree_verify_flow_info (void)
4435 {
4436   int err = 0;
4437   basic_block bb;
4438   block_stmt_iterator bsi;
4439   tree stmt;
4440   edge e;
4441   edge_iterator ei;
4442
4443   if (ENTRY_BLOCK_PTR->il.tree)
4444     {
4445       error ("ENTRY_BLOCK has IL associated with it");
4446       err = 1;
4447     }
4448
4449   if (EXIT_BLOCK_PTR->il.tree)
4450     {
4451       error ("EXIT_BLOCK has IL associated with it");
4452       err = 1;
4453     }
4454
4455   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4456     if (e->flags & EDGE_FALLTHRU)
4457       {
4458         error ("fallthru to exit from bb %d", e->src->index);
4459         err = 1;
4460       }
4461
4462   FOR_EACH_BB (bb)
4463     {
4464       bool found_ctrl_stmt = false;
4465
4466       stmt = NULL_TREE;
4467
4468       /* Skip labels on the start of basic block.  */
4469       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4470         {
4471           tree prev_stmt = stmt;
4472
4473           stmt = bsi_stmt (bsi);
4474
4475           if (TREE_CODE (stmt) != LABEL_EXPR)
4476             break;
4477
4478           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
4479             {
4480               error ("nonlocal label ");
4481               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4482               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4483                        bb->index);
4484               err = 1;
4485             }
4486
4487           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
4488             {
4489               error ("label ");
4490               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4491               fprintf (stderr, " to block does not match in bb %d",
4492                        bb->index);
4493               err = 1;
4494             }
4495
4496           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
4497               != current_function_decl)
4498             {
4499               error ("label ");
4500               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4501               fprintf (stderr, " has incorrect context in bb %d",
4502                        bb->index);
4503               err = 1;
4504             }
4505         }
4506
4507       /* Verify that body of basic block BB is free of control flow.  */
4508       for (; !bsi_end_p (bsi); bsi_next (&bsi))
4509         {
4510           tree stmt = bsi_stmt (bsi);
4511
4512           if (found_ctrl_stmt)
4513             {
4514               error ("control flow in the middle of basic block %d",
4515                      bb->index);
4516               err = 1;
4517             }
4518
4519           if (stmt_ends_bb_p (stmt))
4520             found_ctrl_stmt = true;
4521
4522           if (TREE_CODE (stmt) == LABEL_EXPR)
4523             {
4524               error ("label ");
4525               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4526               fprintf (stderr, " in the middle of basic block %d", bb->index);
4527               err = 1;
4528             }
4529         }
4530
4531       bsi = bsi_last (bb);
4532       if (bsi_end_p (bsi))
4533         continue;
4534
4535       stmt = bsi_stmt (bsi);
4536
4537       err |= verify_eh_edges (stmt);
4538
4539       if (is_ctrl_stmt (stmt))
4540         {
4541           FOR_EACH_EDGE (e, ei, bb->succs)
4542             if (e->flags & EDGE_FALLTHRU)
4543               {
4544                 error ("fallthru edge after a control statement in bb %d",
4545                        bb->index);
4546                 err = 1;
4547               }
4548         }
4549
4550       if (TREE_CODE (stmt) != COND_EXPR)
4551         {
4552           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4553              after anything else but if statement.  */
4554           FOR_EACH_EDGE (e, ei, bb->succs)
4555             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4556               {
4557                 error ("true/false edge after a non-COND_EXPR in bb %d",
4558                        bb->index);
4559                 err = 1;
4560               }
4561         }
4562
4563       switch (TREE_CODE (stmt))
4564         {
4565         case COND_EXPR:
4566           {
4567             edge true_edge;
4568             edge false_edge;
4569
4570             if (COND_EXPR_THEN (stmt) != NULL_TREE
4571                 || COND_EXPR_ELSE (stmt) != NULL_TREE)
4572               {
4573                 error ("COND_EXPR with code in branches at the end of bb %d",
4574                        bb->index);
4575                 err = 1;
4576               }
4577
4578             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4579
4580             if (!true_edge || !false_edge
4581                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4582                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4583                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4584                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4585                 || EDGE_COUNT (bb->succs) >= 3)
4586               {
4587                 error ("wrong outgoing edge flags at end of bb %d",
4588                        bb->index);
4589                 err = 1;
4590               }
4591           }
4592           break;
4593
4594         case GOTO_EXPR:
4595           if (simple_goto_p (stmt))
4596             {
4597               error ("explicit goto at end of bb %d", bb->index);
4598               err = 1;
4599             }
4600           else
4601             {
4602               /* FIXME.  We should double check that the labels in the
4603                  destination blocks have their address taken.  */
4604               FOR_EACH_EDGE (e, ei, bb->succs)
4605                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4606                                  | EDGE_FALSE_VALUE))
4607                     || !(e->flags & EDGE_ABNORMAL))
4608                   {
4609                     error ("wrong outgoing edge flags at end of bb %d",
4610                            bb->index);
4611                     err = 1;
4612                   }
4613             }
4614           break;
4615
4616         case RETURN_EXPR:
4617           if (!single_succ_p (bb)
4618               || (single_succ_edge (bb)->flags
4619                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4620                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4621             {
4622               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4623               err = 1;
4624             }
4625           if (single_succ (bb) != EXIT_BLOCK_PTR)
4626             {
4627               error ("return edge does not point to exit in bb %d",
4628                      bb->index);
4629               err = 1;
4630             }
4631           break;
4632
4633         case SWITCH_EXPR:
4634           {
4635             tree prev;
4636             edge e;
4637             size_t i, n;
4638             tree vec;
4639
4640             vec = SWITCH_LABELS (stmt);
4641             n = TREE_VEC_LENGTH (vec);
4642
4643             /* Mark all the destination basic blocks.  */
4644             for (i = 0; i < n; ++i)
4645               {
4646                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4647                 basic_block label_bb = label_to_block (lab);
4648
4649                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4650                 label_bb->aux = (void *)1;
4651               }
4652
4653             /* Verify that the case labels are sorted.  */
4654             prev = TREE_VEC_ELT (vec, 0);
4655             for (i = 1; i < n; ++i)
4656               {
4657                 tree c = TREE_VEC_ELT (vec, i);
4658                 if (! CASE_LOW (c))
4659                   {
4660                     if (i != n - 1)
4661                       {
4662                         error ("found default case not at end of case vector");
4663                         err = 1;
4664                       }
4665                     continue;
4666                   }
4667                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4668                   {
4669                     error ("case labels not sorted: ");
4670                     print_generic_expr (stderr, prev, 0);
4671                     fprintf (stderr," is greater than ");
4672                     print_generic_expr (stderr, c, 0);
4673                     fprintf (stderr," but comes before it.\n");
4674                     err = 1;
4675                   }
4676                 prev = c;
4677               }
4678             /* VRP will remove the default case if it can prove it will
4679                never be executed.  So do not verify there always exists
4680                a default case here.  */
4681
4682             FOR_EACH_EDGE (e, ei, bb->succs)
4683               {
4684                 if (!e->dest->aux)
4685                   {
4686                     error ("extra outgoing edge %d->%d",
4687                            bb->index, e->dest->index);
4688                     err = 1;
4689                   }
4690                 e->dest->aux = (void *)2;
4691                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4692                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4693                   {
4694                     error ("wrong outgoing edge flags at end of bb %d",
4695                            bb->index);
4696                     err = 1;
4697                   }
4698               }
4699
4700             /* Check that we have all of them.  */
4701             for (i = 0; i < n; ++i)
4702               {
4703                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4704                 basic_block label_bb = label_to_block (lab);
4705
4706                 if (label_bb->aux != (void *)2)
4707                   {
4708                     error ("missing edge %i->%i",
4709                            bb->index, label_bb->index);
4710                     err = 1;
4711                   }
4712               }
4713
4714             FOR_EACH_EDGE (e, ei, bb->succs)
4715               e->dest->aux = (void *)0;
4716           }
4717
4718         default: ;
4719         }
4720     }
4721
4722   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4723     verify_dominators (CDI_DOMINATORS);
4724
4725   return err;
4726 }
4727
4728
4729 /* Updates phi nodes after creating a forwarder block joined
4730    by edge FALLTHRU.  */
4731
4732 static void
4733 tree_make_forwarder_block (edge fallthru)
4734 {
4735   edge e;
4736   edge_iterator ei;
4737   basic_block dummy, bb;
4738   tree phi, new_phi, var;
4739
4740   dummy = fallthru->src;
4741   bb = fallthru->dest;
4742
4743   if (single_pred_p (bb))
4744     return;
4745
4746   /* If we redirected a branch we must create new PHI nodes at the
4747      start of BB.  */
4748   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
4749     {
4750       var = PHI_RESULT (phi);
4751       new_phi = create_phi_node (var, bb);
4752       SSA_NAME_DEF_STMT (var) = new_phi;
4753       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4754       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
4755     }
4756
4757   /* Ensure that the PHI node chain is in the same order.  */
4758   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
4759
4760   /* Add the arguments we have stored on edges.  */
4761   FOR_EACH_EDGE (e, ei, bb->preds)
4762     {
4763       if (e == fallthru)
4764         continue;
4765
4766       flush_pending_stmts (e);
4767     }
4768 }
4769
4770
4771 /* Return a non-special label in the head of basic block BLOCK.
4772    Create one if it doesn't exist.  */
4773
4774 tree
4775 tree_block_label (basic_block bb)
4776 {
4777   block_stmt_iterator i, s = bsi_start (bb);
4778   bool first = true;
4779   tree label, stmt;
4780
4781   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4782     {
4783       stmt = bsi_stmt (i);
4784       if (TREE_CODE (stmt) != LABEL_EXPR)
4785         break;
4786       label = LABEL_EXPR_LABEL (stmt);
4787       if (!DECL_NONLOCAL (label))
4788         {
4789           if (!first)
4790             bsi_move_before (&i, &s);
4791           return label;
4792         }
4793     }
4794
4795   label = create_artificial_label ();
4796   stmt = build1 (LABEL_EXPR, void_type_node, label);
4797   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4798   return label;
4799 }
4800
4801
4802 /* Attempt to perform edge redirection by replacing a possibly complex
4803    jump instruction by a goto or by removing the jump completely.
4804    This can apply only if all edges now point to the same block.  The
4805    parameters and return values are equivalent to
4806    redirect_edge_and_branch.  */
4807
4808 static edge
4809 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4810 {
4811   basic_block src = e->src;
4812   block_stmt_iterator b;
4813   tree stmt;
4814
4815   /* We can replace or remove a complex jump only when we have exactly
4816      two edges.  */
4817   if (EDGE_COUNT (src->succs) != 2
4818       /* Verify that all targets will be TARGET.  Specifically, the
4819          edge that is not E must also go to TARGET.  */
4820       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4821     return NULL;
4822
4823   b = bsi_last (src);
4824   if (bsi_end_p (b))
4825     return NULL;
4826   stmt = bsi_stmt (b);
4827
4828   if (TREE_CODE (stmt) == COND_EXPR
4829       || TREE_CODE (stmt) == SWITCH_EXPR)
4830     {
4831       bsi_remove (&b, true);
4832       e = ssa_redirect_edge (e, target);
4833       e->flags = EDGE_FALLTHRU;
4834       return e;
4835     }
4836
4837   return NULL;
4838 }
4839
4840
4841 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4842    edge representing the redirected branch.  */
4843
4844 static edge
4845 tree_redirect_edge_and_branch (edge e, basic_block dest)
4846 {
4847   basic_block bb = e->src;
4848   block_stmt_iterator bsi;
4849   edge ret;
4850   tree stmt;
4851
4852   if (e->flags & EDGE_ABNORMAL)
4853     return NULL;
4854
4855   if (e->src != ENTRY_BLOCK_PTR
4856       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4857     return ret;
4858
4859   if (e->dest == dest)
4860     return NULL;
4861
4862   bsi = bsi_last (bb);
4863   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4864
4865   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4866     {
4867     case COND_EXPR:
4868       /* For COND_EXPR, we only need to redirect the edge.  */
4869       break;
4870
4871     case GOTO_EXPR:
4872       /* No non-abnormal edges should lead from a non-simple goto, and
4873          simple ones should be represented implicitly.  */
4874       gcc_unreachable ();
4875
4876     case SWITCH_EXPR:
4877       {
4878         tree cases = get_cases_for_edge (e, stmt);
4879         tree label = tree_block_label (dest);
4880
4881         /* If we have a list of cases associated with E, then use it
4882            as it's a lot faster than walking the entire case vector.  */
4883         if (cases)
4884           {
4885             edge e2 = find_edge (e->src, dest);
4886             tree last, first;
4887
4888             first = cases;
4889             while (cases)
4890               {
4891                 last = cases;
4892                 CASE_LABEL (cases) = label;
4893                 cases = TREE_CHAIN (cases);
4894               }
4895
4896             /* If there was already an edge in the CFG, then we need
4897                to move all the cases associated with E to E2.  */
4898             if (e2)
4899               {
4900                 tree cases2 = get_cases_for_edge (e2, stmt);
4901
4902                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4903                 TREE_CHAIN (cases2) = first;
4904               }
4905           }
4906         else
4907           {
4908             tree vec = SWITCH_LABELS (stmt);
4909             size_t i, n = TREE_VEC_LENGTH (vec);
4910
4911             for (i = 0; i < n; i++)
4912               {
4913                 tree elt = TREE_VEC_ELT (vec, i);
4914
4915                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4916                   CASE_LABEL (elt) = label;
4917               }
4918           }
4919
4920         break;
4921       }
4922
4923     case RETURN_EXPR:
4924       bsi_remove (&bsi, true);
4925       e->flags |= EDGE_FALLTHRU;
4926       break;
4927
4928     case OMP_RETURN:
4929     case OMP_CONTINUE:
4930     case OMP_SECTIONS_SWITCH:
4931     case OMP_FOR:
4932       /* The edges from OMP constructs can be simply redirected.  */
4933       break;
4934
4935     default:
4936       /* Otherwise it must be a fallthru edge, and we don't need to
4937          do anything besides redirecting it.  */
4938       gcc_assert (e->flags & EDGE_FALLTHRU);
4939       break;
4940     }
4941
4942   /* Update/insert PHI nodes as necessary.  */
4943
4944   /* Now update the edges in the CFG.  */
4945   e = ssa_redirect_edge (e, dest);
4946
4947   return e;
4948 }
4949
4950 /* Returns true if it is possible to remove edge E by redirecting
4951    it to the destination of the other edge from E->src.  */
4952
4953 static bool
4954 tree_can_remove_branch_p (const_edge e)
4955 {
4956   if (e->flags & EDGE_ABNORMAL)
4957     return false;
4958
4959   return true;
4960 }
4961
4962 /* Simple wrapper, as we can always redirect fallthru edges.  */
4963
4964 static basic_block
4965 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4966 {
4967   e = tree_redirect_edge_and_branch (e, dest);
4968   gcc_assert (e);
4969
4970   return NULL;
4971 }
4972
4973
4974 /* Splits basic block BB after statement STMT (but at least after the
4975    labels).  If STMT is NULL, BB is split just after the labels.  */
4976
4977 static basic_block
4978 tree_split_block (basic_block bb, void *stmt)
4979 {
4980   block_stmt_iterator bsi;
4981   tree_stmt_iterator tsi_tgt;
4982   tree act, list;
4983   basic_block new_bb;
4984   edge e;
4985   edge_iterator ei;
4986
4987   new_bb = create_empty_bb (bb);
4988
4989   /* Redirect the outgoing edges.  */
4990   new_bb->succs = bb->succs;
4991   bb->succs = NULL;
4992   FOR_EACH_EDGE (e, ei, new_bb->succs)
4993     e->src = new_bb;
4994
4995   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4996     stmt = NULL;
4997
4998   /* Move everything from BSI to the new basic block.  */
4999   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5000     {
5001       act = bsi_stmt (bsi);
5002       if (TREE_CODE (act) == LABEL_EXPR)
5003         continue;
5004
5005       if (!stmt)
5006         break;
5007
5008       if (stmt == act)
5009         {
5010           bsi_next (&bsi);
5011           break;
5012         }
5013     }
5014
5015   if (bsi_end_p (bsi))
5016     return new_bb;
5017
5018   /* Split the statement list - avoid re-creating new containers as this
5019      brings ugly quadratic memory consumption in the inliner.
5020      (We are still quadratic since we need to update stmt BB pointers,
5021      sadly.)  */
5022   list = tsi_split_statement_list_before (&bsi.tsi);
5023   set_bb_stmt_list (new_bb, list);
5024   for (tsi_tgt = tsi_start (list);
5025        !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
5026     change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
5027
5028   return new_bb;
5029 }
5030
5031
5032 /* Moves basic block BB after block AFTER.  */
5033
5034 static bool
5035 tree_move_block_after (basic_block bb, basic_block after)
5036 {
5037   if (bb->prev_bb == after)
5038     return true;
5039
5040   unlink_block (bb);
5041   link_block (bb, after);
5042
5043   return true;
5044 }
5045
5046
5047 /* Return true if basic_block can be duplicated.  */
5048
5049 static bool
5050 tree_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5051 {
5052   return true;
5053 }
5054
5055
5056 /* Create a duplicate of the basic block BB.  NOTE: This does not
5057    preserve SSA form.  */
5058
5059 static basic_block
5060 tree_duplicate_bb (basic_block bb)
5061 {
5062   basic_block new_bb;
5063   block_stmt_iterator bsi, bsi_tgt;
5064   tree phi;
5065
5066   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5067
5068   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5069      the incoming edges have not been setup yet.  */
5070   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5071     {
5072       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
5073       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
5074     }
5075
5076   /* Keep the chain of PHI nodes in the same order so that they can be
5077      updated by ssa_redirect_edge.  */
5078   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
5079
5080   bsi_tgt = bsi_start (new_bb);
5081   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5082     {
5083       def_operand_p def_p;
5084       ssa_op_iter op_iter;
5085       tree stmt, copy;
5086       int region;
5087
5088       stmt = bsi_stmt (bsi);
5089       if (TREE_CODE (stmt) == LABEL_EXPR)
5090         continue;
5091
5092       /* Create a new copy of STMT and duplicate STMT's virtual
5093          operands.  */
5094       copy = unshare_expr (stmt);
5095       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
5096       copy_virtual_operands (copy, stmt);
5097       region = lookup_stmt_eh_region (stmt);
5098       if (region >= 0)
5099         add_stmt_to_eh_region (copy, region);
5100       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5101
5102       /* Create new names for all the definitions created by COPY and
5103          add replacement mappings for each new name.  */
5104       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5105         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5106     }
5107
5108   return new_bb;
5109 }
5110
5111 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5112
5113 static void
5114 add_phi_args_after_copy_edge (edge e_copy)
5115 {
5116   basic_block bb, bb_copy = e_copy->src, dest;
5117   edge e;
5118   edge_iterator ei;
5119   tree phi, phi_copy, phi_next, def;
5120
5121   if (!phi_nodes (e_copy->dest))
5122     return;
5123
5124   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5125
5126   if (e_copy->dest->flags & BB_DUPLICATED)
5127     dest = get_bb_original (e_copy->dest);
5128   else
5129     dest = e_copy->dest;
5130
5131   e = find_edge (bb, dest);
5132   if (!e)
5133     {
5134       /* During loop unrolling the target of the latch edge is copied.
5135          In this case we are not looking for edge to dest, but to
5136          duplicated block whose original was dest.  */
5137       FOR_EACH_EDGE (e, ei, bb->succs)
5138         {
5139           if ((e->dest->flags & BB_DUPLICATED)
5140               && get_bb_original (e->dest) == dest)
5141             break;
5142         }
5143
5144       gcc_assert (e != NULL);
5145     }
5146
5147   for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
5148        phi;
5149        phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
5150     {
5151       phi_next = PHI_CHAIN (phi);
5152       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5153       add_phi_arg (phi_copy, def, e_copy);
5154     }
5155 }
5156
5157
5158 /* Basic block BB_COPY was created by code duplication.  Add phi node
5159    arguments for edges going out of BB_COPY.  The blocks that were
5160    duplicated have BB_DUPLICATED set.  */
5161
5162 void
5163 add_phi_args_after_copy_bb (basic_block bb_copy)
5164 {
5165   edge_iterator ei;
5166   edge e_copy;
5167
5168   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5169     {
5170       add_phi_args_after_copy_edge (e_copy);
5171     }
5172 }
5173
5174 /* Blocks in REGION_COPY array of length N_REGION were created by
5175    duplication of basic blocks.  Add phi node arguments for edges
5176    going from these blocks.  If E_COPY is not NULL, also add
5177    phi node arguments for its destination.*/
5178
5179 void
5180 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5181                          edge e_copy)
5182 {
5183   unsigned i;
5184
5185   for (i = 0; i < n_region; i++)
5186     region_copy[i]->flags |= BB_DUPLICATED;
5187
5188   for (i = 0; i < n_region; i++)
5189     add_phi_args_after_copy_bb (region_copy[i]);
5190   if (e_copy)
5191     add_phi_args_after_copy_edge (e_copy);
5192
5193   for (i = 0; i < n_region; i++)
5194     region_copy[i]->flags &= ~BB_DUPLICATED;
5195 }
5196
5197 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5198    important exit edge EXIT.  By important we mean that no SSA name defined
5199    inside region is live over the other exit edges of the region.  All entry
5200    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5201    to the duplicate of the region.  SSA form, dominance and loop information
5202    is updated.  The new basic blocks are stored to REGION_COPY in the same
5203    order as they had in REGION, provided that REGION_COPY is not NULL.
5204    The function returns false if it is unable to copy the region,
5205    true otherwise.  */
5206
5207 bool
5208 tree_duplicate_sese_region (edge entry, edge exit,
5209                             basic_block *region, unsigned n_region,
5210                             basic_block *region_copy)
5211 {
5212   unsigned i;
5213   bool free_region_copy = false, copying_header = false;
5214   struct loop *loop = entry->dest->loop_father;
5215   edge exit_copy;
5216   VEC (basic_block, heap) *doms;
5217   edge redirected;
5218   int total_freq = 0, entry_freq = 0;
5219   gcov_type total_count = 0, entry_count = 0;
5220
5221   if (!can_copy_bbs_p (region, n_region))
5222     return false;
5223
5224   /* Some sanity checking.  Note that we do not check for all possible
5225      missuses of the functions.  I.e. if you ask to copy something weird,
5226      it will work, but the state of structures probably will not be
5227      correct.  */
5228   for (i = 0; i < n_region; i++)
5229     {
5230       /* We do not handle subloops, i.e. all the blocks must belong to the
5231          same loop.  */
5232       if (region[i]->loop_father != loop)
5233         return false;
5234
5235       if (region[i] != entry->dest
5236           && region[i] == loop->header)
5237         return false;
5238     }
5239
5240   set_loop_copy (loop, loop);
5241
5242   /* In case the function is used for loop header copying (which is the primary
5243      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5244   if (loop->header == entry->dest)
5245     {
5246       copying_header = true;
5247       set_loop_copy (loop, loop_outer (loop));
5248
5249       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5250         return false;
5251
5252       for (i = 0; i < n_region; i++)
5253         if (region[i] != exit->src
5254             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5255           return false;
5256     }
5257
5258   if (!region_copy)
5259     {
5260       region_copy = XNEWVEC (basic_block, n_region);
5261       free_region_copy = true;
5262     }
5263
5264   gcc_assert (!need_ssa_update_p ());
5265
5266   /* Record blocks outside the region that are dominated by something
5267      inside.  */
5268   doms = NULL;
5269   initialize_original_copy_tables ();
5270
5271   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5272
5273   if (entry->dest->count)
5274     {
5275       total_count = entry->dest->count;
5276       entry_count = entry->count;
5277       /* Fix up corner cases, to avoid division by zero or creation of negative
5278          frequencies.  */
5279       if (entry_count > total_count)
5280         entry_count = total_count;
5281     }
5282   else
5283     {
5284       total_freq = entry->dest->frequency;
5285       entry_freq = EDGE_FREQUENCY (entry);
5286       /* Fix up corner cases, to avoid division by zero or creation of negative
5287          frequencies.  */
5288       if (total_freq == 0)
5289         total_freq = 1;
5290       else if (entry_freq > total_freq)
5291         entry_freq = total_freq;
5292     }
5293
5294   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5295             split_edge_bb_loc (entry));
5296   if (total_count)
5297     {
5298       scale_bbs_frequencies_gcov_type (region, n_region,
5299                                        total_count - entry_count,
5300                                        total_count);
5301       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5302                                        total_count);
5303     }
5304   else
5305     {
5306       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5307                                  total_freq);
5308       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5309     }
5310
5311   if (copying_header)
5312     {
5313       loop->header = exit->dest;
5314       loop->latch = exit->src;
5315     }
5316
5317   /* Redirect the entry and add the phi node arguments.  */
5318   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5319   gcc_assert (redirected != NULL);
5320   flush_pending_stmts (entry);
5321
5322   /* Concerning updating of dominators:  We must recount dominators
5323      for entry block and its copy.  Anything that is outside of the
5324      region, but was dominated by something inside needs recounting as
5325      well.  */
5326   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5327   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5328   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5329   VEC_free (basic_block, heap, doms);
5330
5331   /* Add the other PHI node arguments.  */
5332   add_phi_args_after_copy (region_copy, n_region, NULL);
5333
5334   /* Update the SSA web.  */
5335   update_ssa (TODO_update_ssa);
5336
5337   if (free_region_copy)
5338     free (region_copy);
5339
5340   free_original_copy_tables ();
5341   return true;
5342 }
5343
5344 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5345    are stored to REGION_COPY in the same order in that they appear
5346    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5347    the region, EXIT an exit from it.  The condition guarding EXIT
5348    is moved to ENTRY.  Returns true if duplication succeeds, false
5349    otherwise.
5350
5351    For example,
5352
5353    some_code;
5354    if (cond)
5355      A;
5356    else
5357      B;
5358
5359    is transformed to
5360
5361    if (cond)
5362      {
5363        some_code;
5364        A;
5365      }
5366    else
5367      {
5368        some_code;
5369        B;
5370      }
5371 */
5372
5373 bool
5374 tree_duplicate_sese_tail (edge entry, edge exit,
5375                           basic_block *region, unsigned n_region,
5376                           basic_block *region_copy)
5377 {
5378   unsigned i;
5379   bool free_region_copy = false;
5380   struct loop *loop = exit->dest->loop_father;
5381   struct loop *orig_loop = entry->dest->loop_father;
5382   basic_block switch_bb, entry_bb, nentry_bb;
5383   VEC (basic_block, heap) *doms;
5384   int total_freq = 0, exit_freq = 0;
5385   gcov_type total_count = 0, exit_count = 0;
5386   edge exits[2], nexits[2], e;
5387   block_stmt_iterator bsi;
5388   tree cond;
5389   edge sorig, snew;
5390
5391   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5392   exits[0] = exit;
5393   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5394
5395   if (!can_copy_bbs_p (region, n_region))
5396     return false;
5397
5398   /* Some sanity checking.  Note that we do not check for all possible
5399      missuses of the functions.  I.e. if you ask to copy something weird
5400      (e.g., in the example, if there is a jump from inside to the middle
5401      of some_code, or come_code defines some of the values used in cond)
5402      it will work, but the resulting code will not be correct.  */
5403   for (i = 0; i < n_region; i++)
5404     {
5405       /* We do not handle subloops, i.e. all the blocks must belong to the
5406          same loop.  */
5407       if (region[i]->loop_father != orig_loop)
5408         return false;
5409
5410       if (region[i] == orig_loop->latch)
5411         return false;
5412     }
5413
5414   initialize_original_copy_tables ();
5415   set_loop_copy (orig_loop, loop);
5416
5417   if (!region_copy)
5418     {
5419       region_copy = XNEWVEC (basic_block, n_region);
5420       free_region_copy = true;
5421     }
5422
5423   gcc_assert (!need_ssa_update_p ());
5424
5425   /* Record blocks outside the region that are dominated by something
5426      inside.  */
5427   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5428
5429   if (exit->src->count)
5430     {
5431       total_count = exit->src->count;
5432       exit_count = exit->count;
5433       /* Fix up corner cases, to avoid division by zero or creation of negative
5434          frequencies.  */
5435       if (exit_count > total_count)
5436         exit_count = total_count;
5437     }
5438   else
5439     {
5440       total_freq = exit->src->frequency;
5441       exit_freq = EDGE_FREQUENCY (exit);
5442       /* Fix up corner cases, to avoid division by zero or creation of negative
5443          frequencies.  */
5444       if (total_freq == 0)
5445         total_freq = 1;
5446       if (exit_freq > total_freq)
5447         exit_freq = total_freq;
5448     }
5449
5450   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5451             split_edge_bb_loc (exit));
5452   if (total_count)
5453     {
5454       scale_bbs_frequencies_gcov_type (region, n_region,
5455                                        total_count - exit_count,
5456                                        total_count);
5457       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5458                                        total_count);
5459     }
5460   else
5461     {
5462       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5463                                  total_freq);
5464       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5465     }
5466
5467   /* Create the switch block, and put the exit condition to it.  */
5468   entry_bb = entry->dest;
5469   nentry_bb = get_bb_copy (entry_bb);
5470   if (!last_stmt (entry->src)
5471       || !stmt_ends_bb_p (last_stmt (entry->src)))
5472     switch_bb = entry->src;
5473   else
5474     switch_bb = split_edge (entry);
5475   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5476
5477   bsi = bsi_last (switch_bb);
5478   cond = last_stmt (exit->src);
5479   gcc_assert (TREE_CODE (cond) == COND_EXPR);
5480   bsi_insert_after (&bsi, unshare_expr (cond), BSI_NEW_STMT);
5481
5482   sorig = single_succ_edge (switch_bb);
5483   sorig->flags = exits[1]->flags;
5484   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5485
5486   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5487   rescan_loop_exit (snew, true, false);
5488
5489   /* Add the PHI node arguments.  */
5490   add_phi_args_after_copy (region_copy, n_region, snew);
5491
5492   /* Get rid of now superfluous conditions and associated edges (and phi node
5493      arguments).  */
5494   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5495   PENDING_STMT (e) = NULL_TREE;
5496   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5497   PENDING_STMT (e) = NULL_TREE;
5498
5499   /* Anything that is outside of the region, but was dominated by something
5500      inside needs to update dominance info.  */
5501   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5502   VEC_free (basic_block, heap, doms);
5503
5504   /* Update the SSA web.  */
5505   update_ssa (TODO_update_ssa);
5506
5507   if (free_region_copy)
5508     free (region_copy);
5509
5510   free_original_copy_tables ();
5511   return true;
5512 }
5513
5514 /*
5515 DEF_VEC_P(basic_block);
5516 DEF_VEC_ALLOC_P(basic_block,heap);
5517 */
5518
5519 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5520    adding blocks when the dominator traversal reaches EXIT.  This
5521    function silently assumes that ENTRY strictly dominates EXIT.  */
5522
5523 void
5524 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5525                               VEC(basic_block,heap) **bbs_p)
5526 {
5527   basic_block son;
5528
5529   for (son = first_dom_son (CDI_DOMINATORS, entry);
5530        son;
5531        son = next_dom_son (CDI_DOMINATORS, son))
5532     {
5533       VEC_safe_push (basic_block, heap, *bbs_p, son);
5534       if (son != exit)
5535         gather_blocks_in_sese_region (son, exit, bbs_p);
5536     }
5537 }
5538
5539 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5540    The duplicates are recorded in VARS_MAP.  */
5541
5542 static void
5543 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5544                            tree to_context)
5545 {
5546   tree t = *tp, new_t;
5547   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5548   void **loc;
5549
5550   if (DECL_CONTEXT (t) == to_context)
5551     return;
5552
5553   loc = pointer_map_contains (vars_map, t);
5554
5555   if (!loc)
5556     {
5557       loc = pointer_map_insert (vars_map, t);
5558
5559       if (SSA_VAR_P (t))
5560         {
5561           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5562           f->local_decls = tree_cons (NULL_TREE, new_t, f->local_decls);
5563         }
5564       else
5565         {
5566           gcc_assert (TREE_CODE (t) == CONST_DECL);
5567           new_t = copy_node (t);
5568         }
5569       DECL_CONTEXT (new_t) = to_context;
5570
5571       *loc = new_t;
5572     }
5573   else
5574     new_t = *loc;
5575
5576   *tp = new_t;
5577 }
5578
5579 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5580    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5581
5582 static tree
5583 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5584                   tree to_context)
5585 {
5586   void **loc;
5587   tree new_name, decl = SSA_NAME_VAR (name);
5588
5589   gcc_assert (is_gimple_reg (name));
5590
5591   loc = pointer_map_contains (vars_map, name);
5592
5593   if (!loc)
5594     {
5595       replace_by_duplicate_decl (&decl, vars_map, to_context);
5596
5597       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5598       if (gimple_in_ssa_p (cfun))
5599         add_referenced_var (decl);
5600
5601       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5602       if (SSA_NAME_IS_DEFAULT_DEF (name))
5603         set_default_def (decl, new_name);
5604       pop_cfun ();
5605
5606       loc = pointer_map_insert (vars_map, name);
5607       *loc = new_name;
5608     }
5609   else
5610     new_name = *loc;
5611
5612   return new_name;
5613 }
5614
5615 struct move_stmt_d
5616 {
5617   tree block;
5618   tree from_context;
5619   tree to_context;
5620   struct pointer_map_t *vars_map;
5621   htab_t new_label_map;
5622   bool remap_decls_p;
5623 };
5624
5625 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5626    contained in *TP and change the DECL_CONTEXT of every local
5627    variable referenced in *TP.  */
5628
5629 static tree
5630 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
5631 {
5632   struct move_stmt_d *p = (struct move_stmt_d *) data;
5633   tree t = *tp;
5634
5635   if (p->block
5636       && (EXPR_P (t) || GIMPLE_STMT_P (t)))
5637     TREE_BLOCK (t) = p->block;
5638
5639   if (OMP_DIRECTIVE_P (t)
5640       && TREE_CODE (t) != OMP_RETURN
5641       && TREE_CODE (t) != OMP_CONTINUE)
5642     {
5643       /* Do not remap variables inside OMP directives.  Variables
5644          referenced in clauses and directive header belong to the
5645          parent function and should not be moved into the child
5646          function.  */
5647       bool save_remap_decls_p = p->remap_decls_p;
5648       p->remap_decls_p = false;
5649       *walk_subtrees = 0;
5650
5651       walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
5652
5653       p->remap_decls_p = save_remap_decls_p;
5654     }
5655   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5656     {
5657       if (TREE_CODE (t) == SSA_NAME)
5658         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5659       else if (TREE_CODE (t) == LABEL_DECL)
5660         {
5661           if (p->new_label_map)
5662             {
5663               struct tree_map in, *out;
5664               in.base.from = t;
5665               out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5666               if (out)
5667                 *tp = t = out->to;
5668             }
5669
5670           DECL_CONTEXT (t) = p->to_context;
5671         }
5672       else if (p->remap_decls_p)
5673         {
5674           /* Replace T with its duplicate.  T should no longer appear in the
5675              parent function, so this looks wasteful; however, it may appear
5676              in referenced_vars, and more importantly, as virtual operands of
5677              statements, and in alias lists of other variables.  It would be
5678              quite difficult to expunge it from all those places.  ??? It might
5679              suffice to do this for addressable variables.  */
5680           if ((TREE_CODE (t) == VAR_DECL
5681                && !is_global_var (t))
5682               || TREE_CODE (t) == CONST_DECL)
5683             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5684
5685           if (SSA_VAR_P (t)
5686               && gimple_in_ssa_p (cfun))
5687             {
5688               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5689               add_referenced_var (*tp);
5690               pop_cfun ();
5691             }
5692         }
5693       *walk_subtrees = 0;
5694     }
5695   else if (TYPE_P (t))
5696     *walk_subtrees = 0;
5697
5698   return NULL_TREE;
5699 }
5700
5701 /* Marks virtual operands of all statements in basic blocks BBS for
5702    renaming.  */
5703
5704 void
5705 mark_virtual_ops_in_bb (basic_block bb)
5706 {
5707   tree phi;
5708   block_stmt_iterator bsi;
5709
5710   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5711     mark_virtual_ops_for_renaming (phi);
5712
5713   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5714     mark_virtual_ops_for_renaming (bsi_stmt (bsi));
5715 }
5716
5717 /* Marks virtual operands of all statements in basic blocks BBS for
5718    renaming.  */
5719
5720 static void
5721 mark_virtual_ops_in_region (VEC (basic_block,heap) *bbs)
5722 {
5723   basic_block bb;
5724   unsigned i;
5725
5726   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5727     mark_virtual_ops_in_bb (bb);
5728 }
5729
5730 /* Move basic block BB from function CFUN to function DEST_FN.  The
5731    block is moved out of the original linked list and placed after
5732    block AFTER in the new list.  Also, the block is removed from the
5733    original array of blocks and placed in DEST_FN's array of blocks.
5734    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5735    updated to reflect the moved edges.
5736
5737    The local variables are remapped to new instances, VARS_MAP is used
5738    to record the mapping.  */
5739
5740 static void
5741 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5742                   basic_block after, bool update_edge_count_p,
5743                   struct pointer_map_t *vars_map, htab_t new_label_map,
5744                   int eh_offset)
5745 {
5746   struct control_flow_graph *cfg;
5747   edge_iterator ei;
5748   edge e;
5749   block_stmt_iterator si;
5750   struct move_stmt_d d;
5751   unsigned old_len, new_len;
5752   tree phi, next_phi;
5753
5754   /* Remove BB from dominance structures.  */
5755   delete_from_dominance_info (CDI_DOMINATORS, bb);
5756   if (current_loops)
5757     remove_bb_from_loops (bb);
5758
5759   /* Link BB to the new linked list.  */
5760   move_block_after (bb, after);
5761
5762   /* Update the edge count in the corresponding flowgraphs.  */
5763   if (update_edge_count_p)
5764     FOR_EACH_EDGE (e, ei, bb->succs)
5765       {
5766         cfun->cfg->x_n_edges--;
5767         dest_cfun->cfg->x_n_edges++;
5768       }
5769
5770   /* Remove BB from the original basic block array.  */
5771   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5772   cfun->cfg->x_n_basic_blocks--;
5773
5774   /* Grow DEST_CFUN's basic block array if needed.  */
5775   cfg = dest_cfun->cfg;
5776   cfg->x_n_basic_blocks++;
5777   if (bb->index >= cfg->x_last_basic_block)
5778     cfg->x_last_basic_block = bb->index + 1;
5779
5780   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5781   if ((unsigned) cfg->x_last_basic_block >= old_len)
5782     {
5783       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5784       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5785                              new_len);
5786     }
5787
5788   VEC_replace (basic_block, cfg->x_basic_block_info,
5789                bb->index, bb);
5790
5791   /* Remap the variables in phi nodes.  */
5792   for (phi = phi_nodes (bb); phi; phi = next_phi)
5793     {
5794       use_operand_p use;
5795       tree op = PHI_RESULT (phi);
5796       ssa_op_iter oi;
5797
5798       next_phi = PHI_CHAIN (phi);
5799       if (!is_gimple_reg (op))
5800         {
5801           /* Remove the phi nodes for virtual operands (alias analysis will be
5802              run for the new function, anyway).  */
5803           remove_phi_node (phi, NULL, true);
5804           continue;
5805         }
5806
5807       SET_PHI_RESULT (phi, replace_ssa_name (op, vars_map, dest_cfun->decl));
5808       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5809         {
5810           op = USE_FROM_PTR (use);
5811           if (TREE_CODE (op) == SSA_NAME)
5812             SET_USE (use, replace_ssa_name (op, vars_map, dest_cfun->decl));
5813         }
5814     }
5815
5816   /* The statements in BB need to be associated with a new TREE_BLOCK.
5817      Labels need to be associated with a new label-to-block map.  */
5818   memset (&d, 0, sizeof (d));
5819   d.vars_map = vars_map;
5820   d.from_context = cfun->decl;
5821   d.to_context = dest_cfun->decl;
5822   d.new_label_map = new_label_map;
5823
5824   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5825     {
5826       tree stmt = bsi_stmt (si);
5827       int region;
5828
5829       d.remap_decls_p = true;
5830       if (TREE_BLOCK (stmt))
5831         d.block = DECL_INITIAL (dest_cfun->decl);
5832
5833       walk_tree (&stmt, move_stmt_r, &d, NULL);
5834
5835       if (TREE_CODE (stmt) == LABEL_EXPR)
5836         {
5837           tree label = LABEL_EXPR_LABEL (stmt);
5838           int uid = LABEL_DECL_UID (label);
5839
5840           gcc_assert (uid > -1);
5841
5842           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5843           if (old_len <= (unsigned) uid)
5844             {
5845               new_len = 3 * uid / 2;
5846               VEC_safe_grow_cleared (basic_block, gc,
5847                                      cfg->x_label_to_block_map, new_len);
5848             }
5849
5850           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5851           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5852
5853           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5854
5855           if (uid >= dest_cfun->cfg->last_label_uid)
5856             dest_cfun->cfg->last_label_uid = uid + 1;
5857         }
5858       else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
5859         TREE_OPERAND (stmt, 0) =
5860           build_int_cst (NULL_TREE,
5861                          TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
5862                          + eh_offset);
5863
5864       region = lookup_stmt_eh_region (stmt);
5865       if (region >= 0)
5866         {
5867           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5868           remove_stmt_from_eh_region (stmt);
5869           gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5870           gimple_remove_stmt_histograms (cfun, stmt);
5871         }
5872
5873       /* We cannot leave any operands allocated from the operand caches of
5874          the current function.  */
5875       free_stmt_operands (stmt);
5876       push_cfun (dest_cfun);
5877       update_stmt (stmt);
5878       pop_cfun ();
5879     }
5880 }
5881
5882 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5883    the outermost EH region.  Use REGION as the incoming base EH region.  */
5884
5885 static int
5886 find_outermost_region_in_block (struct function *src_cfun,
5887                                 basic_block bb, int region)
5888 {
5889   block_stmt_iterator si;
5890
5891   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5892     {
5893       tree stmt = bsi_stmt (si);
5894       int stmt_region;
5895
5896       if (TREE_CODE (stmt) == RESX_EXPR)
5897         stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
5898       else
5899         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5900       if (stmt_region > 0)
5901         {
5902           if (region < 0)
5903             region = stmt_region;
5904           else if (stmt_region != region)
5905             {
5906               region = eh_region_outermost (src_cfun, stmt_region, region);
5907               gcc_assert (region != -1);
5908             }
5909         }
5910     }
5911
5912   return region;
5913 }
5914
5915 static tree
5916 new_label_mapper (tree decl, void *data)
5917 {
5918   htab_t hash = (htab_t) data;
5919   struct tree_map *m;
5920   void **slot;
5921
5922   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5923
5924   m = xmalloc (sizeof (struct tree_map));
5925   m->hash = DECL_UID (decl);
5926   m->base.from = decl;
5927   m->to = create_artificial_label ();
5928   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5929   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
5930     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
5931
5932   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5933   gcc_assert (*slot == NULL);
5934
5935   *slot = m;
5936
5937   return m->to;
5938 }
5939
5940 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5941    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
5942    single basic block in the original CFG and the new basic block is
5943    returned.  DEST_CFUN must not have a CFG yet.
5944
5945    Note that the region need not be a pure SESE region.  Blocks inside
5946    the region may contain calls to abort/exit.  The only restriction
5947    is that ENTRY_BB should be the only entry point and it must
5948    dominate EXIT_BB.
5949
5950    All local variables referenced in the region are assumed to be in
5951    the corresponding BLOCK_VARS and unexpanded variable lists
5952    associated with DEST_CFUN.  */
5953
5954 basic_block
5955 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5956                         basic_block exit_bb)
5957 {
5958   VEC(basic_block,heap) *bbs, *dom_bbs;
5959   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5960   basic_block after, bb, *entry_pred, *exit_succ, abb;
5961   struct function *saved_cfun = cfun;
5962   int *entry_flag, *exit_flag, eh_offset;
5963   unsigned *entry_prob, *exit_prob;
5964   unsigned i, num_entry_edges, num_exit_edges;
5965   edge e;
5966   edge_iterator ei;
5967   htab_t new_label_map;
5968   struct pointer_map_t *vars_map;
5969   struct loop *loop = entry_bb->loop_father;
5970
5971   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5972      region.  */
5973   gcc_assert (entry_bb != exit_bb
5974               && (!exit_bb
5975                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5976
5977   /* Collect all the blocks in the region.  Manually add ENTRY_BB
5978      because it won't be added by dfs_enumerate_from.  */
5979   bbs = NULL;
5980   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5981   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5982
5983   /* The blocks that used to be dominated by something in BBS will now be
5984      dominated by the new block.  */
5985   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5986                                      VEC_address (basic_block, bbs),
5987                                      VEC_length (basic_block, bbs));
5988
5989   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
5990      the predecessor edges to ENTRY_BB and the successor edges to
5991      EXIT_BB so that we can re-attach them to the new basic block that
5992      will replace the region.  */
5993   num_entry_edges = EDGE_COUNT (entry_bb->preds);
5994   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5995   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5996   entry_prob = XNEWVEC (unsigned, num_entry_edges);
5997   i = 0;
5998   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5999     {
6000       entry_prob[i] = e->probability;
6001       entry_flag[i] = e->flags;
6002       entry_pred[i++] = e->src;
6003       remove_edge (e);
6004     }
6005
6006   if (exit_bb)
6007     {
6008       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6009       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6010                                            sizeof (basic_block));
6011       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6012       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6013       i = 0;
6014       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6015         {
6016           exit_prob[i] = e->probability;
6017           exit_flag[i] = e->flags;
6018           exit_succ[i++] = e->dest;
6019           remove_edge (e);
6020         }
6021     }
6022   else
6023     {
6024       num_exit_edges = 0;
6025       exit_succ = NULL;
6026       exit_flag = NULL;
6027       exit_prob = NULL;
6028     }
6029
6030   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6031   gcc_assert (dest_cfun->cfg == NULL);
6032   push_cfun (dest_cfun);
6033
6034   init_empty_tree_cfg ();
6035
6036   /* Initialize EH information for the new function.  */
6037   eh_offset = 0;
6038   new_label_map = NULL;
6039   if (saved_cfun->eh)
6040     {
6041       int region = -1;
6042
6043       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6044         region = find_outermost_region_in_block (saved_cfun, bb, region);
6045
6046       init_eh_for_function ();
6047       if (region != -1)
6048         {
6049           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6050           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
6051                                             new_label_map, region, 0);
6052         }
6053     }
6054
6055   pop_cfun ();
6056
6057   /* The ssa form for virtual operands in the source function will have to
6058      be repaired.  We do not care for the real operands -- the sese region
6059      must be closed with respect to those.  */
6060   mark_virtual_ops_in_region (bbs);
6061
6062   /* Move blocks from BBS into DEST_CFUN.  */
6063   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6064   after = dest_cfun->cfg->x_entry_block_ptr;
6065   vars_map = pointer_map_create ();
6066   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6067     {
6068       /* No need to update edge counts on the last block.  It has
6069          already been updated earlier when we detached the region from
6070          the original CFG.  */
6071       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_map,
6072                         new_label_map, eh_offset);
6073       after = bb;
6074     }
6075
6076   if (new_label_map)
6077     htab_delete (new_label_map);
6078   pointer_map_destroy (vars_map);
6079
6080   /* Rewire the entry and exit blocks.  The successor to the entry
6081      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6082      the child function.  Similarly, the predecessor of DEST_FN's
6083      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6084      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6085      various CFG manipulation function get to the right CFG.
6086
6087      FIXME, this is silly.  The CFG ought to become a parameter to
6088      these helpers.  */
6089   push_cfun (dest_cfun);
6090   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6091   if (exit_bb)
6092     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6093   pop_cfun ();
6094
6095   /* Back in the original function, the SESE region has disappeared,
6096      create a new basic block in its place.  */
6097   bb = create_empty_bb (entry_pred[0]);
6098   if (current_loops)
6099     add_bb_to_loop (bb, loop);
6100   for (i = 0; i < num_entry_edges; i++)
6101     {
6102       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6103       e->probability = entry_prob[i];
6104     }
6105
6106   for (i = 0; i < num_exit_edges; i++)
6107     {
6108       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6109       e->probability = exit_prob[i];
6110     }
6111
6112   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6113   for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
6114     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6115   VEC_free (basic_block, heap, dom_bbs);
6116
6117   if (exit_bb)
6118     {
6119       free (exit_prob);
6120       free (exit_flag);
6121       free (exit_succ);
6122     }
6123   free (entry_prob);
6124   free (entry_flag);
6125   free (entry_pred);
6126   VEC_free (basic_block, heap, bbs);
6127
6128   return bb;
6129 }
6130
6131
6132 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
6133
6134 void
6135 dump_function_to_file (tree fn, FILE *file, int flags)
6136 {
6137   tree arg, vars, var;
6138   struct function *dsf;
6139   bool ignore_topmost_bind = false, any_var = false;
6140   basic_block bb;
6141   tree chain;
6142
6143   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6144
6145   arg = DECL_ARGUMENTS (fn);
6146   while (arg)
6147     {
6148       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6149       fprintf (file, " ");
6150       print_generic_expr (file, arg, dump_flags);
6151       if (TREE_CHAIN (arg))
6152         fprintf (file, ", ");
6153       arg = TREE_CHAIN (arg);
6154     }
6155   fprintf (file, ")\n");
6156
6157   dsf = DECL_STRUCT_FUNCTION (fn);
6158   if (dsf && (flags & TDF_DETAILS))
6159     dump_eh_tree (file, dsf);
6160
6161   if (flags & TDF_RAW)
6162     {
6163       dump_node (fn, TDF_SLIM | flags, file);
6164       return;
6165     }
6166
6167   /* Switch CFUN to point to FN.  */
6168   push_cfun (DECL_STRUCT_FUNCTION (fn));
6169
6170   /* When GIMPLE is lowered, the variables are no longer available in
6171      BIND_EXPRs, so display them separately.  */
6172   if (cfun && cfun->decl == fn && cfun->local_decls)
6173     {
6174       ignore_topmost_bind = true;
6175
6176       fprintf (file, "{\n");
6177       for (vars = cfun->local_decls; vars; vars = TREE_CHAIN (vars))
6178         {
6179           var = TREE_VALUE (vars);
6180
6181           print_generic_decl (file, var, flags);
6182           fprintf (file, "\n");
6183
6184           any_var = true;
6185         }
6186     }
6187
6188   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6189     {
6190       /* Make a CFG based dump.  */
6191       check_bb_profile (ENTRY_BLOCK_PTR, file);
6192       if (!ignore_topmost_bind)
6193         fprintf (file, "{\n");
6194
6195       if (any_var && n_basic_blocks)
6196         fprintf (file, "\n");
6197
6198       FOR_EACH_BB (bb)
6199         dump_generic_bb (file, bb, 2, flags);
6200
6201       fprintf (file, "}\n");
6202       check_bb_profile (EXIT_BLOCK_PTR, file);
6203     }
6204   else
6205     {
6206       int indent;
6207
6208       /* Make a tree based dump.  */
6209       chain = DECL_SAVED_TREE (fn);
6210
6211       if (chain && TREE_CODE (chain) == BIND_EXPR)
6212         {
6213           if (ignore_topmost_bind)
6214             {
6215               chain = BIND_EXPR_BODY (chain);
6216               indent = 2;
6217             }
6218           else
6219             indent = 0;
6220         }
6221       else
6222         {
6223           if (!ignore_topmost_bind)
6224             fprintf (file, "{\n");
6225           indent = 2;
6226         }
6227
6228       if (any_var)
6229         fprintf (file, "\n");
6230
6231       print_generic_stmt_indented (file, chain, flags, indent);
6232       if (ignore_topmost_bind)
6233         fprintf (file, "}\n");
6234     }
6235
6236   fprintf (file, "\n\n");
6237
6238   /* Restore CFUN.  */
6239   pop_cfun ();
6240 }
6241
6242
6243 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6244
6245 void
6246 debug_function (tree fn, int flags)
6247 {
6248   dump_function_to_file (fn, stderr, flags);
6249 }
6250
6251
6252 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6253
6254 static void
6255 print_pred_bbs (FILE *file, basic_block bb)
6256 {
6257   edge e;
6258   edge_iterator ei;
6259
6260   FOR_EACH_EDGE (e, ei, bb->preds)
6261     fprintf (file, "bb_%d ", e->src->index);
6262 }
6263
6264
6265 /* Print on FILE the indexes for the successors of basic_block BB.  */
6266
6267 static void
6268 print_succ_bbs (FILE *file, basic_block bb)
6269 {
6270   edge e;
6271   edge_iterator ei;
6272
6273   FOR_EACH_EDGE (e, ei, bb->succs)
6274     fprintf (file, "bb_%d ", e->dest->index);
6275 }
6276
6277 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6278
6279 void
6280 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6281 {
6282   char *s_indent = (char *) alloca ((size_t) indent + 1);
6283   memset ((void *) s_indent, ' ', (size_t) indent);
6284   s_indent[indent] = '\0';
6285
6286   /* Print basic_block's header.  */
6287   if (verbosity >= 2)
6288     {
6289       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6290       print_pred_bbs (file, bb);
6291       fprintf (file, "}, succs = {");
6292       print_succ_bbs (file, bb);
6293       fprintf (file, "})\n");
6294     }
6295
6296   /* Print basic_block's body.  */
6297   if (verbosity >= 3)
6298     {
6299       fprintf (file, "%s  {\n", s_indent);
6300       tree_dump_bb (bb, file, indent + 4);
6301       fprintf (file, "%s  }\n", s_indent);
6302     }
6303 }
6304
6305 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6306
6307 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6308    VERBOSITY level this outputs the contents of the loop, or just its
6309    structure.  */
6310
6311 static void
6312 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6313 {
6314   char *s_indent;
6315   basic_block bb;
6316
6317   if (loop == NULL)
6318     return;
6319
6320   s_indent = (char *) alloca ((size_t) indent + 1);
6321   memset ((void *) s_indent, ' ', (size_t) indent);
6322   s_indent[indent] = '\0';
6323
6324   /* Print loop's header.  */
6325   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6326            loop->num, loop->header->index, loop->latch->index);
6327   fprintf (file, ", niter = ");
6328   print_generic_expr (file, loop->nb_iterations, 0);
6329
6330   if (loop->any_upper_bound)
6331     {
6332       fprintf (file, ", upper_bound = ");
6333       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6334     }
6335
6336   if (loop->any_estimate)
6337     {
6338       fprintf (file, ", estimate = ");
6339       dump_double_int (file, loop->nb_iterations_estimate, true);
6340     }
6341   fprintf (file, ")\n");
6342
6343   /* Print loop's body.  */
6344   if (verbosity >= 1)
6345     {
6346       fprintf (file, "%s{\n", s_indent);
6347       FOR_EACH_BB (bb)
6348         if (bb->loop_father == loop)
6349           print_loops_bb (file, bb, indent, verbosity);
6350
6351       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6352       fprintf (file, "%s}\n", s_indent);
6353     }
6354 }
6355
6356 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6357    spaces.  Following VERBOSITY level this outputs the contents of the
6358    loop, or just its structure.  */
6359
6360 static void
6361 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6362 {
6363   if (loop == NULL)
6364     return;
6365
6366   print_loop (file, loop, indent, verbosity);
6367   print_loop_and_siblings (file, loop->next, indent, verbosity);
6368 }
6369
6370 /* Follow a CFG edge from the entry point of the program, and on entry
6371    of a loop, pretty print the loop structure on FILE.  */
6372
6373 void
6374 print_loops (FILE *file, int verbosity)
6375 {
6376   basic_block bb;
6377
6378   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
6379   if (bb && bb->loop_father)
6380     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6381 }
6382
6383
6384 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6385
6386 void
6387 debug_loops (int verbosity)
6388 {
6389   print_loops (stderr, verbosity);
6390 }
6391
6392 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6393
6394 void
6395 debug_loop (struct loop *loop, int verbosity)
6396 {
6397   print_loop (stderr, loop, 0, verbosity);
6398 }
6399
6400 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6401    level.  */
6402
6403 void
6404 debug_loop_num (unsigned num, int verbosity)
6405 {
6406   debug_loop (get_loop (num), verbosity);
6407 }
6408
6409 /* Return true if BB ends with a call, possibly followed by some
6410    instructions that must stay with the call.  Return false,
6411    otherwise.  */
6412
6413 static bool
6414 tree_block_ends_with_call_p (basic_block bb)
6415 {
6416   block_stmt_iterator bsi = bsi_last (bb);
6417   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
6418 }
6419
6420
6421 /* Return true if BB ends with a conditional branch.  Return false,
6422    otherwise.  */
6423
6424 static bool
6425 tree_block_ends_with_condjump_p (const_basic_block bb)
6426 {
6427   /* This CONST_CAST is okay because last_stmt doesn't modify its
6428      argument and the return value is not modified.  */
6429   const_tree stmt = last_stmt (CONST_CAST_BB(bb));
6430   return (stmt && TREE_CODE (stmt) == COND_EXPR);
6431 }
6432
6433
6434 /* Return true if we need to add fake edge to exit at statement T.
6435    Helper function for tree_flow_call_edges_add.  */
6436
6437 static bool
6438 need_fake_edge_p (tree t)
6439 {
6440   tree call, fndecl = NULL_TREE;
6441   int call_flags;
6442
6443   /* NORETURN and LONGJMP calls already have an edge to exit.
6444      CONST and PURE calls do not need one.
6445      We don't currently check for CONST and PURE here, although
6446      it would be a good idea, because those attributes are
6447      figured out from the RTL in mark_constant_function, and
6448      the counter incrementation code from -fprofile-arcs
6449      leads to different results from -fbranch-probabilities.  */
6450   call = get_call_expr_in (t);
6451   if (call)
6452     {
6453       fndecl = get_callee_fndecl (call);
6454       call_flags = call_expr_flags (call);
6455     }
6456
6457   if (call && fndecl && DECL_BUILT_IN (fndecl)
6458       && (call_flags & ECF_NOTHROW)
6459       && !(call_flags & ECF_NORETURN)
6460       && !(call_flags & ECF_RETURNS_TWICE))
6461    return false;
6462
6463   if (call && !(call_flags & ECF_NORETURN))
6464     return true;
6465
6466   if (TREE_CODE (t) == ASM_EXPR
6467        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
6468     return true;
6469
6470   return false;
6471 }
6472
6473
6474 /* Add fake edges to the function exit for any non constant and non
6475    noreturn calls, volatile inline assembly in the bitmap of blocks
6476    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6477    the number of blocks that were split.
6478
6479    The goal is to expose cases in which entering a basic block does
6480    not imply that all subsequent instructions must be executed.  */
6481
6482 static int
6483 tree_flow_call_edges_add (sbitmap blocks)
6484 {
6485   int i;
6486   int blocks_split = 0;
6487   int last_bb = last_basic_block;
6488   bool check_last_block = false;
6489
6490   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6491     return 0;
6492
6493   if (! blocks)
6494     check_last_block = true;
6495   else
6496     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6497
6498   /* In the last basic block, before epilogue generation, there will be
6499      a fallthru edge to EXIT.  Special care is required if the last insn
6500      of the last basic block is a call because make_edge folds duplicate
6501      edges, which would result in the fallthru edge also being marked
6502      fake, which would result in the fallthru edge being removed by
6503      remove_fake_edges, which would result in an invalid CFG.
6504
6505      Moreover, we can't elide the outgoing fake edge, since the block
6506      profiler needs to take this into account in order to solve the minimal
6507      spanning tree in the case that the call doesn't return.
6508
6509      Handle this by adding a dummy instruction in a new last basic block.  */
6510   if (check_last_block)
6511     {
6512       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6513       block_stmt_iterator bsi = bsi_last (bb);
6514       tree t = NULL_TREE;
6515       if (!bsi_end_p (bsi))
6516         t = bsi_stmt (bsi);
6517
6518       if (t && need_fake_edge_p (t))
6519         {
6520           edge e;
6521
6522           e = find_edge (bb, EXIT_BLOCK_PTR);
6523           if (e)
6524             {
6525               bsi_insert_on_edge (e, build_empty_stmt ());
6526               bsi_commit_edge_inserts ();
6527             }
6528         }
6529     }
6530
6531   /* Now add fake edges to the function exit for any non constant
6532      calls since there is no way that we can determine if they will
6533      return or not...  */
6534   for (i = 0; i < last_bb; i++)
6535     {
6536       basic_block bb = BASIC_BLOCK (i);
6537       block_stmt_iterator bsi;
6538       tree stmt, last_stmt;
6539
6540       if (!bb)
6541         continue;
6542
6543       if (blocks && !TEST_BIT (blocks, i))
6544         continue;
6545
6546       bsi = bsi_last (bb);
6547       if (!bsi_end_p (bsi))
6548         {
6549           last_stmt = bsi_stmt (bsi);
6550           do
6551             {
6552               stmt = bsi_stmt (bsi);
6553               if (need_fake_edge_p (stmt))
6554                 {
6555                   edge e;
6556                   /* The handling above of the final block before the
6557                      epilogue should be enough to verify that there is
6558                      no edge to the exit block in CFG already.
6559                      Calling make_edge in such case would cause us to
6560                      mark that edge as fake and remove it later.  */
6561 #ifdef ENABLE_CHECKING
6562                   if (stmt == last_stmt)
6563                     {
6564                       e = find_edge (bb, EXIT_BLOCK_PTR);
6565                       gcc_assert (e == NULL);
6566                     }
6567 #endif
6568
6569                   /* Note that the following may create a new basic block
6570                      and renumber the existing basic blocks.  */
6571                   if (stmt != last_stmt)
6572                     {
6573                       e = split_block (bb, stmt);
6574                       if (e)
6575                         blocks_split++;
6576                     }
6577                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6578                 }
6579               bsi_prev (&bsi);
6580             }
6581           while (!bsi_end_p (bsi));
6582         }
6583     }
6584
6585   if (blocks_split)
6586     verify_flow_info ();
6587
6588   return blocks_split;
6589 }
6590
6591 /* Purge dead abnormal call edges from basic block BB.  */
6592
6593 bool
6594 tree_purge_dead_abnormal_call_edges (basic_block bb)
6595 {
6596   bool changed = tree_purge_dead_eh_edges (bb);
6597
6598   if (cfun->has_nonlocal_label)
6599     {
6600       tree stmt = last_stmt (bb);
6601       edge_iterator ei;
6602       edge e;
6603
6604       if (!(stmt && tree_can_make_abnormal_goto (stmt)))
6605         for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6606           {
6607             if (e->flags & EDGE_ABNORMAL)
6608               {
6609                 remove_edge (e);
6610                 changed = true;
6611               }
6612             else
6613               ei_next (&ei);
6614           }
6615
6616       /* See tree_purge_dead_eh_edges below.  */
6617       if (changed)
6618         free_dominance_info (CDI_DOMINATORS);
6619     }
6620
6621   return changed;
6622 }
6623
6624 /* Stores all basic blocks dominated by BB to DOM_BBS.  */
6625
6626 static void
6627 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6628 {
6629   basic_block son;
6630
6631   VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6632   for (son = first_dom_son (CDI_DOMINATORS, bb);
6633        son;
6634        son = next_dom_son (CDI_DOMINATORS, son))
6635     get_all_dominated_blocks (son, dom_bbs);
6636 }
6637
6638 /* Removes edge E and all the blocks dominated by it, and updates dominance
6639    information.  The IL in E->src needs to be updated separately.
6640    If dominance info is not available, only the edge E is removed.*/
6641
6642 void
6643 remove_edge_and_dominated_blocks (edge e)
6644 {
6645   VEC (basic_block, heap) *bbs_to_remove = NULL;
6646   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6647   bitmap df, df_idom;
6648   edge f;
6649   edge_iterator ei;
6650   bool none_removed = false;
6651   unsigned i;
6652   basic_block bb, dbb;
6653   bitmap_iterator bi;
6654
6655   if (!dom_info_available_p (CDI_DOMINATORS))
6656     {
6657       remove_edge (e);
6658       return;
6659     }
6660
6661   /* No updating is needed for edges to exit.  */
6662   if (e->dest == EXIT_BLOCK_PTR)
6663     {
6664       if (cfgcleanup_altered_bbs)
6665         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6666       remove_edge (e);
6667       return;
6668     }
6669
6670   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6671      that is not dominated by E->dest, then this set is empty.  Otherwise,
6672      all the basic blocks dominated by E->dest are removed.
6673
6674      Also, to DF_IDOM we store the immediate dominators of the blocks in
6675      the dominance frontier of E (i.e., of the successors of the
6676      removed blocks, if there are any, and of E->dest otherwise).  */
6677   FOR_EACH_EDGE (f, ei, e->dest->preds)
6678     {
6679       if (f == e)
6680         continue;
6681
6682       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6683         {
6684           none_removed = true;
6685           break;
6686         }
6687     }
6688
6689   df = BITMAP_ALLOC (NULL);
6690   df_idom = BITMAP_ALLOC (NULL);
6691
6692   if (none_removed)
6693     bitmap_set_bit (df_idom,
6694                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6695   else
6696     {
6697       get_all_dominated_blocks (e->dest, &bbs_to_remove);
6698       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6699         {
6700           FOR_EACH_EDGE (f, ei, bb->succs)
6701             {
6702               if (f->dest != EXIT_BLOCK_PTR)
6703                 bitmap_set_bit (df, f->dest->index);
6704             }
6705         }
6706       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6707         bitmap_clear_bit (df, bb->index);
6708
6709       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6710         {
6711           bb = BASIC_BLOCK (i);
6712           bitmap_set_bit (df_idom,
6713                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6714         }
6715     }
6716
6717   if (cfgcleanup_altered_bbs)
6718     {
6719       /* Record the set of the altered basic blocks.  */
6720       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6721       bitmap_ior_into (cfgcleanup_altered_bbs, df);
6722     }
6723
6724   /* Remove E and the cancelled blocks.  */
6725   if (none_removed)
6726     remove_edge (e);
6727   else
6728     {
6729       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6730         delete_basic_block (bb);
6731     }
6732
6733   /* Update the dominance information.  The immediate dominator may change only
6734      for blocks whose immediate dominator belongs to DF_IDOM:
6735
6736      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6737      removal.  Let Z the arbitrary block such that idom(Z) = Y and
6738      Z dominates X after the removal.  Before removal, there exists a path P
6739      from Y to X that avoids Z.  Let F be the last edge on P that is
6740      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
6741      dominates W, and because of P, Z does not dominate W), and W belongs to
6742      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
6743   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6744     {
6745       bb = BASIC_BLOCK (i);
6746       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6747            dbb;
6748            dbb = next_dom_son (CDI_DOMINATORS, dbb))
6749         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6750     }
6751
6752   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6753
6754   BITMAP_FREE (df);
6755   BITMAP_FREE (df_idom);
6756   VEC_free (basic_block, heap, bbs_to_remove);
6757   VEC_free (basic_block, heap, bbs_to_fix_dom);
6758 }
6759
6760 /* Purge dead EH edges from basic block BB.  */
6761
6762 bool
6763 tree_purge_dead_eh_edges (basic_block bb)
6764 {
6765   bool changed = false;
6766   edge e;
6767   edge_iterator ei;
6768   tree stmt = last_stmt (bb);
6769
6770   if (stmt && tree_can_throw_internal (stmt))
6771     return false;
6772
6773   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6774     {
6775       if (e->flags & EDGE_EH)
6776         {
6777           remove_edge_and_dominated_blocks (e);
6778           changed = true;
6779         }
6780       else
6781         ei_next (&ei);
6782     }
6783
6784   return changed;
6785 }
6786
6787 bool
6788 tree_purge_all_dead_eh_edges (const_bitmap blocks)
6789 {
6790   bool changed = false;
6791   unsigned i;
6792   bitmap_iterator bi;
6793
6794   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6795     {
6796       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
6797     }
6798
6799   return changed;
6800 }
6801
6802 /* This function is called whenever a new edge is created or
6803    redirected.  */
6804
6805 static void
6806 tree_execute_on_growing_pred (edge e)
6807 {
6808   basic_block bb = e->dest;
6809
6810   if (phi_nodes (bb))
6811     reserve_phi_args_for_new_edge (bb);
6812 }
6813
6814 /* This function is called immediately before edge E is removed from
6815    the edge vector E->dest->preds.  */
6816
6817 static void
6818 tree_execute_on_shrinking_pred (edge e)
6819 {
6820   if (phi_nodes (e->dest))
6821     remove_phi_args (e);
6822 }
6823
6824 /*---------------------------------------------------------------------------
6825   Helper functions for Loop versioning
6826   ---------------------------------------------------------------------------*/
6827
6828 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
6829    of 'first'. Both of them are dominated by 'new_head' basic block. When
6830    'new_head' was created by 'second's incoming edge it received phi arguments
6831    on the edge by split_edge(). Later, additional edge 'e' was created to
6832    connect 'new_head' and 'first'. Now this routine adds phi args on this
6833    additional edge 'e' that new_head to second edge received as part of edge
6834    splitting.
6835 */
6836
6837 static void
6838 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6839                                 basic_block new_head, edge e)
6840 {
6841   tree phi1, phi2;
6842   edge e2 = find_edge (new_head, second);
6843
6844   /* Because NEW_HEAD has been created by splitting SECOND's incoming
6845      edge, we should always have an edge from NEW_HEAD to SECOND.  */
6846   gcc_assert (e2 != NULL);
6847
6848   /* Browse all 'second' basic block phi nodes and add phi args to
6849      edge 'e' for 'first' head. PHI args are always in correct order.  */
6850
6851   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
6852        phi2 && phi1;
6853        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
6854     {
6855       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
6856       add_phi_arg (phi1, def, e);
6857     }
6858 }
6859
6860 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6861    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6862    the destination of the ELSE part.  */
6863 static void
6864 tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6865                              basic_block second_head ATTRIBUTE_UNUSED,
6866                              basic_block cond_bb, void *cond_e)
6867 {
6868   block_stmt_iterator bsi;
6869   tree new_cond_expr = NULL_TREE;
6870   tree cond_expr = (tree) cond_e;
6871   edge e0;
6872
6873   /* Build new conditional expr */
6874   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
6875                           NULL_TREE, NULL_TREE);
6876
6877   /* Add new cond in cond_bb.  */
6878   bsi = bsi_start (cond_bb);
6879   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
6880   /* Adjust edges appropriately to connect new head with first head
6881      as well as second head.  */
6882   e0 = single_succ_edge (cond_bb);
6883   e0->flags &= ~EDGE_FALLTHRU;
6884   e0->flags |= EDGE_FALSE_VALUE;
6885 }
6886
6887 struct cfg_hooks tree_cfg_hooks = {
6888   "tree",
6889   tree_verify_flow_info,
6890   tree_dump_bb,                 /* dump_bb  */
6891   create_bb,                    /* create_basic_block  */
6892   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
6893   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
6894   tree_can_remove_branch_p,     /* can_remove_branch_p  */
6895   remove_bb,                    /* delete_basic_block  */
6896   tree_split_block,             /* split_block  */
6897   tree_move_block_after,        /* move_block_after  */
6898   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
6899   tree_merge_blocks,            /* merge_blocks  */
6900   tree_predict_edge,            /* predict_edge  */
6901   tree_predicted_by_p,          /* predicted_by_p  */
6902   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
6903   tree_duplicate_bb,            /* duplicate_block  */
6904   tree_split_edge,              /* split_edge  */
6905   tree_make_forwarder_block,    /* make_forward_block  */
6906   NULL,                         /* tidy_fallthru_edge  */
6907   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
6908   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6909   tree_flow_call_edges_add,     /* flow_call_edges_add */
6910   tree_execute_on_growing_pred, /* execute_on_growing_pred */
6911   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6912   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6913   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6914   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6915   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6916   flush_pending_stmts           /* flush_pending_stmts */
6917 };
6918
6919
6920 /* Split all critical edges.  */
6921
6922 static unsigned int
6923 split_critical_edges (void)
6924 {
6925   basic_block bb;
6926   edge e;
6927   edge_iterator ei;
6928
6929   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6930      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
6931      mappings around the calls to split_edge.  */
6932   start_recording_case_labels ();
6933   FOR_ALL_BB (bb)
6934     {
6935       FOR_EACH_EDGE (e, ei, bb->succs)
6936         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6937           {
6938             split_edge (e);
6939           }
6940     }
6941   end_recording_case_labels ();
6942   return 0;
6943 }
6944
6945 struct gimple_opt_pass pass_split_crit_edges =
6946 {
6947  {
6948   GIMPLE_PASS,
6949   "crited",                          /* name */
6950   NULL,                          /* gate */
6951   split_critical_edges,          /* execute */
6952   NULL,                          /* sub */
6953   NULL,                          /* next */
6954   0,                             /* static_pass_number */
6955   TV_TREE_SPLIT_EDGES,           /* tv_id */
6956   PROP_cfg,                      /* properties required */
6957   PROP_no_crit_edges,            /* properties_provided */
6958   0,                             /* properties_destroyed */
6959   0,                             /* todo_flags_start */
6960   TODO_dump_func                 /* todo_flags_finish */
6961  }
6962 };
6963
6964 \f
6965 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
6966    a temporary, make sure and register it to be renamed if necessary,
6967    and finally return the temporary.  Put the statements to compute
6968    EXP before the current statement in BSI.  */
6969
6970 tree
6971 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
6972 {
6973   tree t, new_stmt, orig_stmt;
6974
6975   if (is_gimple_val (exp))
6976     return exp;
6977
6978   t = make_rename_temp (type, NULL);
6979   new_stmt = build_gimple_modify_stmt (t, exp);
6980
6981   orig_stmt = bsi_stmt (*bsi);
6982   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
6983   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
6984
6985   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
6986   if (gimple_in_ssa_p (cfun))
6987     mark_symbols_for_renaming (new_stmt);
6988
6989   return t;
6990 }
6991
6992 /* Build a ternary operation and gimplify it.  Emit code before BSI.
6993    Return the gimple_val holding the result.  */
6994
6995 tree
6996 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
6997                  tree type, tree a, tree b, tree c)
6998 {
6999   tree ret;
7000
7001   ret = fold_build3 (code, type, a, b, c);
7002   STRIP_NOPS (ret);
7003
7004   return gimplify_val (bsi, type, ret);
7005 }
7006
7007 /* Build a binary operation and gimplify it.  Emit code before BSI.
7008    Return the gimple_val holding the result.  */
7009
7010 tree
7011 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
7012                  tree type, tree a, tree b)
7013 {
7014   tree ret;
7015
7016   ret = fold_build2 (code, type, a, b);
7017   STRIP_NOPS (ret);
7018
7019   return gimplify_val (bsi, type, ret);
7020 }
7021
7022 /* Build a unary operation and gimplify it.  Emit code before BSI.
7023    Return the gimple_val holding the result.  */
7024
7025 tree
7026 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
7027                  tree a)
7028 {
7029   tree ret;
7030
7031   ret = fold_build1 (code, type, a);
7032   STRIP_NOPS (ret);
7033
7034   return gimplify_val (bsi, type, ret);
7035 }
7036
7037
7038 \f
7039 /* Emit return warnings.  */
7040
7041 static unsigned int
7042 execute_warn_function_return (void)
7043 {
7044   source_location location;
7045   tree last;
7046   edge e;
7047   edge_iterator ei;
7048
7049   /* If we have a path to EXIT, then we do return.  */
7050   if (TREE_THIS_VOLATILE (cfun->decl)
7051       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7052     {
7053       location = UNKNOWN_LOCATION;
7054       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7055         {
7056           last = last_stmt (e->src);
7057           if (TREE_CODE (last) == RETURN_EXPR
7058               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
7059             break;
7060         }
7061       if (location == UNKNOWN_LOCATION)
7062         location = cfun->function_end_locus;
7063       warning (0, "%H%<noreturn%> function does return", &location);
7064     }
7065
7066   /* If we see "return;" in some basic block, then we do reach the end
7067      without returning a value.  */
7068   else if (warn_return_type
7069            && !TREE_NO_WARNING (cfun->decl)
7070            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7071            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7072     {
7073       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7074         {
7075           tree last = last_stmt (e->src);
7076           if (TREE_CODE (last) == RETURN_EXPR
7077               && TREE_OPERAND (last, 0) == NULL
7078               && !TREE_NO_WARNING (last))
7079             {
7080               location = EXPR_LOCATION (last);
7081               if (location == UNKNOWN_LOCATION)
7082                   location = cfun->function_end_locus;
7083               warning (OPT_Wreturn_type, "%Hcontrol reaches end of non-void function", &location);
7084               TREE_NO_WARNING (cfun->decl) = 1;
7085               break;
7086             }
7087         }
7088     }
7089   return 0;
7090 }
7091
7092
7093 /* Given a basic block B which ends with a conditional and has
7094    precisely two successors, determine which of the edges is taken if
7095    the conditional is true and which is taken if the conditional is
7096    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7097
7098 void
7099 extract_true_false_edges_from_block (basic_block b,
7100                                      edge *true_edge,
7101                                      edge *false_edge)
7102 {
7103   edge e = EDGE_SUCC (b, 0);
7104
7105   if (e->flags & EDGE_TRUE_VALUE)
7106     {
7107       *true_edge = e;
7108       *false_edge = EDGE_SUCC (b, 1);
7109     }
7110   else
7111     {
7112       *false_edge = e;
7113       *true_edge = EDGE_SUCC (b, 1);
7114     }
7115 }
7116
7117 struct gimple_opt_pass pass_warn_function_return =
7118 {
7119  {
7120   GIMPLE_PASS,
7121   NULL,                                 /* name */
7122   NULL,                                 /* gate */
7123   execute_warn_function_return,         /* execute */
7124   NULL,                                 /* sub */
7125   NULL,                                 /* next */
7126   0,                                    /* static_pass_number */
7127   0,                                    /* tv_id */
7128   PROP_cfg,                             /* properties_required */
7129   0,                                    /* properties_provided */
7130   0,                                    /* properties_destroyed */
7131   0,                                    /* todo_flags_start */
7132   0                                     /* todo_flags_finish */
7133  }
7134 };
7135
7136 /* Emit noreturn warnings.  */
7137
7138 static unsigned int
7139 execute_warn_function_noreturn (void)
7140 {
7141   if (warn_missing_noreturn
7142       && !TREE_THIS_VOLATILE (cfun->decl)
7143       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
7144       && !lang_hooks.missing_noreturn_ok_p (cfun->decl))
7145     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
7146              "for attribute %<noreturn%>",
7147              cfun->decl);
7148   return 0;
7149 }
7150
7151 struct gimple_opt_pass pass_warn_function_noreturn =
7152 {
7153  {
7154   GIMPLE_PASS,
7155   NULL,                                 /* name */
7156   NULL,                                 /* gate */
7157   execute_warn_function_noreturn,       /* execute */
7158   NULL,                                 /* sub */
7159   NULL,                                 /* next */
7160   0,                                    /* static_pass_number */
7161   0,                                    /* tv_id */
7162   PROP_cfg,                             /* properties_required */
7163   0,                                    /* properties_provided */
7164   0,                                    /* properties_destroyed */
7165   0,                                    /* todo_flags_start */
7166   0                                     /* todo_flags_finish */
7167  }
7168 };