gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  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 "hashtab.h"
  47 #include "tree-ssa-propagate.h"
  48
  49 /* This file contains functions for building the Control Flow Graph (CFG)
  50    for a function tree.  */
  51
  52 /* Local declarations.  */
  53
  54 /* Initial capacity for the basic block array.  */
  55 static const int initial_cfg_capacity = 20;
  56
  57 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  58    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  59    via their TREE_CHAIN field, which we clear after we're done with the
  60    hash table to prevent problems with duplication of SWITCH_EXPRs.
  61
  62    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  63    update the case vector in response to edge redirections.
  64
  65    Right now this table is set up and torn down at key points in the
  66    compilation process.  It would be nice if we could make the table
  67    more persistent.  The key is getting notification of changes to
  68    the CFG (particularly edge removal, creation and redirection).  */
  69
  70 struct edge_to_cases_elt
  71 {
  72   /* The edge itself.  Necessary for hashing and equality tests.  */
  73   edge e;
  74
  75   /* The case labels associated with this edge.  We link these up via
  76      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
  77      when we destroy the hash table.  This prevents problems when copying
  78      SWITCH_EXPRs.  */
  79   tree case_labels;
  80 };
  81
  82 static htab_t edge_to_cases;
  83
  84 /* CFG statistics.  */
  85 struct cfg_stats_d
  86 {
  87   long num_merged_labels;
  88 };
  89
  90 static struct cfg_stats_d cfg_stats;
  91
  92 /* Nonzero if we found a computed goto while building basic blocks.  */
  93 static bool found_computed_goto;
  94
  95 /* Basic blocks and flowgraphs.  */
  96 static basic_block create_bb (void *, void *, basic_block);
  97 static void make_blocks (tree);
  98 static void factor_computed_gotos (void);
  99
 100 /* Edges.  */
 101 static void make_edges (void);
 102 static void make_ctrl_stmt_edges (basic_block);
 103 static void make_exit_edges (basic_block);
 104 static void make_cond_expr_edges (basic_block);
 105 static void make_switch_expr_edges (basic_block);
 106 static void make_goto_expr_edges (basic_block);
 107 static edge tree_redirect_edge_and_branch (edge, basic_block);
 108 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
 109 static void split_critical_edges (void);
 110
 111 /* Various helpers.  */
 112 static inline bool stmt_starts_bb_p (tree, tree);
 113 static int tree_verify_flow_info (void);
 114 static void tree_make_forwarder_block (edge);
 115 static void tree_cfg2vcg (FILE *);
 116
 117 /* Flowgraph optimization and cleanup.  */
 118 static void tree_merge_blocks (basic_block, basic_block);
 119 static bool tree_can_merge_blocks_p (basic_block, basic_block);
 120 static void remove_bb (basic_block);
 121 static edge find_taken_edge_computed_goto (basic_block, tree);
 122 static edge find_taken_edge_cond_expr (basic_block, tree);
 123 static edge find_taken_edge_switch_expr (basic_block, tree);
 124 static tree find_case_label_for_value (tree, tree);
 125
 126 void
 127 init_empty_tree_cfg (void)
 128 {
 129   /* Initialize the basic block array.  */
 130   init_flow ();
 131   profile_status = PROFILE_ABSENT;
 132   n_basic_blocks = 0;
 133   last_basic_block = 0;
 134   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
 135
 136   /* Build a mapping of labels to their associated blocks.  */
 137   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
 138                   "label to block map");
 139
 140   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 141   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 142 }
 143
 144 /*---------------------------------------------------------------------------
 145                               Create basic blocks
 146 ---------------------------------------------------------------------------*/
 147
 148 /* Entry point to the CFG builder for trees.  TP points to the list of
 149    statements to be added to the flowgraph.  */
 150
 151 static void
 152 build_tree_cfg (tree *tp)
 153 {
 154   /* Register specific tree functions.  */
 155   tree_register_cfg_hooks ();
 156
 157   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 158
 159   init_empty_tree_cfg ();
 160
 161   found_computed_goto = 0;
 162   make_blocks (*tp);
 163
 164   /* Computed gotos are hell to deal with, especially if there are
 165      lots of them with a large number of destinations.  So we factor
 166      them to a common computed goto location before we build the
 167      edge list.  After we convert back to normal form, we will un-factor
 168      the computed gotos since factoring introduces an unwanted jump.  */
 169   if (found_computed_goto)
 170     factor_computed_gotos ();
 171
 172   /* Make sure there is always at least one block, even if it's empty.  */
 173   if (n_basic_blocks == 0)
 174     create_empty_bb (ENTRY_BLOCK_PTR);
 175
 176   /* Adjust the size of the array.  */
 177   VARRAY_GROW (basic_block_info, n_basic_blocks);
 178
 179   /* To speed up statement iterator walks, we first purge dead labels.  */
 180   cleanup_dead_labels ();
 181
 182   /* Group case nodes to reduce the number of edges.
 183      We do this after cleaning up dead labels because otherwise we miss
 184      a lot of obvious case merging opportunities.  */
 185   group_case_labels ();
 186
 187   /* Create the edges of the flowgraph.  */
 188   make_edges ();
 189
 190   /* Debugging dumps.  */
 191
 192   /* Write the flowgraph to a VCG file.  */
 193   {
 194     int local_dump_flags;
 195     FILE *dump_file = dump_begin (TDI_vcg, &local_dump_flags);
 196     if (dump_file)
 197       {
 198         tree_cfg2vcg (dump_file);
 199         dump_end (TDI_vcg, dump_file);
 200       }
 201   }
 202
 203 #ifdef ENABLE_CHECKING
 204   verify_stmts ();
 205 #endif
 206
 207   /* Dump a textual representation of the flowgraph.  */
 208   if (dump_file)
 209     dump_tree_cfg (dump_file, dump_flags);
 210 }
 211
 212 static void
 213 execute_build_cfg (void)
 214 {
 215   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
 216 }
 217
 218 struct tree_opt_pass pass_build_cfg =
 219 {
 220   "cfg",                                /* name */
 221   NULL,                                 /* gate */
 222   execute_build_cfg,                    /* execute */
 223   NULL,                                 /* sub */
 224   NULL,                                 /* next */
 225   0,                                    /* static_pass_number */
 226   TV_TREE_CFG,                          /* tv_id */
 227   PROP_gimple_leh,                      /* properties_required */
 228   PROP_cfg,                             /* properties_provided */
 229   0,                                    /* properties_destroyed */
 230   0,                                    /* todo_flags_start */
 231   TODO_verify_stmts,                    /* todo_flags_finish */
 232   0                                     /* letter */
 233 };
 234
 235 /* Search the CFG for any computed gotos.  If found, factor them to a
 236    common computed goto site.  Also record the location of that site so
 237    that we can un-factor the gotos after we have converted back to
 238    normal form.  */
 239
 240 static void
 241 factor_computed_gotos (void)
 242 {
 243   basic_block bb;
 244   tree factored_label_decl = NULL;
 245   tree var = NULL;
 246   tree factored_computed_goto_label = NULL;
 247   tree factored_computed_goto = NULL;
 248
 249   /* We know there are one or more computed gotos in this function.
 250      Examine the last statement in each basic block to see if the block
 251      ends with a computed goto.  */
 252
 253   FOR_EACH_BB (bb)
 254     {
 255       block_stmt_iterator bsi = bsi_last (bb);
 256       tree last;
 257
 258       if (bsi_end_p (bsi))
 259         continue;
 260       last = bsi_stmt (bsi);
 261
 262       /* Ignore the computed goto we create when we factor the original
 263          computed gotos.  */
 264       if (last == factored_computed_goto)
 265         continue;
 266
 267       /* If the last statement is a computed goto, factor it.  */
 268       if (computed_goto_p (last))
 269         {
 270           tree assignment;
 271
 272           /* The first time we find a computed goto we need to create
 273              the factored goto block and the variable each original
 274              computed goto will use for their goto destination.  */
 275           if (! factored_computed_goto)
 276             {
 277               basic_block new_bb = create_empty_bb (bb);
 278               block_stmt_iterator new_bsi = bsi_start (new_bb);
 279
 280               /* Create the destination of the factored goto.  Each original
 281                  computed goto will put its desired destination into this
 282                  variable and jump to the label we create immediately
 283                  below.  */
 284               var = create_tmp_var (ptr_type_node, "gotovar");
 285
 286               /* Build a label for the new block which will contain the
 287                  factored computed goto.  */
 288               factored_label_decl = create_artificial_label ();
 289               factored_computed_goto_label
 290                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
 291               bsi_insert_after (&new_bsi, factored_computed_goto_label,
 292                                 BSI_NEW_STMT);
 293
 294               /* Build our new computed goto.  */
 295               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
 296               bsi_insert_after (&new_bsi, factored_computed_goto,
 297                                 BSI_NEW_STMT);
 298             }
 299
 300           /* Copy the original computed goto's destination into VAR.  */
 301           assignment = build (MODIFY_EXPR, ptr_type_node,
 302                               var, GOTO_DESTINATION (last));
 303           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
 304
 305           /* And re-vector the computed goto to the new destination.  */
 306           GOTO_DESTINATION (last) = factored_label_decl;
 307         }
 308     }
 309 }
 310
 311
 312 /* Build a flowgraph for the statement_list STMT_LIST.  */
 313
 314 static void
 315 make_blocks (tree stmt_list)
 316 {
 317   tree_stmt_iterator i = tsi_start (stmt_list);
 318   tree stmt = NULL;
 319   bool start_new_block = true;
 320   bool first_stmt_of_list = true;
 321   basic_block bb = ENTRY_BLOCK_PTR;
 322
 323   while (!tsi_end_p (i))
 324     {
 325       tree prev_stmt;
 326
 327       prev_stmt = stmt;
 328       stmt = tsi_stmt (i);
 329
 330       /* If the statement starts a new basic block or if we have determined
 331          in a previous pass that we need to create a new block for STMT, do
 332          so now.  */
 333       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 334         {
 335           if (!first_stmt_of_list)
 336             stmt_list = tsi_split_statement_list_before (&i);
 337           bb = create_basic_block (stmt_list, NULL, bb);
 338           start_new_block = false;
 339         }
 340
 341       /* Now add STMT to BB and create the subgraphs for special statement
 342          codes.  */
 343       set_bb_for_stmt (stmt, bb);
 344
 345       if (computed_goto_p (stmt))
 346         found_computed_goto = true;
 347
 348       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 349          next iteration.  */
 350       if (stmt_ends_bb_p (stmt))
 351         start_new_block = true;
 352
 353       tsi_next (&i);
 354       first_stmt_of_list = false;
 355     }
 356 }
 357
 358
 359 /* Create and return a new empty basic block after bb AFTER.  */
 360
 361 static basic_block
 362 create_bb (void *h, void *e, basic_block after)
 363 {
 364   basic_block bb;
 365
 366   gcc_assert (!e);
 367
 368   /* Create and initialize a new basic block.  Since alloc_block uses
 369      ggc_alloc_cleared to allocate a basic block, we do not have to
 370      clear the newly allocated basic block here.  */
 371   bb = alloc_block ();
 372
 373   bb->index = last_basic_block;
 374   bb->flags = BB_NEW;
 375   bb->stmt_list = h ? h : alloc_stmt_list ();
 376
 377   /* Add the new block to the linked list of blocks.  */
 378   link_block (bb, after);
 379
 380   /* Grow the basic block array if needed.  */
 381   if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
 382     {
 383       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 384       VARRAY_GROW (basic_block_info, new_size);
 385     }
 386
 387   /* Add the newly created block to the array.  */
 388   BASIC_BLOCK (last_basic_block) = bb;
 389
 390   n_basic_blocks++;
 391   last_basic_block++;
 392
 393   return bb;
 394 }
 395
 396
 397 /*---------------------------------------------------------------------------
 398                                  Edge creation
 399 ---------------------------------------------------------------------------*/
 400
 401 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 402
 403 void
 404 fold_cond_expr_cond (void)
 405 {
 406   basic_block bb;
 407
 408   FOR_EACH_BB (bb)
 409     {
 410       tree stmt = last_stmt (bb);
 411
 412       if (stmt
 413           && TREE_CODE (stmt) == COND_EXPR)
 414         {
 415           tree cond = fold (COND_EXPR_COND (stmt));
 416           if (integer_zerop (cond))
 417             COND_EXPR_COND (stmt) = boolean_false_node;
 418           else if (integer_onep (cond))
 419             COND_EXPR_COND (stmt) = boolean_true_node;
 420         }
 421     }
 422 }
 423
 424 /* Join all the blocks in the flowgraph.  */
 425
 426 static void
 427 make_edges (void)
 428 {
 429   basic_block bb;
 430
 431   /* Create an edge from entry to the first block with executable
 432      statements in it.  */
 433   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
 434
 435   /* Traverse the basic block array placing edges.  */
 436   FOR_EACH_BB (bb)
 437     {
 438       tree first = first_stmt (bb);
 439       tree last = last_stmt (bb);
 440
 441       if (first)
 442         {
 443           /* Edges for statements that always alter flow control.  */
 444           if (is_ctrl_stmt (last))
 445             make_ctrl_stmt_edges (bb);
 446
 447           /* Edges for statements that sometimes alter flow control.  */
 448           if (is_ctrl_altering_stmt (last))
 449             make_exit_edges (bb);
 450         }
 451
 452       /* Finally, if no edges were created above, this is a regular
 453          basic block that only needs a fallthru edge.  */
 454       if (EDGE_COUNT (bb->succs) == 0)
 455         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 456     }
 457
 458   /* We do not care about fake edges, so remove any that the CFG
 459      builder inserted for completeness.  */
 460   remove_fake_exit_edges ();
 461
 462   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 463   fold_cond_expr_cond ();
 464
 465   /* Clean up the graph and warn for unreachable code.  */
 466   cleanup_tree_cfg ();
 467 }
 468
 469
 470 /* Create edges for control statement at basic block BB.  */
 471
 472 static void
 473 make_ctrl_stmt_edges (basic_block bb)
 474 {
 475   tree last = last_stmt (bb);
 476
 477   gcc_assert (last);
 478   switch (TREE_CODE (last))
 479     {
 480     case GOTO_EXPR:
 481       make_goto_expr_edges (bb);
 482       break;
 483
 484     case RETURN_EXPR:
 485       make_edge (bb, EXIT_BLOCK_PTR, 0);
 486       break;
 487
 488     case COND_EXPR:
 489       make_cond_expr_edges (bb);
 490       break;
 491
 492     case SWITCH_EXPR:
 493       make_switch_expr_edges (bb);
 494       break;
 495
 496     case RESX_EXPR:
 497       make_eh_edges (last);
 498       /* Yet another NORETURN hack.  */
 499       if (EDGE_COUNT (bb->succs) == 0)
 500         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 501       break;
 502
 503     default:
 504       gcc_unreachable ();
 505     }
 506 }
 507
 508
 509 /* Create exit edges for statements in block BB that alter the flow of
 510    control.  Statements that alter the control flow are 'goto', 'return'
 511    and calls to non-returning functions.  */
 512
 513 static void
 514 make_exit_edges (basic_block bb)
 515 {
 516   tree last = last_stmt (bb), op;
 517
 518   gcc_assert (last);
 519   switch (TREE_CODE (last))
 520     {
 521     case RESX_EXPR:
 522       break;
 523     case CALL_EXPR:
 524       /* If this function receives a nonlocal goto, then we need to
 525          make edges from this call site to all the nonlocal goto
 526          handlers.  */
 527       if (TREE_SIDE_EFFECTS (last)
 528           && current_function_has_nonlocal_label)
 529         make_goto_expr_edges (bb);
 530
 531       /* If this statement has reachable exception handlers, then
 532          create abnormal edges to them.  */
 533       make_eh_edges (last);
 534
 535       /* Some calls are known not to return.  For such calls we create
 536          a fake edge.
 537
 538          We really need to revamp how we build edges so that it's not
 539          such a bloody pain to avoid creating edges for this case since
 540          all we do is remove these edges when we're done building the
 541          CFG.  */
 542       if (call_expr_flags (last) & ECF_NORETURN)
 543         {
 544           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 545           return;
 546         }
 547
 548       /* Don't forget the fall-thru edge.  */
 549       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 550       break;
 551
 552     case MODIFY_EXPR:
 553       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
 554          may have an abnormal edge.  Search the RHS for this case and
 555          create any required edges.  */
 556       op = get_call_expr_in (last);
 557       if (op && TREE_SIDE_EFFECTS (op)
 558           && current_function_has_nonlocal_label)
 559         make_goto_expr_edges (bb);
 560
 561       make_eh_edges (last);
 562       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 563       break;
 564
 565     default:
 566       gcc_unreachable ();
 567     }
 568 }
 569
 570
 571 /* Create the edges for a COND_EXPR starting at block BB.
 572    At this point, both clauses must contain only simple gotos.  */
 573
 574 static void
 575 make_cond_expr_edges (basic_block bb)
 576 {
 577   tree entry = last_stmt (bb);
 578   basic_block then_bb, else_bb;
 579   tree then_label, else_label;
 580   edge e;
 581
 582   gcc_assert (entry);
 583   gcc_assert (TREE_CODE (entry) == COND_EXPR);
 584
 585   /* Entry basic blocks for each component.  */
 586   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
 587   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
 588   then_bb = label_to_block (then_label);
 589   else_bb = label_to_block (else_label);
 590
 591   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 592 #ifdef USE_MAPPED_LOCATION
 593   e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
 594 #else
 595   e->goto_locus = EXPR_LOCUS (COND_EXPR_THEN (entry));
 596 #endif
 597   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 598   if (e)
 599     {
 600 #ifdef USE_MAPPED_LOCATION
 601       e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
 602 #else
 603       e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
 604 #endif
 605     }
 606 }
 607
 608 /* Hashing routine for EDGE_TO_CASES.  */
 609
 610 static hashval_t
 611 edge_to_cases_hash (const void *p)
 612 {
 613   edge e = ((struct edge_to_cases_elt *)p)->e;
 614
 615   /* Hash on the edge itself (which is a pointer).  */
 616   return htab_hash_pointer (e);
 617 }
 618
 619 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
 620    for equality is just a pointer comparison.  */
 621
 622 static int
 623 edge_to_cases_eq (const void *p1, const void *p2)
 624 {
 625   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
 626   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
 627
 628   return e1 == e2;
 629 }
 630
 631 /* Called for each element in the hash table (P) as we delete the
 632    edge to cases hash table.
 633
 634    Clear all the TREE_CHAINs to prevent problems with copying of
 635    SWITCH_EXPRs and structure sharing rules, then free the hash table
 636    element.  */
 637
 638 static void
 639 edge_to_cases_cleanup (void *p)
 640 {
 641   struct edge_to_cases_elt *elt = p;
 642   tree t, next;
 643
 644   for (t = elt->case_labels; t; t = next)
 645     {
 646       next = TREE_CHAIN (t);
 647       TREE_CHAIN (t) = NULL;
 648     }
 649   free (p);
 650 }
 651
 652 /* Start recording information mapping edges to case labels.  */
 653
 654 void
 655 start_recording_case_labels (void)
 656 {
 657   gcc_assert (edge_to_cases == NULL);
 658
 659   edge_to_cases = htab_create (37,
 660                                edge_to_cases_hash,
 661                                edge_to_cases_eq,
 662                                edge_to_cases_cleanup);
 663 }
 664
 665 /* Return nonzero if we are recording information for case labels.  */
 666
 667 static bool
 668 recording_case_labels_p (void)
 669 {
 670   return (edge_to_cases != NULL);
 671 }
 672
 673 /* Stop recording information mapping edges to case labels and
 674    remove any information we have recorded.  */
 675 void
 676 end_recording_case_labels (void)
 677 {
 678   htab_delete (edge_to_cases);
 679   edge_to_cases = NULL;
 680 }
 681
 682 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
 683
 684 static void
 685 record_switch_edge (edge e, tree case_label)
 686 {
 687   struct edge_to_cases_elt *elt;
 688   void **slot;
 689
 690   /* Build a hash table element so we can see if E is already
 691      in the table.  */
 692   elt = xmalloc (sizeof (struct edge_to_cases_elt));
 693   elt->e = e;
 694   elt->case_labels = case_label;
 695
 696   slot = htab_find_slot (edge_to_cases, elt, INSERT);
 697
 698   if (*slot == NULL)
 699     {
 700       /* E was not in the hash table.  Install E into the hash table.  */
 701       *slot = (void *)elt;
 702     }
 703   else
 704     {
 705       /* E was already in the hash table.  Free ELT as we do not need it
 706          anymore.  */
 707       free (elt);
 708
 709       /* Get the entry stored in the hash table.  */
 710       elt = (struct edge_to_cases_elt *) *slot;
 711
 712       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
 713       TREE_CHAIN (case_label) = elt->case_labels;
 714       elt->case_labels = case_label;
 715     }
 716 }
 717
 718 /* If we are inside a {start,end}_recording_cases block, then return
 719    a chain of CASE_LABEL_EXPRs from T which reference E.
 720
 721    Otherwise return NULL.  */
 722
 723 static tree
 724 get_cases_for_edge (edge e, tree t)
 725 {
 726   struct edge_to_cases_elt elt, *elt_p;
 727   void **slot;
 728   size_t i, n;
 729   tree vec;
 730
 731   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 732      chains available.  Return NULL so the caller can detect this case.  */
 733   if (!recording_case_labels_p ())
 734     return NULL;
 735
 736 restart:
 737   elt.e = e;
 738   elt.case_labels = NULL;
 739   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
 740
 741   if (slot)
 742     {
 743       elt_p = (struct edge_to_cases_elt *)*slot;
 744       return elt_p->case_labels;
 745     }
 746
 747   /* If we did not find E in the hash table, then this must be the first
 748      time we have been queried for information about E & T.  Add all the
 749      elements from T to the hash table then perform the query again.  */
 750
 751   vec = SWITCH_LABELS (t);
 752   n = TREE_VEC_LENGTH (vec);
 753   for (i = 0; i < n; i++)
 754     {
 755       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 756       basic_block label_bb = label_to_block (lab);
 757       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
 758     }
 759   goto restart;
 760 }
 761
 762 /* Create the edges for a SWITCH_EXPR starting at block BB.
 763    At this point, the switch body has been lowered and the
 764    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
 765
 766 static void
 767 make_switch_expr_edges (basic_block bb)
 768 {
 769   tree entry = last_stmt (bb);
 770   size_t i, n;
 771   tree vec;
 772
 773   vec = SWITCH_LABELS (entry);
 774   n = TREE_VEC_LENGTH (vec);
 775
 776   for (i = 0; i < n; ++i)
 777     {
 778       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 779       basic_block label_bb = label_to_block (lab);
 780       make_edge (bb, label_bb, 0);
 781     }
 782 }
 783
 784
 785 /* Return the basic block holding label DEST.  */
 786
 787 basic_block
 788 label_to_block_fn (struct function *ifun, tree dest)
 789 {
 790   int uid = LABEL_DECL_UID (dest);
 791
 792   /* We would die hard when faced by an undefined label.  Emit a label to
 793      the very first basic block.  This will hopefully make even the dataflow
 794      and undefined variable warnings quite right.  */
 795   if ((errorcount || sorrycount) && uid < 0)
 796     {
 797       block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
 798       tree stmt;
 799
 800       stmt = build1 (LABEL_EXPR, void_type_node, dest);
 801       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 802       uid = LABEL_DECL_UID (dest);
 803     }
 804   if (VARRAY_SIZE (ifun->cfg->x_label_to_block_map) <= (unsigned int)uid)
 805     return NULL;
 806   return VARRAY_BB (ifun->cfg->x_label_to_block_map, uid);
 807 }
 808
 809 /* Create edges for a goto statement at block BB.  */
 810
 811 static void
 812 make_goto_expr_edges (basic_block bb)
 813 {
 814   tree goto_t;
 815   basic_block target_bb;
 816   int for_call;
 817   block_stmt_iterator last = bsi_last (bb);
 818
 819   goto_t = bsi_stmt (last);
 820
 821   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
 822      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
 823      from a nonlocal goto.  */
 824   if (TREE_CODE (goto_t) != GOTO_EXPR)
 825     for_call = 1;
 826   else
 827     {
 828       tree dest = GOTO_DESTINATION (goto_t);
 829       for_call = 0;
 830
 831       /* A GOTO to a local label creates normal edges.  */
 832       if (simple_goto_p (goto_t))
 833         {
 834           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
 835 #ifdef USE_MAPPED_LOCATION
 836           e->goto_locus = EXPR_LOCATION (goto_t);
 837 #else
 838           e->goto_locus = EXPR_LOCUS (goto_t);
 839 #endif
 840           bsi_remove (&last);
 841           return;
 842         }
 843
 844       /* Nothing more to do for nonlocal gotos.  */
 845       if (TREE_CODE (dest) == LABEL_DECL)
 846         return;
 847
 848       /* Computed gotos remain.  */
 849     }
 850
 851   /* Look for the block starting with the destination label.  In the
 852      case of a computed goto, make an edge to any label block we find
 853      in the CFG.  */
 854   FOR_EACH_BB (target_bb)
 855     {
 856       block_stmt_iterator bsi;
 857
 858       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
 859         {
 860           tree target = bsi_stmt (bsi);
 861
 862           if (TREE_CODE (target) != LABEL_EXPR)
 863             break;
 864
 865           if (
 866               /* Computed GOTOs.  Make an edge to every label block that has
 867                  been marked as a potential target for a computed goto.  */
 868               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
 869               /* Nonlocal GOTO target.  Make an edge to every label block
 870                  that has been marked as a potential target for a nonlocal
 871                  goto.  */
 872               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
 873             {
 874               make_edge (bb, target_bb, EDGE_ABNORMAL);
 875               break;
 876             }
 877         }
 878     }
 879
 880   /* Degenerate case of computed goto with no labels.  */
 881   if (!for_call && EDGE_COUNT (bb->succs) == 0)
 882     make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 883 }
 884
 885
 886 /*---------------------------------------------------------------------------
 887                                Flowgraph analysis
 888 ---------------------------------------------------------------------------*/
 889
 890 /* Cleanup useless labels in basic blocks.  This is something we wish
 891    to do early because it allows us to group case labels before creating
 892    the edges for the CFG, and it speeds up block statement iterators in
 893    all passes later on.
 894    We only run this pass once, running it more than once is probably not
 895    profitable.  */
 896
 897 /* A map from basic block index to the leading label of that block.  */
 898 static tree *label_for_bb;
 899
 900 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
 901 static void
 902 update_eh_label (struct eh_region *region)
 903 {
 904   tree old_label = get_eh_region_tree_label (region);
 905   if (old_label)
 906     {
 907       tree new_label;
 908       basic_block bb = label_to_block (old_label);
 909
 910       /* ??? After optimizing, there may be EH regions with labels
 911          that have already been removed from the function body, so
 912          there is no basic block for them.  */
 913       if (! bb)
 914         return;
 915
 916       new_label = label_for_bb[bb->index];
 917       set_eh_region_tree_label (region, new_label);
 918     }
 919 }
 920
 921 /* Given LABEL return the first label in the same basic block.  */
 922 static tree
 923 main_block_label (tree label)
 924 {
 925   basic_block bb = label_to_block (label);
 926
 927   /* label_to_block possibly inserted undefined label into the chain.  */
 928   if (!label_for_bb[bb->index])
 929     label_for_bb[bb->index] = label;
 930   return label_for_bb[bb->index];
 931 }
 932
 933 /* Cleanup redundant labels.  This is a three-step process:
 934      1) Find the leading label for each block.
 935      2) Redirect all references to labels to the leading labels.
 936      3) Cleanup all useless labels.  */
 937
 938 void
 939 cleanup_dead_labels (void)
 940 {
 941   basic_block bb;
 942   label_for_bb = xcalloc (last_basic_block, sizeof (tree));
 943
 944   /* Find a suitable label for each block.  We use the first user-defined
 945      label if there is one, or otherwise just the first label we see.  */
 946   FOR_EACH_BB (bb)
 947     {
 948       block_stmt_iterator i;
 949
 950       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 951         {
 952           tree label, stmt = bsi_stmt (i);
 953
 954           if (TREE_CODE (stmt) != LABEL_EXPR)
 955             break;
 956
 957           label = LABEL_EXPR_LABEL (stmt);
 958
 959           /* If we have not yet seen a label for the current block,
 960              remember this one and see if there are more labels.  */
 961           if (! label_for_bb[bb->index])
 962             {
 963               label_for_bb[bb->index] = label;
 964               continue;
 965             }
 966
 967           /* If we did see a label for the current block already, but it
 968              is an artificially created label, replace it if the current
 969              label is a user defined label.  */
 970           if (! DECL_ARTIFICIAL (label)
 971               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
 972             {
 973               label_for_bb[bb->index] = label;
 974               break;
 975             }
 976         }
 977     }
 978
 979   /* Now redirect all jumps/branches to the selected label.
 980      First do so for each block ending in a control statement.  */
 981   FOR_EACH_BB (bb)
 982     {
 983       tree stmt = last_stmt (bb);
 984       if (!stmt)
 985         continue;
 986
 987       switch (TREE_CODE (stmt))
 988         {
 989         case COND_EXPR:
 990           {
 991             tree true_branch, false_branch;
 992
 993             true_branch = COND_EXPR_THEN (stmt);
 994             false_branch = COND_EXPR_ELSE (stmt);
 995
 996             GOTO_DESTINATION (true_branch)
 997               = main_block_label (GOTO_DESTINATION (true_branch));
 998             GOTO_DESTINATION (false_branch)
 999               = main_block_label (GOTO_DESTINATION (false_branch));
1000
1001             break;
1002           }
1003
1004         case SWITCH_EXPR:
1005           {
1006             size_t i;
1007             tree vec = SWITCH_LABELS (stmt);
1008             size_t n = TREE_VEC_LENGTH (vec);
1009
1010             /* Replace all destination labels.  */
1011             for (i = 0; i < n; ++i)
1012               {
1013                 tree elt = TREE_VEC_ELT (vec, i);
1014                 tree label = main_block_label (CASE_LABEL (elt));
1015                 CASE_LABEL (elt) = label;
1016               }
1017             break;
1018           }
1019
1020         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1021            remove them until after we've created the CFG edges.  */
1022         case GOTO_EXPR:
1023           if (! computed_goto_p (stmt))
1024             {
1025               GOTO_DESTINATION (stmt)
1026                 = main_block_label (GOTO_DESTINATION (stmt));
1027               break;
1028             }
1029
1030         default:
1031           break;
1032       }
1033     }
1034
1035   for_each_eh_region (update_eh_label);
1036
1037   /* Finally, purge dead labels.  All user-defined labels and labels that
1038      can be the target of non-local gotos are preserved.  */
1039   FOR_EACH_BB (bb)
1040     {
1041       block_stmt_iterator i;
1042       tree label_for_this_bb = label_for_bb[bb->index];
1043
1044       if (! label_for_this_bb)
1045         continue;
1046
1047       for (i = bsi_start (bb); !bsi_end_p (i); )
1048         {
1049           tree label, stmt = bsi_stmt (i);
1050
1051           if (TREE_CODE (stmt) != LABEL_EXPR)
1052             break;
1053
1054           label = LABEL_EXPR_LABEL (stmt);
1055
1056           if (label == label_for_this_bb
1057               || ! DECL_ARTIFICIAL (label)
1058               || DECL_NONLOCAL (label))
1059             bsi_next (&i);
1060           else
1061             bsi_remove (&i);
1062         }
1063     }
1064
1065   free (label_for_bb);
1066 }
1067
1068 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1069    and scan the sorted vector of cases.  Combine the ones jumping to the
1070    same label.
1071    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1072
1073 void
1074 group_case_labels (void)
1075 {
1076   basic_block bb;
1077
1078   FOR_EACH_BB (bb)
1079     {
1080       tree stmt = last_stmt (bb);
1081       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1082         {
1083           tree labels = SWITCH_LABELS (stmt);
1084           int old_size = TREE_VEC_LENGTH (labels);
1085           int i, j, new_size = old_size;
1086           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1087           tree default_label;
1088
1089           /* The default label is always the last case in a switch
1090              statement after gimplification.  */
1091           default_label = CASE_LABEL (default_case);
1092
1093           /* Look for possible opportunities to merge cases.
1094              Ignore the last element of the label vector because it
1095              must be the default case.  */
1096           i = 0;
1097           while (i < old_size - 1)
1098             {
1099               tree base_case, base_label, base_high;
1100               base_case = TREE_VEC_ELT (labels, i);
1101
1102               gcc_assert (base_case);
1103               base_label = CASE_LABEL (base_case);
1104
1105               /* Discard cases that have the same destination as the
1106                  default case.  */
1107               if (base_label == default_label)
1108                 {
1109                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1110                   i++;
1111                   new_size--;
1112                   continue;
1113                 }
1114
1115               base_high = CASE_HIGH (base_case) ?
1116                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1117               i++;
1118               /* Try to merge case labels.  Break out when we reach the end
1119                  of the label vector or when we cannot merge the next case
1120                  label with the current one.  */
1121               while (i < old_size - 1)
1122                 {
1123                   tree merge_case = TREE_VEC_ELT (labels, i);
1124                   tree merge_label = CASE_LABEL (merge_case);
1125                   tree t = int_const_binop (PLUS_EXPR, base_high,
1126                                             integer_one_node, 1);
1127
1128                   /* Merge the cases if they jump to the same place,
1129                      and their ranges are consecutive.  */
1130                   if (merge_label == base_label
1131                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1132                     {
1133                       base_high = CASE_HIGH (merge_case) ?
1134                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1135                       CASE_HIGH (base_case) = base_high;
1136                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1137                       new_size--;
1138                       i++;
1139                     }
1140                   else
1141                     break;
1142                 }
1143             }
1144
1145           /* Compress the case labels in the label vector, and adjust the
1146              length of the vector.  */
1147           for (i = 0, j = 0; i < new_size; i++)
1148             {
1149               while (! TREE_VEC_ELT (labels, j))
1150                 j++;
1151               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1152             }
1153           TREE_VEC_LENGTH (labels) = new_size;
1154         }
1155     }
1156 }
1157
1158 /* Checks whether we can merge block B into block A.  */
1159
1160 static bool
1161 tree_can_merge_blocks_p (basic_block a, basic_block b)
1162 {
1163   tree stmt;
1164   block_stmt_iterator bsi;
1165   tree phi;
1166
1167   if (!single_succ_p (a))
1168     return false;
1169
1170   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1171     return false;
1172
1173   if (single_succ (a) != b)
1174     return false;
1175
1176   if (!single_pred_p (b))
1177     return false;
1178
1179   if (b == EXIT_BLOCK_PTR)
1180     return false;
1181
1182   /* If A ends by a statement causing exceptions or something similar, we
1183      cannot merge the blocks.  */
1184   stmt = last_stmt (a);
1185   if (stmt && stmt_ends_bb_p (stmt))
1186     return false;
1187
1188   /* Do not allow a block with only a non-local label to be merged.  */
1189   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1190       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1191     return false;
1192
1193   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1194      is not up-to-date, we cannot eliminate any phis.  */
1195   phi = phi_nodes (b);
1196   if (phi)
1197     {
1198       if (need_ssa_update_p ())
1199         return false;
1200
1201       for (; phi; phi = PHI_CHAIN (phi))
1202         if (!is_gimple_reg (PHI_RESULT (phi))
1203             && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1204           return false;
1205     }
1206
1207   /* Do not remove user labels.  */
1208   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1209     {
1210       stmt = bsi_stmt (bsi);
1211       if (TREE_CODE (stmt) != LABEL_EXPR)
1212         break;
1213       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1214         return false;
1215     }
1216
1217   /* Protect the loop latches.  */
1218   if (current_loops
1219       && b->loop_father->latch == b)
1220     return false;
1221
1222   return true;
1223 }
1224
1225 /* Replaces all uses of NAME by VAL.  */
1226
1227 void
1228 replace_uses_by (tree name, tree val)
1229 {
1230   imm_use_iterator imm_iter;
1231   use_operand_p use;
1232   tree stmt;
1233   edge e;
1234   unsigned i;
1235   VEC(tree,heap) *stmts = VEC_alloc (tree, heap, 20);
1236
1237   FOR_EACH_IMM_USE_SAFE (use, imm_iter, name)
1238     {
1239       stmt = USE_STMT (use);
1240
1241       SET_USE (use, val);
1242
1243       if (TREE_CODE (stmt) == PHI_NODE)
1244         {
1245           e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1246           if (e->flags & EDGE_ABNORMAL)
1247             {
1248               /* This can only occur for virtual operands, since
1249                  for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1250                  would prevent replacement.  */
1251               gcc_assert (!is_gimple_reg (name));
1252               SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1253             }
1254         }
1255       else
1256         VEC_safe_push (tree, heap, stmts, stmt);
1257     }
1258
1259   /* We do not update the statements in the loop above.  Consider
1260      x = w * w;
1261
1262      If we performed the update in the first loop, the statement
1263      would be rescanned after first occurrence of w is replaced,
1264      the new uses would be placed to the beginning of the list,
1265      and we would never process them.  */
1266   for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++)
1267     {
1268       tree rhs;
1269
1270       fold_stmt_inplace (stmt);
1271
1272       rhs = get_rhs (stmt);
1273       if (TREE_CODE (rhs) == ADDR_EXPR)
1274         recompute_tree_invarant_for_addr_expr (rhs);
1275
1276       mark_new_vars_to_rename (stmt);
1277     }
1278
1279   VEC_free (tree, heap, stmts);
1280
1281   /* Also update the trees stored in loop structures.  */
1282   if (current_loops)
1283     {
1284       struct loop *loop;
1285
1286       for (i = 0; i < current_loops->num; i++)
1287         {
1288           loop = current_loops->parray[i];
1289           if (loop)
1290             substitute_in_loop_info (loop, name, val);
1291         }
1292     }
1293 }
1294
1295 /* Merge block B into block A.  */
1296
1297 static void
1298 tree_merge_blocks (basic_block a, basic_block b)
1299 {
1300   block_stmt_iterator bsi;
1301   tree_stmt_iterator last;
1302   tree phi;
1303
1304   if (dump_file)
1305     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1306
1307   /* Remove all single-valued PHI nodes from block B of the form
1308      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1309   bsi = bsi_last (a);
1310   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1311     {
1312       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1313       tree copy;
1314
1315       if (!may_propagate_copy (def, use))
1316         {
1317           gcc_assert (is_gimple_reg (def));
1318
1319           /* Note that just emitting the copies is fine -- there is no problem
1320              with ordering of phi nodes.  This is because A is the single
1321              predecessor of B, therefore results of the phi nodes cannot
1322              appear as arguments of the phi nodes.  */
1323           copy = build2 (MODIFY_EXPR, void_type_node, def, use);
1324           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1325           SET_PHI_RESULT (phi, NULL_TREE);
1326           SSA_NAME_DEF_STMT (def) = copy;
1327         }
1328       else
1329         replace_uses_by (def, use);
1330
1331       remove_phi_node (phi, NULL);
1332     }
1333
1334   /* Ensure that B follows A.  */
1335   move_block_after (b, a);
1336
1337   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1338   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1339
1340   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1341   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1342     {
1343       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1344         {
1345           tree label = bsi_stmt (bsi);
1346
1347           bsi_remove (&bsi);
1348           /* Now that we can thread computed gotos, we might have
1349              a situation where we have a forced label in block B
1350              However, the label at the start of block B might still be
1351              used in other ways (think about the runtime checking for
1352              Fortran assigned gotos).  So we can not just delete the
1353              label.  Instead we move the label to the start of block A.  */
1354           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1355             {
1356               block_stmt_iterator dest_bsi = bsi_start (a);
1357               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1358             }
1359         }
1360       else
1361         {
1362           set_bb_for_stmt (bsi_stmt (bsi), a);
1363           bsi_next (&bsi);
1364         }
1365     }
1366
1367   /* Merge the chains.  */
1368   last = tsi_last (a->stmt_list);
1369   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1370   b->stmt_list = NULL;
1371 }
1372
1373
1374 /* Walk the function tree removing unnecessary statements.
1375
1376      * Empty statement nodes are removed
1377
1378      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1379
1380      * Unnecessary COND_EXPRs are removed
1381
1382      * Some unnecessary BIND_EXPRs are removed
1383
1384    Clearly more work could be done.  The trick is doing the analysis
1385    and removal fast enough to be a net improvement in compile times.
1386
1387    Note that when we remove a control structure such as a COND_EXPR
1388    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1389    to ensure we eliminate all the useless code.  */
1390
1391 struct rus_data
1392 {
1393   tree *last_goto;
1394   bool repeat;
1395   bool may_throw;
1396   bool may_branch;
1397   bool has_label;
1398 };
1399
1400 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1401
1402 static bool
1403 remove_useless_stmts_warn_notreached (tree stmt)
1404 {
1405   if (EXPR_HAS_LOCATION (stmt))
1406     {
1407       location_t loc = EXPR_LOCATION (stmt);
1408       if (LOCATION_LINE (loc) > 0)
1409         {
1410           warning (0, "%Hwill never be executed", &loc);
1411           return true;
1412         }
1413     }
1414
1415   switch (TREE_CODE (stmt))
1416     {
1417     case STATEMENT_LIST:
1418       {
1419         tree_stmt_iterator i;
1420         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1421           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1422             return true;
1423       }
1424       break;
1425
1426     case COND_EXPR:
1427       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1428         return true;
1429       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1430         return true;
1431       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1432         return true;
1433       break;
1434
1435     case TRY_FINALLY_EXPR:
1436     case TRY_CATCH_EXPR:
1437       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1438         return true;
1439       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1440         return true;
1441       break;
1442
1443     case CATCH_EXPR:
1444       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1445     case EH_FILTER_EXPR:
1446       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1447     case BIND_EXPR:
1448       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1449
1450     default:
1451       /* Not a live container.  */
1452       break;
1453     }
1454
1455   return false;
1456 }
1457
1458 static void
1459 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1460 {
1461   tree then_clause, else_clause, cond;
1462   bool save_has_label, then_has_label, else_has_label;
1463
1464   save_has_label = data->has_label;
1465   data->has_label = false;
1466   data->last_goto = NULL;
1467
1468   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1469
1470   then_has_label = data->has_label;
1471   data->has_label = false;
1472   data->last_goto = NULL;
1473
1474   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1475
1476   else_has_label = data->has_label;
1477   data->has_label = save_has_label | then_has_label | else_has_label;
1478
1479   then_clause = COND_EXPR_THEN (*stmt_p);
1480   else_clause = COND_EXPR_ELSE (*stmt_p);
1481   cond = fold (COND_EXPR_COND (*stmt_p));
1482
1483   /* If neither arm does anything at all, we can remove the whole IF.  */
1484   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1485     {
1486       *stmt_p = build_empty_stmt ();
1487       data->repeat = true;
1488     }
1489
1490   /* If there are no reachable statements in an arm, then we can
1491      zap the entire conditional.  */
1492   else if (integer_nonzerop (cond) && !else_has_label)
1493     {
1494       if (warn_notreached)
1495         remove_useless_stmts_warn_notreached (else_clause);
1496       *stmt_p = then_clause;
1497       data->repeat = true;
1498     }
1499   else if (integer_zerop (cond) && !then_has_label)
1500     {
1501       if (warn_notreached)
1502         remove_useless_stmts_warn_notreached (then_clause);
1503       *stmt_p = else_clause;
1504       data->repeat = true;
1505     }
1506
1507   /* Check a couple of simple things on then/else with single stmts.  */
1508   else
1509     {
1510       tree then_stmt = expr_only (then_clause);
1511       tree else_stmt = expr_only (else_clause);
1512
1513       /* Notice branches to a common destination.  */
1514       if (then_stmt && else_stmt
1515           && TREE_CODE (then_stmt) == GOTO_EXPR
1516           && TREE_CODE (else_stmt) == GOTO_EXPR
1517           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1518         {
1519           *stmt_p = then_stmt;
1520           data->repeat = true;
1521         }
1522
1523       /* If the THEN/ELSE clause merely assigns a value to a variable or
1524          parameter which is already known to contain that value, then
1525          remove the useless THEN/ELSE clause.  */
1526       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1527         {
1528           if (else_stmt
1529               && TREE_CODE (else_stmt) == MODIFY_EXPR
1530               && TREE_OPERAND (else_stmt, 0) == cond
1531               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1532             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1533         }
1534       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1535                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1536                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1537                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1538         {
1539           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1540                        ? then_stmt : else_stmt);
1541           tree *location = (TREE_CODE (cond) == EQ_EXPR
1542                             ? &COND_EXPR_THEN (*stmt_p)
1543                             : &COND_EXPR_ELSE (*stmt_p));
1544
1545           if (stmt
1546               && TREE_CODE (stmt) == MODIFY_EXPR
1547               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1548               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1549             *location = alloc_stmt_list ();
1550         }
1551     }
1552
1553   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1554      would be re-introduced during lowering.  */
1555   data->last_goto = NULL;
1556 }
1557
1558
1559 static void
1560 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1561 {
1562   bool save_may_branch, save_may_throw;
1563   bool this_may_branch, this_may_throw;
1564
1565   /* Collect may_branch and may_throw information for the body only.  */
1566   save_may_branch = data->may_branch;
1567   save_may_throw = data->may_throw;
1568   data->may_branch = false;
1569   data->may_throw = false;
1570   data->last_goto = NULL;
1571
1572   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1573
1574   this_may_branch = data->may_branch;
1575   this_may_throw = data->may_throw;
1576   data->may_branch |= save_may_branch;
1577   data->may_throw |= save_may_throw;
1578   data->last_goto = NULL;
1579
1580   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1581
1582   /* If the body is empty, then we can emit the FINALLY block without
1583      the enclosing TRY_FINALLY_EXPR.  */
1584   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1585     {
1586       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1587       data->repeat = true;
1588     }
1589
1590   /* If the handler is empty, then we can emit the TRY block without
1591      the enclosing TRY_FINALLY_EXPR.  */
1592   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1593     {
1594       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1595       data->repeat = true;
1596     }
1597
1598   /* If the body neither throws, nor branches, then we can safely
1599      string the TRY and FINALLY blocks together.  */
1600   else if (!this_may_branch && !this_may_throw)
1601     {
1602       tree stmt = *stmt_p;
1603       *stmt_p = TREE_OPERAND (stmt, 0);
1604       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1605       data->repeat = true;
1606     }
1607 }
1608
1609
1610 static void
1611 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1612 {
1613   bool save_may_throw, this_may_throw;
1614   tree_stmt_iterator i;
1615   tree stmt;
1616
1617   /* Collect may_throw information for the body only.  */
1618   save_may_throw = data->may_throw;
1619   data->may_throw = false;
1620   data->last_goto = NULL;
1621
1622   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1623
1624   this_may_throw = data->may_throw;
1625   data->may_throw = save_may_throw;
1626
1627   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1628   if (!this_may_throw)
1629     {
1630       if (warn_notreached)
1631         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1632       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1633       data->repeat = true;
1634       return;
1635     }
1636
1637   /* Process the catch clause specially.  We may be able to tell that
1638      no exceptions propagate past this point.  */
1639
1640   this_may_throw = true;
1641   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1642   stmt = tsi_stmt (i);
1643   data->last_goto = NULL;
1644
1645   switch (TREE_CODE (stmt))
1646     {
1647     case CATCH_EXPR:
1648       for (; !tsi_end_p (i); tsi_next (&i))
1649         {
1650           stmt = tsi_stmt (i);
1651           /* If we catch all exceptions, then the body does not
1652              propagate exceptions past this point.  */
1653           if (CATCH_TYPES (stmt) == NULL)
1654             this_may_throw = false;
1655           data->last_goto = NULL;
1656           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1657         }
1658       break;
1659
1660     case EH_FILTER_EXPR:
1661       if (EH_FILTER_MUST_NOT_THROW (stmt))
1662         this_may_throw = false;
1663       else if (EH_FILTER_TYPES (stmt) == NULL)
1664         this_may_throw = false;
1665       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1666       break;
1667
1668     default:
1669       /* Otherwise this is a cleanup.  */
1670       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1671
1672       /* If the cleanup is empty, then we can emit the TRY block without
1673          the enclosing TRY_CATCH_EXPR.  */
1674       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1675         {
1676           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1677           data->repeat = true;
1678         }
1679       break;
1680     }
1681   data->may_throw |= this_may_throw;
1682 }
1683
1684
1685 static void
1686 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1687 {
1688   tree block;
1689
1690   /* First remove anything underneath the BIND_EXPR.  */
1691   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1692
1693   /* If the BIND_EXPR has no variables, then we can pull everything
1694      up one level and remove the BIND_EXPR, unless this is the toplevel
1695      BIND_EXPR for the current function or an inlined function.
1696
1697      When this situation occurs we will want to apply this
1698      optimization again.  */
1699   block = BIND_EXPR_BLOCK (*stmt_p);
1700   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1701       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1702       && (! block
1703           || ! BLOCK_ABSTRACT_ORIGIN (block)
1704           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1705               != FUNCTION_DECL)))
1706     {
1707       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1708       data->repeat = true;
1709     }
1710 }
1711
1712
1713 static void
1714 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1715 {
1716   tree dest = GOTO_DESTINATION (*stmt_p);
1717
1718   data->may_branch = true;
1719   data->last_goto = NULL;
1720
1721   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1722   if (TREE_CODE (dest) == LABEL_DECL)
1723     data->last_goto = stmt_p;
1724 }
1725
1726
1727 static void
1728 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1729 {
1730   tree label = LABEL_EXPR_LABEL (*stmt_p);
1731
1732   data->has_label = true;
1733
1734   /* We do want to jump across non-local label receiver code.  */
1735   if (DECL_NONLOCAL (label))
1736     data->last_goto = NULL;
1737
1738   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1739     {
1740       *data->last_goto = build_empty_stmt ();
1741       data->repeat = true;
1742     }
1743
1744   /* ??? Add something here to delete unused labels.  */
1745 }
1746
1747
1748 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1749    decl.  This allows us to eliminate redundant or useless
1750    calls to "const" functions.
1751
1752    Gimplifier already does the same operation, but we may notice functions
1753    being const and pure once their calls has been gimplified, so we need
1754    to update the flag.  */
1755
1756 static void
1757 update_call_expr_flags (tree call)
1758 {
1759   tree decl = get_callee_fndecl (call);
1760   if (!decl)
1761     return;
1762   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1763     TREE_SIDE_EFFECTS (call) = 0;
1764   if (TREE_NOTHROW (decl))
1765     TREE_NOTHROW (call) = 1;
1766 }
1767
1768
1769 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1770
1771 void
1772 notice_special_calls (tree t)
1773 {
1774   int flags = call_expr_flags (t);
1775
1776   if (flags & ECF_MAY_BE_ALLOCA)
1777     current_function_calls_alloca = true;
1778   if (flags & ECF_RETURNS_TWICE)
1779     current_function_calls_setjmp = true;
1780 }
1781
1782
1783 /* Clear flags set by notice_special_calls.  Used by dead code removal
1784    to update the flags.  */
1785
1786 void
1787 clear_special_calls (void)
1788 {
1789   current_function_calls_alloca = false;
1790   current_function_calls_setjmp = false;
1791 }
1792
1793
1794 static void
1795 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1796 {
1797   tree t = *tp, op;
1798
1799   switch (TREE_CODE (t))
1800     {
1801     case COND_EXPR:
1802       remove_useless_stmts_cond (tp, data);
1803       break;
1804
1805     case TRY_FINALLY_EXPR:
1806       remove_useless_stmts_tf (tp, data);
1807       break;
1808
1809     case TRY_CATCH_EXPR:
1810       remove_useless_stmts_tc (tp, data);
1811       break;
1812
1813     case BIND_EXPR:
1814       remove_useless_stmts_bind (tp, data);
1815       break;
1816
1817     case GOTO_EXPR:
1818       remove_useless_stmts_goto (tp, data);
1819       break;
1820
1821     case LABEL_EXPR:
1822       remove_useless_stmts_label (tp, data);
1823       break;
1824
1825     case RETURN_EXPR:
1826       fold_stmt (tp);
1827       data->last_goto = NULL;
1828       data->may_branch = true;
1829       break;
1830
1831     case CALL_EXPR:
1832       fold_stmt (tp);
1833       data->last_goto = NULL;
1834       notice_special_calls (t);
1835       update_call_expr_flags (t);
1836       if (tree_could_throw_p (t))
1837         data->may_throw = true;
1838       break;
1839
1840     case MODIFY_EXPR:
1841       data->last_goto = NULL;
1842       fold_stmt (tp);
1843       op = get_call_expr_in (t);
1844       if (op)
1845         {
1846           update_call_expr_flags (op);
1847           notice_special_calls (op);
1848         }
1849       if (tree_could_throw_p (t))
1850         data->may_throw = true;
1851       break;
1852
1853     case STATEMENT_LIST:
1854       {
1855         tree_stmt_iterator i = tsi_start (t);
1856         while (!tsi_end_p (i))
1857           {
1858             t = tsi_stmt (i);
1859             if (IS_EMPTY_STMT (t))
1860               {
1861                 tsi_delink (&i);
1862                 continue;
1863               }
1864
1865             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1866
1867             t = tsi_stmt (i);
1868             if (TREE_CODE (t) == STATEMENT_LIST)
1869               {
1870                 tsi_link_before (&i, t, TSI_SAME_STMT);
1871                 tsi_delink (&i);
1872               }
1873             else
1874               tsi_next (&i);
1875           }
1876       }
1877       break;
1878     case ASM_EXPR:
1879       fold_stmt (tp);
1880       data->last_goto = NULL;
1881       break;
1882
1883     default:
1884       data->last_goto = NULL;
1885       break;
1886     }
1887 }
1888
1889 static void
1890 remove_useless_stmts (void)
1891 {
1892   struct rus_data data;
1893
1894   clear_special_calls ();
1895
1896   do
1897     {
1898       memset (&data, 0, sizeof (data));
1899       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1900     }
1901   while (data.repeat);
1902 }
1903
1904
1905 struct tree_opt_pass pass_remove_useless_stmts =
1906 {
1907   "useless",                            /* name */
1908   NULL,                                 /* gate */
1909   remove_useless_stmts,                 /* execute */
1910   NULL,                                 /* sub */
1911   NULL,                                 /* next */
1912   0,                                    /* static_pass_number */
1913   0,                                    /* tv_id */
1914   PROP_gimple_any,                      /* properties_required */
1915   0,                                    /* properties_provided */
1916   0,                                    /* properties_destroyed */
1917   0,                                    /* todo_flags_start */
1918   TODO_dump_func,                       /* todo_flags_finish */
1919   0                                     /* letter */
1920 };
1921
1922 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1923
1924 static void
1925 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1926 {
1927   tree phi;
1928
1929   /* Since this block is no longer reachable, we can just delete all
1930      of its PHI nodes.  */
1931   phi = phi_nodes (bb);
1932   while (phi)
1933     {
1934       tree next = PHI_CHAIN (phi);
1935       remove_phi_node (phi, NULL_TREE);
1936       phi = next;
1937     }
1938
1939   /* Remove edges to BB's successors.  */
1940   while (EDGE_COUNT (bb->succs) > 0)
1941     remove_edge (EDGE_SUCC (bb, 0));
1942 }
1943
1944
1945 /* Remove statements of basic block BB.  */
1946
1947 static void
1948 remove_bb (basic_block bb)
1949 {
1950   block_stmt_iterator i;
1951 #ifdef USE_MAPPED_LOCATION
1952   source_location loc = UNKNOWN_LOCATION;
1953 #else
1954   source_locus loc = 0;
1955 #endif
1956
1957   if (dump_file)
1958     {
1959       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1960       if (dump_flags & TDF_DETAILS)
1961         {
1962           dump_bb (bb, dump_file, 0);
1963           fprintf (dump_file, "\n");
1964         }
1965     }
1966
1967   /* If we remove the header or the latch of a loop, mark the loop for
1968      removal by setting its header and latch to NULL.  */
1969   if (current_loops)
1970     {
1971       struct loop *loop = bb->loop_father;
1972
1973       if (loop->latch == bb
1974           || loop->header == bb)
1975         {
1976           loop->latch = NULL;
1977           loop->header = NULL;
1978         }
1979     }
1980
1981   /* Remove all the instructions in the block.  */
1982   for (i = bsi_start (bb); !bsi_end_p (i);)
1983     {
1984       tree stmt = bsi_stmt (i);
1985       if (TREE_CODE (stmt) == LABEL_EXPR
1986           && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
1987               || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
1988         {
1989           basic_block new_bb;
1990           block_stmt_iterator new_bsi;
1991
1992           /* A non-reachable non-local label may still be referenced.
1993              But it no longer needs to carry the extra semantics of
1994              non-locality.  */
1995           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1996             {
1997               DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
1998               FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
1999             }
2000
2001           new_bb = bb->prev_bb;
2002           new_bsi = bsi_start (new_bb);
2003           bsi_remove (&i);
2004           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2005         }
2006       else
2007         {
2008           /* Release SSA definitions if we are in SSA.  Note that we
2009              may be called when not in SSA.  For example,
2010              final_cleanup calls this function via
2011              cleanup_tree_cfg.  */
2012           if (in_ssa_p)
2013             release_defs (stmt);
2014
2015           bsi_remove (&i);
2016         }
2017
2018       /* Don't warn for removed gotos.  Gotos are often removed due to
2019          jump threading, thus resulting in bogus warnings.  Not great,
2020          since this way we lose warnings for gotos in the original
2021          program that are indeed unreachable.  */
2022       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2023         {
2024 #ifdef USE_MAPPED_LOCATION
2025           if (EXPR_HAS_LOCATION (stmt))
2026             loc = EXPR_LOCATION (stmt);
2027 #else
2028           source_locus t;
2029           t = EXPR_LOCUS (stmt);
2030           if (t && LOCATION_LINE (*t) > 0)
2031             loc = t;
2032 #endif
2033         }
2034     }
2035
2036   /* If requested, give a warning that the first statement in the
2037      block is unreachable.  We walk statements backwards in the
2038      loop above, so the last statement we process is the first statement
2039      in the block.  */
2040 #ifdef USE_MAPPED_LOCATION
2041   if (loc > BUILTINS_LOCATION)
2042     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2043 #else
2044   if (loc)
2045     warning (OPT_Wunreachable_code, "%Hwill never be executed", loc);
2046 #endif
2047
2048   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2049 }
2050
2051
2052 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2053    predicate VAL, return the edge that will be taken out of the block.
2054    If VAL does not match a unique edge, NULL is returned.  */
2055
2056 edge
2057 find_taken_edge (basic_block bb, tree val)
2058 {
2059   tree stmt;
2060
2061   stmt = last_stmt (bb);
2062
2063   gcc_assert (stmt);
2064   gcc_assert (is_ctrl_stmt (stmt));
2065   gcc_assert (val);
2066
2067   if (! is_gimple_min_invariant (val))
2068     return NULL;
2069
2070   if (TREE_CODE (stmt) == COND_EXPR)
2071     return find_taken_edge_cond_expr (bb, val);
2072
2073   if (TREE_CODE (stmt) == SWITCH_EXPR)
2074     return find_taken_edge_switch_expr (bb, val);
2075
2076   if (computed_goto_p (stmt))
2077     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2078
2079   gcc_unreachable ();
2080 }
2081
2082 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2083    statement, determine which of the outgoing edges will be taken out of the
2084    block.  Return NULL if either edge may be taken.  */
2085
2086 static edge
2087 find_taken_edge_computed_goto (basic_block bb, tree val)
2088 {
2089   basic_block dest;
2090   edge e = NULL;
2091
2092   dest = label_to_block (val);
2093   if (dest)
2094     {
2095       e = find_edge (bb, dest);
2096       gcc_assert (e != NULL);
2097     }
2098
2099   return e;
2100 }
2101
2102 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2103    statement, determine which of the two edges will be taken out of the
2104    block.  Return NULL if either edge may be taken.  */
2105
2106 static edge
2107 find_taken_edge_cond_expr (basic_block bb, tree val)
2108 {
2109   edge true_edge, false_edge;
2110
2111   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2112
2113   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2114   return (zero_p (val) ? false_edge : true_edge);
2115 }
2116
2117 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2118    statement, determine which edge will be taken out of the block.  Return
2119    NULL if any edge may be taken.  */
2120
2121 static edge
2122 find_taken_edge_switch_expr (basic_block bb, tree val)
2123 {
2124   tree switch_expr, taken_case;
2125   basic_block dest_bb;
2126   edge e;
2127
2128   switch_expr = last_stmt (bb);
2129   taken_case = find_case_label_for_value (switch_expr, val);
2130   dest_bb = label_to_block (CASE_LABEL (taken_case));
2131
2132   e = find_edge (bb, dest_bb);
2133   gcc_assert (e);
2134   return e;
2135 }
2136
2137
2138 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2139    We can make optimal use here of the fact that the case labels are
2140    sorted: We can do a binary search for a case matching VAL.  */
2141
2142 static tree
2143 find_case_label_for_value (tree switch_expr, tree val)
2144 {
2145   tree vec = SWITCH_LABELS (switch_expr);
2146   size_t low, high, n = TREE_VEC_LENGTH (vec);
2147   tree default_case = TREE_VEC_ELT (vec, n - 1);
2148
2149   for (low = -1, high = n - 1; high - low > 1; )
2150     {
2151       size_t i = (high + low) / 2;
2152       tree t = TREE_VEC_ELT (vec, i);
2153       int cmp;
2154
2155       /* Cache the result of comparing CASE_LOW and val.  */
2156       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2157
2158       if (cmp > 0)
2159         high = i;
2160       else
2161         low = i;
2162
2163       if (CASE_HIGH (t) == NULL)
2164         {
2165           /* A singe-valued case label.  */
2166           if (cmp == 0)
2167             return t;
2168         }
2169       else
2170         {
2171           /* A case range.  We can only handle integer ranges.  */
2172           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2173             return t;
2174         }
2175     }
2176
2177   return default_case;
2178 }
2179
2180
2181
2182
2183 /*---------------------------------------------------------------------------
2184                               Debugging functions
2185 ---------------------------------------------------------------------------*/
2186
2187 /* Dump tree-specific information of block BB to file OUTF.  */
2188
2189 void
2190 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2191 {
2192   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2193 }
2194
2195
2196 /* Dump a basic block on stderr.  */
2197
2198 void
2199 debug_tree_bb (basic_block bb)
2200 {
2201   dump_bb (bb, stderr, 0);
2202 }
2203
2204
2205 /* Dump basic block with index N on stderr.  */
2206
2207 basic_block
2208 debug_tree_bb_n (int n)
2209 {
2210   debug_tree_bb (BASIC_BLOCK (n));
2211   return BASIC_BLOCK (n);
2212 }
2213
2214
2215 /* Dump the CFG on stderr.
2216
2217    FLAGS are the same used by the tree dumping functions
2218    (see TDF_* in tree.h).  */
2219
2220 void
2221 debug_tree_cfg (int flags)
2222 {
2223   dump_tree_cfg (stderr, flags);
2224 }
2225
2226
2227 /* Dump the program showing basic block boundaries on the given FILE.
2228
2229    FLAGS are the same used by the tree dumping functions (see TDF_* in
2230    tree.h).  */
2231
2232 void
2233 dump_tree_cfg (FILE *file, int flags)
2234 {
2235   if (flags & TDF_DETAILS)
2236     {
2237       const char *funcname
2238         = lang_hooks.decl_printable_name (current_function_decl, 2);
2239
2240       fputc ('\n', file);
2241       fprintf (file, ";; Function %s\n\n", funcname);
2242       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2243                n_basic_blocks, n_edges, last_basic_block);
2244
2245       brief_dump_cfg (file);
2246       fprintf (file, "\n");
2247     }
2248
2249   if (flags & TDF_STATS)
2250     dump_cfg_stats (file);
2251
2252   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2253 }
2254
2255
2256 /* Dump CFG statistics on FILE.  */
2257
2258 void
2259 dump_cfg_stats (FILE *file)
2260 {
2261   static long max_num_merged_labels = 0;
2262   unsigned long size, total = 0;
2263   long num_edges;
2264   basic_block bb;
2265   const char * const fmt_str   = "%-30s%-13s%12s\n";
2266   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2267   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2268   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2269   const char *funcname
2270     = lang_hooks.decl_printable_name (current_function_decl, 2);
2271
2272
2273   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2274
2275   fprintf (file, "---------------------------------------------------------\n");
2276   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2277   fprintf (file, fmt_str, "", "  instances  ", "used ");
2278   fprintf (file, "---------------------------------------------------------\n");
2279
2280   size = n_basic_blocks * sizeof (struct basic_block_def);
2281   total += size;
2282   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2283            SCALE (size), LABEL (size));
2284
2285   num_edges = 0;
2286   FOR_EACH_BB (bb)
2287     num_edges += EDGE_COUNT (bb->succs);
2288   size = num_edges * sizeof (struct edge_def);
2289   total += size;
2290   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2291
2292   fprintf (file, "---------------------------------------------------------\n");
2293   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2294            LABEL (total));
2295   fprintf (file, "---------------------------------------------------------\n");
2296   fprintf (file, "\n");
2297
2298   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2299     max_num_merged_labels = cfg_stats.num_merged_labels;
2300
2301   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2302            cfg_stats.num_merged_labels, max_num_merged_labels);
2303
2304   fprintf (file, "\n");
2305 }
2306
2307
2308 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2309    linked in the final executable.  */
2310
2311 void
2312 debug_cfg_stats (void)
2313 {
2314   dump_cfg_stats (stderr);
2315 }
2316
2317
2318 /* Dump the flowgraph to a .vcg FILE.  */
2319
2320 static void
2321 tree_cfg2vcg (FILE *file)
2322 {
2323   edge e;
2324   edge_iterator ei;
2325   basic_block bb;
2326   const char *funcname
2327     = lang_hooks.decl_printable_name (current_function_decl, 2);
2328
2329   /* Write the file header.  */
2330   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2331   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2332   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2333
2334   /* Write blocks and edges.  */
2335   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2336     {
2337       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2338                e->dest->index);
2339
2340       if (e->flags & EDGE_FAKE)
2341         fprintf (file, " linestyle: dotted priority: 10");
2342       else
2343         fprintf (file, " linestyle: solid priority: 100");
2344
2345       fprintf (file, " }\n");
2346     }
2347   fputc ('\n', file);
2348
2349   FOR_EACH_BB (bb)
2350     {
2351       enum tree_code head_code, end_code;
2352       const char *head_name, *end_name;
2353       int head_line = 0;
2354       int end_line = 0;
2355       tree first = first_stmt (bb);
2356       tree last = last_stmt (bb);
2357
2358       if (first)
2359         {
2360           head_code = TREE_CODE (first);
2361           head_name = tree_code_name[head_code];
2362           head_line = get_lineno (first);
2363         }
2364       else
2365         head_name = "no-statement";
2366
2367       if (last)
2368         {
2369           end_code = TREE_CODE (last);
2370           end_name = tree_code_name[end_code];
2371           end_line = get_lineno (last);
2372         }
2373       else
2374         end_name = "no-statement";
2375
2376       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2377                bb->index, bb->index, head_name, head_line, end_name,
2378                end_line);
2379
2380       FOR_EACH_EDGE (e, ei, bb->succs)
2381         {
2382           if (e->dest == EXIT_BLOCK_PTR)
2383             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2384           else
2385             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2386
2387           if (e->flags & EDGE_FAKE)
2388             fprintf (file, " priority: 10 linestyle: dotted");
2389           else
2390             fprintf (file, " priority: 100 linestyle: solid");
2391
2392           fprintf (file, " }\n");
2393         }
2394
2395       if (bb->next_bb != EXIT_BLOCK_PTR)
2396         fputc ('\n', file);
2397     }
2398
2399   fputs ("}\n\n", file);
2400 }
2401
2402
2403
2404 /*---------------------------------------------------------------------------
2405                              Miscellaneous helpers
2406 ---------------------------------------------------------------------------*/
2407
2408 /* Return true if T represents a stmt that always transfers control.  */
2409
2410 bool
2411 is_ctrl_stmt (tree t)
2412 {
2413   return (TREE_CODE (t) == COND_EXPR
2414           || TREE_CODE (t) == SWITCH_EXPR
2415           || TREE_CODE (t) == GOTO_EXPR
2416           || TREE_CODE (t) == RETURN_EXPR
2417           || TREE_CODE (t) == RESX_EXPR);
2418 }
2419
2420
2421 /* Return true if T is a statement that may alter the flow of control
2422    (e.g., a call to a non-returning function).  */
2423
2424 bool
2425 is_ctrl_altering_stmt (tree t)
2426 {
2427   tree call;
2428
2429   gcc_assert (t);
2430   call = get_call_expr_in (t);
2431   if (call)
2432     {
2433       /* A non-pure/const CALL_EXPR alters flow control if the current
2434          function has nonlocal labels.  */
2435       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2436         return true;
2437
2438       /* A CALL_EXPR also alters control flow if it does not return.  */
2439       if (call_expr_flags (call) & ECF_NORETURN)
2440         return true;
2441     }
2442
2443   /* If a statement can throw, it alters control flow.  */
2444   return tree_can_throw_internal (t);
2445 }
2446
2447
2448 /* Return true if T is a computed goto.  */
2449
2450 bool
2451 computed_goto_p (tree t)
2452 {
2453   return (TREE_CODE (t) == GOTO_EXPR
2454           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2455 }
2456
2457
2458 /* Checks whether EXPR is a simple local goto.  */
2459
2460 bool
2461 simple_goto_p (tree expr)
2462 {
2463   return (TREE_CODE (expr) == GOTO_EXPR
2464           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2465 }
2466
2467
2468 /* Return true if T should start a new basic block.  PREV_T is the
2469    statement preceding T.  It is used when T is a label or a case label.
2470    Labels should only start a new basic block if their previous statement
2471    wasn't a label.  Otherwise, sequence of labels would generate
2472    unnecessary basic blocks that only contain a single label.  */
2473
2474 static inline bool
2475 stmt_starts_bb_p (tree t, tree prev_t)
2476 {
2477   if (t == NULL_TREE)
2478     return false;
2479
2480   /* LABEL_EXPRs start a new basic block only if the preceding
2481      statement wasn't a label of the same type.  This prevents the
2482      creation of consecutive blocks that have nothing but a single
2483      label.  */
2484   if (TREE_CODE (t) == LABEL_EXPR)
2485     {
2486       /* Nonlocal and computed GOTO targets always start a new block.  */
2487       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2488           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2489         return true;
2490
2491       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2492         {
2493           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2494             return true;
2495
2496           cfg_stats.num_merged_labels++;
2497           return false;
2498         }
2499       else
2500         return true;
2501     }
2502
2503   return false;
2504 }
2505
2506
2507 /* Return true if T should end a basic block.  */
2508
2509 bool
2510 stmt_ends_bb_p (tree t)
2511 {
2512   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2513 }
2514
2515
2516 /* Add gotos that used to be represented implicitly in the CFG.  */
2517
2518 void
2519 disband_implicit_edges (void)
2520 {
2521   basic_block bb;
2522   block_stmt_iterator last;
2523   edge e;
2524   edge_iterator ei;
2525   tree stmt, label;
2526
2527   FOR_EACH_BB (bb)
2528     {
2529       last = bsi_last (bb);
2530       stmt = last_stmt (bb);
2531
2532       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2533         {
2534           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2535              from cfg_remove_useless_stmts here since it violates the
2536              invariants for tree--cfg correspondence and thus fits better
2537              here where we do it anyway.  */
2538           e = find_edge (bb, bb->next_bb);
2539           if (e)
2540             {
2541               if (e->flags & EDGE_TRUE_VALUE)
2542                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2543               else if (e->flags & EDGE_FALSE_VALUE)
2544                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2545               else
2546                 gcc_unreachable ();
2547               e->flags |= EDGE_FALLTHRU;
2548             }
2549
2550           continue;
2551         }
2552
2553       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2554         {
2555           /* Remove the RETURN_EXPR if we may fall though to the exit
2556              instead.  */
2557           gcc_assert (single_succ_p (bb));
2558           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2559
2560           if (bb->next_bb == EXIT_BLOCK_PTR
2561               && !TREE_OPERAND (stmt, 0))
2562             {
2563               bsi_remove (&last);
2564               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2565             }
2566           continue;
2567         }
2568
2569       /* There can be no fallthru edge if the last statement is a control
2570          one.  */
2571       if (stmt && is_ctrl_stmt (stmt))
2572         continue;
2573
2574       /* Find a fallthru edge and emit the goto if necessary.  */
2575       FOR_EACH_EDGE (e, ei, bb->succs)
2576         if (e->flags & EDGE_FALLTHRU)
2577           break;
2578
2579       if (!e || e->dest == bb->next_bb)
2580         continue;
2581
2582       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2583       label = tree_block_label (e->dest);
2584
2585       stmt = build1 (GOTO_EXPR, void_type_node, label);
2586 #ifdef USE_MAPPED_LOCATION
2587       SET_EXPR_LOCATION (stmt, e->goto_locus);
2588 #else
2589       SET_EXPR_LOCUS (stmt, e->goto_locus);
2590 #endif
2591       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2592       e->flags &= ~EDGE_FALLTHRU;
2593     }
2594 }
2595
2596 /* Remove block annotations and other datastructures.  */
2597
2598 void
2599 delete_tree_cfg_annotations (void)
2600 {
2601   label_to_block_map = NULL;
2602 }
2603
2604
2605 /* Return the first statement in basic block BB.  */
2606
2607 tree
2608 first_stmt (basic_block bb)
2609 {
2610   block_stmt_iterator i = bsi_start (bb);
2611   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2612 }
2613
2614
2615 /* Return the last statement in basic block BB.  */
2616
2617 tree
2618 last_stmt (basic_block bb)
2619 {
2620   block_stmt_iterator b = bsi_last (bb);
2621   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2622 }
2623
2624
2625 /* Return a pointer to the last statement in block BB.  */
2626
2627 tree *
2628 last_stmt_ptr (basic_block bb)
2629 {
2630   block_stmt_iterator last = bsi_last (bb);
2631   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2632 }
2633
2634
2635 /* Return the last statement of an otherwise empty block.  Return NULL
2636    if the block is totally empty, or if it contains more than one
2637    statement.  */
2638
2639 tree
2640 last_and_only_stmt (basic_block bb)
2641 {
2642   block_stmt_iterator i = bsi_last (bb);
2643   tree last, prev;
2644
2645   if (bsi_end_p (i))
2646     return NULL_TREE;
2647
2648   last = bsi_stmt (i);
2649   bsi_prev (&i);
2650   if (bsi_end_p (i))
2651     return last;
2652
2653   /* Empty statements should no longer appear in the instruction stream.
2654      Everything that might have appeared before should be deleted by
2655      remove_useless_stmts, and the optimizers should just bsi_remove
2656      instead of smashing with build_empty_stmt.
2657
2658      Thus the only thing that should appear here in a block containing
2659      one executable statement is a label.  */
2660   prev = bsi_stmt (i);
2661   if (TREE_CODE (prev) == LABEL_EXPR)
2662     return last;
2663   else
2664     return NULL_TREE;
2665 }
2666
2667
2668 /* Mark BB as the basic block holding statement T.  */
2669
2670 void
2671 set_bb_for_stmt (tree t, basic_block bb)
2672 {
2673   if (TREE_CODE (t) == PHI_NODE)
2674     PHI_BB (t) = bb;
2675   else if (TREE_CODE (t) == STATEMENT_LIST)
2676     {
2677       tree_stmt_iterator i;
2678       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2679         set_bb_for_stmt (tsi_stmt (i), bb);
2680     }
2681   else
2682     {
2683       stmt_ann_t ann = get_stmt_ann (t);
2684       ann->bb = bb;
2685
2686       /* If the statement is a label, add the label to block-to-labels map
2687          so that we can speed up edge creation for GOTO_EXPRs.  */
2688       if (TREE_CODE (t) == LABEL_EXPR)
2689         {
2690           int uid;
2691
2692           t = LABEL_EXPR_LABEL (t);
2693           uid = LABEL_DECL_UID (t);
2694           if (uid == -1)
2695             {
2696               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2697               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2698                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2699             }
2700           else
2701             /* We're moving an existing label.  Make sure that we've
2702                 removed it from the old block.  */
2703             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2704           VARRAY_BB (label_to_block_map, uid) = bb;
2705         }
2706     }
2707 }
2708
2709 /* Finds iterator for STMT.  */
2710
2711 extern block_stmt_iterator
2712 bsi_for_stmt (tree stmt)
2713 {
2714   block_stmt_iterator bsi;
2715
2716   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2717     if (bsi_stmt (bsi) == stmt)
2718       return bsi;
2719
2720   gcc_unreachable ();
2721 }
2722
2723 /* Mark statement T as modified, and update it.  */
2724 static inline void
2725 update_modified_stmts (tree t)
2726 {
2727   if (TREE_CODE (t) == STATEMENT_LIST)
2728     {
2729       tree_stmt_iterator i;
2730       tree stmt;
2731       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2732         {
2733           stmt = tsi_stmt (i);
2734           update_stmt_if_modified (stmt);
2735         }
2736     }
2737   else
2738     update_stmt_if_modified (t);
2739 }
2740
2741 /* Insert statement (or statement list) T before the statement
2742    pointed-to by iterator I.  M specifies how to update iterator I
2743    after insertion (see enum bsi_iterator_update).  */
2744
2745 void
2746 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2747 {
2748   set_bb_for_stmt (t, i->bb);
2749   update_modified_stmts (t);
2750   tsi_link_before (&i->tsi, t, m);
2751 }
2752
2753
2754 /* Insert statement (or statement list) T after the statement
2755    pointed-to by iterator I.  M specifies how to update iterator I
2756    after insertion (see enum bsi_iterator_update).  */
2757
2758 void
2759 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2760 {
2761   set_bb_for_stmt (t, i->bb);
2762   update_modified_stmts (t);
2763   tsi_link_after (&i->tsi, t, m);
2764 }
2765
2766
2767 /* Remove the statement pointed to by iterator I.  The iterator is updated
2768    to the next statement.  */
2769
2770 void
2771 bsi_remove (block_stmt_iterator *i)
2772 {
2773   tree t = bsi_stmt (*i);
2774   set_bb_for_stmt (t, NULL);
2775   delink_stmt_imm_use (t);
2776   tsi_delink (&i->tsi);
2777   mark_stmt_modified (t);
2778 }
2779
2780
2781 /* Move the statement at FROM so it comes right after the statement at TO.  */
2782
2783 void
2784 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2785 {
2786   tree stmt = bsi_stmt (*from);
2787   bsi_remove (from);
2788   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2789 }
2790
2791
2792 /* Move the statement at FROM so it comes right before the statement at TO.  */
2793
2794 void
2795 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2796 {
2797   tree stmt = bsi_stmt (*from);
2798   bsi_remove (from);
2799   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2800 }
2801
2802
2803 /* Move the statement at FROM to the end of basic block BB.  */
2804
2805 void
2806 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2807 {
2808   block_stmt_iterator last = bsi_last (bb);
2809
2810   /* Have to check bsi_end_p because it could be an empty block.  */
2811   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2812     bsi_move_before (from, &last);
2813   else
2814     bsi_move_after (from, &last);
2815 }
2816
2817
2818 /* Replace the contents of the statement pointed to by iterator BSI
2819    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2820    information of the original statement is preserved.  */
2821
2822 void
2823 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2824 {
2825   int eh_region;
2826   tree orig_stmt = bsi_stmt (*bsi);
2827
2828   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2829   set_bb_for_stmt (stmt, bsi->bb);
2830
2831   /* Preserve EH region information from the original statement, if
2832      requested by the caller.  */
2833   if (preserve_eh_info)
2834     {
2835       eh_region = lookup_stmt_eh_region (orig_stmt);
2836       if (eh_region >= 0)
2837         add_stmt_to_eh_region (stmt, eh_region);
2838     }
2839
2840   delink_stmt_imm_use (orig_stmt);
2841   *bsi_stmt_ptr (*bsi) = stmt;
2842   mark_stmt_modified (stmt);
2843   update_modified_stmts (stmt);
2844 }
2845
2846
2847 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2848    is made to place the statement in an existing basic block, but
2849    sometimes that isn't possible.  When it isn't possible, the edge is
2850    split and the statement is added to the new block.
2851
2852    In all cases, the returned *BSI points to the correct location.  The
2853    return value is true if insertion should be done after the location,
2854    or false if it should be done before the location.  If new basic block
2855    has to be created, it is stored in *NEW_BB.  */
2856
2857 static bool
2858 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2859                            basic_block *new_bb)
2860 {
2861   basic_block dest, src;
2862   tree tmp;
2863
2864   dest = e->dest;
2865  restart:
2866
2867   /* If the destination has one predecessor which has no PHI nodes,
2868      insert there.  Except for the exit block.
2869
2870      The requirement for no PHI nodes could be relaxed.  Basically we
2871      would have to examine the PHIs to prove that none of them used
2872      the value set by the statement we want to insert on E.  That
2873      hardly seems worth the effort.  */
2874   if (single_pred_p (dest)
2875       && ! phi_nodes (dest)
2876       && dest != EXIT_BLOCK_PTR)
2877     {
2878       *bsi = bsi_start (dest);
2879       if (bsi_end_p (*bsi))
2880         return true;
2881
2882       /* Make sure we insert after any leading labels.  */
2883       tmp = bsi_stmt (*bsi);
2884       while (TREE_CODE (tmp) == LABEL_EXPR)
2885         {
2886           bsi_next (bsi);
2887           if (bsi_end_p (*bsi))
2888             break;
2889           tmp = bsi_stmt (*bsi);
2890         }
2891
2892       if (bsi_end_p (*bsi))
2893         {
2894           *bsi = bsi_last (dest);
2895           return true;
2896         }
2897       else
2898         return false;
2899     }
2900
2901   /* If the source has one successor, the edge is not abnormal and
2902      the last statement does not end a basic block, insert there.
2903      Except for the entry block.  */
2904   src = e->src;
2905   if ((e->flags & EDGE_ABNORMAL) == 0
2906       && single_succ_p (src)
2907       && src != ENTRY_BLOCK_PTR)
2908     {
2909       *bsi = bsi_last (src);
2910       if (bsi_end_p (*bsi))
2911         return true;
2912
2913       tmp = bsi_stmt (*bsi);
2914       if (!stmt_ends_bb_p (tmp))
2915         return true;
2916
2917       /* Insert code just before returning the value.  We may need to decompose
2918          the return in the case it contains non-trivial operand.  */
2919       if (TREE_CODE (tmp) == RETURN_EXPR)
2920         {
2921           tree op = TREE_OPERAND (tmp, 0);
2922           if (!is_gimple_val (op))
2923             {
2924               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
2925               bsi_insert_before (bsi, op, BSI_NEW_STMT);
2926               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
2927             }
2928           bsi_prev (bsi);
2929           return true;
2930         }
2931     }
2932
2933   /* Otherwise, create a new basic block, and split this edge.  */
2934   dest = split_edge (e);
2935   if (new_bb)
2936     *new_bb = dest;
2937   e = single_pred_edge (dest);
2938   goto restart;
2939 }
2940
2941
2942 /* This routine will commit all pending edge insertions, creating any new
2943    basic blocks which are necessary.  */
2944
2945 void
2946 bsi_commit_edge_inserts (void)
2947 {
2948   basic_block bb;
2949   edge e;
2950   edge_iterator ei;
2951
2952   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
2953
2954   FOR_EACH_BB (bb)
2955     FOR_EACH_EDGE (e, ei, bb->succs)
2956       bsi_commit_one_edge_insert (e, NULL);
2957 }
2958
2959
2960 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
2961    to this block, otherwise set it to NULL.  */
2962
2963 void
2964 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
2965 {
2966   if (new_bb)
2967     *new_bb = NULL;
2968   if (PENDING_STMT (e))
2969     {
2970       block_stmt_iterator bsi;
2971       tree stmt = PENDING_STMT (e);
2972
2973       PENDING_STMT (e) = NULL_TREE;
2974
2975       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
2976         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2977       else
2978         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2979     }
2980 }
2981
2982
2983 /* Add STMT to the pending list of edge E.  No actual insertion is
2984    made until a call to bsi_commit_edge_inserts () is made.  */
2985
2986 void
2987 bsi_insert_on_edge (edge e, tree stmt)
2988 {
2989   append_to_statement_list (stmt, &PENDING_STMT (e));
2990 }
2991
2992 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
2993    block has to be created, it is returned.  */
2994
2995 basic_block
2996 bsi_insert_on_edge_immediate (edge e, tree stmt)
2997 {
2998   block_stmt_iterator bsi;
2999   basic_block new_bb = NULL;
3000
3001   gcc_assert (!PENDING_STMT (e));
3002
3003   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3004     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3005   else
3006     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3007
3008   return new_bb;
3009 }
3010
3011 /*---------------------------------------------------------------------------
3012              Tree specific functions for CFG manipulation
3013 ---------------------------------------------------------------------------*/
3014
3015 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3016
3017 static void
3018 reinstall_phi_args (edge new_edge, edge old_edge)
3019 {
3020   tree var, phi;
3021
3022   if (!PENDING_STMT (old_edge))
3023     return;
3024
3025   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3026        var && phi;
3027        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3028     {
3029       tree result = TREE_PURPOSE (var);
3030       tree arg = TREE_VALUE (var);
3031
3032       gcc_assert (result == PHI_RESULT (phi));
3033
3034       add_phi_arg (phi, arg, new_edge);
3035     }
3036
3037   PENDING_STMT (old_edge) = NULL;
3038 }
3039
3040 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3041    Abort on abnormal edges.  */
3042
3043 static basic_block
3044 tree_split_edge (edge edge_in)
3045 {
3046   basic_block new_bb, after_bb, dest, src;
3047   edge new_edge, e;
3048
3049   /* Abnormal edges cannot be split.  */
3050   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3051
3052   src = edge_in->src;
3053   dest = edge_in->dest;
3054
3055   /* Place the new block in the block list.  Try to keep the new block
3056      near its "logical" location.  This is of most help to humans looking
3057      at debugging dumps.  */
3058   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3059     after_bb = edge_in->src;
3060   else
3061     after_bb = dest->prev_bb;
3062
3063   new_bb = create_empty_bb (after_bb);
3064   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3065   new_bb->count = edge_in->count;
3066   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3067   new_edge->probability = REG_BR_PROB_BASE;
3068   new_edge->count = edge_in->count;
3069
3070   e = redirect_edge_and_branch (edge_in, new_bb);
3071   gcc_assert (e);
3072   reinstall_phi_args (new_edge, e);
3073
3074   return new_bb;
3075 }
3076
3077
3078 /* Return true when BB has label LABEL in it.  */
3079
3080 static bool
3081 has_label_p (basic_block bb, tree label)
3082 {
3083   block_stmt_iterator bsi;
3084
3085   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3086     {
3087       tree stmt = bsi_stmt (bsi);
3088
3089       if (TREE_CODE (stmt) != LABEL_EXPR)
3090         return false;
3091       if (LABEL_EXPR_LABEL (stmt) == label)
3092         return true;
3093     }
3094   return false;
3095 }
3096
3097
3098 /* Callback for walk_tree, check that all elements with address taken are
3099    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3100    inside a PHI node.  */
3101
3102 static tree
3103 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3104 {
3105   tree t = *tp, x;
3106   bool in_phi = (data != NULL);
3107
3108   if (TYPE_P (t))
3109     *walk_subtrees = 0;
3110
3111   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3112 #define CHECK_OP(N, MSG) \
3113   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3114        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3115
3116   switch (TREE_CODE (t))
3117     {
3118     case SSA_NAME:
3119       if (SSA_NAME_IN_FREE_LIST (t))
3120         {
3121           error ("SSA name in freelist but still referenced");
3122           return *tp;
3123         }
3124       break;
3125
3126     case ASSERT_EXPR:
3127       x = fold (ASSERT_EXPR_COND (t));
3128       if (x == boolean_false_node)
3129         {
3130           error ("ASSERT_EXPR with an always-false condition");
3131           return *tp;
3132         }
3133       break;
3134
3135     case MODIFY_EXPR:
3136       x = TREE_OPERAND (t, 0);
3137       if (TREE_CODE (x) == BIT_FIELD_REF
3138           && is_gimple_reg (TREE_OPERAND (x, 0)))
3139         {
3140           error ("GIMPLE register modified with BIT_FIELD_REF");
3141           return t;
3142         }
3143       break;
3144
3145     case ADDR_EXPR:
3146       {
3147         bool old_invariant;
3148         bool old_constant;
3149         bool old_side_effects;
3150         bool new_invariant;
3151         bool new_constant;
3152         bool new_side_effects;
3153
3154         /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3155            dead PHIs that take the address of something.  But if the PHI
3156            result is dead, the fact that it takes the address of anything
3157            is irrelevant.  Because we can not tell from here if a PHI result
3158            is dead, we just skip this check for PHIs altogether.  This means
3159            we may be missing "valid" checks, but what can you do?
3160            This was PR19217.  */
3161         if (in_phi)
3162           break;
3163
3164         old_invariant = TREE_INVARIANT (t);
3165         old_constant = TREE_CONSTANT (t);
3166         old_side_effects = TREE_SIDE_EFFECTS (t);
3167
3168         recompute_tree_invarant_for_addr_expr (t);
3169         new_invariant = TREE_INVARIANT (t);
3170         new_side_effects = TREE_SIDE_EFFECTS (t);
3171         new_constant = TREE_CONSTANT (t);
3172
3173         if (old_invariant != new_invariant)
3174           {
3175             error ("invariant not recomputed when ADDR_EXPR changed");
3176             return t;
3177           }
3178
3179         if (old_constant != new_constant)
3180           {
3181             error ("constant not recomputed when ADDR_EXPR changed");
3182             return t;
3183           }
3184         if (old_side_effects != new_side_effects)
3185           {
3186             error ("side effects not recomputed when ADDR_EXPR changed");
3187             return t;
3188           }
3189
3190         /* Skip any references (they will be checked when we recurse down the
3191            tree) and ensure that any variable used as a prefix is marked
3192            addressable.  */
3193         for (x = TREE_OPERAND (t, 0);
3194              handled_component_p (x);
3195              x = TREE_OPERAND (x, 0))
3196           ;
3197
3198         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3199           return NULL;
3200         if (!TREE_ADDRESSABLE (x))
3201           {
3202             error ("address taken, but ADDRESSABLE bit not set");
3203             return x;
3204           }
3205         break;
3206       }
3207
3208     case COND_EXPR:
3209       x = COND_EXPR_COND (t);
3210       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3211         {
3212           error ("non-boolean used in condition");
3213           return x;
3214         }
3215       if (!is_gimple_condexpr (x))
3216         {
3217           error ("invalid conditional operand");
3218           return x;
3219         }
3220       break;
3221
3222     case NOP_EXPR:
3223     case CONVERT_EXPR:
3224     case FIX_TRUNC_EXPR:
3225     case FIX_CEIL_EXPR:
3226     case FIX_FLOOR_EXPR:
3227     case FIX_ROUND_EXPR:
3228     case FLOAT_EXPR:
3229     case NEGATE_EXPR:
3230     case ABS_EXPR:
3231     case BIT_NOT_EXPR:
3232     case NON_LVALUE_EXPR:
3233     case TRUTH_NOT_EXPR:
3234       CHECK_OP (0, "invalid operand to unary operator");
3235       break;
3236
3237     case REALPART_EXPR:
3238     case IMAGPART_EXPR:
3239     case COMPONENT_REF:
3240     case ARRAY_REF:
3241     case ARRAY_RANGE_REF:
3242     case BIT_FIELD_REF:
3243     case VIEW_CONVERT_EXPR:
3244       /* We have a nest of references.  Verify that each of the operands
3245          that determine where to reference is either a constant or a variable,
3246          verify that the base is valid, and then show we've already checked
3247          the subtrees.  */
3248       while (handled_component_p (t))
3249         {
3250           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3251             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3252           else if (TREE_CODE (t) == ARRAY_REF
3253                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3254             {
3255               CHECK_OP (1, "invalid array index");
3256               if (TREE_OPERAND (t, 2))
3257                 CHECK_OP (2, "invalid array lower bound");
3258               if (TREE_OPERAND (t, 3))
3259                 CHECK_OP (3, "invalid array stride");
3260             }
3261           else if (TREE_CODE (t) == BIT_FIELD_REF)
3262             {
3263               CHECK_OP (1, "invalid operand to BIT_FIELD_REF");
3264               CHECK_OP (2, "invalid operand to BIT_FIELD_REF");
3265             }
3266
3267           t = TREE_OPERAND (t, 0);
3268         }
3269
3270       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3271         {
3272           error ("invalid reference prefix");
3273           return t;
3274         }
3275       *walk_subtrees = 0;
3276       break;
3277
3278     case LT_EXPR:
3279     case LE_EXPR:
3280     case GT_EXPR:
3281     case GE_EXPR:
3282     case EQ_EXPR:
3283     case NE_EXPR:
3284     case UNORDERED_EXPR:
3285     case ORDERED_EXPR:
3286     case UNLT_EXPR:
3287     case UNLE_EXPR:
3288     case UNGT_EXPR:
3289     case UNGE_EXPR:
3290     case UNEQ_EXPR:
3291     case LTGT_EXPR:
3292     case PLUS_EXPR:
3293     case MINUS_EXPR:
3294     case MULT_EXPR:
3295     case TRUNC_DIV_EXPR:
3296     case CEIL_DIV_EXPR:
3297     case FLOOR_DIV_EXPR:
3298     case ROUND_DIV_EXPR:
3299     case TRUNC_MOD_EXPR:
3300     case CEIL_MOD_EXPR:
3301     case FLOOR_MOD_EXPR:
3302     case ROUND_MOD_EXPR:
3303     case RDIV_EXPR:
3304     case EXACT_DIV_EXPR:
3305     case MIN_EXPR:
3306     case MAX_EXPR:
3307     case LSHIFT_EXPR:
3308     case RSHIFT_EXPR:
3309     case LROTATE_EXPR:
3310     case RROTATE_EXPR:
3311     case BIT_IOR_EXPR:
3312     case BIT_XOR_EXPR:
3313     case BIT_AND_EXPR:
3314       CHECK_OP (0, "invalid operand to binary operator");
3315       CHECK_OP (1, "invalid operand to binary operator");
3316       break;
3317
3318     default:
3319       break;
3320     }
3321   return NULL;
3322
3323 #undef CHECK_OP
3324 }
3325
3326
3327 /* Verify STMT, return true if STMT is not in GIMPLE form.
3328    TODO: Implement type checking.  */
3329
3330 static bool
3331 verify_stmt (tree stmt, bool last_in_block)
3332 {
3333   tree addr;
3334
3335   if (!is_gimple_stmt (stmt))
3336     {
3337       error ("is not a valid GIMPLE statement");
3338       goto fail;
3339     }
3340
3341   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3342   if (addr)
3343     {
3344       debug_generic_stmt (addr);
3345       return true;
3346     }
3347
3348   /* If the statement is marked as part of an EH region, then it is
3349      expected that the statement could throw.  Verify that when we
3350      have optimizations that simplify statements such that we prove
3351      that they cannot throw, that we update other data structures
3352      to match.  */
3353   if (lookup_stmt_eh_region (stmt) >= 0)
3354     {
3355       if (!tree_could_throw_p (stmt))
3356         {
3357           error ("statement marked for throw, but doesn%'t");
3358           goto fail;
3359         }
3360       if (!last_in_block && tree_can_throw_internal (stmt))
3361         {
3362           error ("statement marked for throw in middle of block");
3363           goto fail;
3364         }
3365     }
3366
3367   return false;
3368
3369  fail:
3370   debug_generic_stmt (stmt);
3371   return true;
3372 }
3373
3374
3375 /* Return true when the T can be shared.  */
3376
3377 static bool
3378 tree_node_can_be_shared (tree t)
3379 {
3380   if (IS_TYPE_OR_DECL_P (t)
3381       /* We check for constants explicitly since they are not considered
3382          gimple invariants if they overflowed.  */
3383       || CONSTANT_CLASS_P (t)
3384       || is_gimple_min_invariant (t)
3385       || TREE_CODE (t) == SSA_NAME
3386       || t == error_mark_node)
3387     return true;
3388
3389   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3390     return true;
3391
3392   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3393           /* We check for constants explicitly since they are not considered
3394              gimple invariants if they overflowed.  */
3395           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3396               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3397          || (TREE_CODE (t) == COMPONENT_REF
3398              || TREE_CODE (t) == REALPART_EXPR
3399              || TREE_CODE (t) == IMAGPART_EXPR))
3400     t = TREE_OPERAND (t, 0);
3401
3402   if (DECL_P (t))
3403     return true;
3404
3405   return false;
3406 }
3407
3408
3409 /* Called via walk_trees.  Verify tree sharing.  */
3410
3411 static tree
3412 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3413 {
3414   htab_t htab = (htab_t) data;
3415   void **slot;
3416
3417   if (tree_node_can_be_shared (*tp))
3418     {
3419       *walk_subtrees = false;
3420       return NULL;
3421     }
3422
3423   slot = htab_find_slot (htab, *tp, INSERT);
3424   if (*slot)
3425     return *slot;
3426   *slot = *tp;
3427
3428   return NULL;
3429 }
3430
3431
3432 /* Verify the GIMPLE statement chain.  */
3433
3434 void
3435 verify_stmts (void)
3436 {
3437   basic_block bb;
3438   block_stmt_iterator bsi;
3439   bool err = false;
3440   htab_t htab;
3441   tree addr;
3442
3443   timevar_push (TV_TREE_STMT_VERIFY);
3444   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3445
3446   FOR_EACH_BB (bb)
3447     {
3448       tree phi;
3449       int i;
3450
3451       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3452         {
3453           int phi_num_args = PHI_NUM_ARGS (phi);
3454
3455           if (bb_for_stmt (phi) != bb)
3456             {
3457               error ("bb_for_stmt (phi) is set to a wrong basic block");
3458               err |= true;
3459             }
3460
3461           for (i = 0; i < phi_num_args; i++)
3462             {
3463               tree t = PHI_ARG_DEF (phi, i);
3464               tree addr;
3465
3466               /* Addressable variables do have SSA_NAMEs but they
3467                  are not considered gimple values.  */
3468               if (TREE_CODE (t) != SSA_NAME
3469                   && TREE_CODE (t) != FUNCTION_DECL
3470                   && !is_gimple_val (t))
3471                 {
3472                   error ("PHI def is not a GIMPLE value");
3473                   debug_generic_stmt (phi);
3474                   debug_generic_stmt (t);
3475                   err |= true;
3476                 }
3477
3478               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3479               if (addr)
3480                 {
3481                   debug_generic_stmt (addr);
3482                   err |= true;
3483                 }
3484
3485               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3486               if (addr)
3487                 {
3488                   error ("incorrect sharing of tree nodes");
3489                   debug_generic_stmt (phi);
3490                   debug_generic_stmt (addr);
3491                   err |= true;
3492                 }
3493             }
3494         }
3495
3496       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3497         {
3498           tree stmt = bsi_stmt (bsi);
3499
3500           if (bb_for_stmt (stmt) != bb)
3501             {
3502               error ("bb_for_stmt (stmt) is set to a wrong basic block");
3503               err |= true;
3504             }
3505
3506           bsi_next (&bsi);
3507           err |= verify_stmt (stmt, bsi_end_p (bsi));
3508           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3509           if (addr)
3510             {
3511               error ("incorrect sharing of tree nodes");
3512               debug_generic_stmt (stmt);
3513               debug_generic_stmt (addr);
3514               err |= true;
3515             }
3516         }
3517     }
3518
3519   if (err)
3520     internal_error ("verify_stmts failed");
3521
3522   htab_delete (htab);
3523   timevar_pop (TV_TREE_STMT_VERIFY);
3524 }
3525
3526
3527 /* Verifies that the flow information is OK.  */
3528
3529 static int
3530 tree_verify_flow_info (void)
3531 {
3532   int err = 0;
3533   basic_block bb;
3534   block_stmt_iterator bsi;
3535   tree stmt;
3536   edge e;
3537   edge_iterator ei;
3538
3539   if (ENTRY_BLOCK_PTR->stmt_list)
3540     {
3541       error ("ENTRY_BLOCK has a statement list associated with it");
3542       err = 1;
3543     }
3544
3545   if (EXIT_BLOCK_PTR->stmt_list)
3546     {
3547       error ("EXIT_BLOCK has a statement list associated with it");
3548       err = 1;
3549     }
3550
3551   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3552     if (e->flags & EDGE_FALLTHRU)
3553       {
3554         error ("fallthru to exit from bb %d", e->src->index);
3555         err = 1;
3556       }
3557
3558   FOR_EACH_BB (bb)
3559     {
3560       bool found_ctrl_stmt = false;
3561
3562       stmt = NULL_TREE;
3563
3564       /* Skip labels on the start of basic block.  */
3565       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3566         {
3567           tree prev_stmt = stmt;
3568
3569           stmt = bsi_stmt (bsi);
3570
3571           if (TREE_CODE (stmt) != LABEL_EXPR)
3572             break;
3573
3574           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3575             {
3576               error ("nonlocal label %s is not first "
3577                      "in a sequence of labels in bb %d",
3578                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3579                      bb->index);
3580               err = 1;
3581             }
3582
3583           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3584             {
3585               error ("label %s to block does not match in bb %d",
3586                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3587                      bb->index);
3588               err = 1;
3589             }
3590
3591           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3592               != current_function_decl)
3593             {
3594               error ("label %s has incorrect context in bb %d",
3595                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3596                      bb->index);
3597               err = 1;
3598             }
3599         }
3600
3601       /* Verify that body of basic block BB is free of control flow.  */
3602       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3603         {
3604           tree stmt = bsi_stmt (bsi);
3605
3606           if (found_ctrl_stmt)
3607             {
3608               error ("control flow in the middle of basic block %d",
3609                      bb->index);
3610               err = 1;
3611             }
3612
3613           if (stmt_ends_bb_p (stmt))
3614             found_ctrl_stmt = true;
3615
3616           if (TREE_CODE (stmt) == LABEL_EXPR)
3617             {
3618               error ("label %s in the middle of basic block %d",
3619                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3620                      bb->index);
3621               err = 1;
3622             }
3623         }
3624       bsi = bsi_last (bb);
3625       if (bsi_end_p (bsi))
3626         continue;
3627
3628       stmt = bsi_stmt (bsi);
3629
3630       err |= verify_eh_edges (stmt);
3631
3632       if (is_ctrl_stmt (stmt))
3633         {
3634           FOR_EACH_EDGE (e, ei, bb->succs)
3635             if (e->flags & EDGE_FALLTHRU)
3636               {
3637                 error ("fallthru edge after a control statement in bb %d",
3638                        bb->index);
3639                 err = 1;
3640               }
3641         }
3642
3643       switch (TREE_CODE (stmt))
3644         {
3645         case COND_EXPR:
3646           {
3647             edge true_edge;
3648             edge false_edge;
3649             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3650                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3651               {
3652                 error ("structured COND_EXPR at the end of bb %d", bb->index);
3653                 err = 1;
3654               }
3655
3656             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3657
3658             if (!true_edge || !false_edge
3659                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3660                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3661                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3662                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3663                 || EDGE_COUNT (bb->succs) >= 3)
3664               {
3665                 error ("wrong outgoing edge flags at end of bb %d",
3666                        bb->index);
3667                 err = 1;
3668               }
3669
3670             if (!has_label_p (true_edge->dest,
3671                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3672               {
3673                 error ("%<then%> label does not match edge at end of bb %d",
3674                        bb->index);
3675                 err = 1;
3676               }
3677
3678             if (!has_label_p (false_edge->dest,
3679                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3680               {
3681                 error ("%<else%> label does not match edge at end of bb %d",
3682                        bb->index);
3683                 err = 1;
3684               }
3685           }
3686           break;
3687
3688         case GOTO_EXPR:
3689           if (simple_goto_p (stmt))
3690             {
3691               error ("explicit goto at end of bb %d", bb->index);
3692               err = 1;
3693             }
3694           else
3695             {
3696               /* FIXME.  We should double check that the labels in the
3697                  destination blocks have their address taken.  */
3698               FOR_EACH_EDGE (e, ei, bb->succs)
3699                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3700                                  | EDGE_FALSE_VALUE))
3701                     || !(e->flags & EDGE_ABNORMAL))
3702                   {
3703                     error ("wrong outgoing edge flags at end of bb %d",
3704                            bb->index);
3705                     err = 1;
3706                   }
3707             }
3708           break;
3709
3710         case RETURN_EXPR:
3711           if (!single_succ_p (bb)
3712               || (single_succ_edge (bb)->flags
3713                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3714                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3715             {
3716               error ("wrong outgoing edge flags at end of bb %d", bb->index);
3717               err = 1;
3718             }
3719           if (single_succ (bb) != EXIT_BLOCK_PTR)
3720             {
3721               error ("return edge does not point to exit in bb %d",
3722                      bb->index);
3723               err = 1;
3724             }
3725           break;
3726
3727         case SWITCH_EXPR:
3728           {
3729             tree prev;
3730             edge e;
3731             size_t i, n;
3732             tree vec;
3733
3734             vec = SWITCH_LABELS (stmt);
3735             n = TREE_VEC_LENGTH (vec);
3736
3737             /* Mark all the destination basic blocks.  */
3738             for (i = 0; i < n; ++i)
3739               {
3740                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3741                 basic_block label_bb = label_to_block (lab);
3742
3743                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3744                 label_bb->aux = (void *)1;
3745               }
3746
3747             /* Verify that the case labels are sorted.  */
3748             prev = TREE_VEC_ELT (vec, 0);
3749             for (i = 1; i < n - 1; ++i)
3750               {
3751                 tree c = TREE_VEC_ELT (vec, i);
3752                 if (! CASE_LOW (c))
3753                   {
3754                     error ("found default case not at end of case vector");
3755                     err = 1;
3756                     continue;
3757                   }
3758                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3759                   {
3760                     error ("case labels not sorted:");
3761                     print_generic_expr (stderr, prev, 0);
3762                     fprintf (stderr," is greater than ");
3763                     print_generic_expr (stderr, c, 0);
3764                     fprintf (stderr," but comes before it.\n");
3765                     err = 1;
3766                   }
3767                 prev = c;
3768               }
3769             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3770               {
3771                 error ("no default case found at end of case vector");
3772                 err = 1;
3773               }
3774
3775             FOR_EACH_EDGE (e, ei, bb->succs)
3776               {
3777                 if (!e->dest->aux)
3778                   {
3779                     error ("extra outgoing edge %d->%d",
3780                            bb->index, e->dest->index);
3781                     err = 1;
3782                   }
3783                 e->dest->aux = (void *)2;
3784                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3785                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3786                   {
3787                     error ("wrong outgoing edge flags at end of bb %d",
3788                            bb->index);
3789                     err = 1;
3790                   }
3791               }
3792
3793             /* Check that we have all of them.  */
3794             for (i = 0; i < n; ++i)
3795               {
3796                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3797                 basic_block label_bb = label_to_block (lab);
3798
3799                 if (label_bb->aux != (void *)2)
3800                   {
3801                     error ("missing edge %i->%i",
3802                            bb->index, label_bb->index);
3803                     err = 1;
3804                   }
3805               }
3806
3807             FOR_EACH_EDGE (e, ei, bb->succs)
3808               e->dest->aux = (void *)0;
3809           }
3810
3811         default: ;
3812         }
3813     }
3814
3815   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3816     verify_dominators (CDI_DOMINATORS);
3817
3818   return err;
3819 }
3820
3821
3822 /* Updates phi nodes after creating a forwarder block joined
3823    by edge FALLTHRU.  */
3824
3825 static void
3826 tree_make_forwarder_block (edge fallthru)
3827 {
3828   edge e;
3829   edge_iterator ei;
3830   basic_block dummy, bb;
3831   tree phi, new_phi, var;
3832
3833   dummy = fallthru->src;
3834   bb = fallthru->dest;
3835
3836   if (single_pred_p (bb))
3837     return;
3838
3839   /* If we redirected a branch we must create new phi nodes at the
3840      start of BB.  */
3841   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3842     {
3843       var = PHI_RESULT (phi);
3844       new_phi = create_phi_node (var, bb);
3845       SSA_NAME_DEF_STMT (var) = new_phi;
3846       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3847       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3848     }
3849
3850   /* Ensure that the PHI node chain is in the same order.  */
3851   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3852
3853   /* Add the arguments we have stored on edges.  */
3854   FOR_EACH_EDGE (e, ei, bb->preds)
3855     {
3856       if (e == fallthru)
3857         continue;
3858
3859       flush_pending_stmts (e);
3860     }
3861 }
3862
3863
3864 /* Return a non-special label in the head of basic block BLOCK.
3865    Create one if it doesn't exist.  */
3866
3867 tree
3868 tree_block_label (basic_block bb)
3869 {
3870   block_stmt_iterator i, s = bsi_start (bb);
3871   bool first = true;
3872   tree label, stmt;
3873
3874   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3875     {
3876       stmt = bsi_stmt (i);
3877       if (TREE_CODE (stmt) != LABEL_EXPR)
3878         break;
3879       label = LABEL_EXPR_LABEL (stmt);
3880       if (!DECL_NONLOCAL (label))
3881         {
3882           if (!first)
3883             bsi_move_before (&i, &s);
3884           return label;
3885         }
3886     }
3887
3888   label = create_artificial_label ();
3889   stmt = build1 (LABEL_EXPR, void_type_node, label);
3890   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
3891   return label;
3892 }
3893
3894
3895 /* Attempt to perform edge redirection by replacing a possibly complex
3896    jump instruction by a goto or by removing the jump completely.
3897    This can apply only if all edges now point to the same block.  The
3898    parameters and return values are equivalent to
3899    redirect_edge_and_branch.  */
3900
3901 static edge
3902 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
3903 {
3904   basic_block src = e->src;
3905   block_stmt_iterator b;
3906   tree stmt;
3907
3908   /* We can replace or remove a complex jump only when we have exactly
3909      two edges.  */
3910   if (EDGE_COUNT (src->succs) != 2
3911       /* Verify that all targets will be TARGET.  Specifically, the
3912          edge that is not E must also go to TARGET.  */
3913       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
3914     return NULL;
3915
3916   b = bsi_last (src);
3917   if (bsi_end_p (b))
3918     return NULL;
3919   stmt = bsi_stmt (b);
3920
3921   if (TREE_CODE (stmt) == COND_EXPR
3922       || TREE_CODE (stmt) == SWITCH_EXPR)
3923     {
3924       bsi_remove (&b);
3925       e = ssa_redirect_edge (e, target);
3926       e->flags = EDGE_FALLTHRU;
3927       return e;
3928     }
3929
3930   return NULL;
3931 }
3932
3933
3934 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
3935    edge representing the redirected branch.  */
3936
3937 static edge
3938 tree_redirect_edge_and_branch (edge e, basic_block dest)
3939 {
3940   basic_block bb = e->src;
3941   block_stmt_iterator bsi;
3942   edge ret;
3943   tree label, stmt;
3944
3945   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
3946     return NULL;
3947
3948   if (e->src != ENTRY_BLOCK_PTR
3949       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
3950     return ret;
3951
3952   if (e->dest == dest)
3953     return NULL;
3954
3955   label = tree_block_label (dest);
3956
3957   bsi = bsi_last (bb);
3958   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
3959
3960   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
3961     {
3962     case COND_EXPR:
3963       stmt = (e->flags & EDGE_TRUE_VALUE
3964               ? COND_EXPR_THEN (stmt)
3965               : COND_EXPR_ELSE (stmt));
3966       GOTO_DESTINATION (stmt) = label;
3967       break;
3968
3969     case GOTO_EXPR:
3970       /* No non-abnormal edges should lead from a non-simple goto, and
3971          simple ones should be represented implicitly.  */
3972       gcc_unreachable ();
3973
3974     case SWITCH_EXPR:
3975       {
3976         tree cases = get_cases_for_edge (e, stmt);
3977
3978         /* If we have a list of cases associated with E, then use it
3979            as it's a lot faster than walking the entire case vector.  */
3980         if (cases)
3981           {
3982             edge e2 = find_edge (e->src, dest);
3983             tree last, first;
3984
3985             first = cases;
3986             while (cases)
3987               {
3988                 last = cases;
3989                 CASE_LABEL (cases) = label;
3990                 cases = TREE_CHAIN (cases);
3991               }
3992
3993             /* If there was already an edge in the CFG, then we need
3994                to move all the cases associated with E to E2.  */
3995             if (e2)
3996               {
3997                 tree cases2 = get_cases_for_edge (e2, stmt);
3998
3999                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4000                 TREE_CHAIN (cases2) = first;
4001               }
4002           }
4003         else
4004           {
4005             tree vec = SWITCH_LABELS (stmt);
4006             size_t i, n = TREE_VEC_LENGTH (vec);
4007
4008             for (i = 0; i < n; i++)
4009               {
4010                 tree elt = TREE_VEC_ELT (vec, i);
4011
4012                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4013                   CASE_LABEL (elt) = label;
4014               }
4015           }
4016
4017         break;
4018       }
4019
4020     case RETURN_EXPR:
4021       bsi_remove (&bsi);
4022       e->flags |= EDGE_FALLTHRU;
4023       break;
4024
4025     default:
4026       /* Otherwise it must be a fallthru edge, and we don't need to
4027          do anything besides redirecting it.  */
4028       gcc_assert (e->flags & EDGE_FALLTHRU);
4029       break;
4030     }
4031
4032   /* Update/insert PHI nodes as necessary.  */
4033
4034   /* Now update the edges in the CFG.  */
4035   e = ssa_redirect_edge (e, dest);
4036
4037   return e;
4038 }
4039
4040
4041 /* Simple wrapper, as we can always redirect fallthru edges.  */
4042
4043 static basic_block
4044 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4045 {
4046   e = tree_redirect_edge_and_branch (e, dest);
4047   gcc_assert (e);
4048
4049   return NULL;
4050 }
4051
4052
4053 /* Splits basic block BB after statement STMT (but at least after the
4054    labels).  If STMT is NULL, BB is split just after the labels.  */
4055
4056 static basic_block
4057 tree_split_block (basic_block bb, void *stmt)
4058 {
4059   block_stmt_iterator bsi, bsi_tgt;
4060   tree act;
4061   basic_block new_bb;
4062   edge e;
4063   edge_iterator ei;
4064
4065   new_bb = create_empty_bb (bb);
4066
4067   /* Redirect the outgoing edges.  */
4068   new_bb->succs = bb->succs;
4069   bb->succs = NULL;
4070   FOR_EACH_EDGE (e, ei, new_bb->succs)
4071     e->src = new_bb;
4072
4073   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4074     stmt = NULL;
4075
4076   /* Move everything from BSI to the new basic block.  */
4077   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4078     {
4079       act = bsi_stmt (bsi);
4080       if (TREE_CODE (act) == LABEL_EXPR)
4081         continue;
4082
4083       if (!stmt)
4084         break;
4085
4086       if (stmt == act)
4087         {
4088           bsi_next (&bsi);
4089           break;
4090         }
4091     }
4092
4093   bsi_tgt = bsi_start (new_bb);
4094   while (!bsi_end_p (bsi))
4095     {
4096       act = bsi_stmt (bsi);
4097       bsi_remove (&bsi);
4098       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4099     }
4100
4101   return new_bb;
4102 }
4103
4104
4105 /* Moves basic block BB after block AFTER.  */
4106
4107 static bool
4108 tree_move_block_after (basic_block bb, basic_block after)
4109 {
4110   if (bb->prev_bb == after)
4111     return true;
4112
4113   unlink_block (bb);
4114   link_block (bb, after);
4115
4116   return true;
4117 }
4118
4119
4120 /* Return true if basic_block can be duplicated.  */
4121
4122 static bool
4123 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4124 {
4125   return true;
4126 }
4127
4128
4129 /* Create a duplicate of the basic block BB.  NOTE: This does not
4130    preserve SSA form.  */
4131
4132 static basic_block
4133 tree_duplicate_bb (basic_block bb)
4134 {
4135   basic_block new_bb;
4136   block_stmt_iterator bsi, bsi_tgt;
4137   tree phi;
4138
4139   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4140
4141   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4142      the incoming edges have not been setup yet.  */
4143   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4144     {
4145       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4146       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4147     }
4148
4149   /* Keep the chain of PHI nodes in the same order so that they can be
4150      updated by ssa_redirect_edge.  */
4151   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4152
4153   bsi_tgt = bsi_start (new_bb);
4154   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4155     {
4156       def_operand_p def_p;
4157       ssa_op_iter op_iter;
4158       tree stmt, copy;
4159       int region;
4160
4161       stmt = bsi_stmt (bsi);
4162       if (TREE_CODE (stmt) == LABEL_EXPR)
4163         continue;
4164
4165       /* Create a new copy of STMT and duplicate STMT's virtual
4166          operands.  */
4167       copy = unshare_expr (stmt);
4168       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4169       copy_virtual_operands (copy, stmt);
4170       region = lookup_stmt_eh_region (stmt);
4171       if (region >= 0)
4172         add_stmt_to_eh_region (copy, region);
4173
4174       /* Create new names for all the definitions created by COPY and
4175          add replacement mappings for each new name.  */
4176       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4177         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4178     }
4179
4180   return new_bb;
4181 }
4182
4183
4184 /* Basic block BB_COPY was created by code duplication.  Add phi node
4185    arguments for edges going out of BB_COPY.  The blocks that were
4186    duplicated have BB_DUPLICATED set.  */
4187
4188 void
4189 add_phi_args_after_copy_bb (basic_block bb_copy)
4190 {
4191   basic_block bb, dest;
4192   edge e, e_copy;
4193   edge_iterator ei;
4194   tree phi, phi_copy, phi_next, def;
4195
4196   bb = get_bb_original (bb_copy);
4197
4198   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4199     {
4200       if (!phi_nodes (e_copy->dest))
4201         continue;
4202
4203       if (e_copy->dest->flags & BB_DUPLICATED)
4204         dest = get_bb_original (e_copy->dest);
4205       else
4206         dest = e_copy->dest;
4207
4208       e = find_edge (bb, dest);
4209       if (!e)
4210         {
4211           /* During loop unrolling the target of the latch edge is copied.
4212              In this case we are not looking for edge to dest, but to
4213              duplicated block whose original was dest.  */
4214           FOR_EACH_EDGE (e, ei, bb->succs)
4215             if ((e->dest->flags & BB_DUPLICATED)
4216                 && get_bb_original (e->dest) == dest)
4217               break;
4218
4219           gcc_assert (e != NULL);
4220         }
4221
4222       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4223            phi;
4224            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4225         {
4226           phi_next = PHI_CHAIN (phi);
4227           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4228           add_phi_arg (phi_copy, def, e_copy);
4229         }
4230     }
4231 }
4232
4233 /* Blocks in REGION_COPY array of length N_REGION were created by
4234    duplication of basic blocks.  Add phi node arguments for edges
4235    going from these blocks.  */
4236
4237 void
4238 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4239 {
4240   unsigned i;
4241
4242   for (i = 0; i < n_region; i++)
4243     region_copy[i]->flags |= BB_DUPLICATED;
4244
4245   for (i = 0; i < n_region; i++)
4246     add_phi_args_after_copy_bb (region_copy[i]);
4247
4248   for (i = 0; i < n_region; i++)
4249     region_copy[i]->flags &= ~BB_DUPLICATED;
4250 }
4251
4252 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4253    important exit edge EXIT.  By important we mean that no SSA name defined
4254    inside region is live over the other exit edges of the region.  All entry
4255    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4256    to the duplicate of the region.  SSA form, dominance and loop information
4257    is updated.  The new basic blocks are stored to REGION_COPY in the same
4258    order as they had in REGION, provided that REGION_COPY is not NULL.
4259    The function returns false if it is unable to copy the region,
4260    true otherwise.  */
4261
4262 bool
4263 tree_duplicate_sese_region (edge entry, edge exit,
4264                             basic_block *region, unsigned n_region,
4265                             basic_block *region_copy)
4266 {
4267   unsigned i, n_doms;
4268   bool free_region_copy = false, copying_header = false;
4269   struct loop *loop = entry->dest->loop_father;
4270   edge exit_copy;
4271   basic_block *doms;
4272   edge redirected;
4273   int total_freq = 0, entry_freq = 0;
4274   gcov_type total_count = 0, entry_count = 0;
4275
4276   if (!can_copy_bbs_p (region, n_region))
4277     return false;
4278
4279   /* Some sanity checking.  Note that we do not check for all possible
4280      missuses of the functions.  I.e. if you ask to copy something weird,
4281      it will work, but the state of structures probably will not be
4282      correct.  */
4283   for (i = 0; i < n_region; i++)
4284     {
4285       /* We do not handle subloops, i.e. all the blocks must belong to the
4286          same loop.  */
4287       if (region[i]->loop_father != loop)
4288         return false;
4289
4290       if (region[i] != entry->dest
4291           && region[i] == loop->header)
4292         return false;
4293     }
4294
4295   loop->copy = loop;
4296
4297   /* In case the function is used for loop header copying (which is the primary
4298      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4299   if (loop->header == entry->dest)
4300     {
4301       copying_header = true;
4302       loop->copy = loop->outer;
4303
4304       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4305         return false;
4306
4307       for (i = 0; i < n_region; i++)
4308         if (region[i] != exit->src
4309             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4310           return false;
4311     }
4312
4313   if (!region_copy)
4314     {
4315       region_copy = xmalloc (sizeof (basic_block) * n_region);
4316       free_region_copy = true;
4317     }
4318
4319   gcc_assert (!need_ssa_update_p ());
4320
4321   /* Record blocks outside the region that are dominated by something
4322      inside.  */
4323   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4324   initialize_original_copy_tables ();
4325
4326   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4327
4328   if (entry->dest->count)
4329     {
4330       total_count = entry->dest->count;
4331       entry_count = entry->count;
4332       /* Fix up corner cases, to avoid division by zero or creation of negative
4333          frequencies.  */
4334       if (entry_count > total_count)
4335         entry_count = total_count;
4336     }
4337   else
4338     {
4339       total_freq = entry->dest->frequency;
4340       entry_freq = EDGE_FREQUENCY (entry);
4341       /* Fix up corner cases, to avoid division by zero or creation of negative
4342          frequencies.  */
4343       if (total_freq == 0)
4344         total_freq = 1;
4345       else if (entry_freq > total_freq)
4346         entry_freq = total_freq;
4347     }
4348
4349   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4350   if (total_count)
4351     {
4352       scale_bbs_frequencies_gcov_type (region, n_region,
4353                                        total_count - entry_count,
4354                                        total_count);
4355       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4356                                        total_count);
4357     }
4358   else
4359     {
4360       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4361                                  total_freq);
4362       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4363     }
4364
4365   if (copying_header)
4366     {
4367       loop->header = exit->dest;
4368       loop->latch = exit->src;
4369     }
4370
4371   /* Redirect the entry and add the phi node arguments.  */
4372   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4373   gcc_assert (redirected != NULL);
4374   flush_pending_stmts (entry);
4375
4376   /* Concerning updating of dominators:  We must recount dominators
4377      for entry block and its copy.  Anything that is outside of the
4378      region, but was dominated by something inside needs recounting as
4379      well.  */
4380   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4381   doms[n_doms++] = get_bb_original (entry->dest);
4382   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4383   free (doms);
4384
4385   /* Add the other PHI node arguments.  */
4386   add_phi_args_after_copy (region_copy, n_region);
4387
4388   /* Update the SSA web.  */
4389   update_ssa (TODO_update_ssa);
4390
4391   if (free_region_copy)
4392     free (region_copy);
4393
4394   free_original_copy_tables ();
4395   return true;
4396 }
4397
4398
4399 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4400
4401 void
4402 dump_function_to_file (tree fn, FILE *file, int flags)
4403 {
4404   tree arg, vars, var;
4405   bool ignore_topmost_bind = false, any_var = false;
4406   basic_block bb;
4407   tree chain;
4408
4409   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4410
4411   arg = DECL_ARGUMENTS (fn);
4412   while (arg)
4413     {
4414       print_generic_expr (file, arg, dump_flags);
4415       if (TREE_CHAIN (arg))
4416         fprintf (file, ", ");
4417       arg = TREE_CHAIN (arg);
4418     }
4419   fprintf (file, ")\n");
4420
4421   if (flags & TDF_DETAILS)
4422     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4423   if (flags & TDF_RAW)
4424     {
4425       dump_node (fn, TDF_SLIM | flags, file);
4426       return;
4427     }
4428
4429   /* When GIMPLE is lowered, the variables are no longer available in
4430      BIND_EXPRs, so display them separately.  */
4431   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
4432     {
4433       ignore_topmost_bind = true;
4434
4435       fprintf (file, "{\n");
4436       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4437         {
4438           var = TREE_VALUE (vars);
4439
4440           print_generic_decl (file, var, flags);
4441           fprintf (file, "\n");
4442
4443           any_var = true;
4444         }
4445     }
4446
4447   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
4448     {
4449       /* Make a CFG based dump.  */
4450       check_bb_profile (ENTRY_BLOCK_PTR, file);
4451       if (!ignore_topmost_bind)
4452         fprintf (file, "{\n");
4453
4454       if (any_var && n_basic_blocks)
4455         fprintf (file, "\n");
4456
4457       FOR_EACH_BB (bb)
4458         dump_generic_bb (file, bb, 2, flags);
4459
4460       fprintf (file, "}\n");
4461       check_bb_profile (EXIT_BLOCK_PTR, file);
4462     }
4463   else
4464     {
4465       int indent;
4466
4467       /* Make a tree based dump.  */
4468       chain = DECL_SAVED_TREE (fn);
4469
4470       if (TREE_CODE (chain) == BIND_EXPR)
4471         {
4472           if (ignore_topmost_bind)
4473             {
4474               chain = BIND_EXPR_BODY (chain);
4475               indent = 2;
4476             }
4477           else
4478             indent = 0;
4479         }
4480       else
4481         {
4482           if (!ignore_topmost_bind)
4483             fprintf (file, "{\n");
4484           indent = 2;
4485         }
4486
4487       if (any_var)
4488         fprintf (file, "\n");
4489
4490       print_generic_stmt_indented (file, chain, flags, indent);
4491       if (ignore_topmost_bind)
4492         fprintf (file, "}\n");
4493     }
4494
4495   fprintf (file, "\n\n");
4496 }
4497
4498
4499 /* Pretty print of the loops intermediate representation.  */
4500 static void print_loop (FILE *, struct loop *, int);
4501 static void print_pred_bbs (FILE *, basic_block bb);
4502 static void print_succ_bbs (FILE *, basic_block bb);
4503
4504
4505 /* Print the predecessors indexes of edge E on FILE.  */
4506
4507 static void
4508 print_pred_bbs (FILE *file, basic_block bb)
4509 {
4510   edge e;
4511   edge_iterator ei;
4512
4513   FOR_EACH_EDGE (e, ei, bb->preds)
4514     fprintf (file, "bb_%d", e->src->index);
4515 }
4516
4517
4518 /* Print the successors indexes of edge E on FILE.  */
4519
4520 static void
4521 print_succ_bbs (FILE *file, basic_block bb)
4522 {
4523   edge e;
4524   edge_iterator ei;
4525
4526   FOR_EACH_EDGE (e, ei, bb->succs)
4527     fprintf (file, "bb_%d", e->src->index);
4528 }
4529
4530
4531 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
4532
4533 static void
4534 print_loop (FILE *file, struct loop *loop, int indent)
4535 {
4536   char *s_indent;
4537   basic_block bb;
4538
4539   if (loop == NULL)
4540     return;
4541
4542   s_indent = (char *) alloca ((size_t) indent + 1);
4543   memset ((void *) s_indent, ' ', (size_t) indent);
4544   s_indent[indent] = '\0';
4545
4546   /* Print the loop's header.  */
4547   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
4548
4549   /* Print the loop's body.  */
4550   fprintf (file, "%s{\n", s_indent);
4551   FOR_EACH_BB (bb)
4552     if (bb->loop_father == loop)
4553       {
4554         /* Print the basic_block's header.  */
4555         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
4556         print_pred_bbs (file, bb);
4557         fprintf (file, "}, succs = {");
4558         print_succ_bbs (file, bb);
4559         fprintf (file, "})\n");
4560
4561         /* Print the basic_block's body.  */
4562         fprintf (file, "%s  {\n", s_indent);
4563         tree_dump_bb (bb, file, indent + 4);
4564         fprintf (file, "%s  }\n", s_indent);
4565       }
4566
4567   print_loop (file, loop->inner, indent + 2);
4568   fprintf (file, "%s}\n", s_indent);
4569   print_loop (file, loop->next, indent);
4570 }
4571
4572
4573 /* Follow a CFG edge from the entry point of the program, and on entry
4574    of a loop, pretty print the loop structure on FILE.  */
4575
4576 void
4577 print_loop_ir (FILE *file)
4578 {
4579   basic_block bb;
4580
4581   bb = BASIC_BLOCK (0);
4582   if (bb && bb->loop_father)
4583     print_loop (file, bb->loop_father, 0);
4584 }
4585
4586
4587 /* Debugging loops structure at tree level.  */
4588
4589 void
4590 debug_loop_ir (void)
4591 {
4592   print_loop_ir (stderr);
4593 }
4594
4595
4596 /* Return true if BB ends with a call, possibly followed by some
4597    instructions that must stay with the call.  Return false,
4598    otherwise.  */
4599
4600 static bool
4601 tree_block_ends_with_call_p (basic_block bb)
4602 {
4603   block_stmt_iterator bsi = bsi_last (bb);
4604   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
4605 }
4606
4607
4608 /* Return true if BB ends with a conditional branch.  Return false,
4609    otherwise.  */
4610
4611 static bool
4612 tree_block_ends_with_condjump_p (basic_block bb)
4613 {
4614   tree stmt = last_stmt (bb);
4615   return (stmt && TREE_CODE (stmt) == COND_EXPR);
4616 }
4617
4618
4619 /* Return true if we need to add fake edge to exit at statement T.
4620    Helper function for tree_flow_call_edges_add.  */
4621
4622 static bool
4623 need_fake_edge_p (tree t)
4624 {
4625   tree call;
4626
4627   /* NORETURN and LONGJMP calls already have an edge to exit.
4628      CONST and PURE calls do not need one.
4629      We don't currently check for CONST and PURE here, although
4630      it would be a good idea, because those attributes are
4631      figured out from the RTL in mark_constant_function, and
4632      the counter incrementation code from -fprofile-arcs
4633      leads to different results from -fbranch-probabilities.  */
4634   call = get_call_expr_in (t);
4635   if (call
4636       && !(call_expr_flags (call) & ECF_NORETURN))
4637     return true;
4638
4639   if (TREE_CODE (t) == ASM_EXPR
4640        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
4641     return true;
4642
4643   return false;
4644 }
4645
4646
4647 /* Add fake edges to the function exit for any non constant and non
4648    noreturn calls, volatile inline assembly in the bitmap of blocks
4649    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
4650    the number of blocks that were split.
4651
4652    The goal is to expose cases in which entering a basic block does
4653    not imply that all subsequent instructions must be executed.  */
4654
4655 static int
4656 tree_flow_call_edges_add (sbitmap blocks)
4657 {
4658   int i;
4659   int blocks_split = 0;
4660   int last_bb = last_basic_block;
4661   bool check_last_block = false;
4662
4663   if (n_basic_blocks == 0)
4664     return 0;
4665
4666   if (! blocks)
4667     check_last_block = true;
4668   else
4669     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
4670
4671   /* In the last basic block, before epilogue generation, there will be
4672      a fallthru edge to EXIT.  Special care is required if the last insn
4673      of the last basic block is a call because make_edge folds duplicate
4674      edges, which would result in the fallthru edge also being marked
4675      fake, which would result in the fallthru edge being removed by
4676      remove_fake_edges, which would result in an invalid CFG.
4677
4678      Moreover, we can't elide the outgoing fake edge, since the block
4679      profiler needs to take this into account in order to solve the minimal
4680      spanning tree in the case that the call doesn't return.
4681
4682      Handle this by adding a dummy instruction in a new last basic block.  */
4683   if (check_last_block)
4684     {
4685       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
4686       block_stmt_iterator bsi = bsi_last (bb);
4687       tree t = NULL_TREE;
4688       if (!bsi_end_p (bsi))
4689         t = bsi_stmt (bsi);
4690
4691       if (need_fake_edge_p (t))
4692         {
4693           edge e;
4694
4695           e = find_edge (bb, EXIT_BLOCK_PTR);
4696           if (e)
4697             {
4698               bsi_insert_on_edge (e, build_empty_stmt ());
4699               bsi_commit_edge_inserts ();
4700             }
4701         }
4702     }
4703
4704   /* Now add fake edges to the function exit for any non constant
4705      calls since there is no way that we can determine if they will
4706      return or not...  */
4707   for (i = 0; i < last_bb; i++)
4708     {
4709       basic_block bb = BASIC_BLOCK (i);
4710       block_stmt_iterator bsi;
4711       tree stmt, last_stmt;
4712
4713       if (!bb)
4714         continue;
4715
4716       if (blocks && !TEST_BIT (blocks, i))
4717         continue;
4718
4719       bsi = bsi_last (bb);
4720       if (!bsi_end_p (bsi))
4721         {
4722           last_stmt = bsi_stmt (bsi);
4723           do
4724             {
4725               stmt = bsi_stmt (bsi);
4726               if (need_fake_edge_p (stmt))
4727                 {
4728                   edge e;
4729                   /* The handling above of the final block before the
4730                      epilogue should be enough to verify that there is
4731                      no edge to the exit block in CFG already.
4732                      Calling make_edge in such case would cause us to
4733                      mark that edge as fake and remove it later.  */
4734 #ifdef ENABLE_CHECKING
4735                   if (stmt == last_stmt)
4736                     {
4737                       e = find_edge (bb, EXIT_BLOCK_PTR);
4738                       gcc_assert (e == NULL);
4739                     }
4740 #endif
4741
4742                   /* Note that the following may create a new basic block
4743                      and renumber the existing basic blocks.  */
4744                   if (stmt != last_stmt)
4745                     {
4746                       e = split_block (bb, stmt);
4747                       if (e)
4748                         blocks_split++;
4749                     }
4750                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
4751                 }
4752               bsi_prev (&bsi);
4753             }
4754           while (!bsi_end_p (bsi));
4755         }
4756     }
4757
4758   if (blocks_split)
4759     verify_flow_info ();
4760
4761   return blocks_split;
4762 }
4763
4764 bool
4765 tree_purge_dead_eh_edges (basic_block bb)
4766 {
4767   bool changed = false;
4768   edge e;
4769   edge_iterator ei;
4770   tree stmt = last_stmt (bb);
4771
4772   if (stmt && tree_can_throw_internal (stmt))
4773     return false;
4774
4775   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
4776     {
4777       if (e->flags & EDGE_EH)
4778         {
4779           remove_edge (e);
4780           changed = true;
4781         }
4782       else
4783         ei_next (&ei);
4784     }
4785
4786   /* Removal of dead EH edges might change dominators of not
4787      just immediate successors.  E.g. when bb1 is changed so that
4788      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
4789      eh edges purged by this function in:
4790            0
4791           / \
4792          v   v
4793          1-->2
4794         / \  |
4795        v   v |
4796        3-->4 |
4797         \    v
4798          --->5
4799              |
4800              -
4801      idom(bb5) must be recomputed.  For now just free the dominance
4802      info.  */
4803   if (changed)
4804     free_dominance_info (CDI_DOMINATORS);
4805
4806   return changed;
4807 }
4808
4809 bool
4810 tree_purge_all_dead_eh_edges (bitmap blocks)
4811 {
4812   bool changed = false;
4813   unsigned i;
4814   bitmap_iterator bi;
4815
4816   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
4817     {
4818       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
4819     }
4820
4821   return changed;
4822 }
4823
4824 /* This function is called whenever a new edge is created or
4825    redirected.  */
4826
4827 static void
4828 tree_execute_on_growing_pred (edge e)
4829 {
4830   basic_block bb = e->dest;
4831
4832   if (phi_nodes (bb))
4833     reserve_phi_args_for_new_edge (bb);
4834 }
4835
4836 /* This function is called immediately before edge E is removed from
4837    the edge vector E->dest->preds.  */
4838
4839 static void
4840 tree_execute_on_shrinking_pred (edge e)
4841 {
4842   if (phi_nodes (e->dest))
4843     remove_phi_args (e);
4844 }
4845
4846 /*---------------------------------------------------------------------------
4847   Helper functions for Loop versioning
4848   ---------------------------------------------------------------------------*/
4849
4850 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
4851    of 'first'. Both of them are dominated by 'new_head' basic block. When
4852    'new_head' was created by 'second's incoming edge it received phi arguments
4853    on the edge by split_edge(). Later, additional edge 'e' was created to
4854    connect 'new_head' and 'first'. Now this routine adds phi args on this
4855    additional edge 'e' that new_head to second edge received as part of edge
4856    splitting.
4857 */
4858
4859 static void
4860 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
4861                                 basic_block new_head, edge e)
4862 {
4863   tree phi1, phi2;
4864   edge e2 = find_edge (new_head, second);
4865
4866   /* Because NEW_HEAD has been created by splitting SECOND's incoming
4867      edge, we should always have an edge from NEW_HEAD to SECOND.  */
4868   gcc_assert (e2 != NULL);
4869
4870   /* Browse all 'second' basic block phi nodes and add phi args to
4871      edge 'e' for 'first' head. PHI args are always in correct order.  */
4872
4873   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
4874        phi2 && phi1;
4875        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
4876     {
4877       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
4878       add_phi_arg (phi1, def, e);
4879     }
4880 }
4881
4882 /* Adds a if else statement to COND_BB with condition COND_EXPR.
4883    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
4884    the destination of the ELSE part.  */
4885 static void
4886 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
4887                             basic_block cond_bb, void *cond_e)
4888 {
4889   block_stmt_iterator bsi;
4890   tree goto1 = NULL_TREE;
4891   tree goto2 = NULL_TREE;
4892   tree new_cond_expr = NULL_TREE;
4893   tree cond_expr = (tree) cond_e;
4894   edge e0;
4895
4896   /* Build new conditional expr */
4897   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
4898   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
4899   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
4900
4901   /* Add new cond in cond_bb.  */
4902   bsi = bsi_start (cond_bb);
4903   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
4904   /* Adjust edges appropriately to connect new head with first head
4905      as well as second head.  */
4906   e0 = single_succ_edge (cond_bb);
4907   e0->flags &= ~EDGE_FALLTHRU;
4908   e0->flags |= EDGE_FALSE_VALUE;
4909 }
4910
4911 struct cfg_hooks tree_cfg_hooks = {
4912   "tree",
4913   tree_verify_flow_info,
4914   tree_dump_bb,                 /* dump_bb  */
4915   create_bb,                    /* create_basic_block  */
4916   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
4917   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
4918   remove_bb,                    /* delete_basic_block  */
4919   tree_split_block,             /* split_block  */
4920   tree_move_block_after,        /* move_block_after  */
4921   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
4922   tree_merge_blocks,            /* merge_blocks  */
4923   tree_predict_edge,            /* predict_edge  */
4924   tree_predicted_by_p,          /* predicted_by_p  */
4925   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
4926   tree_duplicate_bb,            /* duplicate_block  */
4927   tree_split_edge,              /* split_edge  */
4928   tree_make_forwarder_block,    /* make_forward_block  */
4929   NULL,                         /* tidy_fallthru_edge  */
4930   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
4931   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
4932   tree_flow_call_edges_add,     /* flow_call_edges_add */
4933   tree_execute_on_growing_pred, /* execute_on_growing_pred */
4934   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
4935   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
4936   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
4937   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
4938   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
4939   flush_pending_stmts           /* flush_pending_stmts */
4940 };
4941
4942
4943 /* Split all critical edges.  */
4944
4945 static void
4946 split_critical_edges (void)
4947 {
4948   basic_block bb;
4949   edge e;
4950   edge_iterator ei;
4951
4952   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
4953      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
4954      mappings around the calls to split_edge.  */
4955   start_recording_case_labels ();
4956   FOR_ALL_BB (bb)
4957     {
4958       FOR_EACH_EDGE (e, ei, bb->succs)
4959         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
4960           {
4961             split_edge (e);
4962           }
4963     }
4964   end_recording_case_labels ();
4965 }
4966
4967 struct tree_opt_pass pass_split_crit_edges =
4968 {
4969   "crited",                          /* name */
4970   NULL,                          /* gate */
4971   split_critical_edges,          /* execute */
4972   NULL,                          /* sub */
4973   NULL,                          /* next */
4974   0,                             /* static_pass_number */
4975   TV_TREE_SPLIT_EDGES,           /* tv_id */
4976   PROP_cfg,                      /* properties required */
4977   PROP_no_crit_edges,            /* properties_provided */
4978   0,                             /* properties_destroyed */
4979   0,                             /* todo_flags_start */
4980   TODO_dump_func,                /* todo_flags_finish */
4981   0                              /* letter */
4982 };
4983
4984 \f
4985 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
4986    a temporary, make sure and register it to be renamed if necessary,
4987    and finally return the temporary.  Put the statements to compute
4988    EXP before the current statement in BSI.  */
4989
4990 tree
4991 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
4992 {
4993   tree t, new_stmt, orig_stmt;
4994
4995   if (is_gimple_val (exp))
4996     return exp;
4997
4998   t = make_rename_temp (type, NULL);
4999   new_stmt = build (MODIFY_EXPR, type, t, exp);
5000
5001   orig_stmt = bsi_stmt (*bsi);
5002   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5003   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5004
5005   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5006
5007   return t;
5008 }
5009
5010 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5011    Return the gimple_val holding the result.  */
5012
5013 tree
5014 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5015                  tree type, tree a, tree b, tree c)
5016 {
5017   tree ret;
5018
5019   ret = fold_build3 (code, type, a, b, c);
5020   STRIP_NOPS (ret);
5021
5022   return gimplify_val (bsi, type, ret);
5023 }
5024
5025 /* Build a binary operation and gimplify it.  Emit code before BSI.
5026    Return the gimple_val holding the result.  */
5027
5028 tree
5029 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5030                  tree type, tree a, tree b)
5031 {
5032   tree ret;
5033
5034   ret = fold_build2 (code, type, a, b);
5035   STRIP_NOPS (ret);
5036
5037   return gimplify_val (bsi, type, ret);
5038 }
5039
5040 /* Build a unary operation and gimplify it.  Emit code before BSI.
5041    Return the gimple_val holding the result.  */
5042
5043 tree
5044 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5045                  tree a)
5046 {
5047   tree ret;
5048
5049   ret = fold_build1 (code, type, a);
5050   STRIP_NOPS (ret);
5051
5052   return gimplify_val (bsi, type, ret);
5053 }
5054
5055
5056 \f
5057 /* Emit return warnings.  */
5058
5059 static void
5060 execute_warn_function_return (void)
5061 {
5062 #ifdef USE_MAPPED_LOCATION
5063   source_location location;
5064 #else
5065   location_t *locus;
5066 #endif
5067   tree last;
5068   edge e;
5069   edge_iterator ei;
5070
5071   /* If we have a path to EXIT, then we do return.  */
5072   if (TREE_THIS_VOLATILE (cfun->decl)
5073       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5074     {
5075 #ifdef USE_MAPPED_LOCATION
5076       location = UNKNOWN_LOCATION;
5077 #else
5078       locus = NULL;
5079 #endif
5080       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5081         {
5082           last = last_stmt (e->src);
5083           if (TREE_CODE (last) == RETURN_EXPR
5084 #ifdef USE_MAPPED_LOCATION
5085               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5086 #else
5087               && (locus = EXPR_LOCUS (last)) != NULL)
5088 #endif
5089             break;
5090         }
5091 #ifdef USE_MAPPED_LOCATION
5092       if (location == UNKNOWN_LOCATION)
5093         location = cfun->function_end_locus;
5094       warning (0, "%H%<noreturn%> function does return", &location);
5095 #else
5096       if (!locus)
5097         locus = &cfun->function_end_locus;
5098       warning (0, "%H%<noreturn%> function does return", locus);
5099 #endif
5100     }
5101
5102   /* If we see "return;" in some basic block, then we do reach the end
5103      without returning a value.  */
5104   else if (warn_return_type
5105            && !TREE_NO_WARNING (cfun->decl)
5106            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5107            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5108     {
5109       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5110         {
5111           tree last = last_stmt (e->src);
5112           if (TREE_CODE (last) == RETURN_EXPR
5113               && TREE_OPERAND (last, 0) == NULL)
5114             {
5115 #ifdef USE_MAPPED_LOCATION
5116               location = EXPR_LOCATION (last);
5117               if (location == UNKNOWN_LOCATION)
5118                   location = cfun->function_end_locus;
5119               warning (0, "%Hcontrol reaches end of non-void function", &location);
5120 #else
5121               locus = EXPR_LOCUS (last);
5122               if (!locus)
5123                 locus = &cfun->function_end_locus;
5124               warning (0, "%Hcontrol reaches end of non-void function", locus);
5125 #endif
5126               TREE_NO_WARNING (cfun->decl) = 1;
5127               break;
5128             }
5129         }
5130     }
5131 }
5132
5133
5134 /* Given a basic block B which ends with a conditional and has
5135    precisely two successors, determine which of the edges is taken if
5136    the conditional is true and which is taken if the conditional is
5137    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5138
5139 void
5140 extract_true_false_edges_from_block (basic_block b,
5141                                      edge *true_edge,
5142                                      edge *false_edge)
5143 {
5144   edge e = EDGE_SUCC (b, 0);
5145
5146   if (e->flags & EDGE_TRUE_VALUE)
5147     {
5148       *true_edge = e;
5149       *false_edge = EDGE_SUCC (b, 1);
5150     }
5151   else
5152     {
5153       *false_edge = e;
5154       *true_edge = EDGE_SUCC (b, 1);
5155     }
5156 }
5157
5158 struct tree_opt_pass pass_warn_function_return =
5159 {
5160   NULL,                                 /* name */
5161   NULL,                                 /* gate */
5162   execute_warn_function_return,         /* execute */
5163   NULL,                                 /* sub */
5164   NULL,                                 /* next */
5165   0,                                    /* static_pass_number */
5166   0,                                    /* tv_id */
5167   PROP_cfg,                             /* properties_required */
5168   0,                                    /* properties_provided */
5169   0,                                    /* properties_destroyed */
5170   0,                                    /* todo_flags_start */
5171   0,                                    /* todo_flags_finish */
5172   0                                     /* letter */
5173 };
5174
5175 /* Emit noreturn warnings.  */
5176
5177 static void
5178 execute_warn_function_noreturn (void)
5179 {
5180   if (warn_missing_noreturn
5181       && !TREE_THIS_VOLATILE (cfun->decl)
5182       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5183       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5184     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5185              "for attribute %<noreturn%>",
5186              cfun->decl);
5187 }
5188
5189 struct tree_opt_pass pass_warn_function_noreturn =
5190 {
5191   NULL,                                 /* name */
5192   NULL,                                 /* gate */
5193   execute_warn_function_noreturn,       /* execute */
5194   NULL,                                 /* sub */
5195   NULL,                                 /* next */
5196   0,                                    /* static_pass_number */
5197   0,                                    /* tv_id */
5198   PROP_cfg,                             /* properties_required */
5199   0,                                    /* properties_provided */
5200   0,                                    /* properties_destroyed */
5201   0,                                    /* todo_flags_start */
5202   0,                                    /* todo_flags_finish */
5203   0                                     /* letter */
5204 };