gcc/tree-cfg.c

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