gcc/tree-cfg.c

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