gcc/tree-cfg.c

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