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