gcc/tree-cfg.c

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