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