gcc/tree-cfg.c

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