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 (const_basic_block, const_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 (const_basic_block a, const_basic_block b)
1140 {
1141   const_tree stmt;
1142   const_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 = cbsi_start (b); !cbsi_end_p (bsi); cbsi_next (&bsi))
1191     {
1192       stmt = cbsi_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 = const_get_call_expr_in (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         tree ptr_type;
3774         if (!is_gimple_addressable (op))
3775           {
3776             error ("invalid operand in unary expression");
3777             return true;
3778           }
3779         ptr_type = build_pointer_type (TREE_TYPE (op));
3780         if (!useless_type_conversion_p (type, ptr_type)
3781             /* FIXME: a longstanding wart, &a == &a[0].  */
3782             && (TREE_CODE (TREE_TYPE (op)) != ARRAY_TYPE
3783                 || !useless_type_conversion_p (type,
3784                         build_pointer_type (TREE_TYPE (TREE_TYPE (op))))))
3785           {
3786             error ("type mismatch in address expression");
3787             debug_generic_stmt (TREE_TYPE (expr));
3788             debug_generic_stmt (ptr_type);
3789             return true;
3790           }
3791
3792         return verify_gimple_reference (op);
3793       }
3794
3795     case TRUTH_ANDIF_EXPR:
3796     case TRUTH_ORIF_EXPR:
3797     case TRUTH_AND_EXPR:
3798     case TRUTH_OR_EXPR:
3799     case TRUTH_XOR_EXPR:
3800       {
3801         tree op0 = TREE_OPERAND (expr, 0);
3802         tree op1 = TREE_OPERAND (expr, 1);
3803
3804         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3805           {
3806             error ("invalid operands in truth expression");
3807             return true;
3808           }
3809
3810         /* We allow any kind of integral typed argument and result.  */
3811         if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3812             || !INTEGRAL_TYPE_P (TREE_TYPE (op1))
3813             || !INTEGRAL_TYPE_P (type))
3814           {
3815             error ("type mismatch in binary truth expression");
3816             debug_generic_stmt (type);
3817             debug_generic_stmt (TREE_TYPE (op0));
3818             debug_generic_stmt (TREE_TYPE (op1));
3819             return true;
3820           }
3821
3822         return false;
3823       }
3824
3825     case TRUTH_NOT_EXPR:
3826       {
3827         tree op = TREE_OPERAND (expr, 0);
3828
3829         if (!is_gimple_val (op))
3830           {
3831             error ("invalid operand in unary not");
3832             return true;
3833           }
3834
3835         /* For TRUTH_NOT_EXPR we can have any kind of integral
3836            typed arguments and results.  */
3837         if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3838             || !INTEGRAL_TYPE_P (type))
3839           {
3840             error ("type mismatch in not expression");
3841             debug_generic_expr (TREE_TYPE (expr));
3842             debug_generic_expr (TREE_TYPE (op));
3843             return true;
3844           }
3845
3846         return false;
3847       }
3848
3849     case CALL_EXPR:
3850       /* FIXME.  The C frontend passes unpromoted arguments in case it
3851          didn't see a function declaration before the call.  */
3852       return false;
3853
3854     default:;
3855     }
3856
3857   /* Generic handling via classes.  */
3858   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3859     {
3860     case tcc_unary:
3861       return verify_gimple_unary_expr (expr);
3862
3863     case tcc_binary:
3864       return verify_gimple_binary_expr (expr);
3865
3866     case tcc_reference:
3867       return verify_gimple_reference (expr);
3868
3869     case tcc_comparison:
3870       {
3871         tree op0 = TREE_OPERAND (expr, 0);
3872         tree op1 = TREE_OPERAND (expr, 1);
3873         if (!is_gimple_val (op0) || !is_gimple_val (op1))
3874           {
3875             error ("invalid operands in comparison expression");
3876             return true;
3877           }
3878         /* For comparisons we do not have the operations type as the
3879            effective type the comparison is carried out in.  Instead
3880            we require that either the first operand is trivially
3881            convertible into the second, or the other way around.
3882            The resulting type of a comparison may be any integral type.
3883            Because we special-case pointers to void we allow
3884            comparisons of pointers with the same mode as well.  */
3885         if ((!useless_type_conversion_p (TREE_TYPE (op0), TREE_TYPE (op1))
3886              && !useless_type_conversion_p (TREE_TYPE (op1), TREE_TYPE (op0))
3887              && (!POINTER_TYPE_P (TREE_TYPE (op0))
3888                  || !POINTER_TYPE_P (TREE_TYPE (op1))
3889                  || TYPE_MODE (TREE_TYPE (op0)) != TYPE_MODE (TREE_TYPE (op1))))
3890             || !INTEGRAL_TYPE_P (type))
3891           {
3892             error ("type mismatch in comparison expression");
3893             debug_generic_stmt (TREE_TYPE (expr));
3894             debug_generic_stmt (TREE_TYPE (op0));
3895             debug_generic_stmt (TREE_TYPE (op1));
3896             return true;
3897           }
3898         break;
3899       }
3900
3901     default:
3902       gcc_unreachable ();
3903     }
3904
3905   return false;
3906 }
3907
3908 /* Verify the GIMPLE assignment statement STMT.  Returns true if there
3909    is an error, otherwise false.  */
3910
3911 static bool
3912 verify_gimple_modify_stmt (const_tree stmt)
3913 {
3914   tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3915   tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3916
3917   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3918
3919   if (!useless_type_conversion_p (TREE_TYPE (lhs),
3920                                   TREE_TYPE (rhs)))
3921     {
3922       error ("non-trivial conversion at assignment");
3923       debug_generic_expr (TREE_TYPE (lhs));
3924       debug_generic_expr (TREE_TYPE (rhs));
3925       return true;
3926     }
3927
3928   /* Loads/stores from/to a variable are ok.  */
3929   if ((is_gimple_val (lhs)
3930        && is_gimple_variable (rhs))
3931       || (is_gimple_val (rhs)
3932           && is_gimple_variable (lhs)))
3933     return false;
3934
3935   /* Aggregate copies are ok.  */
3936   if (!is_gimple_reg_type (TREE_TYPE (lhs))
3937       && !is_gimple_reg_type (TREE_TYPE (rhs)))
3938     return false;
3939
3940   /* We might get 'loads' from a parameter which is not a gimple value.  */
3941   if (TREE_CODE (rhs) == PARM_DECL)
3942     return verify_gimple_expr (lhs);
3943
3944   if (!is_gimple_variable (lhs)
3945       && verify_gimple_expr (lhs))
3946     return true;
3947
3948   if (!is_gimple_variable (rhs)
3949       && verify_gimple_expr (rhs))
3950     return true;
3951
3952   return false;
3953 }
3954
3955 /* Verify the GIMPLE statement STMT.  Returns true if there is an
3956    error, otherwise false.  */
3957
3958 static bool
3959 verify_gimple_stmt (tree stmt)
3960 {
3961   if (!is_gimple_stmt (stmt))
3962     {
3963       error ("is not a valid GIMPLE statement");
3964       return true;
3965     }
3966
3967   if (OMP_DIRECTIVE_P (stmt))
3968     {
3969       /* OpenMP directives are validated by the FE and never operated
3970          on by the optimizers.  Furthermore, OMP_FOR may contain
3971          non-gimple expressions when the main index variable has had
3972          its address taken.  This does not affect the loop itself
3973          because the header of an OMP_FOR is merely used to determine
3974          how to setup the parallel iteration.  */
3975       return false;
3976     }
3977
3978   switch (TREE_CODE (stmt))
3979     {
3980     case GIMPLE_MODIFY_STMT:
3981       return verify_gimple_modify_stmt (stmt);
3982
3983     case GOTO_EXPR:
3984     case LABEL_EXPR:
3985       return false;
3986
3987     case SWITCH_EXPR:
3988       if (!is_gimple_val (TREE_OPERAND (stmt, 0)))
3989         {
3990           error ("invalid operand to switch statement");
3991           debug_generic_expr (TREE_OPERAND (stmt, 0));
3992         }
3993       return false;
3994
3995     case RETURN_EXPR:
3996       {
3997         tree op = TREE_OPERAND (stmt, 0);
3998
3999         if (TREE_CODE (TREE_TYPE (stmt)) != VOID_TYPE)
4000           {
4001             error ("type error in return expression");
4002             return true;
4003           }
4004
4005         if (op == NULL_TREE
4006             || TREE_CODE (op) == RESULT_DECL)
4007           return false;
4008
4009         return verify_gimple_modify_stmt (op);
4010       }
4011
4012     case CALL_EXPR:
4013     case COND_EXPR:
4014       return verify_gimple_expr (stmt);
4015
4016     case NOP_EXPR:
4017     case CHANGE_DYNAMIC_TYPE_EXPR:
4018     case ASM_EXPR:
4019       return false;
4020
4021     default:
4022       gcc_unreachable ();
4023     }
4024 }
4025
4026 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4027
4028 void
4029 verify_gimple_1 (tree stmts)
4030 {
4031   tree_stmt_iterator tsi;
4032
4033   for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
4034     {
4035       tree stmt = tsi_stmt (tsi);
4036
4037       switch (TREE_CODE (stmt))
4038         {
4039         case BIND_EXPR:
4040           verify_gimple_1 (BIND_EXPR_BODY (stmt));
4041           break;
4042
4043         case TRY_CATCH_EXPR:
4044         case TRY_FINALLY_EXPR:
4045           verify_gimple_1 (TREE_OPERAND (stmt, 0));
4046           verify_gimple_1 (TREE_OPERAND (stmt, 1));
4047           break;
4048
4049         case CATCH_EXPR:
4050           verify_gimple_1 (CATCH_BODY (stmt));
4051           break;
4052
4053         case EH_FILTER_EXPR:
4054           verify_gimple_1 (EH_FILTER_FAILURE (stmt));
4055           break;
4056
4057         default:
4058           if (verify_gimple_stmt (stmt))
4059             debug_generic_expr (stmt);
4060         }
4061     }
4062 }
4063
4064 /* Verify the GIMPLE statements inside the current function.  */
4065
4066 void
4067 verify_gimple (void)
4068 {
4069   verify_gimple_1 (BIND_EXPR_BODY (DECL_SAVED_TREE (cfun->decl)));
4070 }
4071
4072 /* Verify STMT, return true if STMT is not in GIMPLE form.
4073    TODO: Implement type checking.  */
4074
4075 static bool
4076 verify_stmt (tree stmt, bool last_in_block)
4077 {
4078   tree addr;
4079
4080   if (OMP_DIRECTIVE_P (stmt))
4081     {
4082       /* OpenMP directives are validated by the FE and never operated
4083          on by the optimizers.  Furthermore, OMP_FOR may contain
4084          non-gimple expressions when the main index variable has had
4085          its address taken.  This does not affect the loop itself
4086          because the header of an OMP_FOR is merely used to determine
4087          how to setup the parallel iteration.  */
4088       return false;
4089     }
4090
4091   if (!is_gimple_stmt (stmt))
4092     {
4093       error ("is not a valid GIMPLE statement");
4094       goto fail;
4095     }
4096
4097   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
4098   if (addr)
4099     {
4100       debug_generic_stmt (addr);
4101       return true;
4102     }
4103
4104   /* If the statement is marked as part of an EH region, then it is
4105      expected that the statement could throw.  Verify that when we
4106      have optimizations that simplify statements such that we prove
4107      that they cannot throw, that we update other data structures
4108      to match.  */
4109   if (lookup_stmt_eh_region (stmt) >= 0)
4110     {
4111       if (!tree_could_throw_p (stmt))
4112         {
4113           error ("statement marked for throw, but doesn%'t");
4114           goto fail;
4115         }
4116       if (!last_in_block && tree_can_throw_internal (stmt))
4117         {
4118           error ("statement marked for throw in middle of block");
4119           goto fail;
4120         }
4121     }
4122
4123   return false;
4124
4125  fail:
4126   debug_generic_stmt (stmt);
4127   return true;
4128 }
4129
4130
4131 /* Return true when the T can be shared.  */
4132
4133 static bool
4134 tree_node_can_be_shared (tree t)
4135 {
4136   if (IS_TYPE_OR_DECL_P (t)
4137       || is_gimple_min_invariant (t)
4138       || TREE_CODE (t) == SSA_NAME
4139       || t == error_mark_node
4140       || TREE_CODE (t) == IDENTIFIER_NODE)
4141     return true;
4142
4143   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4144     return true;
4145
4146   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4147            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4148          || TREE_CODE (t) == COMPONENT_REF
4149          || TREE_CODE (t) == REALPART_EXPR
4150          || TREE_CODE (t) == IMAGPART_EXPR)
4151     t = TREE_OPERAND (t, 0);
4152
4153   if (DECL_P (t))
4154     return true;
4155
4156   return false;
4157 }
4158
4159
4160 /* Called via walk_trees.  Verify tree sharing.  */
4161
4162 static tree
4163 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
4164 {
4165   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4166
4167   if (tree_node_can_be_shared (*tp))
4168     {
4169       *walk_subtrees = false;
4170       return NULL;
4171     }
4172
4173   if (pointer_set_insert (visited, *tp))
4174     return *tp;
4175
4176   return NULL;
4177 }
4178
4179
4180 /* Helper function for verify_gimple_tuples.  */
4181
4182 static tree
4183 verify_gimple_tuples_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
4184                          void *data ATTRIBUTE_UNUSED)
4185 {
4186   switch (TREE_CODE (*tp))
4187     {
4188     case MODIFY_EXPR:
4189       error ("unexpected non-tuple");
4190       debug_tree (*tp);
4191       gcc_unreachable ();
4192       return NULL_TREE;
4193
4194     default:
4195       return NULL_TREE;
4196     }
4197 }
4198
4199 /* Verify that there are no trees that should have been converted to
4200    gimple tuples.  Return true if T contains a node that should have
4201    been converted to a gimple tuple, but hasn't.  */
4202
4203 static bool
4204 verify_gimple_tuples (tree t)
4205 {
4206   return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
4207 }
4208
4209 static bool eh_error_found;
4210 static int
4211 verify_eh_throw_stmt_node (void **slot, void *data)
4212 {
4213   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4214   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4215
4216   if (!pointer_set_contains (visited, node->stmt))
4217     {
4218       error ("Dead STMT in EH table");
4219       debug_generic_stmt (node->stmt);
4220       eh_error_found = true;
4221     }
4222   return 0;
4223 }
4224
4225 /* Verify the GIMPLE statement chain.  */
4226
4227 void
4228 verify_stmts (void)
4229 {
4230   basic_block bb;
4231   block_stmt_iterator bsi;
4232   bool err = false;
4233   struct pointer_set_t *visited, *visited_stmts;
4234   tree addr;
4235
4236   timevar_push (TV_TREE_STMT_VERIFY);
4237   visited = pointer_set_create ();
4238   visited_stmts = pointer_set_create ();
4239
4240   FOR_EACH_BB (bb)
4241     {
4242       tree phi;
4243       int i;
4244
4245       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4246         {
4247           int phi_num_args = PHI_NUM_ARGS (phi);
4248
4249           pointer_set_insert (visited_stmts, phi);
4250           if (bb_for_stmt (phi) != bb)
4251             {
4252               error ("bb_for_stmt (phi) is set to a wrong basic block");
4253               err |= true;
4254             }
4255
4256           for (i = 0; i < phi_num_args; i++)
4257             {
4258               tree t = PHI_ARG_DEF (phi, i);
4259               tree addr;
4260
4261               /* Addressable variables do have SSA_NAMEs but they
4262                  are not considered gimple values.  */
4263               if (TREE_CODE (t) != SSA_NAME
4264                   && TREE_CODE (t) != FUNCTION_DECL
4265                   && !is_gimple_val (t))
4266                 {
4267                   error ("PHI def is not a GIMPLE value");
4268                   debug_generic_stmt (phi);
4269                   debug_generic_stmt (t);
4270                   err |= true;
4271                 }
4272
4273               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
4274               if (addr)
4275                 {
4276                   debug_generic_stmt (addr);
4277                   err |= true;
4278                 }
4279
4280               addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4281               if (addr)
4282                 {
4283                   error ("incorrect sharing of tree nodes");
4284                   debug_generic_stmt (phi);
4285                   debug_generic_stmt (addr);
4286                   err |= true;
4287                 }
4288             }
4289         }
4290
4291       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4292         {
4293           tree stmt = bsi_stmt (bsi);
4294
4295           pointer_set_insert (visited_stmts, stmt);
4296           err |= verify_gimple_tuples (stmt);
4297
4298           if (bb_for_stmt (stmt) != bb)
4299             {
4300               error ("bb_for_stmt (stmt) is set to a wrong basic block");
4301               err |= true;
4302             }
4303
4304           bsi_next (&bsi);
4305           err |= verify_stmt (stmt, bsi_end_p (bsi));
4306           addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
4307           if (addr)
4308             {
4309               error ("incorrect sharing of tree nodes");
4310               debug_generic_stmt (stmt);
4311               debug_generic_stmt (addr);
4312               err |= true;
4313             }
4314         }
4315     }
4316   eh_error_found = false;
4317   if (get_eh_throw_stmt_table (cfun))
4318     htab_traverse (get_eh_throw_stmt_table (cfun),
4319                    verify_eh_throw_stmt_node,
4320                    visited_stmts);
4321
4322   if (err | eh_error_found)
4323     internal_error ("verify_stmts failed");
4324
4325   pointer_set_destroy (visited);
4326   pointer_set_destroy (visited_stmts);
4327   verify_histograms ();
4328   timevar_pop (TV_TREE_STMT_VERIFY);
4329 }
4330
4331
4332 /* Verifies that the flow information is OK.  */
4333
4334 static int
4335 tree_verify_flow_info (void)
4336 {
4337   int err = 0;
4338   basic_block bb;
4339   block_stmt_iterator bsi;
4340   tree stmt;
4341   edge e;
4342   edge_iterator ei;
4343
4344   if (ENTRY_BLOCK_PTR->il.tree)
4345     {
4346       error ("ENTRY_BLOCK has IL associated with it");
4347       err = 1;
4348     }
4349
4350   if (EXIT_BLOCK_PTR->il.tree)
4351     {
4352       error ("EXIT_BLOCK has IL associated with it");
4353       err = 1;
4354     }
4355
4356   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4357     if (e->flags & EDGE_FALLTHRU)
4358       {
4359         error ("fallthru to exit from bb %d", e->src->index);
4360         err = 1;
4361       }
4362
4363   FOR_EACH_BB (bb)
4364     {
4365       bool found_ctrl_stmt = false;
4366
4367       stmt = NULL_TREE;
4368
4369       /* Skip labels on the start of basic block.  */
4370       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4371         {
4372           tree prev_stmt = stmt;
4373
4374           stmt = bsi_stmt (bsi);
4375
4376           if (TREE_CODE (stmt) != LABEL_EXPR)
4377             break;
4378
4379           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
4380             {
4381               error ("nonlocal label ");
4382               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4383               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4384                        bb->index);
4385               err = 1;
4386             }
4387
4388           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
4389             {
4390               error ("label ");
4391               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4392               fprintf (stderr, " to block does not match in bb %d",
4393                        bb->index);
4394               err = 1;
4395             }
4396
4397           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
4398               != current_function_decl)
4399             {
4400               error ("label ");
4401               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4402               fprintf (stderr, " has incorrect context in bb %d",
4403                        bb->index);
4404               err = 1;
4405             }
4406         }
4407
4408       /* Verify that body of basic block BB is free of control flow.  */
4409       for (; !bsi_end_p (bsi); bsi_next (&bsi))
4410         {
4411           tree stmt = bsi_stmt (bsi);
4412
4413           if (found_ctrl_stmt)
4414             {
4415               error ("control flow in the middle of basic block %d",
4416                      bb->index);
4417               err = 1;
4418             }
4419
4420           if (stmt_ends_bb_p (stmt))
4421             found_ctrl_stmt = true;
4422
4423           if (TREE_CODE (stmt) == LABEL_EXPR)
4424             {
4425               error ("label ");
4426               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4427               fprintf (stderr, " in the middle of basic block %d", bb->index);
4428               err = 1;
4429             }
4430         }
4431
4432       bsi = bsi_last (bb);
4433       if (bsi_end_p (bsi))
4434         continue;
4435
4436       stmt = bsi_stmt (bsi);
4437
4438       err |= verify_eh_edges (stmt);
4439
4440       if (is_ctrl_stmt (stmt))
4441         {
4442           FOR_EACH_EDGE (e, ei, bb->succs)
4443             if (e->flags & EDGE_FALLTHRU)
4444               {
4445                 error ("fallthru edge after a control statement in bb %d",
4446                        bb->index);
4447                 err = 1;
4448               }
4449         }
4450
4451       if (TREE_CODE (stmt) != COND_EXPR)
4452         {
4453           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4454              after anything else but if statement.  */
4455           FOR_EACH_EDGE (e, ei, bb->succs)
4456             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4457               {
4458                 error ("true/false edge after a non-COND_EXPR in bb %d",
4459                        bb->index);
4460                 err = 1;
4461               }
4462         }
4463
4464       switch (TREE_CODE (stmt))
4465         {
4466         case COND_EXPR:
4467           {
4468             edge true_edge;
4469             edge false_edge;
4470
4471             if (COND_EXPR_THEN (stmt) != NULL_TREE
4472                 || COND_EXPR_ELSE (stmt) != NULL_TREE)
4473               {
4474                 error ("COND_EXPR with code in branches at the end of bb %d",
4475                        bb->index);
4476                 err = 1;
4477               }
4478
4479             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4480
4481             if (!true_edge || !false_edge
4482                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4483                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4484                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4485                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4486                 || EDGE_COUNT (bb->succs) >= 3)
4487               {
4488                 error ("wrong outgoing edge flags at end of bb %d",
4489                        bb->index);
4490                 err = 1;
4491               }
4492           }
4493           break;
4494
4495         case GOTO_EXPR:
4496           if (simple_goto_p (stmt))
4497             {
4498               error ("explicit goto at end of bb %d", bb->index);
4499               err = 1;
4500             }
4501           else
4502             {
4503               /* FIXME.  We should double check that the labels in the
4504                  destination blocks have their address taken.  */
4505               FOR_EACH_EDGE (e, ei, bb->succs)
4506                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4507                                  | EDGE_FALSE_VALUE))
4508                     || !(e->flags & EDGE_ABNORMAL))
4509                   {
4510                     error ("wrong outgoing edge flags at end of bb %d",
4511                            bb->index);
4512                     err = 1;
4513                   }
4514             }
4515           break;
4516
4517         case RETURN_EXPR:
4518           if (!single_succ_p (bb)
4519               || (single_succ_edge (bb)->flags
4520                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4521                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4522             {
4523               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4524               err = 1;
4525             }
4526           if (single_succ (bb) != EXIT_BLOCK_PTR)
4527             {
4528               error ("return edge does not point to exit in bb %d",
4529                      bb->index);
4530               err = 1;
4531             }
4532           break;
4533
4534         case SWITCH_EXPR:
4535           {
4536             tree prev;
4537             edge e;
4538             size_t i, n;
4539             tree vec;
4540
4541             vec = SWITCH_LABELS (stmt);
4542             n = TREE_VEC_LENGTH (vec);
4543
4544             /* Mark all the destination basic blocks.  */
4545             for (i = 0; i < n; ++i)
4546               {
4547                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4548                 basic_block label_bb = label_to_block (lab);
4549
4550                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4551                 label_bb->aux = (void *)1;
4552               }
4553
4554             /* Verify that the case labels are sorted.  */
4555             prev = TREE_VEC_ELT (vec, 0);
4556             for (i = 1; i < n - 1; ++i)
4557               {
4558                 tree c = TREE_VEC_ELT (vec, i);
4559                 if (! CASE_LOW (c))
4560                   {
4561                     error ("found default case not at end of case vector");
4562                     err = 1;
4563                     continue;
4564                   }
4565                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4566                   {
4567                     error ("case labels not sorted: ");
4568                     print_generic_expr (stderr, prev, 0);
4569                     fprintf (stderr," is greater than ");
4570                     print_generic_expr (stderr, c, 0);
4571                     fprintf (stderr," but comes before it.\n");
4572                     err = 1;
4573                   }
4574                 prev = c;
4575               }
4576             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
4577               {
4578                 error ("no default case found at end of case vector");
4579                 err = 1;
4580               }
4581
4582             FOR_EACH_EDGE (e, ei, bb->succs)
4583               {
4584                 if (!e->dest->aux)
4585                   {
4586                     error ("extra outgoing edge %d->%d",
4587                            bb->index, e->dest->index);
4588                     err = 1;
4589                   }
4590                 e->dest->aux = (void *)2;
4591                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4592                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4593                   {
4594                     error ("wrong outgoing edge flags at end of bb %d",
4595                            bb->index);
4596                     err = 1;
4597                   }
4598               }
4599
4600             /* Check that we have all of them.  */
4601             for (i = 0; i < n; ++i)
4602               {
4603                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4604                 basic_block label_bb = label_to_block (lab);
4605
4606                 if (label_bb->aux != (void *)2)
4607                   {
4608                     error ("missing edge %i->%i",
4609                            bb->index, label_bb->index);
4610                     err = 1;
4611                   }
4612               }
4613
4614             FOR_EACH_EDGE (e, ei, bb->succs)
4615               e->dest->aux = (void *)0;
4616           }
4617
4618         default: ;
4619         }
4620     }
4621
4622   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4623     verify_dominators (CDI_DOMINATORS);
4624
4625   return err;
4626 }
4627
4628
4629 /* Updates phi nodes after creating a forwarder block joined
4630    by edge FALLTHRU.  */
4631
4632 static void
4633 tree_make_forwarder_block (edge fallthru)
4634 {
4635   edge e;
4636   edge_iterator ei;
4637   basic_block dummy, bb;
4638   tree phi, new_phi, var;
4639
4640   dummy = fallthru->src;
4641   bb = fallthru->dest;
4642
4643   if (single_pred_p (bb))
4644     return;
4645
4646   /* If we redirected a branch we must create new PHI nodes at the
4647      start of BB.  */
4648   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
4649     {
4650       var = PHI_RESULT (phi);
4651       new_phi = create_phi_node (var, bb);
4652       SSA_NAME_DEF_STMT (var) = new_phi;
4653       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4654       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
4655     }
4656
4657   /* Ensure that the PHI node chain is in the same order.  */
4658   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
4659
4660   /* Add the arguments we have stored on edges.  */
4661   FOR_EACH_EDGE (e, ei, bb->preds)
4662     {
4663       if (e == fallthru)
4664         continue;
4665
4666       flush_pending_stmts (e);
4667     }
4668 }
4669
4670
4671 /* Return a non-special label in the head of basic block BLOCK.
4672    Create one if it doesn't exist.  */
4673
4674 tree
4675 tree_block_label (basic_block bb)
4676 {
4677   block_stmt_iterator i, s = bsi_start (bb);
4678   bool first = true;
4679   tree label, stmt;
4680
4681   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4682     {
4683       stmt = bsi_stmt (i);
4684       if (TREE_CODE (stmt) != LABEL_EXPR)
4685         break;
4686       label = LABEL_EXPR_LABEL (stmt);
4687       if (!DECL_NONLOCAL (label))
4688         {
4689           if (!first)
4690             bsi_move_before (&i, &s);
4691           return label;
4692         }
4693     }
4694
4695   label = create_artificial_label ();
4696   stmt = build1 (LABEL_EXPR, void_type_node, label);
4697   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4698   return label;
4699 }
4700
4701
4702 /* Attempt to perform edge redirection by replacing a possibly complex
4703    jump instruction by a goto or by removing the jump completely.
4704    This can apply only if all edges now point to the same block.  The
4705    parameters and return values are equivalent to
4706    redirect_edge_and_branch.  */
4707
4708 static edge
4709 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4710 {
4711   basic_block src = e->src;
4712   block_stmt_iterator b;
4713   tree stmt;
4714
4715   /* We can replace or remove a complex jump only when we have exactly
4716      two edges.  */
4717   if (EDGE_COUNT (src->succs) != 2
4718       /* Verify that all targets will be TARGET.  Specifically, the
4719          edge that is not E must also go to TARGET.  */
4720       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4721     return NULL;
4722
4723   b = bsi_last (src);
4724   if (bsi_end_p (b))
4725     return NULL;
4726   stmt = bsi_stmt (b);
4727
4728   if (TREE_CODE (stmt) == COND_EXPR
4729       || TREE_CODE (stmt) == SWITCH_EXPR)
4730     {
4731       bsi_remove (&b, true);
4732       e = ssa_redirect_edge (e, target);
4733       e->flags = EDGE_FALLTHRU;
4734       return e;
4735     }
4736
4737   return NULL;
4738 }
4739
4740
4741 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4742    edge representing the redirected branch.  */
4743
4744 static edge
4745 tree_redirect_edge_and_branch (edge e, basic_block dest)
4746 {
4747   basic_block bb = e->src;
4748   block_stmt_iterator bsi;
4749   edge ret;
4750   tree stmt;
4751
4752   if (e->flags & EDGE_ABNORMAL)
4753     return NULL;
4754
4755   if (e->src != ENTRY_BLOCK_PTR
4756       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4757     return ret;
4758
4759   if (e->dest == dest)
4760     return NULL;
4761
4762   bsi = bsi_last (bb);
4763   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4764
4765   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4766     {
4767     case COND_EXPR:
4768       /* For COND_EXPR, we only need to redirect the edge.  */
4769       break;
4770
4771     case GOTO_EXPR:
4772       /* No non-abnormal edges should lead from a non-simple goto, and
4773          simple ones should be represented implicitly.  */
4774       gcc_unreachable ();
4775
4776     case SWITCH_EXPR:
4777       {
4778         tree cases = get_cases_for_edge (e, stmt);
4779         tree label = tree_block_label (dest);
4780
4781         /* If we have a list of cases associated with E, then use it
4782            as it's a lot faster than walking the entire case vector.  */
4783         if (cases)
4784           {
4785             edge e2 = find_edge (e->src, dest);
4786             tree last, first;
4787
4788             first = cases;
4789             while (cases)
4790               {
4791                 last = cases;
4792                 CASE_LABEL (cases) = label;
4793                 cases = TREE_CHAIN (cases);
4794               }
4795
4796             /* If there was already an edge in the CFG, then we need
4797                to move all the cases associated with E to E2.  */
4798             if (e2)
4799               {
4800                 tree cases2 = get_cases_for_edge (e2, stmt);
4801
4802                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4803                 TREE_CHAIN (cases2) = first;
4804               }
4805           }
4806         else
4807           {
4808             tree vec = SWITCH_LABELS (stmt);
4809             size_t i, n = TREE_VEC_LENGTH (vec);
4810
4811             for (i = 0; i < n; i++)
4812               {
4813                 tree elt = TREE_VEC_ELT (vec, i);
4814
4815                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4816                   CASE_LABEL (elt) = label;
4817               }
4818           }
4819
4820         break;
4821       }
4822
4823     case RETURN_EXPR:
4824       bsi_remove (&bsi, true);
4825       e->flags |= EDGE_FALLTHRU;
4826       break;
4827
4828     case OMP_RETURN:
4829     case OMP_CONTINUE:
4830     case OMP_SECTIONS_SWITCH:
4831     case OMP_FOR:
4832       /* The edges from OMP constructs can be simply redirected.  */
4833       break;
4834
4835     default:
4836       /* Otherwise it must be a fallthru edge, and we don't need to
4837          do anything besides redirecting it.  */
4838       gcc_assert (e->flags & EDGE_FALLTHRU);
4839       break;
4840     }
4841
4842   /* Update/insert PHI nodes as necessary.  */
4843
4844   /* Now update the edges in the CFG.  */
4845   e = ssa_redirect_edge (e, dest);
4846
4847   return e;
4848 }
4849
4850 /* Returns true if it is possible to remove edge E by redirecting
4851    it to the destination of the other edge from E->src.  */
4852
4853 static bool
4854 tree_can_remove_branch_p (const_edge e)
4855 {
4856   if (e->flags & EDGE_ABNORMAL)
4857     return false;
4858
4859   return true;
4860 }
4861
4862 /* Simple wrapper, as we can always redirect fallthru edges.  */
4863
4864 static basic_block
4865 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4866 {
4867   e = tree_redirect_edge_and_branch (e, dest);
4868   gcc_assert (e);
4869
4870   return NULL;
4871 }
4872
4873
4874 /* Splits basic block BB after statement STMT (but at least after the
4875    labels).  If STMT is NULL, BB is split just after the labels.  */
4876
4877 static basic_block
4878 tree_split_block (basic_block bb, void *stmt)
4879 {
4880   block_stmt_iterator bsi;
4881   tree_stmt_iterator tsi_tgt;
4882   tree act, list;
4883   basic_block new_bb;
4884   edge e;
4885   edge_iterator ei;
4886
4887   new_bb = create_empty_bb (bb);
4888
4889   /* Redirect the outgoing edges.  */
4890   new_bb->succs = bb->succs;
4891   bb->succs = NULL;
4892   FOR_EACH_EDGE (e, ei, new_bb->succs)
4893     e->src = new_bb;
4894
4895   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4896     stmt = NULL;
4897
4898   /* Move everything from BSI to the new basic block.  */
4899   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4900     {
4901       act = bsi_stmt (bsi);
4902       if (TREE_CODE (act) == LABEL_EXPR)
4903         continue;
4904
4905       if (!stmt)
4906         break;
4907
4908       if (stmt == act)
4909         {
4910           bsi_next (&bsi);
4911           break;
4912         }
4913     }
4914
4915   if (bsi_end_p (bsi))
4916     return new_bb;
4917
4918   /* Split the statement list - avoid re-creating new containers as this
4919      brings ugly quadratic memory consumption in the inliner.
4920      (We are still quadratic since we need to update stmt BB pointers,
4921      sadly.)  */
4922   list = tsi_split_statement_list_before (&bsi.tsi);
4923   set_bb_stmt_list (new_bb, list);
4924   for (tsi_tgt = tsi_start (list);
4925        !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
4926     change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
4927
4928   return new_bb;
4929 }
4930
4931
4932 /* Moves basic block BB after block AFTER.  */
4933
4934 static bool
4935 tree_move_block_after (basic_block bb, basic_block after)
4936 {
4937   if (bb->prev_bb == after)
4938     return true;
4939
4940   unlink_block (bb);
4941   link_block (bb, after);
4942
4943   return true;
4944 }
4945
4946
4947 /* Return true if basic_block can be duplicated.  */
4948
4949 static bool
4950 tree_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
4951 {
4952   return true;
4953 }
4954
4955
4956 /* Create a duplicate of the basic block BB.  NOTE: This does not
4957    preserve SSA form.  */
4958
4959 static basic_block
4960 tree_duplicate_bb (basic_block bb)
4961 {
4962   basic_block new_bb;
4963   block_stmt_iterator bsi, bsi_tgt;
4964   tree phi;
4965
4966   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4967
4968   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4969      the incoming edges have not been setup yet.  */
4970   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4971     {
4972       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4973       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4974     }
4975
4976   /* Keep the chain of PHI nodes in the same order so that they can be
4977      updated by ssa_redirect_edge.  */
4978   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4979
4980   bsi_tgt = bsi_start (new_bb);
4981   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4982     {
4983       def_operand_p def_p;
4984       ssa_op_iter op_iter;
4985       tree stmt, copy;
4986       int region;
4987
4988       stmt = bsi_stmt (bsi);
4989       if (TREE_CODE (stmt) == LABEL_EXPR)
4990         continue;
4991
4992       /* Create a new copy of STMT and duplicate STMT's virtual
4993          operands.  */
4994       copy = unshare_expr (stmt);
4995       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4996       copy_virtual_operands (copy, stmt);
4997       region = lookup_stmt_eh_region (stmt);
4998       if (region >= 0)
4999         add_stmt_to_eh_region (copy, region);
5000       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5001
5002       /* Create new names for all the definitions created by COPY and
5003          add replacement mappings for each new name.  */
5004       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5005         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5006     }
5007
5008   return new_bb;
5009 }
5010
5011
5012 /* Basic block BB_COPY was created by code duplication.  Add phi node
5013    arguments for edges going out of BB_COPY.  The blocks that were
5014    duplicated have BB_DUPLICATED set.  */
5015
5016 void
5017 add_phi_args_after_copy_bb (basic_block bb_copy)
5018 {
5019   basic_block bb, dest;
5020   edge e, e_copy;
5021   edge_iterator ei;
5022   tree phi, phi_copy, phi_next, def;
5023
5024   bb = get_bb_original (bb_copy);
5025
5026   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5027     {
5028       if (!phi_nodes (e_copy->dest))
5029         continue;
5030
5031       if (e_copy->dest->flags & BB_DUPLICATED)
5032         dest = get_bb_original (e_copy->dest);
5033       else
5034         dest = e_copy->dest;
5035
5036       e = find_edge (bb, dest);
5037       if (!e)
5038         {
5039           /* During loop unrolling the target of the latch edge is copied.
5040              In this case we are not looking for edge to dest, but to
5041              duplicated block whose original was dest.  */
5042           FOR_EACH_EDGE (e, ei, bb->succs)
5043             if ((e->dest->flags & BB_DUPLICATED)
5044                 && get_bb_original (e->dest) == dest)
5045               break;
5046
5047           gcc_assert (e != NULL);
5048         }
5049
5050       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
5051            phi;
5052            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
5053         {
5054           phi_next = PHI_CHAIN (phi);
5055           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5056           add_phi_arg (phi_copy, def, e_copy);
5057         }
5058     }
5059 }
5060
5061 /* Blocks in REGION_COPY array of length N_REGION were created by
5062    duplication of basic blocks.  Add phi node arguments for edges
5063    going from these blocks.  */
5064
5065 void
5066 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
5067 {
5068   unsigned i;
5069
5070   for (i = 0; i < n_region; i++)
5071     region_copy[i]->flags |= BB_DUPLICATED;
5072
5073   for (i = 0; i < n_region; i++)
5074     add_phi_args_after_copy_bb (region_copy[i]);
5075
5076   for (i = 0; i < n_region; i++)
5077     region_copy[i]->flags &= ~BB_DUPLICATED;
5078 }
5079
5080 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5081    important exit edge EXIT.  By important we mean that no SSA name defined
5082    inside region is live over the other exit edges of the region.  All entry
5083    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5084    to the duplicate of the region.  SSA form, dominance and loop information
5085    is updated.  The new basic blocks are stored to REGION_COPY in the same
5086    order as they had in REGION, provided that REGION_COPY is not NULL.
5087    The function returns false if it is unable to copy the region,
5088    true otherwise.  */
5089
5090 bool
5091 tree_duplicate_sese_region (edge entry, edge exit,
5092                             basic_block *region, unsigned n_region,
5093                             basic_block *region_copy)
5094 {
5095   unsigned i;
5096   bool free_region_copy = false, copying_header = false;
5097   struct loop *loop = entry->dest->loop_father;
5098   edge exit_copy;
5099   VEC (basic_block, heap) *doms;
5100   edge redirected;
5101   int total_freq = 0, entry_freq = 0;
5102   gcov_type total_count = 0, entry_count = 0;
5103
5104   if (!can_copy_bbs_p (region, n_region))
5105     return false;
5106
5107   /* Some sanity checking.  Note that we do not check for all possible
5108      missuses of the functions.  I.e. if you ask to copy something weird,
5109      it will work, but the state of structures probably will not be
5110      correct.  */
5111   for (i = 0; i < n_region; i++)
5112     {
5113       /* We do not handle subloops, i.e. all the blocks must belong to the
5114          same loop.  */
5115       if (region[i]->loop_father != loop)
5116         return false;
5117
5118       if (region[i] != entry->dest
5119           && region[i] == loop->header)
5120         return false;
5121     }
5122
5123   set_loop_copy (loop, loop);
5124
5125   /* In case the function is used for loop header copying (which is the primary
5126      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5127   if (loop->header == entry->dest)
5128     {
5129       copying_header = true;
5130       set_loop_copy (loop, loop_outer (loop));
5131
5132       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5133         return false;
5134
5135       for (i = 0; i < n_region; i++)
5136         if (region[i] != exit->src
5137             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5138           return false;
5139     }
5140
5141   if (!region_copy)
5142     {
5143       region_copy = XNEWVEC (basic_block, n_region);
5144       free_region_copy = true;
5145     }
5146
5147   gcc_assert (!need_ssa_update_p ());
5148
5149   /* Record blocks outside the region that are dominated by something
5150      inside.  */
5151   doms = NULL;
5152   initialize_original_copy_tables ();
5153
5154   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5155
5156   if (entry->dest->count)
5157     {
5158       total_count = entry->dest->count;
5159       entry_count = entry->count;
5160       /* Fix up corner cases, to avoid division by zero or creation of negative
5161          frequencies.  */
5162       if (entry_count > total_count)
5163         entry_count = total_count;
5164     }
5165   else
5166     {
5167       total_freq = entry->dest->frequency;
5168       entry_freq = EDGE_FREQUENCY (entry);
5169       /* Fix up corner cases, to avoid division by zero or creation of negative
5170          frequencies.  */
5171       if (total_freq == 0)
5172         total_freq = 1;
5173       else if (entry_freq > total_freq)
5174         entry_freq = total_freq;
5175     }
5176
5177   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5178             split_edge_bb_loc (entry));
5179   if (total_count)
5180     {
5181       scale_bbs_frequencies_gcov_type (region, n_region,
5182                                        total_count - entry_count,
5183                                        total_count);
5184       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5185                                        total_count);
5186     }
5187   else
5188     {
5189       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5190                                  total_freq);
5191       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5192     }
5193
5194   if (copying_header)
5195     {
5196       loop->header = exit->dest;
5197       loop->latch = exit->src;
5198     }
5199
5200   /* Redirect the entry and add the phi node arguments.  */
5201   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5202   gcc_assert (redirected != NULL);
5203   flush_pending_stmts (entry);
5204
5205   /* Concerning updating of dominators:  We must recount dominators
5206      for entry block and its copy.  Anything that is outside of the
5207      region, but was dominated by something inside needs recounting as
5208      well.  */
5209   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5210   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5211   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5212   free (doms);
5213
5214   /* Add the other PHI node arguments.  */
5215   add_phi_args_after_copy (region_copy, n_region);
5216
5217   /* Update the SSA web.  */
5218   update_ssa (TODO_update_ssa);
5219
5220   if (free_region_copy)
5221     free (region_copy);
5222
5223   free_original_copy_tables ();
5224   return true;
5225 }
5226
5227 /*
5228 DEF_VEC_P(basic_block);
5229 DEF_VEC_ALLOC_P(basic_block,heap);
5230 */
5231
5232 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5233    adding blocks when the dominator traversal reaches EXIT.  This
5234    function silently assumes that ENTRY strictly dominates EXIT.  */
5235
5236 static void
5237 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5238                               VEC(basic_block,heap) **bbs_p)
5239 {
5240   basic_block son;
5241
5242   for (son = first_dom_son (CDI_DOMINATORS, entry);
5243        son;
5244        son = next_dom_son (CDI_DOMINATORS, son))
5245     {
5246       VEC_safe_push (basic_block, heap, *bbs_p, son);
5247       if (son != exit)
5248         gather_blocks_in_sese_region (son, exit, bbs_p);
5249     }
5250 }
5251
5252 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5253    The duplicates are recorded in VARS_MAP.  */
5254
5255 static void
5256 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5257                            tree to_context)
5258 {
5259   tree t = *tp, new_t;
5260   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5261   void **loc;
5262
5263   if (DECL_CONTEXT (t) == to_context)
5264     return;
5265
5266   loc = pointer_map_contains (vars_map, t);
5267
5268   if (!loc)
5269     {
5270       loc = pointer_map_insert (vars_map, t);
5271
5272       if (SSA_VAR_P (t))
5273         {
5274           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5275           f->unexpanded_var_list
5276                   = tree_cons (NULL_TREE, new_t, f->unexpanded_var_list);
5277         }
5278       else
5279         {
5280           gcc_assert (TREE_CODE (t) == CONST_DECL);
5281           new_t = copy_node (t);
5282         }
5283       DECL_CONTEXT (new_t) = to_context;
5284
5285       *loc = new_t;
5286     }
5287   else
5288     new_t = *loc;
5289
5290   *tp = new_t;
5291 }
5292
5293 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5294    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5295
5296 static tree
5297 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5298                   tree to_context)
5299 {
5300   void **loc;
5301   tree new_name, decl = SSA_NAME_VAR (name);
5302
5303   gcc_assert (is_gimple_reg (name));
5304
5305   loc = pointer_map_contains (vars_map, name);
5306
5307   if (!loc)
5308     {
5309       replace_by_duplicate_decl (&decl, vars_map, to_context);
5310
5311       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5312       if (gimple_in_ssa_p (cfun))
5313         add_referenced_var (decl);
5314
5315       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5316       if (SSA_NAME_IS_DEFAULT_DEF (name))
5317         set_default_def (decl, new_name);
5318       pop_cfun ();
5319
5320       loc = pointer_map_insert (vars_map, name);
5321       *loc = new_name;
5322     }
5323   else
5324     new_name = *loc;
5325
5326   return new_name;
5327 }
5328
5329 struct move_stmt_d
5330 {
5331   tree block;
5332   tree from_context;
5333   tree to_context;
5334   struct pointer_map_t *vars_map;
5335   htab_t new_label_map;
5336   bool remap_decls_p;
5337 };
5338
5339 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5340    contained in *TP and change the DECL_CONTEXT of every local
5341    variable referenced in *TP.  */
5342
5343 static tree
5344 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
5345 {
5346   struct move_stmt_d *p = (struct move_stmt_d *) data;
5347   tree t = *tp;
5348
5349   if (p->block
5350       && (EXPR_P (t) || GIMPLE_STMT_P (t)))
5351     TREE_BLOCK (t) = p->block;
5352
5353   if (OMP_DIRECTIVE_P (t)
5354       && TREE_CODE (t) != OMP_RETURN
5355       && TREE_CODE (t) != OMP_CONTINUE)
5356     {
5357       /* Do not remap variables inside OMP directives.  Variables
5358          referenced in clauses and directive header belong to the
5359          parent function and should not be moved into the child
5360          function.  */
5361       bool save_remap_decls_p = p->remap_decls_p;
5362       p->remap_decls_p = false;
5363       *walk_subtrees = 0;
5364
5365       walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
5366
5367       p->remap_decls_p = save_remap_decls_p;
5368     }
5369   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5370     {
5371       if (TREE_CODE (t) == SSA_NAME)
5372         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5373       else if (TREE_CODE (t) == LABEL_DECL)
5374         {
5375           if (p->new_label_map)
5376             {
5377               struct tree_map in, *out;
5378               in.base.from = t;
5379               out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5380               if (out)
5381                 *tp = t = out->to;
5382             }
5383
5384           DECL_CONTEXT (t) = p->to_context;
5385         }
5386       else if (p->remap_decls_p)
5387         {
5388           /* Replace T with its duplicate.  T should no longer appear in the
5389              parent function, so this looks wasteful; however, it may appear
5390              in referenced_vars, and more importantly, as virtual operands of
5391              statements, and in alias lists of other variables.  It would be
5392              quite difficult to expunge it from all those places.  ??? It might
5393              suffice to do this for addressable variables.  */
5394           if ((TREE_CODE (t) == VAR_DECL
5395                && !is_global_var (t))
5396               || TREE_CODE (t) == CONST_DECL)
5397             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5398
5399           if (SSA_VAR_P (t)
5400               && gimple_in_ssa_p (cfun))
5401             {
5402               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5403               add_referenced_var (*tp);
5404               pop_cfun ();
5405             }
5406         }
5407       *walk_subtrees = 0;
5408     }
5409   else if (TYPE_P (t))
5410     *walk_subtrees = 0;
5411
5412   return NULL_TREE;
5413 }
5414
5415 /* Marks virtual operands of all statements in basic blocks BBS for
5416    renaming.  */
5417
5418 static void
5419 mark_virtual_ops_in_region (VEC (basic_block,heap) *bbs)
5420 {
5421   tree phi;
5422   block_stmt_iterator bsi;
5423   basic_block bb;
5424   unsigned i;
5425
5426   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5427     {
5428       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5429         mark_virtual_ops_for_renaming (phi);
5430
5431       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5432         mark_virtual_ops_for_renaming (bsi_stmt (bsi));
5433     }
5434 }
5435
5436 /* Move basic block BB from function CFUN to function DEST_FN.  The
5437    block is moved out of the original linked list and placed after
5438    block AFTER in the new list.  Also, the block is removed from the
5439    original array of blocks and placed in DEST_FN's array of blocks.
5440    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5441    updated to reflect the moved edges.
5442
5443    The local variables are remapped to new instances, VARS_MAP is used
5444    to record the mapping.  */
5445
5446 static void
5447 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5448                   basic_block after, bool update_edge_count_p,
5449                   struct pointer_map_t *vars_map, htab_t new_label_map,
5450                   int eh_offset)
5451 {
5452   struct control_flow_graph *cfg;
5453   edge_iterator ei;
5454   edge e;
5455   block_stmt_iterator si;
5456   struct move_stmt_d d;
5457   unsigned old_len, new_len;
5458   tree phi;
5459
5460   /* Remove BB from dominance structures.  */
5461   delete_from_dominance_info (CDI_DOMINATORS, bb);
5462
5463   /* Link BB to the new linked list.  */
5464   move_block_after (bb, after);
5465
5466   /* Update the edge count in the corresponding flowgraphs.  */
5467   if (update_edge_count_p)
5468     FOR_EACH_EDGE (e, ei, bb->succs)
5469       {
5470         cfun->cfg->x_n_edges--;
5471         dest_cfun->cfg->x_n_edges++;
5472       }
5473
5474   /* Remove BB from the original basic block array.  */
5475   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5476   cfun->cfg->x_n_basic_blocks--;
5477
5478   /* Grow DEST_CFUN's basic block array if needed.  */
5479   cfg = dest_cfun->cfg;
5480   cfg->x_n_basic_blocks++;
5481   if (bb->index >= cfg->x_last_basic_block)
5482     cfg->x_last_basic_block = bb->index + 1;
5483
5484   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5485   if ((unsigned) cfg->x_last_basic_block >= old_len)
5486     {
5487       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5488       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5489                              new_len);
5490     }
5491
5492   VEC_replace (basic_block, cfg->x_basic_block_info,
5493                bb->index, bb);
5494
5495   /* Remap the variables in phi nodes.  */
5496   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5497     {
5498       use_operand_p use;
5499       tree op = PHI_RESULT (phi);
5500       ssa_op_iter oi;
5501
5502       if (!is_gimple_reg (op))
5503         continue;
5504
5505       SET_PHI_RESULT (phi, replace_ssa_name (op, vars_map, dest_cfun->decl));
5506       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5507         {
5508           op = USE_FROM_PTR (use);
5509           if (TREE_CODE (op) == SSA_NAME)
5510             SET_USE (use, replace_ssa_name (op, vars_map, dest_cfun->decl));
5511         }
5512     }
5513
5514   /* The statements in BB need to be associated with a new TREE_BLOCK.
5515      Labels need to be associated with a new label-to-block map.  */
5516   memset (&d, 0, sizeof (d));
5517   d.vars_map = vars_map;
5518   d.from_context = cfun->decl;
5519   d.to_context = dest_cfun->decl;
5520   d.new_label_map = new_label_map;
5521
5522   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5523     {
5524       tree stmt = bsi_stmt (si);
5525       int region;
5526
5527       d.remap_decls_p = true;
5528       if (TREE_BLOCK (stmt))
5529         d.block = DECL_INITIAL (dest_cfun->decl);
5530
5531       walk_tree (&stmt, move_stmt_r, &d, NULL);
5532
5533       if (TREE_CODE (stmt) == LABEL_EXPR)
5534         {
5535           tree label = LABEL_EXPR_LABEL (stmt);
5536           int uid = LABEL_DECL_UID (label);
5537
5538           gcc_assert (uid > -1);
5539
5540           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5541           if (old_len <= (unsigned) uid)
5542             {
5543               new_len = 3 * uid / 2;
5544               VEC_safe_grow_cleared (basic_block, gc,
5545                                      cfg->x_label_to_block_map, new_len);
5546             }
5547
5548           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5549           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5550
5551           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5552
5553           if (uid >= dest_cfun->last_label_uid)
5554             dest_cfun->last_label_uid = uid + 1;
5555         }
5556       else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
5557         TREE_OPERAND (stmt, 0) =
5558           build_int_cst (NULL_TREE,
5559                          TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
5560                          + eh_offset);
5561
5562       region = lookup_stmt_eh_region (stmt);
5563       if (region >= 0)
5564         {
5565           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5566           remove_stmt_from_eh_region (stmt);
5567           gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5568           gimple_remove_stmt_histograms (cfun, stmt);
5569         }
5570
5571       update_stmt (stmt);
5572     }
5573 }
5574
5575 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5576    the outermost EH region.  Use REGION as the incoming base EH region.  */
5577
5578 static int
5579 find_outermost_region_in_block (struct function *src_cfun,
5580                                 basic_block bb, int region)
5581 {
5582   block_stmt_iterator si;
5583
5584   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5585     {
5586       tree stmt = bsi_stmt (si);
5587       int stmt_region;
5588
5589       if (TREE_CODE (stmt) == RESX_EXPR)
5590         stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
5591       else
5592         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5593       if (stmt_region > 0)
5594         {
5595           if (region < 0)
5596             region = stmt_region;
5597           else if (stmt_region != region)
5598             {
5599               region = eh_region_outermost (src_cfun, stmt_region, region);
5600               gcc_assert (region != -1);
5601             }
5602         }
5603     }
5604
5605   return region;
5606 }
5607
5608 static tree
5609 new_label_mapper (tree decl, void *data)
5610 {
5611   htab_t hash = (htab_t) data;
5612   struct tree_map *m;
5613   void **slot;
5614
5615   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5616
5617   m = xmalloc (sizeof (struct tree_map));
5618   m->hash = DECL_UID (decl);
5619   m->base.from = decl;
5620   m->to = create_artificial_label ();
5621   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5622
5623   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5624   gcc_assert (*slot == NULL);
5625
5626   *slot = m;
5627
5628   return m->to;
5629 }
5630
5631 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5632    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
5633    single basic block in the original CFG and the new basic block is
5634    returned.  DEST_CFUN must not have a CFG yet.
5635
5636    Note that the region need not be a pure SESE region.  Blocks inside
5637    the region may contain calls to abort/exit.  The only restriction
5638    is that ENTRY_BB should be the only entry point and it must
5639    dominate EXIT_BB.
5640
5641    All local variables referenced in the region are assumed to be in
5642    the corresponding BLOCK_VARS and unexpanded variable lists
5643    associated with DEST_CFUN.  */
5644
5645 basic_block
5646 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5647                         basic_block exit_bb)
5648 {
5649   VEC(basic_block,heap) *bbs, *dom_bbs;
5650   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5651   basic_block after, bb, *entry_pred, *exit_succ, abb;
5652   struct function *saved_cfun = cfun;
5653   int *entry_flag, *exit_flag, eh_offset;
5654   unsigned *entry_prob, *exit_prob;
5655   unsigned i, num_entry_edges, num_exit_edges;
5656   edge e;
5657   edge_iterator ei;
5658   htab_t new_label_map;
5659   struct pointer_map_t *vars_map;
5660
5661   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5662      region.  */
5663   gcc_assert (entry_bb != exit_bb
5664               && (!exit_bb
5665                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5666
5667   /* Collect all the blocks in the region.  Manually add ENTRY_BB
5668      because it won't be added by dfs_enumerate_from.  */
5669   bbs = NULL;
5670   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5671   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5672
5673   /* The blocks that used to be dominated by something in BBS will now be
5674      dominated by the new block.  */
5675   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5676                                      VEC_address (basic_block, bbs),
5677                                      VEC_length (basic_block, bbs));
5678
5679   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
5680      the predecessor edges to ENTRY_BB and the successor edges to
5681      EXIT_BB so that we can re-attach them to the new basic block that
5682      will replace the region.  */
5683   num_entry_edges = EDGE_COUNT (entry_bb->preds);
5684   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5685   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5686   entry_prob = XNEWVEC (unsigned, num_entry_edges);
5687   i = 0;
5688   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5689     {
5690       entry_prob[i] = e->probability;
5691       entry_flag[i] = e->flags;
5692       entry_pred[i++] = e->src;
5693       remove_edge (e);
5694     }
5695
5696   if (exit_bb)
5697     {
5698       num_exit_edges = EDGE_COUNT (exit_bb->succs);
5699       exit_succ = (basic_block *) xcalloc (num_exit_edges,
5700                                            sizeof (basic_block));
5701       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
5702       exit_prob = XNEWVEC (unsigned, num_exit_edges);
5703       i = 0;
5704       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
5705         {
5706           exit_prob[i] = e->probability;
5707           exit_flag[i] = e->flags;
5708           exit_succ[i++] = e->dest;
5709           remove_edge (e);
5710         }
5711     }
5712   else
5713     {
5714       num_exit_edges = 0;
5715       exit_succ = NULL;
5716       exit_flag = NULL;
5717       exit_prob = NULL;
5718     }
5719
5720   /* Switch context to the child function to initialize DEST_FN's CFG.  */
5721   gcc_assert (dest_cfun->cfg == NULL);
5722   push_cfun (dest_cfun);
5723
5724   init_empty_tree_cfg ();
5725
5726   /* Initialize EH information for the new function.  */
5727   eh_offset = 0;
5728   new_label_map = NULL;
5729   if (saved_cfun->eh)
5730     {
5731       int region = -1;
5732
5733       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5734         region = find_outermost_region_in_block (saved_cfun, bb, region);
5735
5736       init_eh_for_function ();
5737       if (region != -1)
5738         {
5739           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
5740           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
5741                                             new_label_map, region, 0);
5742         }
5743     }
5744
5745   pop_cfun ();
5746
5747   /* The ssa form for virtual operands in the source function will have to
5748      be repaired.  We do not care for the real operands -- the sese region
5749      must be closed with respect to those.  */
5750   mark_virtual_ops_in_region (bbs);
5751
5752   /* Move blocks from BBS into DEST_CFUN.  */
5753   gcc_assert (VEC_length (basic_block, bbs) >= 2);
5754   after = dest_cfun->cfg->x_entry_block_ptr;
5755   vars_map = pointer_map_create ();
5756   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5757     {
5758       /* No need to update edge counts on the last block.  It has
5759          already been updated earlier when we detached the region from
5760          the original CFG.  */
5761       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_map,
5762                         new_label_map, eh_offset);
5763       after = bb;
5764     }
5765
5766   if (new_label_map)
5767     htab_delete (new_label_map);
5768   pointer_map_destroy (vars_map);
5769
5770   /* Rewire the entry and exit blocks.  The successor to the entry
5771      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
5772      the child function.  Similarly, the predecessor of DEST_FN's
5773      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
5774      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
5775      various CFG manipulation function get to the right CFG.
5776
5777      FIXME, this is silly.  The CFG ought to become a parameter to
5778      these helpers.  */
5779   push_cfun (dest_cfun);
5780   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
5781   if (exit_bb)
5782     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
5783   pop_cfun ();
5784
5785   /* Back in the original function, the SESE region has disappeared,
5786      create a new basic block in its place.  */
5787   bb = create_empty_bb (entry_pred[0]);
5788   for (i = 0; i < num_entry_edges; i++)
5789     {
5790       e = make_edge (entry_pred[i], bb, entry_flag[i]);
5791       e->probability = entry_prob[i];
5792     }
5793
5794   for (i = 0; i < num_exit_edges; i++)
5795     {
5796       e = make_edge (bb, exit_succ[i], exit_flag[i]);
5797       e->probability = exit_prob[i];
5798     }
5799
5800   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
5801   for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
5802     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
5803   VEC_free (basic_block, heap, dom_bbs);
5804
5805   if (exit_bb)
5806     {
5807       free (exit_prob);
5808       free (exit_flag);
5809       free (exit_succ);
5810     }
5811   free (entry_prob);
5812   free (entry_flag);
5813   free (entry_pred);
5814   VEC_free (basic_block, heap, bbs);
5815
5816   return bb;
5817 }
5818
5819
5820 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
5821
5822 void
5823 dump_function_to_file (tree fn, FILE *file, int flags)
5824 {
5825   tree arg, vars, var;
5826   struct function *dsf;
5827   bool ignore_topmost_bind = false, any_var = false;
5828   basic_block bb;
5829   tree chain;
5830
5831   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
5832
5833   arg = DECL_ARGUMENTS (fn);
5834   while (arg)
5835     {
5836       print_generic_expr (file, arg, dump_flags);
5837       if (TREE_CHAIN (arg))
5838         fprintf (file, ", ");
5839       arg = TREE_CHAIN (arg);
5840     }
5841   fprintf (file, ")\n");
5842
5843   dsf = DECL_STRUCT_FUNCTION (fn);
5844   if (dsf && (flags & TDF_DETAILS))
5845     dump_eh_tree (file, dsf);
5846
5847   if (flags & TDF_RAW)
5848     {
5849       dump_node (fn, TDF_SLIM | flags, file);
5850       return;
5851     }
5852
5853   /* Switch CFUN to point to FN.  */
5854   push_cfun (DECL_STRUCT_FUNCTION (fn));
5855
5856   /* When GIMPLE is lowered, the variables are no longer available in
5857      BIND_EXPRs, so display them separately.  */
5858   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
5859     {
5860       ignore_topmost_bind = true;
5861
5862       fprintf (file, "{\n");
5863       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
5864         {
5865           var = TREE_VALUE (vars);
5866
5867           print_generic_decl (file, var, flags);
5868           fprintf (file, "\n");
5869
5870           any_var = true;
5871         }
5872     }
5873
5874   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5875     {
5876       /* Make a CFG based dump.  */
5877       check_bb_profile (ENTRY_BLOCK_PTR, file);
5878       if (!ignore_topmost_bind)
5879         fprintf (file, "{\n");
5880
5881       if (any_var && n_basic_blocks)
5882         fprintf (file, "\n");
5883
5884       FOR_EACH_BB (bb)
5885         dump_generic_bb (file, bb, 2, flags);
5886
5887       fprintf (file, "}\n");
5888       check_bb_profile (EXIT_BLOCK_PTR, file);
5889     }
5890   else
5891     {
5892       int indent;
5893
5894       /* Make a tree based dump.  */
5895       chain = DECL_SAVED_TREE (fn);
5896
5897       if (chain && TREE_CODE (chain) == BIND_EXPR)
5898         {
5899           if (ignore_topmost_bind)
5900             {
5901               chain = BIND_EXPR_BODY (chain);
5902               indent = 2;
5903             }
5904           else
5905             indent = 0;
5906         }
5907       else
5908         {
5909           if (!ignore_topmost_bind)
5910             fprintf (file, "{\n");
5911           indent = 2;
5912         }
5913
5914       if (any_var)
5915         fprintf (file, "\n");
5916
5917       print_generic_stmt_indented (file, chain, flags, indent);
5918       if (ignore_topmost_bind)
5919         fprintf (file, "}\n");
5920     }
5921
5922   fprintf (file, "\n\n");
5923
5924   /* Restore CFUN.  */
5925   pop_cfun ();
5926 }
5927
5928
5929 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5930
5931 void
5932 debug_function (tree fn, int flags)
5933 {
5934   dump_function_to_file (fn, stderr, flags);
5935 }
5936
5937
5938 /* Pretty print of the loops intermediate representation.  */
5939 static void print_loop (FILE *, struct loop *, int);
5940 static void print_pred_bbs (FILE *, basic_block bb);
5941 static void print_succ_bbs (FILE *, basic_block bb);
5942
5943
5944 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5945
5946 static void
5947 print_pred_bbs (FILE *file, basic_block bb)
5948 {
5949   edge e;
5950   edge_iterator ei;
5951
5952   FOR_EACH_EDGE (e, ei, bb->preds)
5953     fprintf (file, "bb_%d ", e->src->index);
5954 }
5955
5956
5957 /* Print on FILE the indexes for the successors of basic_block BB.  */
5958
5959 static void
5960 print_succ_bbs (FILE *file, basic_block bb)
5961 {
5962   edge e;
5963   edge_iterator ei;
5964
5965   FOR_EACH_EDGE (e, ei, bb->succs)
5966     fprintf (file, "bb_%d ", e->dest->index);
5967 }
5968
5969
5970 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5971
5972 static void
5973 print_loop (FILE *file, struct loop *loop, int indent)
5974 {
5975   char *s_indent;
5976   basic_block bb;
5977
5978   if (loop == NULL)
5979     return;
5980
5981   s_indent = (char *) alloca ((size_t) indent + 1);
5982   memset ((void *) s_indent, ' ', (size_t) indent);
5983   s_indent[indent] = '\0';
5984
5985   /* Print the loop's header.  */
5986   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5987
5988   /* Print the loop's body.  */
5989   fprintf (file, "%s{\n", s_indent);
5990   FOR_EACH_BB (bb)
5991     if (bb->loop_father == loop)
5992       {
5993         /* Print the basic_block's header.  */
5994         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5995         print_pred_bbs (file, bb);
5996         fprintf (file, "}, succs = {");
5997         print_succ_bbs (file, bb);
5998         fprintf (file, "})\n");
5999
6000         /* Print the basic_block's body.  */
6001         fprintf (file, "%s  {\n", s_indent);
6002         tree_dump_bb (bb, file, indent + 4);
6003         fprintf (file, "%s  }\n", s_indent);
6004       }
6005
6006   print_loop (file, loop->inner, indent + 2);
6007   fprintf (file, "%s}\n", s_indent);
6008   print_loop (file, loop->next, indent);
6009 }
6010
6011
6012 /* Follow a CFG edge from the entry point of the program, and on entry
6013    of a loop, pretty print the loop structure on FILE.  */
6014
6015 void
6016 print_loop_ir (FILE *file)
6017 {
6018   basic_block bb;
6019
6020   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
6021   if (bb && bb->loop_father)
6022     print_loop (file, bb->loop_father, 0);
6023 }
6024
6025
6026 /* Debugging loops structure at tree level.  */
6027
6028 void
6029 debug_loop_ir (void)
6030 {
6031   print_loop_ir (stderr);
6032 }
6033
6034
6035 /* Return true if BB ends with a call, possibly followed by some
6036    instructions that must stay with the call.  Return false,
6037    otherwise.  */
6038
6039 static bool
6040 tree_block_ends_with_call_p (const_basic_block bb)
6041 {
6042   const_block_stmt_iterator bsi = cbsi_last (bb);
6043   return const_get_call_expr_in (cbsi_stmt (bsi)) != NULL;
6044 }
6045
6046
6047 /* Return true if BB ends with a conditional branch.  Return false,
6048    otherwise.  */
6049
6050 static bool
6051 tree_block_ends_with_condjump_p (const_basic_block bb)
6052 {
6053   /* This CONST_CAST is okay because last_stmt doesn't modify its
6054      argument and the return value is not modified.  */
6055   const_tree stmt = last_stmt (CONST_CAST_BB(bb));
6056   return (stmt && TREE_CODE (stmt) == COND_EXPR);
6057 }
6058
6059
6060 /* Return true if we need to add fake edge to exit at statement T.
6061    Helper function for tree_flow_call_edges_add.  */
6062
6063 static bool
6064 need_fake_edge_p (tree t)
6065 {
6066   tree call;
6067
6068   /* NORETURN and LONGJMP calls already have an edge to exit.
6069      CONST and PURE calls do not need one.
6070      We don't currently check for CONST and PURE here, although
6071      it would be a good idea, because those attributes are
6072      figured out from the RTL in mark_constant_function, and
6073      the counter incrementation code from -fprofile-arcs
6074      leads to different results from -fbranch-probabilities.  */
6075   call = get_call_expr_in (t);
6076   if (call
6077       && !(call_expr_flags (call) & ECF_NORETURN))
6078     return true;
6079
6080   if (TREE_CODE (t) == ASM_EXPR
6081        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
6082     return true;
6083
6084   return false;
6085 }
6086
6087
6088 /* Add fake edges to the function exit for any non constant and non
6089    noreturn calls, volatile inline assembly in the bitmap of blocks
6090    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6091    the number of blocks that were split.
6092
6093    The goal is to expose cases in which entering a basic block does
6094    not imply that all subsequent instructions must be executed.  */
6095
6096 static int
6097 tree_flow_call_edges_add (sbitmap blocks)
6098 {
6099   int i;
6100   int blocks_split = 0;
6101   int last_bb = last_basic_block;
6102   bool check_last_block = false;
6103
6104   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6105     return 0;
6106
6107   if (! blocks)
6108     check_last_block = true;
6109   else
6110     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6111
6112   /* In the last basic block, before epilogue generation, there will be
6113      a fallthru edge to EXIT.  Special care is required if the last insn
6114      of the last basic block is a call because make_edge folds duplicate
6115      edges, which would result in the fallthru edge also being marked
6116      fake, which would result in the fallthru edge being removed by
6117      remove_fake_edges, which would result in an invalid CFG.
6118
6119      Moreover, we can't elide the outgoing fake edge, since the block
6120      profiler needs to take this into account in order to solve the minimal
6121      spanning tree in the case that the call doesn't return.
6122
6123      Handle this by adding a dummy instruction in a new last basic block.  */
6124   if (check_last_block)
6125     {
6126       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6127       block_stmt_iterator bsi = bsi_last (bb);
6128       tree t = NULL_TREE;
6129       if (!bsi_end_p (bsi))
6130         t = bsi_stmt (bsi);
6131
6132       if (t && need_fake_edge_p (t))
6133         {
6134           edge e;
6135
6136           e = find_edge (bb, EXIT_BLOCK_PTR);
6137           if (e)
6138             {
6139               bsi_insert_on_edge (e, build_empty_stmt ());
6140               bsi_commit_edge_inserts ();
6141             }
6142         }
6143     }
6144
6145   /* Now add fake edges to the function exit for any non constant
6146      calls since there is no way that we can determine if they will
6147      return or not...  */
6148   for (i = 0; i < last_bb; i++)
6149     {
6150       basic_block bb = BASIC_BLOCK (i);
6151       block_stmt_iterator bsi;
6152       tree stmt, last_stmt;
6153
6154       if (!bb)
6155         continue;
6156
6157       if (blocks && !TEST_BIT (blocks, i))
6158         continue;
6159
6160       bsi = bsi_last (bb);
6161       if (!bsi_end_p (bsi))
6162         {
6163           last_stmt = bsi_stmt (bsi);
6164           do
6165             {
6166               stmt = bsi_stmt (bsi);
6167               if (need_fake_edge_p (stmt))
6168                 {
6169                   edge e;
6170                   /* The handling above of the final block before the
6171                      epilogue should be enough to verify that there is
6172                      no edge to the exit block in CFG already.
6173                      Calling make_edge in such case would cause us to
6174                      mark that edge as fake and remove it later.  */
6175 #ifdef ENABLE_CHECKING
6176                   if (stmt == last_stmt)
6177                     {
6178                       e = find_edge (bb, EXIT_BLOCK_PTR);
6179                       gcc_assert (e == NULL);
6180                     }
6181 #endif
6182
6183                   /* Note that the following may create a new basic block
6184                      and renumber the existing basic blocks.  */
6185                   if (stmt != last_stmt)
6186                     {
6187                       e = split_block (bb, stmt);
6188                       if (e)
6189                         blocks_split++;
6190                     }
6191                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6192                 }
6193               bsi_prev (&bsi);
6194             }
6195           while (!bsi_end_p (bsi));
6196         }
6197     }
6198
6199   if (blocks_split)
6200     verify_flow_info ();
6201
6202   return blocks_split;
6203 }
6204
6205 /* Purge dead abnormal call edges from basic block BB.  */
6206
6207 bool
6208 tree_purge_dead_abnormal_call_edges (basic_block bb)
6209 {
6210   bool changed = tree_purge_dead_eh_edges (bb);
6211
6212   if (current_function_has_nonlocal_label)
6213     {
6214       tree stmt = last_stmt (bb);
6215       edge_iterator ei;
6216       edge e;
6217
6218       if (!(stmt && tree_can_make_abnormal_goto (stmt)))
6219         for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6220           {
6221             if (e->flags & EDGE_ABNORMAL)
6222               {
6223                 remove_edge (e);
6224                 changed = true;
6225               }
6226             else
6227               ei_next (&ei);
6228           }
6229
6230       /* See tree_purge_dead_eh_edges below.  */
6231       if (changed)
6232         free_dominance_info (CDI_DOMINATORS);
6233     }
6234
6235   return changed;
6236 }
6237
6238 /* Stores all basic blocks dominated by BB to DOM_BBS.  */
6239
6240 static void
6241 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6242 {
6243   basic_block son;
6244
6245   VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6246   for (son = first_dom_son (CDI_DOMINATORS, bb);
6247        son;
6248        son = next_dom_son (CDI_DOMINATORS, son))
6249     get_all_dominated_blocks (son, dom_bbs);
6250 }
6251
6252 /* Removes edge E and all the blocks dominated by it, and updates dominance
6253    information.  The IL in E->src needs to be updated separately.
6254    If dominance info is not available, only the edge E is removed.*/
6255
6256 void
6257 remove_edge_and_dominated_blocks (edge e)
6258 {
6259   VEC (basic_block, heap) *bbs_to_remove = NULL;
6260   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6261   bitmap df, df_idom;
6262   edge f;
6263   edge_iterator ei;
6264   bool none_removed = false;
6265   unsigned i;
6266   basic_block bb, dbb;
6267   bitmap_iterator bi;
6268
6269   if (!dom_info_available_p (CDI_DOMINATORS))
6270     {
6271       remove_edge (e);
6272       return;
6273     }
6274
6275   /* No updating is needed for edges to exit.  */
6276   if (e->dest == EXIT_BLOCK_PTR)
6277     {
6278       if (cfgcleanup_altered_bbs)
6279         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6280       remove_edge (e);
6281       return;
6282     }
6283
6284   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6285      that is not dominated by E->dest, then this set is empty.  Otherwise,
6286      all the basic blocks dominated by E->dest are removed.
6287
6288      Also, to DF_IDOM we store the immediate dominators of the blocks in
6289      the dominance frontier of E (i.e., of the successors of the
6290      removed blocks, if there are any, and of E->dest otherwise).  */
6291   FOR_EACH_EDGE (f, ei, e->dest->preds)
6292     {
6293       if (f == e)
6294         continue;
6295
6296       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6297         {
6298           none_removed = true;
6299           break;
6300         }
6301     }
6302
6303   df = BITMAP_ALLOC (NULL);
6304   df_idom = BITMAP_ALLOC (NULL);
6305
6306   if (none_removed)
6307     bitmap_set_bit (df_idom,
6308                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6309   else
6310     {
6311       get_all_dominated_blocks (e->dest, &bbs_to_remove);
6312       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6313         {
6314           FOR_EACH_EDGE (f, ei, bb->succs)
6315             {
6316               if (f->dest != EXIT_BLOCK_PTR)
6317                 bitmap_set_bit (df, f->dest->index);
6318             }
6319         }
6320       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6321         bitmap_clear_bit (df, bb->index);
6322
6323       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6324         {
6325           bb = BASIC_BLOCK (i);
6326           bitmap_set_bit (df_idom,
6327                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6328         }
6329     }
6330
6331   if (cfgcleanup_altered_bbs)
6332     {
6333       /* Record the set of the altered basic blocks.  */
6334       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6335       bitmap_ior_into (cfgcleanup_altered_bbs, df);
6336     }
6337
6338   /* Remove E and the cancelled blocks.  */
6339   if (none_removed)
6340     remove_edge (e);
6341   else
6342     {
6343       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6344         delete_basic_block (bb);
6345     }
6346
6347   /* Update the dominance information.  The immediate dominator may change only
6348      for blocks whose immediate dominator belongs to DF_IDOM:
6349
6350      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6351      removal.  Let Z the arbitrary block such that idom(Z) = Y and
6352      Z dominates X after the removal.  Before removal, there exists a path P
6353      from Y to X that avoids Z.  Let F be the last edge on P that is
6354      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
6355      dominates W, and because of P, Z does not dominate W), and W belongs to
6356      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
6357   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6358     {
6359       bb = BASIC_BLOCK (i);
6360       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6361            dbb;
6362            dbb = next_dom_son (CDI_DOMINATORS, dbb))
6363         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6364     }
6365
6366   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6367
6368   BITMAP_FREE (df);
6369   BITMAP_FREE (df_idom);
6370   VEC_free (basic_block, heap, bbs_to_remove);
6371   VEC_free (basic_block, heap, bbs_to_fix_dom);
6372 }
6373
6374 /* Purge dead EH edges from basic block BB.  */
6375
6376 bool
6377 tree_purge_dead_eh_edges (basic_block bb)
6378 {
6379   bool changed = false;
6380   edge e;
6381   edge_iterator ei;
6382   tree stmt = last_stmt (bb);
6383
6384   if (stmt && tree_can_throw_internal (stmt))
6385     return false;
6386
6387   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6388     {
6389       if (e->flags & EDGE_EH)
6390         {
6391           remove_edge_and_dominated_blocks (e);
6392           changed = true;
6393         }
6394       else
6395         ei_next (&ei);
6396     }
6397
6398   return changed;
6399 }
6400
6401 bool
6402 tree_purge_all_dead_eh_edges (const_bitmap blocks)
6403 {
6404   bool changed = false;
6405   unsigned i;
6406   bitmap_iterator bi;
6407
6408   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6409     {
6410       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
6411     }
6412
6413   return changed;
6414 }
6415
6416 /* This function is called whenever a new edge is created or
6417    redirected.  */
6418
6419 static void
6420 tree_execute_on_growing_pred (edge e)
6421 {
6422   basic_block bb = e->dest;
6423
6424   if (phi_nodes (bb))
6425     reserve_phi_args_for_new_edge (bb);
6426 }
6427
6428 /* This function is called immediately before edge E is removed from
6429    the edge vector E->dest->preds.  */
6430
6431 static void
6432 tree_execute_on_shrinking_pred (edge e)
6433 {
6434   if (phi_nodes (e->dest))
6435     remove_phi_args (e);
6436 }
6437
6438 /*---------------------------------------------------------------------------
6439   Helper functions for Loop versioning
6440   ---------------------------------------------------------------------------*/
6441
6442 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
6443    of 'first'. Both of them are dominated by 'new_head' basic block. When
6444    'new_head' was created by 'second's incoming edge it received phi arguments
6445    on the edge by split_edge(). Later, additional edge 'e' was created to
6446    connect 'new_head' and 'first'. Now this routine adds phi args on this
6447    additional edge 'e' that new_head to second edge received as part of edge
6448    splitting.
6449 */
6450
6451 static void
6452 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6453                                 basic_block new_head, edge e)
6454 {
6455   tree phi1, phi2;
6456   edge e2 = find_edge (new_head, second);
6457
6458   /* Because NEW_HEAD has been created by splitting SECOND's incoming
6459      edge, we should always have an edge from NEW_HEAD to SECOND.  */
6460   gcc_assert (e2 != NULL);
6461
6462   /* Browse all 'second' basic block phi nodes and add phi args to
6463      edge 'e' for 'first' head. PHI args are always in correct order.  */
6464
6465   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
6466        phi2 && phi1;
6467        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
6468     {
6469       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
6470       add_phi_arg (phi1, def, e);
6471     }
6472 }
6473
6474 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6475    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6476    the destination of the ELSE part.  */
6477 static void
6478 tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6479                              basic_block second_head ATTRIBUTE_UNUSED,
6480                              basic_block cond_bb, void *cond_e)
6481 {
6482   block_stmt_iterator bsi;
6483   tree new_cond_expr = NULL_TREE;
6484   tree cond_expr = (tree) cond_e;
6485   edge e0;
6486
6487   /* Build new conditional expr */
6488   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
6489                           NULL_TREE, NULL_TREE);
6490
6491   /* Add new cond in cond_bb.  */
6492   bsi = bsi_start (cond_bb);
6493   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
6494   /* Adjust edges appropriately to connect new head with first head
6495      as well as second head.  */
6496   e0 = single_succ_edge (cond_bb);
6497   e0->flags &= ~EDGE_FALLTHRU;
6498   e0->flags |= EDGE_FALSE_VALUE;
6499 }
6500
6501 struct cfg_hooks tree_cfg_hooks = {
6502   "tree",
6503   tree_verify_flow_info,
6504   tree_dump_bb,                 /* dump_bb  */
6505   create_bb,                    /* create_basic_block  */
6506   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
6507   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
6508   tree_can_remove_branch_p,     /* can_remove_branch_p  */
6509   remove_bb,                    /* delete_basic_block  */
6510   tree_split_block,             /* split_block  */
6511   tree_move_block_after,        /* move_block_after  */
6512   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
6513   tree_merge_blocks,            /* merge_blocks  */
6514   tree_predict_edge,            /* predict_edge  */
6515   tree_predicted_by_p,          /* predicted_by_p  */
6516   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
6517   tree_duplicate_bb,            /* duplicate_block  */
6518   tree_split_edge,              /* split_edge  */
6519   tree_make_forwarder_block,    /* make_forward_block  */
6520   NULL,                         /* tidy_fallthru_edge  */
6521   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
6522   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6523   tree_flow_call_edges_add,     /* flow_call_edges_add */
6524   tree_execute_on_growing_pred, /* execute_on_growing_pred */
6525   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6526   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6527   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6528   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6529   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6530   flush_pending_stmts           /* flush_pending_stmts */
6531 };
6532
6533
6534 /* Split all critical edges.  */
6535
6536 static unsigned int
6537 split_critical_edges (void)
6538 {
6539   basic_block bb;
6540   edge e;
6541   edge_iterator ei;
6542
6543   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6544      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
6545      mappings around the calls to split_edge.  */
6546   start_recording_case_labels ();
6547   FOR_ALL_BB (bb)
6548     {
6549       FOR_EACH_EDGE (e, ei, bb->succs)
6550         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6551           {
6552             split_edge (e);
6553           }
6554     }
6555   end_recording_case_labels ();
6556   return 0;
6557 }
6558
6559 struct tree_opt_pass pass_split_crit_edges =
6560 {
6561   "crited",                          /* name */
6562   NULL,                          /* gate */
6563   split_critical_edges,          /* execute */
6564   NULL,                          /* sub */
6565   NULL,                          /* next */
6566   0,                             /* static_pass_number */
6567   TV_TREE_SPLIT_EDGES,           /* tv_id */
6568   PROP_cfg,                      /* properties required */
6569   PROP_no_crit_edges,            /* properties_provided */
6570   0,                             /* properties_destroyed */
6571   0,                             /* todo_flags_start */
6572   TODO_dump_func,                /* todo_flags_finish */
6573   0                              /* letter */
6574 };
6575
6576 \f
6577 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
6578    a temporary, make sure and register it to be renamed if necessary,
6579    and finally return the temporary.  Put the statements to compute
6580    EXP before the current statement in BSI.  */
6581
6582 tree
6583 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
6584 {
6585   tree t, new_stmt, orig_stmt;
6586
6587   if (is_gimple_val (exp))
6588     return exp;
6589
6590   t = make_rename_temp (type, NULL);
6591   new_stmt = build_gimple_modify_stmt (t, exp);
6592
6593   orig_stmt = bsi_stmt (*bsi);
6594   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
6595   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
6596
6597   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
6598   if (gimple_in_ssa_p (cfun))
6599     mark_symbols_for_renaming (new_stmt);
6600
6601   return t;
6602 }
6603
6604 /* Build a ternary operation and gimplify it.  Emit code before BSI.
6605    Return the gimple_val holding the result.  */
6606
6607 tree
6608 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
6609                  tree type, tree a, tree b, tree c)
6610 {
6611   tree ret;
6612
6613   ret = fold_build3 (code, type, a, b, c);
6614   STRIP_NOPS (ret);
6615
6616   return gimplify_val (bsi, type, ret);
6617 }
6618
6619 /* Build a binary operation and gimplify it.  Emit code before BSI.
6620    Return the gimple_val holding the result.  */
6621
6622 tree
6623 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
6624                  tree type, tree a, tree b)
6625 {
6626   tree ret;
6627
6628   ret = fold_build2 (code, type, a, b);
6629   STRIP_NOPS (ret);
6630
6631   return gimplify_val (bsi, type, ret);
6632 }
6633
6634 /* Build a unary operation and gimplify it.  Emit code before BSI.
6635    Return the gimple_val holding the result.  */
6636
6637 tree
6638 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
6639                  tree a)
6640 {
6641   tree ret;
6642
6643   ret = fold_build1 (code, type, a);
6644   STRIP_NOPS (ret);
6645
6646   return gimplify_val (bsi, type, ret);
6647 }
6648
6649
6650 \f
6651 /* Emit return warnings.  */
6652
6653 static unsigned int
6654 execute_warn_function_return (void)
6655 {
6656 #ifdef USE_MAPPED_LOCATION
6657   source_location location;
6658 #else
6659   location_t *locus;
6660 #endif
6661   tree last;
6662   edge e;
6663   edge_iterator ei;
6664
6665   /* If we have a path to EXIT, then we do return.  */
6666   if (TREE_THIS_VOLATILE (cfun->decl)
6667       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
6668     {
6669 #ifdef USE_MAPPED_LOCATION
6670       location = UNKNOWN_LOCATION;
6671 #else
6672       locus = NULL;
6673 #endif
6674       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
6675         {
6676           last = last_stmt (e->src);
6677           if (TREE_CODE (last) == RETURN_EXPR
6678 #ifdef USE_MAPPED_LOCATION
6679               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
6680 #else
6681               && (locus = EXPR_LOCUS (last)) != NULL)
6682 #endif
6683             break;
6684         }
6685 #ifdef USE_MAPPED_LOCATION
6686       if (location == UNKNOWN_LOCATION)
6687         location = cfun->function_end_locus;
6688       warning (0, "%H%<noreturn%> function does return", &location);
6689 #else
6690       if (!locus)
6691         locus = &cfun->function_end_locus;
6692       warning (0, "%H%<noreturn%> function does return", locus);
6693 #endif
6694     }
6695
6696   /* If we see "return;" in some basic block, then we do reach the end
6697      without returning a value.  */
6698   else if (warn_return_type
6699            && !TREE_NO_WARNING (cfun->decl)
6700            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
6701            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
6702     {
6703       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
6704         {
6705           tree last = last_stmt (e->src);
6706           if (TREE_CODE (last) == RETURN_EXPR
6707               && TREE_OPERAND (last, 0) == NULL
6708               && !TREE_NO_WARNING (last))
6709             {
6710 #ifdef USE_MAPPED_LOCATION
6711               location = EXPR_LOCATION (last);
6712               if (location == UNKNOWN_LOCATION)
6713                   location = cfun->function_end_locus;
6714               warning (0, "%Hcontrol reaches end of non-void function", &location);
6715 #else
6716               locus = EXPR_LOCUS (last);
6717               if (!locus)
6718                 locus = &cfun->function_end_locus;
6719               warning (0, "%Hcontrol reaches end of non-void function", locus);
6720 #endif
6721               TREE_NO_WARNING (cfun->decl) = 1;
6722               break;
6723             }
6724         }
6725     }
6726   return 0;
6727 }
6728
6729
6730 /* Given a basic block B which ends with a conditional and has
6731    precisely two successors, determine which of the edges is taken if
6732    the conditional is true and which is taken if the conditional is
6733    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
6734
6735 void
6736 extract_true_false_edges_from_block (basic_block b,
6737                                      edge *true_edge,
6738                                      edge *false_edge)
6739 {
6740   edge e = EDGE_SUCC (b, 0);
6741
6742   if (e->flags & EDGE_TRUE_VALUE)
6743     {
6744       *true_edge = e;
6745       *false_edge = EDGE_SUCC (b, 1);
6746     }
6747   else
6748     {
6749       *false_edge = e;
6750       *true_edge = EDGE_SUCC (b, 1);
6751     }
6752 }
6753
6754 struct tree_opt_pass pass_warn_function_return =
6755 {
6756   NULL,                                 /* name */
6757   NULL,                                 /* gate */
6758   execute_warn_function_return,         /* execute */
6759   NULL,                                 /* sub */
6760   NULL,                                 /* next */
6761   0,                                    /* static_pass_number */
6762   0,                                    /* tv_id */
6763   PROP_cfg,                             /* properties_required */
6764   0,                                    /* properties_provided */
6765   0,                                    /* properties_destroyed */
6766   0,                                    /* todo_flags_start */
6767   0,                                    /* todo_flags_finish */
6768   0                                     /* letter */
6769 };
6770
6771 /* Emit noreturn warnings.  */
6772
6773 static unsigned int
6774 execute_warn_function_noreturn (void)
6775 {
6776   if (warn_missing_noreturn
6777       && !TREE_THIS_VOLATILE (cfun->decl)
6778       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
6779       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
6780     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
6781              "for attribute %<noreturn%>",
6782              cfun->decl);
6783   return 0;
6784 }
6785
6786 struct tree_opt_pass pass_warn_function_noreturn =
6787 {
6788   NULL,                                 /* name */
6789   NULL,                                 /* gate */
6790   execute_warn_function_noreturn,       /* execute */
6791   NULL,                                 /* sub */
6792   NULL,                                 /* next */
6793   0,                                    /* static_pass_number */
6794   0,                                    /* tv_id */
6795   PROP_cfg,                             /* properties_required */
6796   0,                                    /* properties_provided */
6797   0,                                    /* properties_destroyed */
6798   0,                                    /* todo_flags_start */
6799   0,                                    /* todo_flags_finish */
6800   0                                     /* letter */
6801 };