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