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