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