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