gcc/tree-cfg.c

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