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