gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003 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 "toplev.h"
  43 #include "except.h"
  44 #include "cfgloop.h"
  45
  46 /* This file contains functions for building the Control Flow Graph (CFG)
  47    for a function tree.  */
  48
  49 /* Statements in basic blocks are kept in double-linked list of tree_cell
  50    nodes.  On the beginning of the block there may be some labels, then
  51    statements follow.  The last statement is either control one (COND_EXPR
  52    or SWITCH_EXPR), the one that ends the block from some other reason
  53    or other.
  54
  55    If it is COND_EXPR, its then and else branches contain GOTO_EXPR to the
  56    target location.  None of the outgoing edges is marked fallthru.
  57
  58    If it is SWITCH_EXPR, its body contains a list (linked by COMPOUND_EXPRs)
  59    containing pairs of CASE_LABEL_EXPRs and GOTO_EXPRs (CASE_* macros below
  60    should be used to access them).  There always must be a default branch.
  61    None of the outgoing edges is marked fallthru.  There is a link case_edge
  62    from statement annotation of the CASE_LABEL_EXPRs to the appropriate edges.
  63
  64    If it is other block-ending statement (exception handling), the normal
  65    flow edge is marked fallthru.  It does not have to really lead to the
  66    following block.
  67
  68    If it is any other statement, there is exactly one fallthru edge to the
  69    following block.  (This is ugly.  The explicit gotos should not be
  70    here at all.  Still we cannot get rid of them completely -- computed gotos;
  71    so some special handling would be needed anyway, so let it be for now
  72    this way).
  73
  74    Some of these invariants may be violated by optimization passes.
  75    New blocks may be created on fallthru edges, and edges may be removed
  76    when they become unreachable.  The function tree_cleanup_edges fixes
  77    these issues (but it is ugly too.  The optimizations should be fixed
  78    to keep the state consistent.)  */
  79
  80 /* Local declarations.  */
  81
  82 /* Initial capacity for the basic block array.  */
  83 static const int initial_cfg_capacity = 20;
  84
  85 /* Dump files and flags.  */
  86 static FILE *dump_file;         /* CFG dump file. */
  87 static int dump_flags;          /* CFG dump flags.  */
  88
  89 /* Mapping of labels to their associated blocks.  This can greatly speed up
  90    building of the CFG in code with lots of gotos.  */
  91 static varray_type label_to_block_map;
  92
  93 /* Set if we no longer want bb_for_stmt to be kept.  */
  94 int no_bb_for_stmt;
  95
  96 /* CFG statistics.  */
  97 struct cfg_stats_d
  98 {
  99   long num_merged_cases;
 100   long num_merged_labels;
 101   long num_failed_bind_expr_merges;
 102 };
 103
 104 static dominance_info pdom_info = NULL;
 105
 106 static struct cfg_stats_d cfg_stats;
 107
 108 static struct obstack block_ann_obstack;
 109 static void *first_block_ann_obj = 0;
 110
 111 /* Control structure decomposition tree.  */
 112 struct control
 113 {
 114   enum cs_type
 115     {
 116       CS_TOP,
 117       CS_WHILE_LOOP,
 118       CS_DO_WHILE_LOOP,
 119       CS_INFINITE_LOOP,
 120       CS_IF_THEN_ELSE,
 121       CS_IF_THEN,
 122       CS_IF_ELSE,
 123       CS_BB
 124     } type;                     /* Type of the structure.  */
 125
 126   struct control *outer;        /* Outer sutructure.  */
 127   struct control *son;          /* The first substructure.  */
 128   struct control *next, *prev;  /* The next control structure in a chain.  */
 129
 130   int level;                    /* Nesting level of the structure.  */
 131   bool visited;                 /* A mark.  */
 132   varray_type exits;            /* Exits from the structure.  */
 133   struct control *lay_head, *lay_next, *lay_last;
 134   struct control *follow_node;  /* The next cs after the structure.  */
 135                                 /* Chain of layout.  */
 136   struct control *else_node;
 137
 138   tree artificial_label;        /* In case artificial label is to be added
 139                                    to the start of the block, its set here.  */
 140   enum fa
 141     {
 142       MAKE_FALLTHRU,
 143       ADD_GOTO,
 144       ADD_BREAK,
 145       ADD_CONTINUE
 146     } fa_then, fa_else;         /* What to do with final statement?  */
 147
 148   basic_block header;           /* Entry of the structure.  */
 149   basic_block latch;            /* Latch of a loop.  */
 150   basic_block follow;           /* The next block after the structure.  */
 151 };
 152
 153 /* Basic blocks and flowgraphs.  */
 154 static void make_blocks (tree_cell);
 155 static inline void append_stmt_to_bb (tree_cell, basic_block);
 156 extern void debug_tree_chain (tree_cell);
 157 static void create_blocks_annotations (void);
 158 static void create_block_annotation (basic_block);
 159 static void free_blocks_annotations (void);
 160 static void clear_blocks_annotations (void);
 161
 162 /* Edges.  */
 163 static void make_edges (void);
 164 static void make_ctrl_stmt_edges (basic_block);
 165 static void make_exit_edges (basic_block);
 166 static void make_cond_expr_edges (basic_block);
 167 static void make_goto_expr_edges (basic_block);
 168 static void make_switch_expr_edges (basic_block);
 169 static bool tree_redirect_edge_and_branch (edge, basic_block);
 170
 171 /* Various helpers.  */
 172 static inline bool stmt_starts_bb_p (tree, tree);
 173 static inline bool stmt_ends_bb_p (tree);
 174 static int tree_verify_flow_info (void);
 175 static basic_block tree_make_forwarder_block (basic_block, int, int, edge, int);
 176 static void replace_stmt (tree_cell, tree);
 177 static struct loops *tree_loop_optimizer_init (FILE *);
 178 static void tree_loop_optimizer_finalize (struct loops *, FILE *);
 179
 180 /* Flowgraph optimization and cleanup.  */
 181 static void remove_bb (basic_block);
 182 static void tree_merge_blocks (basic_block, basic_block);
 183 static void remove_stmt (tree_cell, basic_block, bool);
 184 static edge find_taken_edge_cond_expr (basic_block, tree);
 185 static edge find_taken_edge_switch_expr (basic_block, tree);
 186 static tree find_edge_goto (tree, edge);
 187 static bool value_matches_label (edge, tree, tree, edge *);
 188 static void tree_cleanup_edges (void);
 189 static void remove_superfluous_labels (void);
 190 static void thread_jumps (void);
 191 static bool tree_forwarder_block_p (basic_block);
 192 static void merge_seq_blocks (void);
 193 static tree CASE_GOTO (tree_stmt_iterator);
 194 static struct control *determine_structures (struct control *[]);
 195 static struct control *make_control_node (enum cs_type, struct control *,
 196                                           basic_block, basic_block,
 197                                           basic_block);
 198 static void try_move_control_node (struct control *, struct control *,
 199                                    struct control *);
 200 static void move_control_node (struct control *, struct control *);
 201 static void dump_cs_tree (FILE *, int, struct control *, struct control *[]);
 202 static void free_cs_tree (struct control *);
 203 static void add_bb_cs_nodes (struct control *[]);
 204 static void assign_levels (struct control *, int);
 205 static void compute_structure_exits (struct control *[]);
 206 static void layout_structures (struct control *, struct control *[]);
 207 static void layout_structure (struct control *, struct control *,
 208                               struct control *[]);
 209 static void add_to_layout (struct control *);
 210 static void finish_layout (struct control *);
 211 static tree reconstruct_tree (struct control *, struct control *[]);
 212 static bool inside_cs (basic_block, struct control *, struct control *[]);
 213 static struct control *lift (struct control *, int);
 214 static basic_block first_cs_bb (struct control *);
 215 static void fixup_gotos (struct control *, struct control *[],
 216                          struct control *, basic_block, basic_block);
 217 static void establish_gotos (tree *, enum fa, struct control *);
 218 static enum fa decide_final_action (basic_block, basic_block, basic_block,
 219                                     basic_block, struct control *[]);
 220
 221 /* Location to track pending stmt for edge insertion.  */
 222 #define PENDING_STMT(e) ((tree)(e->insns))
 223
 224 /* Set the pending stmt field.  */
 225 #define SET_PENDING_STMT(e, t)  ((e->insns) = (rtx)t)
 226
 227 /* Accessors for switch statement case list.  */
 228 #define CASE_START(STMT) tsi_start (&SWITCH_BODY (STMT))
 229 #define CASE_NEXT(TSI) tsi_next (&TSI), tsi_next (&TSI)
 230 #define CASE_END_P(TSI) tsi_end_p (TSI)
 231 static tree
 232 CASE_GOTO (tree_stmt_iterator tsi)
 233 {
 234   tsi_next (&tsi);
 235   return tsi_stmt (tsi);
 236 }
 237 #define CASE_DESTINATION(TSI) (GOTO_DESTINATION (CASE_GOTO (TSI)))
 238 #define CASE_CASE(TSI) (tsi_stmt(TSI))
 239 #define CASE_EDGE(TSI) (get_stmt_ann (CASE_CASE (TSI))->case_edge)
 240
 241 /* FIXME These need to be filled in with appropriate pointers.  But this
 242    implies an ABI change in some functions.  */
 243 struct cfg_hooks tree_cfg_hooks = {
 244   tree_verify_flow_info,
 245   NULL,                         /* dump_bb  */
 246   NULL,                         /* create_basic_block  */
 247   tree_redirect_edge_and_branch, /* redirect_edge_and_branch  */
 248   NULL,                         /* redirect_edge_and_branch_force  */
 249   remove_bb,                    /* delete_basic_block  */
 250   NULL,                         /* split_block  */
 251   NULL,                         /* can_merge_blocks_p  */
 252   tree_merge_blocks,            /* merge_blocks  */
 253   tree_split_edge,              /* cfgh_split_edge  */
 254   tree_make_forwarder_block,    /* cfgh_make_forward_block  */
 255   tree_cleanup_edges,           /* cfgh_tidy_fallthru_edges  */
 256   tree_loop_optimizer_init,     /* cfgh_loop_optimizer_init  */
 257   tree_loop_optimizer_finalize  /* cfgh_loop_optimizer_finalize  */
 258 };
 259
 260 /*---------------------------------------------------------------------------
 261                               Create basic blocks
 262 ---------------------------------------------------------------------------*/
 263
 264 /* Entry point to the CFG builder for trees.  FNBODY is the body of the
 265    function to process.  */
 266
 267 void
 268 build_tree_cfg (tree_cell fnbody)
 269 {
 270   timevar_push (TV_TREE_CFG);
 271
 272   /* Register specific tree functions.  */
 273   tree_register_cfg_hooks ();
 274
 275   /* Initialize the basic block array.  */
 276   n_basic_blocks = 0;
 277   last_basic_block = 0;
 278   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
 279   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 280   no_bb_for_stmt = false;
 281
 282   /* Build a mapping of labels to their associated blocks.  */
 283   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
 284                   "label to block map");
 285
 286   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 287   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 288
 289   /* Find the basic blocks for the flowgraph.  Ignore empty functions.  */
 290   if (!fnbody)
 291     {
 292       timevar_pop (TV_TREE_CFG);
 293       return;
 294     }
 295
 296   /* Create block annotations.  */
 297   create_blocks_annotations ();
 298
 299   make_blocks (fnbody);
 300
 301   if (n_basic_blocks > 0)
 302     {
 303       /* Adjust the size of the array.  */
 304       VARRAY_GROW (basic_block_info, n_basic_blocks);
 305
 306       /* Create the edges of the flowgraph.  */
 307       make_edges ();
 308     }
 309
 310 #if 0
 311   {
 312     /* The loop analyzer should be initialized right after the CFG
 313        construction because some loops will need latch blocks, and these
 314        need to be added before we do anything else.  If you use this
 315        structure you'll have to ensure that optimizers don't invalidate the
 316        information gathered in the loops structure via modifications to the
 317        underlying structure: the CFG.  */
 318     struct loops *loops = loop_optimizer_init (NULL);
 319
 320     /* Once initialized, it's not really necessary to keep the loop data
 321        structures around.  They may be rescanned using flow_loops_find.  */
 322     loop_optimizer_finalize (loops, NULL);
 323   }
 324 #endif
 325
 326   timevar_pop (TV_TREE_CFG);
 327
 328   cleanup_tree_cfg (true);
 329 #if defined ENABLE_CHECKING
 330   verify_flow_info ();
 331 #endif
 332
 333   /* Debugging dumps.  */
 334   if (n_basic_blocks > 0)
 335     {
 336       /* Write the flowgraph to a dot file.  */
 337       dump_file = dump_begin (TDI_dot, &dump_flags);
 338       if (dump_file)
 339         {
 340           tree_cfg2dot (dump_file);
 341           dump_end (TDI_dot, dump_file);
 342         }
 343
 344       /* Dump a textual representation of the flowgraph.  */
 345       dump_file = dump_begin (TDI_cfg, &dump_flags);
 346       if (dump_file)
 347         {
 348           dump_tree_cfg (dump_file, dump_flags);
 349           dump_end (TDI_cfg, dump_file);
 350         }
 351     }
 352 }
 353
 354 /* Create annotations for all the basic blocks.  */
 355
 356 static void create_blocks_annotations (void)
 357 {
 358   basic_block bb;
 359   static int initialized;
 360
 361   if (!initialized)
 362     {
 363       gcc_obstack_init (&block_ann_obstack);
 364       initialized = 1;
 365     }
 366   /* Check whether TREE_ANNOTATIONS data are still allocated.  */
 367   else if (first_block_ann_obj)
 368     abort ();
 369
 370   first_block_ann_obj = obstack_alloc (&block_ann_obstack, 0);
 371
 372   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 373     create_block_annotation (bb);
 374 }
 375
 376 /* Create annotations for a single basic block.  */
 377
 378 static void create_block_annotation (basic_block bb)
 379 {
 380   /* Verify that the tree_annotations field is clear.  */
 381   if (bb->tree_annotations || !first_block_ann_obj)
 382     abort ();
 383   bb->tree_annotations = obstack_alloc (&block_ann_obstack,
 384                                         sizeof (struct bb_ann_d));
 385   memset (bb->tree_annotations, 0, sizeof (struct bb_ann_d));
 386 }
 387
 388 /* Free the annotations for all the basic blocks.  */
 389
 390 static void free_blocks_annotations (void)
 391 {
 392   if (!first_block_ann_obj)
 393     abort ();
 394   obstack_free (&block_ann_obstack, first_block_ann_obj);
 395   first_block_ann_obj = NULL;
 396
 397   clear_blocks_annotations ();
 398 }
 399
 400 /* Clear the annotations for all the basic blocks.  */
 401
 402 static void
 403 clear_blocks_annotations (void)
 404 {
 405   basic_block bb;
 406
 407   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 408     bb->tree_annotations = NULL;
 409 }
 410
 411 /* Build a flowgraph for the statements starting at the statement STMT.  */
 412
 413 static void
 414 make_blocks (tree_cell stmt)
 415 {
 416   tree_cell act, next;
 417   basic_block bb = NULL;
 418   tree prev_stmt;
 419
 420   if (stmt == NULL
 421       || stmt->stmt == error_mark_node)
 422     return;
 423
 424   for (act = stmt; act; act = next)
 425     {
 426       next = act->next;
 427
 428       prev_stmt = act->prev ? act->prev->stmt : NULL_TREE;
 429       if (!bb || stmt_starts_bb_p (act->stmt, prev_stmt))
 430         {
 431           if (act->prev)
 432             act->prev->next = NULL;
 433           act->prev = NULL;
 434           bb = create_bb ();
 435         }
 436
 437       append_stmt_to_bb (act, bb);
 438
 439       if (stmt_ends_bb_p (act->stmt))
 440         {
 441           bb = NULL;
 442           act->next = NULL;
 443         }
 444     }
 445 }
 446
 447 /* Add statement STMT to basic block BB and update BB's
 448    boundaries accordingly.  */
 449
 450 static inline void
 451 append_stmt_to_bb (tree_cell stmt, basic_block bb)
 452 {
 453   set_bb_for_stmt (stmt->stmt, bb);
 454
 455   /* Update the head and tail of the block.  */
 456   if (bb->head_tree == NULL)
 457     bb->head_tree = stmt;
 458
 459   bb->end_tree = stmt;
 460 }
 461
 462 /* Create and return a new basic block.  */
 463
 464 basic_block
 465 create_bb (void)
 466 {
 467   basic_block bb;
 468
 469   /* Create and initialize a new basic block.  */
 470   bb = alloc_block ();
 471   memset (bb, 0, sizeof (*bb));
 472   create_block_annotation (bb);
 473
 474   bb->index = last_basic_block;
 475   bb->flags = BB_NEW;
 476
 477   /* Add the new block to the linked list of blocks.  */
 478   link_block (bb, EXIT_BLOCK_PTR->prev_bb);
 479
 480   /* Grow the basic block array if needed.  */
 481   if ((size_t) n_basic_blocks == VARRAY_SIZE (basic_block_info))
 482     VARRAY_GROW (basic_block_info, n_basic_blocks + (n_basic_blocks + 3) / 4);
 483
 484   /* Add the newly created block to the array.  */
 485   BASIC_BLOCK (n_basic_blocks) = bb;
 486   n_basic_blocks++;
 487   last_basic_block++;
 488
 489   return bb;
 490 }
 491
 492 /*---------------------------------------------------------------------------
 493                                  Edge creation
 494 ---------------------------------------------------------------------------*/
 495
 496 /* Join all the blocks in the flowgraph.  */
 497
 498 static void
 499 make_edges (void)
 500 {
 501   basic_block bb;
 502
 503   /* Create an edge from entry to the first block with executable
 504      statements in it.  */
 505   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
 506
 507   /* Traverse basic block array placing edges.  */
 508   FOR_EACH_BB (bb)
 509     {
 510       tree first = first_stmt (bb);
 511       tree last = last_stmt (bb);
 512
 513       if (first)
 514         {
 515           /* Edges for statements that always alter flow control.  */
 516           if (is_ctrl_stmt (last))
 517             make_ctrl_stmt_edges (bb);
 518
 519           /* Edges for statements that sometimes alter flow control.  */
 520           if (is_ctrl_altering_stmt (last))
 521             make_exit_edges (bb);
 522         }
 523
 524       /* Finally, if no edges were created above, this is a regular
 525          basic block that only needs a fallthru edge.  */
 526       if (bb->succ == NULL)
 527         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 528     }
 529
 530   /* We do not care about fake edges, so remove any that the CFG
 531      builder inserted for completeness.  */
 532   remove_fake_edges ();
 533 }
 534
 535 /* Create edges for control statement at basic block BB.  */
 536
 537 static void
 538 make_ctrl_stmt_edges (basic_block bb)
 539 {
 540   tree last = last_stmt (bb);
 541
 542 #if defined ENABLE_CHECKING
 543   if (last == NULL_TREE)
 544     abort();
 545 #endif
 546
 547   switch (TREE_CODE (last))
 548     {
 549     case GOTO_EXPR:
 550       make_goto_expr_edges (bb);
 551
 552       /* If this is potentially a nonlocal goto, then this should also
 553          create an edge to the exit block.   */
 554       if ((TREE_CODE (GOTO_DESTINATION (last)) == LABEL_DECL
 555            && (decl_function_context (GOTO_DESTINATION (last))
 556                != current_function_decl))
 557           || (TREE_CODE (GOTO_DESTINATION (last)) != LABEL_DECL
 558               && DECL_CONTEXT (current_function_decl)))
 559         make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL);
 560       break;
 561
 562     case RETURN_EXPR:
 563       make_edge (bb, EXIT_BLOCK_PTR, 0);
 564       break;
 565
 566     case COND_EXPR:
 567       make_cond_expr_edges (bb);
 568       break;
 569
 570     case SWITCH_EXPR:
 571       make_switch_expr_edges (bb);
 572       break;
 573
 574     case RESX_EXPR:
 575       make_eh_edges (last);
 576       /* Yet another NORETURN hack.  */
 577       if (bb->succ == NULL)
 578         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 579       break;
 580
 581     default:
 582       abort ();
 583     }
 584 }
 585
 586 /* Checks whether STMT is potentially a nonlocal goto.  */
 587 static bool
 588 nonlocal_goto_p (tree stmt)
 589 {
 590   return (TREE_CODE (GOTO_DESTINATION (stmt)) == LABEL_DECL
 591           && (decl_function_context (GOTO_DESTINATION (stmt))
 592                != current_function_decl))
 593           || (TREE_CODE (GOTO_DESTINATION (stmt)) != LABEL_DECL
 594               && DECL_CONTEXT (current_function_decl));
 595 }
 596
 597 /* Create exit edges for statements in block BB that alter the flow of
 598    control.  Statements that alter the control flow are 'goto', 'return'
 599    and calls to non-returning functions.  */
 600
 601 static void
 602 make_exit_edges (basic_block bb)
 603 {
 604   tree last = last_stmt (bb);
 605
 606   if (last == NULL_TREE)
 607     abort ();
 608
 609   switch (TREE_CODE (last))
 610     {
 611     case CALL_EXPR:
 612       /* If this function receives a nonlocal goto, then we need to
 613          make edges from this call site to all the nonlocal goto
 614          handlers.  */
 615       if (FUNCTION_RECEIVES_NONLOCAL_GOTO (current_function_decl))
 616         make_goto_expr_edges (bb);
 617
 618       /* If this statement has reachable exception handlers, then
 619          create abnormal edges to them.  */
 620       make_eh_edges (last);
 621
 622       /* Some calls are known not to return.  For such calls we create
 623          a fake edge.
 624
 625          We really need to revamp how we build edges so that it's not
 626          such a bloody pain to avoid creating edges for this case since
 627          all we do is remove these edges when we're done building the
 628          CFG.  */
 629       if (call_expr_flags (last) & (ECF_NORETURN | ECF_LONGJMP))
 630         {
 631           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 632           return;
 633         }
 634
 635       /* Don't forget the fall-thru edge.  */
 636       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 637       break;
 638
 639     case MODIFY_EXPR:
 640       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
 641          may have an abnormal edge.  Search the RHS for this case and
 642          create any required edges.  */
 643       if (TREE_CODE (TREE_OPERAND (last, 1)) == CALL_EXPR
 644           && FUNCTION_RECEIVES_NONLOCAL_GOTO (current_function_decl))
 645         make_goto_expr_edges (bb);
 646
 647       make_eh_edges (last);
 648       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 649       break;
 650
 651     default:
 652       abort ();
 653     }
 654 }
 655
 656 /* Create the edges for a COND_EXPR starting at block BB.  */
 657
 658 static void
 659 make_cond_expr_edges (basic_block bb)
 660 {
 661   tree entry = last_stmt (bb);
 662   basic_block then_bb, else_bb;
 663   tree then_label, else_label;
 664
 665 #if defined ENABLE_CHECKING
 666   if (entry == NULL_TREE || TREE_CODE (entry) != COND_EXPR)
 667     abort ();
 668 #endif
 669
 670   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
 671   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
 672   then_bb = VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (then_label));
 673   else_bb = VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (else_label));
 674   make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 675   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 676 }
 677
 678 /* Create the edges for a SWITCH_EXPR starting at block BB.  */
 679
 680 static void
 681 make_switch_expr_edges (basic_block bb)
 682 {
 683   tree entry = last_stmt (bb);
 684   basic_block label_bb;
 685   tree label;
 686   tree_stmt_iterator case_entry;
 687   edge e;
 688
 689 #if defined ENABLE_CHECKING
 690   if (entry == NULL_TREE || TREE_CODE (entry) != SWITCH_EXPR)
 691     abort ();
 692 #endif
 693
 694   for (case_entry = CASE_START (entry);
 695        !CASE_END_P (case_entry);
 696        CASE_NEXT (case_entry))
 697     {
 698       label = CASE_DESTINATION (case_entry);
 699       label_bb = VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (label));
 700       e = make_edge (bb, label_bb, 0);
 701       if (!e)
 702         e = find_edge (bb, label_bb);
 703       if (!e)
 704         abort ();
 705       CASE_EDGE (case_entry) = e;
 706     }
 707 }
 708
 709 /* Redirects edge E to basic block DEST.  */
 710 static bool
 711 tree_redirect_edge_and_branch (edge e, basic_block dest)
 712 {
 713   block_stmt_iterator bsi;
 714   tree stmt, gto;
 715   basic_block bb = e->src;
 716   edge old;
 717   tree_stmt_iterator case_entry;
 718
 719   if (e->dest == dest)
 720     return true;
 721
 722   if (e->flags & EDGE_ABNORMAL)
 723     return false;
 724
 725   stmt = last_stmt (bb);
 726   bsi = bsi_last (bb);
 727
 728   /* If some edge is already there, use it if possible.  */
 729   old = find_edge (bb, dest);
 730   if (old && (old->flags & EDGE_ABNORMAL))
 731     return false;
 732
 733   if (!stmt
 734       || !stmt_ends_bb_p (stmt))
 735     {
 736       if (!(e->flags & EDGE_FALLTHRU))
 737         abort ();
 738
 739       if (old)
 740         abort ();
 741
 742       goto redirect;
 743     }
 744
 745   if (TREE_CODE (stmt) == COND_EXPR
 746       || TREE_CODE (stmt) == GOTO_EXPR)
 747     {
 748       gto = find_edge_goto (stmt, e);
 749       GOTO_DESTINATION (gto) = tree_block_label (dest);
 750       goto redirect;
 751     }
 752
 753   if (TREE_CODE (stmt) == SWITCH_EXPR)
 754     {
 755       /* This is more complicated, since there may be more gotos corresponding
 756          to this edge.  */
 757       for (case_entry = CASE_START (stmt);
 758            !CASE_END_P (case_entry);
 759            CASE_NEXT (case_entry))
 760         if (CASE_EDGE (case_entry) == e)
 761           {
 762             CASE_DESTINATION (case_entry) = tree_block_label (dest);
 763             if (old)
 764               CASE_EDGE (case_entry) = old;
 765           }
 766
 767       goto redirect;
 768     }
 769
 770   if (e->flags & EDGE_FALLTHRU)
 771     goto redirect;
 772
 773   return false;
 774
 775 redirect:
 776   if (old)
 777     ssa_remove_edge (e);
 778   else
 779     {
 780       tree phi;
 781
 782       for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
 783         remove_phi_arg (phi, e->src);
 784       redirect_edge_succ (e, dest);
 785     }
 786   tree_cleanup_block_edges (bb, false);
 787   return true;
 788 }
 789
 790 basic_block
 791 label_to_block (tree dest)
 792 {
 793   return VARRAY_BB (label_to_block_map, LABEL_DECL_INDEX (dest));
 794 }
 795
 796 /* Create edges for a goto statement at block BB.  */
 797
 798 static void
 799 make_goto_expr_edges (basic_block bb)
 800 {
 801   tree goto_t, dest;
 802   basic_block target_bb;
 803   int edge_flags;
 804   int for_call;
 805
 806   goto_t = last_stmt (bb);
 807
 808   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
 809      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
 810      from a nonlocal goto.  */
 811   if (TREE_CODE (goto_t) != GOTO_EXPR)
 812     {
 813       dest = error_mark_node;
 814       for_call = 1;
 815       edge_flags = EDGE_ABNORMAL;
 816     }
 817   else
 818     {
 819       dest = GOTO_DESTINATION (goto_t);
 820       for_call = 0;
 821
 822       /* A GOTO to a local label creates normal edges.  */
 823       if (TREE_CODE (dest) == LABEL_DECL && ! NONLOCAL_LABEL (dest))
 824         {
 825           make_edge (bb, label_to_block (dest), 0);
 826           return;
 827         }
 828
 829       /* If we reach here, then we either have a computed goto or
 830          a nonlocal goto.  */
 831       edge_flags = EDGE_ABNORMAL;
 832     }
 833
 834   /* Look for the block starting with the destination label.  In the
 835      case of a computed goto, make an edge to any label block we find
 836      in the CFG.  */
 837   FOR_EACH_BB (target_bb)
 838     {
 839       block_stmt_iterator bsi;
 840
 841       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
 842         {
 843           tree target = bsi_stmt (bsi);
 844
 845           if (TREE_CODE (target) != LABEL_EXPR)
 846             break;
 847
 848           /* Computed GOTOs.  Make an edge to every label block that has
 849              been marked as a potential target for a computed goto.  */
 850           if (TREE_CODE (dest) != LABEL_DECL
 851               && FORCED_LABEL (LABEL_EXPR_LABEL (target))
 852               && for_call == 0)
 853             make_edge (bb, target_bb, edge_flags);
 854
 855           /* Nonlocal GOTO target.  Make an edge to every label block that has
 856              been marked as a potential target for a nonlocal goto.  */
 857           else if (TREE_CODE (dest) != LABEL_DECL
 858                    && NONLOCAL_LABEL (LABEL_EXPR_LABEL (target))
 859                    && for_call == 1)
 860             make_edge (bb, target_bb, edge_flags);
 861         }
 862     }
 863 }
 864
 865 /*---------------------------------------------------------------------------
 866                                Flowgraph analysis
 867 ---------------------------------------------------------------------------*/
 868
 869 /* Remove unreachable blocks and other miscellaneous clean up work.  */
 870
 871 void
 872 cleanup_tree_cfg (int expensive)
 873 {
 874   int orig_n_basic_blocks = n_basic_blocks;
 875
 876   timevar_push (TV_TREE_CLEANUP_CFG);
 877   if (pdom_info != NULL)
 878     {
 879       free_dominance_info (pdom_info);
 880       pdom_info = NULL;
 881     }
 882   tree_cleanup_edges ();
 883   if (expensive)
 884     {
 885       remove_superfluous_labels ();
 886       thread_jumps ();
 887     }
 888   delete_unreachable_blocks ();
 889   merge_seq_blocks ();
 890   compact_blocks ();
 891 #ifdef ENABLE_CHECKING
 892   verify_flow_info ();
 893 #endif
 894
 895   /* If we expunged any basic blocks, then the dominator tree is
 896      no longer valid.  */
 897   if (n_basic_blocks != orig_n_basic_blocks)
 898     {
 899       basic_block bb;
 900
 901       FOR_EACH_BB (bb)
 902         clear_dom_children (bb);
 903     }
 904
 905   timevar_pop (TV_TREE_CLEANUP_CFG);
 906 }
 907
 908 /* Remove PHI nodes associated with basic block BB and all edges into
 909    and out of BB.  */
 910 void
 911 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
 912 {
 913   /* Remove the edges into and out of this block.  */
 914   while (bb->pred != NULL)
 915     {
 916       tree phi;
 917
 918       /* Since this block is no longer reachable, we can just delete all
 919          of its PHI nodes.  */
 920       phi = phi_nodes (bb);
 921       while (phi)
 922         {
 923           tree next = TREE_CHAIN (phi);
 924           remove_phi_node (phi, NULL_TREE, bb);
 925           phi = next;
 926         }
 927
 928       remove_edge (bb->pred);
 929     }
 930
 931   /* Remove edges to BB's successors.  */
 932   while (bb->succ != NULL)
 933     ssa_remove_edge (bb->succ);
 934 }
 935
 936 /* Remove block BB and its statements from the flowgraph.  */
 937
 938 static void
 939 remove_bb (basic_block bb)
 940 {
 941   block_stmt_iterator i;
 942   location_t loc;
 943
 944   dump_file = dump_begin (TDI_cfg, &dump_flags);
 945   if (dump_file)
 946     {
 947       fprintf (dump_file, "Removing basic block %d\n", bb->index);
 948       dump_tree_bb (dump_file, "", bb, 0);
 949       fprintf (dump_file, "\n");
 950       dump_end (TDI_cfg, dump_file);
 951       dump_file = NULL;
 952     }
 953
 954   loc.line = -1;
 955
 956   /* Remove all the instructions in the block.  */
 957   for (i = bsi_last (bb); !bsi_end_p (i); i = bsi_last (bb))
 958     {
 959       tree stmt = bsi_stmt (i);
 960
 961       if (get_lineno (stmt) >= 0)
 962         {
 963           loc.file = get_filename (stmt);
 964           loc.line = get_lineno (stmt);
 965         }
 966       bsi_remove (&i);
 967       set_bb_for_stmt (stmt, NULL);
 968     }
 969
 970   /* If requested, give a warning that the first statement in the
 971      block is unreachable.  We walk statements backwards in the
 972      loop above, so the last statement we process is the first statement
 973      in the block.  */
 974   if (warn_notreached && loc.line >= 0)
 975     warning ("%Hwill never be executed", &loc);
 976
 977   remove_phi_nodes_and_edges_for_unreachable_block (bb);
 978
 979   /* If we have pdom information, then we must also make sure to
 980      clean up the dominance information.  */
 981   if (pdom_info)
 982     delete_from_dominance_info (pdom_info, bb);
 983
 984   /* Remove the basic block from the array.  */
 985   expunge_block (bb);
 986 }
 987
 988 /* Merges block B into block A.  */
 989 static void
 990 tree_merge_blocks (basic_block a, basic_block b)
 991 {
 992   block_stmt_iterator bsi;
 993   edge e;
 994   tree phi, stmt;
 995
 996   /* Ensure that b follows a.  */
 997   if (a->next_bb != b)
 998     tree_move_block_after (b, a, false);
 999
1000   if (!(a->succ->flags & EDGE_FALLTHRU))
1001     abort ();
1002
1003   if (last_stmt (a)
1004       && stmt_ends_bb_p (last_stmt (a)))
1005     abort ();
1006
1007   /* Turn phi nodes into assignments.  */
1008   bsi = bsi_last (a);
1009   for (phi = phi_nodes (b); phi; phi = TREE_CHAIN (phi))
1010     {
1011       tree src = PHI_ARG_DEF (phi, 0);
1012       tree dest = PHI_RESULT (phi);
1013
1014       if (virtual_op_p (SSA_NAME_VAR (dest)))
1015         {
1016           tree vdef;
1017
1018           stmt = build_empty_stmt ();
1019           get_stmt_ann (stmt);
1020           add_vdef (SSA_NAME_VAR (dest), stmt, NULL);
1021           vdef = VARRAY_TREE (vdef_ops (stmt), 0);
1022           VDEF_RESULT (vdef) = dest;
1023           VDEF_OP (vdef) = src;
1024         }
1025       else
1026         stmt = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
1027
1028       SSA_NAME_DEF_STMT (dest) = stmt;
1029       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1030     }
1031
1032   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1033   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1034     {
1035       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1036         bsi_remove (&bsi);
1037       else
1038         {
1039           set_bb_for_stmt (bsi_stmt (bsi), a);
1040           bsi_next (&bsi);
1041         }
1042     }
1043
1044   remove_edge (a->succ);
1045
1046   /* Merge the chains.  */
1047   if (a->end_tree)
1048     a->end_tree->next = b->head_tree;
1049   else
1050     a->head_tree = b->head_tree;
1051   if (b->head_tree)
1052     {
1053       b->head_tree->prev = a->end_tree;
1054       a->end_tree = b->end_tree;
1055     }
1056   b->head_tree = b->end_tree = NULL;
1057
1058   /* Redirect the edges.  */
1059   a->succ = b->succ;
1060   b->succ = NULL;
1061   for (e = a->succ; e; e = e->succ_next)
1062     e->src = a;
1063
1064   /* Remove B.  */
1065   delete_basic_block (b);
1066 }
1067
1068 /* Remove statement pointed by iterator I.  */
1069
1070 void
1071 bsi_remove (block_stmt_iterator *i)
1072 {
1073   tree_cell cell = bsi_cell (*i);
1074
1075   bsi_next (i);
1076
1077   remove_stmt (cell, i->bb, true);
1078 }
1079
1080 /* Remove statement pointed by iterator I, but leave the annotations.  */
1081
1082 void
1083 bsi_remove_leave_annot (block_stmt_iterator *i)
1084 {
1085   tree_cell cell = bsi_cell (*i);
1086
1087   bsi_next (i);
1088
1089   remove_stmt (cell, i->bb, false);
1090 }
1091
1092 /* Move the statement at FROM so it comes right after the statement at
1093    TO.  */
1094 void
1095 bsi_move_after (block_stmt_iterator from, block_stmt_iterator to)
1096 {
1097   tree stmt = bsi_stmt (from);
1098   bsi_remove_leave_annot (&from);
1099   bsi_insert_after (&to, stmt, BSI_SAME_STMT);
1100 }
1101
1102 /* Move the statement at FROM so it comes right before the statement
1103    at TO.  */
1104 void
1105 bsi_move_before (block_stmt_iterator from, block_stmt_iterator to)
1106 {
1107   tree stmt = bsi_stmt (from);
1108   bsi_remove_leave_annot (&from);
1109   bsi_insert_before (&to, stmt, BSI_SAME_STMT);
1110 }
1111
1112 /* Move the statement at FROM to the end of basic block BB, */
1113 void
1114 bsi_move_to_bb_end (block_stmt_iterator from, basic_block bb)
1115 {
1116   block_stmt_iterator last = bsi_last (bb);
1117
1118   /* Have to check bsi_end_p because it could be an empty block.  */
1119   if (!bsi_end_p (last)
1120       && is_ctrl_stmt (bsi_stmt (last)))
1121     {
1122       bsi_move_before (from, last);
1123     }
1124   else
1125     {
1126       bsi_move_after (from, last);
1127     }
1128 }
1129
1130 /* Replace the contents of a stmt with another. The replacement cannot be
1131    a COMPOUND_EXPR node, only a gimple stmt.  */
1132
1133 void
1134 bsi_replace (block_stmt_iterator bsi, tree stmt)
1135 {
1136   if (TREE_CODE (stmt) == COMPOUND_EXPR)
1137     abort ();
1138
1139   replace_stmt (bsi_cell (bsi), stmt);
1140   modify_stmt (bsi_stmt (bsi));
1141 }
1142
1143 /* Remove statement CELL in basic block BB.  Reset the annotations if
1144    REMOVE_ANNOTATIONS is true.  */
1145
1146 static void
1147 remove_stmt (tree_cell cell, basic_block bb, bool remove_annotations)
1148 {
1149   varray_type vdefs;
1150   size_t i;
1151   varray_type defs;
1152   tree stmt = cell->stmt;
1153
1154   /* If the statement is a LABEL_EXPR, remove the LABEL_DECL from
1155      the symbol table.  */
1156   if (TREE_CODE (stmt) == LABEL_EXPR)
1157     remove_decl (LABEL_EXPR_LABEL (stmt), DECL_INITIAL (current_function_decl));
1158
1159   if (remove_annotations)
1160     {
1161       /* If the statement is already in SSA form, mark all the
1162          definitions made in the statement invalid.
1163
1164          FIXME: We should probably traverse all the def-use edges
1165          originating at this statement to update each use of the
1166          definitions made here, but that is expensive and can easily
1167          be checked by every pass by checking if SSA_NAME_DEF_STMT is
1168          a nop.  */
1169       defs = def_ops (stmt);
1170       for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
1171         {
1172           tree *def_p = VARRAY_GENERIC_PTR (defs, i);
1173           if (TREE_CODE (*def_p) == SSA_NAME)
1174             SSA_NAME_DEF_STMT (*def_p) = build_empty_stmt ();
1175         }
1176
1177       vdefs = vdef_ops (stmt);
1178       for (i = 0; vdefs && i < VARRAY_ACTIVE_SIZE (vdefs); i++)
1179         {
1180           tree vdef = VDEF_RESULT (VARRAY_TREE (vdefs, i));
1181           if (TREE_CODE (vdef) == SSA_NAME)
1182             SSA_NAME_DEF_STMT (vdef) = build_empty_stmt ();
1183         }
1184
1185       stmt->common.ann = NULL;
1186     }
1187
1188   /* The RHS of a MODIFY_EXPR has an annotation for the benefit of
1189      SSA-PRE.  Make sure to remove that annotation as well.
1190
1191      We're somewhat conservative here in that we do not remove all
1192      annotations on the RHS of the MODIFY_EXPR, just those of type
1193      TREE_ANN_COMMON.  If the annotation had another type such
1194      as VAR_ANN other code may still need it and it'll get removed
1195      when we remove all the VAR_ANNs as we tear down the SSA form.  */
1196   if (TREE_CODE (stmt) == MODIFY_EXPR
1197       && TREE_OPERAND (stmt, 1)->common.ann
1198       && TREE_OPERAND (stmt, 1)->common.ann->common.type == TREE_ANN_COMMON)
1199     TREE_OPERAND (stmt, 1)->common.ann = NULL;
1200
1201   if (cell->prev)
1202     cell->prev->next = cell->next;
1203   else
1204     bb->head_tree = cell->next;
1205
1206   if (cell->next)
1207     cell->next->prev = cell->prev;
1208   else
1209     bb->end_tree = cell->prev;
1210
1211   cell->prev = cell->next = NULL;
1212 }
1213
1214 /* Given a control block BB and a constant value VAL, return the edge that
1215    will be taken out of the block.  If VAL does not match a unique edge,
1216    NULL is returned.  */
1217
1218 edge
1219 find_taken_edge (basic_block bb, tree val)
1220 {
1221   tree stmt;
1222
1223   stmt = last_stmt (bb);
1224
1225 #if defined ENABLE_CHECKING
1226   if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
1227     abort ();
1228 #endif
1229
1230   /* If VAL is not a constant, we can't determine which edge might
1231      be taken.  */
1232   if (val == NULL || !really_constant_p (val))
1233     return NULL;
1234
1235   if (TREE_CODE (stmt) == COND_EXPR)
1236     return find_taken_edge_cond_expr (bb, val);
1237
1238   if (TREE_CODE (stmt) == SWITCH_EXPR)
1239     return find_taken_edge_switch_expr (bb, val);
1240
1241   return bb->succ;
1242 }
1243
1244
1245 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1246    statement, determine which of the two edges will be taken out of the
1247    block.  Return NULL if either edge may be taken.  */
1248
1249 static edge
1250 find_taken_edge_cond_expr (basic_block bb, tree val)
1251 {
1252   bool always_false;
1253   bool always_true;
1254   edge e;
1255
1256   /* Determine which branch of the if() will be taken.  */
1257   always_false = (simple_cst_equal (val, integer_zero_node) == 1);
1258   always_true = (simple_cst_equal (val, integer_one_node) == 1);
1259
1260   /* If VAL is a constant but it can't be reduced to a 0 or a 1, then
1261      we don't really know which edge will be taken at runtime.  This
1262      may happen when comparing addresses (e.g., if (&var1 == 4))  */
1263   if (!always_false && !always_true)
1264     return NULL;
1265
1266   for (e = bb->succ; e; e = e->succ_next)
1267     if (((e->flags & EDGE_TRUE_VALUE) && always_true)
1268         || ((e->flags & EDGE_FALSE_VALUE) && always_false))
1269       return e;
1270
1271   return NULL;
1272 }
1273
1274
1275 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
1276    statement, determine which edge will be taken out of the block.  Return
1277    NULL if any edge may be taken.  */
1278
1279 static edge
1280 find_taken_edge_switch_expr (basic_block bb, tree val)
1281 {
1282   edge e, default_edge;
1283   tree case_label;
1284   tree_stmt_iterator case_entry;
1285
1286   /* See if the switch() value matches one of the case labels.  */
1287   default_edge = NULL;
1288   for (case_entry = CASE_START (last_stmt (bb));
1289        !CASE_END_P (case_entry);
1290        CASE_NEXT (case_entry))
1291     {
1292       e = CASE_EDGE (case_entry);
1293       case_label = CASE_CASE (case_entry);
1294
1295       if (value_matches_label (e, val, case_label, &default_edge))
1296         return e;
1297     }
1298
1299   /* If no case exists for the value used in the switch(), we use the
1300      default label.  */
1301   if (!default_edge)
1302     abort ();
1303
1304   return default_edge;
1305 }
1306
1307 /* Return true if VAL matches the LABEL.  If one of the LABEL is the DEFAULT
1308    label, DEST_EDGE is stored into *DEFAULT_EDGE_P to indicate that this edge
1309    goes to the DEFAULT label.  This is used by the caller when no other case
1310    label is found to match VAL.  */
1311
1312 static bool
1313 value_matches_label (edge dest_edge, tree val, tree label, edge *default_edge_p)
1314 {
1315   if (TREE_CODE (label) != CASE_LABEL_EXPR)
1316     abort ();
1317
1318   /* Remember that we found a default label, just in case no other
1319      label matches the switch() value.  */
1320   if (CASE_LOW (label) == NULL_TREE)
1321     *default_edge_p = dest_edge;
1322   else
1323     {
1324       /* If we found a match, we are done.  */
1325       tree label_val = CASE_LOW (label);
1326       if (simple_cst_equal (label_val, val) == 1)
1327         return true;
1328     }
1329
1330   return false;
1331 }
1332
1333 /*---------------------------------------------------------------------------
1334                               Debugging functions
1335 ---------------------------------------------------------------------------*/
1336
1337 /* Dump a basic block to a file.  */
1338
1339 void
1340 dump_tree_bb (FILE *outf, const char *prefix, basic_block bb, int indent)
1341 {
1342   edge e;
1343   char *s_indent;
1344   block_stmt_iterator si;
1345   tree phi;
1346
1347   s_indent = (char *) alloca ((size_t) indent + 1);
1348   memset ((void *) s_indent, ' ', (size_t) indent);
1349   s_indent[indent] = '\0';
1350
1351   fprintf (outf, "%s%sBLOCK       %d\n", s_indent, prefix, bb->index);
1352
1353   fprintf (outf, "%s%sPRED:      ", s_indent, prefix);
1354   for (e = bb->pred; e; e = e->pred_next)
1355     dump_edge_info (outf, e, 0);
1356   putc ('\n', outf);
1357
1358   fprintf (outf, "%s%sSUCC:      ", s_indent, prefix);
1359   for (e = bb->succ; e; e = e->succ_next)
1360     dump_edge_info (outf, e, 1);
1361   putc ('\n', outf);
1362
1363   fprintf (outf, "%s%sLOOP DEPTH: %d\n", s_indent, prefix, bb->loop_depth);
1364
1365   fprintf (outf, "%s%sNEXT BLOCK: ", s_indent, prefix);
1366   if (bb->next_bb)
1367     fprintf (outf, "%d\n", bb->next_bb->index);
1368   else
1369     fprintf (outf, "nil\n");
1370
1371   fprintf (outf, "%s%sPREV BLOCK: ", s_indent, prefix);
1372   if (bb->prev_bb)
1373     fprintf (outf, "%d\n", bb->prev_bb->index);
1374   else
1375     fprintf (outf, "nil\n");
1376
1377   if (bb->tree_annotations)
1378     for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1379       {
1380         fprintf (outf, "%s%s# ", s_indent, prefix);
1381         print_generic_stmt (outf, phi, 0);
1382       }
1383
1384   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1385     {
1386       fprintf (outf, "%s%s%d  ", s_indent, prefix, get_lineno (bsi_stmt (si)));
1387       print_generic_stmt (outf, bsi_stmt (si), 0);
1388       fprintf (outf, "\n");
1389     }
1390 }
1391
1392
1393 /* Dump a basic block on stderr.  */
1394
1395 void
1396 debug_tree_bb (basic_block bb)
1397 {
1398   dump_tree_bb (stderr, "", bb, 0);
1399 }
1400
1401 /* Dump a basic block N on stderr.  */
1402
1403 basic_block
1404 debug_tree_bb_n (int n)
1405 {
1406   debug_tree_bb (BASIC_BLOCK (n));
1407   return BASIC_BLOCK (n);
1408 }
1409
1410 /* Dump the CFG on stderr.
1411
1412    FLAGS are the same used by the tree dumping functions
1413    (see TDF_* in tree.h).  */
1414
1415 void
1416 debug_tree_cfg (int flags)
1417 {
1418   dump_tree_cfg (stderr, flags);
1419 }
1420
1421
1422 /* Dump the program showing basic block boundaries on the given FILE.
1423
1424    FLAGS are the same used by the tree dumping functions (see TDF_* in
1425    tree.h).  */
1426
1427 void
1428 dump_tree_cfg (FILE *file, int flags)
1429 {
1430   basic_block bb;
1431
1432   if (flags & TDF_DETAILS)
1433     {
1434       const char *funcname
1435         = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
1436
1437       fputc ('\n', file);
1438       fprintf (file, ";; Function %s\n\n", funcname);
1439       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n",
1440                n_basic_blocks, n_edges, last_basic_block);
1441
1442       FOR_EACH_BB (bb)
1443         {
1444           dump_tree_bb (file, "", bb, 0);
1445           fputc ('\n', file);
1446         }
1447     }
1448
1449   if (flags & TDF_STATS)
1450     dump_cfg_stats (file);
1451
1452   if (n_basic_blocks > 0)
1453     dump_cfg_function_to_file (current_function_decl, file, flags|TDF_BLOCKS);
1454 }
1455
1456 /* Dumps function FN to FILE, with details given by FLAGS.  Function body is
1457    taken from cfg.  */
1458 void
1459 dump_cfg_function_to_file (tree fn, FILE *file, int flags)
1460 {
1461   basic_block bb;
1462   tree arg, phi;
1463   block_stmt_iterator si;
1464   edge e;
1465   int show_bb_headers = flags & TDF_BLOCKS;
1466
1467   flags &= ~TDF_BLOCKS;
1468
1469   fprintf (file, "\n;; Function %s",
1470             (*lang_hooks.decl_printable_name) (fn, 2));
1471   fprintf (file, " (%s)\n",
1472             IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fn)));
1473   fprintf (file, "\n");
1474
1475   fprintf (file, "%s (", (*lang_hooks.decl_printable_name) (fn, 2));
1476
1477   arg = DECL_ARGUMENTS (fn);
1478   while (arg)
1479     {
1480       print_generic_expr (file, arg, 0);
1481       if (TREE_CHAIN (arg))
1482         fprintf (file, ", ");
1483       arg = TREE_CHAIN (arg);
1484     }
1485   fprintf (file, ")\n");
1486
1487   if (flags & TDF_RECONSTRUCT)
1488     {
1489       struct control *cs_tree, **bb_to_cs;
1490       bb_to_cs = xmalloc (sizeof (struct control *) * last_basic_block);
1491
1492       cs_tree = determine_structures (bb_to_cs);
1493       dump_cs_tree (file, flags, cs_tree, bb_to_cs);
1494
1495       free_cs_tree (cs_tree);
1496       free (bb_to_cs);
1497     }
1498   else
1499     {
1500       fprintf (file, "{\n");
1501       FOR_EACH_BB (bb)
1502         {
1503           if (show_bb_headers)
1504             {
1505               fprintf (file, "# BLOCK %d\n ", bb->index);
1506               fprintf (file, "# PRED");
1507               for (e = bb->pred; e; e = e->pred_next)
1508                 dump_edge_info (file, e, 0);
1509               putc ('\n', file);
1510             }
1511           for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1512             {
1513               fprintf (file, "\t# ");
1514               print_generic_stmt (file, phi, flags);
1515               fprintf (file, "\n");
1516             }
1517
1518           for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1519             {
1520               fprintf (file, "%d\t", get_lineno (bsi_stmt (si)));
1521               print_generic_stmt (file, bsi_stmt (si), flags & ~TDF_VOPS);
1522               fprintf (file, "\n");
1523             }
1524
1525           if (show_bb_headers)
1526             {
1527               fprintf (file, "# SUCC");
1528               for (e = bb->succ; e; e = e->succ_next)
1529                 dump_edge_info (file, e, 1);
1530               fprintf (file, "\n\n");
1531             }
1532         }
1533       fprintf (file, "}\n\n");
1534     }
1535 }
1536
1537 /* Determine control structures, returning their tree and assignment of
1538    blocks to them in BELONGS_TO.  */
1539
1540 static struct control *
1541 determine_structures (struct control *bb_to_cs[])
1542 {
1543   struct control *root, *nw, *old;
1544   int i, *rc_order, *rc_number;
1545   basic_block header, follow;
1546   edge e, latch;
1547   dominance_info dom = calculate_dominance_info (CDI_DOMINATORS);
1548
1549   root = make_control_node (CS_TOP, NULL, ENTRY_BLOCK_PTR->succ->dest, NULL,
1550                             NULL);
1551
1552   rc_order = xmalloc (n_basic_blocks * sizeof (int));
1553   flow_depth_first_order_compute (NULL, rc_order);
1554
1555   mark_dfs_back_edges ();
1556
1557   rc_number = xmalloc (last_basic_block * sizeof (int));
1558   for (i = 0; i < n_basic_blocks; i++)
1559     {
1560       bb_to_cs[rc_order[i]] = root;
1561       rc_number[rc_order[i]] = i;
1562     }
1563
1564   for (i = 0; i < n_basic_blocks; i++)
1565     {
1566       header = BASIC_BLOCK (rc_order[i]);
1567
1568       latch = NULL;
1569       for (e = header->pred; e; e = e->pred_next)
1570         {
1571           if (e->flags & EDGE_ABNORMAL)
1572             {
1573               latch = NULL;
1574               break;
1575             }
1576
1577           if ((e->flags & EDGE_DFS_BACK)
1578               && dominated_by_p (dom, e->src, header))
1579             {
1580               if (!latch
1581                   /* Take the latch with the greatest rc number.  */
1582                   || rc_number[e->src->index] > rc_number[latch->src->index])
1583               latch = e;
1584             }
1585         }
1586
1587       if (!latch)
1588         continue;
1589
1590       nw = make_control_node (CS_INFINITE_LOOP, bb_to_cs[header->index],
1591                               header, latch->src, NULL);
1592
1593       /* Mark the nodes belonging to the loop.  */
1594       DFS_BACKWARD (latch->src, bb, e,
1595                     e->dest != header,
1596                     bb_to_cs[bb->index] = nw,);
1597
1598       /* Determine follow and the type of the loop.  If the header has
1599          a successor outside of loop, it is a while loop and the successor is
1600          the follow.  */
1601       follow = NULL;
1602       for (e = header->succ; e; e = e->succ_next)
1603         if (e->dest == EXIT_BLOCK_PTR
1604             || bb_to_cs[e->dest->index] != nw)
1605           follow = e->dest;
1606       if (follow)
1607         {
1608           nw->type = CS_WHILE_LOOP;
1609           nw->follow = follow;
1610           continue;
1611         }
1612
1613       /* If latch has a successor outside of loop, it is a do-while loop.  */
1614       follow = NULL;
1615       for (e = latch->src->succ; e; e = e->succ_next)
1616         if (e->dest == EXIT_BLOCK_PTR
1617             || bb_to_cs[e->dest->index] != nw)
1618           follow = e->dest;
1619       if (follow)
1620         {
1621           nw->type = CS_DO_WHILE_LOOP;
1622           nw->follow = follow;
1623           continue;
1624         }
1625
1626       /* Otherwise it is an endless loop.  Set follow as the successor with the
1627          lowest rc number.  */
1628       follow = NULL;
1629       DFS_BACKWARD (latch->src, bb, f,
1630                     bb_to_cs[f->dest->index] != nw,
1631                     if (bb_to_cs[bb->index] != nw
1632                         && (!follow
1633                             || rc_number[follow->index] > rc_number[bb->index]))
1634                       follow = bb,);
1635
1636       nw->follow = follow;
1637     }
1638
1639   /* Now we have a loop tree.  Add information about if then else
1640      structures.  Traverse the basic blocks in the completion order,
1641      so that inner structures are identified first.  */
1642   for (i = n_basic_blocks - 1; i >= 0; i--)
1643     {
1644       tree stmt;
1645       edge e_then, e_else;
1646       enum cs_type type;
1647       basic_block l;
1648
1649       header = BASIC_BLOCK (rc_order[i]);
1650       stmt = last_stmt (header);
1651
1652       if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1653         continue;
1654
1655       e_then = e_else = NULL;
1656       for (e = header->succ; e; e = e->succ_next)
1657         {
1658           if (e->flags & EDGE_TRUE_VALUE)
1659             e_then = e;
1660           if (e->flags & EDGE_FALSE_VALUE)
1661             e_else = e;
1662         }
1663
1664       if (!e_then || !e_else || e_then == e_else
1665           || e_then->dest == header
1666           || e_else->dest == header)
1667         continue;
1668
1669       /* Clasify the structure.  */
1670
1671       old = bb_to_cs[header->index];
1672       if (dominated_by_p (dom, e_then->dest, header))
1673         {
1674           for (e = e_else->dest->pred; e; e = e->pred_next)
1675             if (dominated_by_p (dom, e->src, e_then->dest))
1676               break;
1677
1678           if (e)
1679             {
1680               if (!inside_cs (e->src, old, bb_to_cs))
1681                 continue;
1682               type = CS_IF_THEN;
1683               follow = e_else->dest;
1684               l = e->src;
1685             }
1686           else if (dominated_by_p (dom, e_else->dest, header))
1687             {
1688               if (!inside_cs (e_then->dest, old, bb_to_cs)
1689                   || !inside_cs (e_else->dest, old, bb_to_cs))
1690                 continue;
1691               type = CS_IF_THEN_ELSE;
1692               follow = NULL;
1693               l = NULL;
1694             }
1695           else
1696             continue;
1697         }
1698       else if (dominated_by_p (dom, e_else->dest, header))
1699         {
1700           for (e = e_then->dest->pred; e; e = e->pred_next)
1701             if (dominated_by_p (dom, e->src, e_else->dest))
1702               break;
1703
1704           if (e)
1705             {
1706               if (!inside_cs (e->src, old, bb_to_cs))
1707                 continue;
1708               type = CS_IF_ELSE;
1709               follow = e_then->dest;
1710               l = e->src;
1711             }
1712           else
1713             continue;
1714         }
1715       else
1716         continue;
1717
1718       nw = make_control_node (type, bb_to_cs[header->index],
1719                               header, l, follow);
1720
1721       /* Find the basic blocks belonging to the structure.  */
1722       bb_to_cs[header->index] = nw;
1723       if (type == CS_IF_THEN || type == CS_IF_THEN_ELSE)
1724         DFS_FORWARD (e_then->dest, bb, e,
1725                      dominated_by_p (dom, e->dest, e_then->dest)
1726                      && inside_cs (e->dest, old, bb_to_cs),
1727                      if (bb_to_cs[bb->index] == old)
1728                        bb_to_cs[bb->index] = nw;
1729                      else
1730                        try_move_control_node (bb_to_cs[bb->index], old, nw);,);
1731       if (type == CS_IF_ELSE || type == CS_IF_THEN_ELSE)
1732         DFS_FORWARD (e_else->dest, bb, e,
1733                      dominated_by_p (dom, e->dest, e_else->dest)
1734                      && inside_cs (e->dest, old, bb_to_cs),
1735                      if (bb_to_cs[bb->index] == old)
1736                        bb_to_cs[bb->index] = nw;
1737                      else
1738                        try_move_control_node (bb_to_cs[bb->index], old, nw);,);
1739       if (type == CS_IF_THEN_ELSE)
1740         {
1741           /* Determine the follow node as the basic block that has predecessors
1742              in both branches.  */
1743           DFS_FORWARD (e_then->dest, bb, f,
1744                        dominated_by_p (dom, f->src, e_then->dest)
1745                        && inside_cs (f->src, old, bb_to_cs),
1746                        if (bb_to_cs[bb->index] != nw)
1747                          {
1748                            for (e = bb->pred; e; e = e->pred_next)
1749                              if (bb_to_cs[e->src->index] == nw
1750                                  && dominated_by_p (dom, e->src, e_else->dest)
1751                                  && (!follow
1752                                      || rc_number[follow->index] > rc_number[bb->index]))
1753                                follow = bb;
1754                          },);
1755         }
1756     }
1757
1758   free (rc_number);
1759   free (rc_order);
1760
1761   free_dominance_info (dom);
1762
1763   return root;
1764 }
1765
1766 /* Releases memory occupied by control structures tree CS_TREE.  */
1767
1768 static void
1769 free_cs_tree (struct control *cs_tree)
1770 {
1771   struct control *son, *next;
1772
1773   if (cs_tree->son)
1774     {
1775       son = cs_tree->son;
1776       son->prev->next = NULL;
1777
1778       for (; son; son = next)
1779         {
1780           next = son->next;
1781           free_cs_tree (son);
1782         }
1783     }
1784
1785   free (cs_tree);
1786 }
1787
1788 /* Dumps the program to FILE with details described by FLAGS.  Structures are
1789    recreated according to CS_TREE.  Blocks are assigned to structures according
1790    to BB_TO_CS.  */
1791
1792 static void
1793 dump_cs_tree (FILE *file, int flags, struct control *cs_tree,
1794               struct control *bb_to_cs[])
1795 {
1796   tree body;
1797
1798   add_bb_cs_nodes (bb_to_cs);
1799   assign_levels (cs_tree, 0);
1800   compute_structure_exits (bb_to_cs);
1801   layout_structures (cs_tree, bb_to_cs);
1802   fixup_gotos (cs_tree, bb_to_cs, NULL, NULL, NULL);
1803
1804   body = reconstruct_tree (cs_tree, bb_to_cs);
1805   print_generic_stmt (file, body, flags);
1806 }
1807
1808 /* Adds or removes gotos and labels as needed for structures in NODE.
1809    NEXT is the next structure after NODE in layout.  BREAK_DEST and CONT_DEST
1810    are the blocks to that continue/break statements would go.  BB_TO_CS maps
1811    basic blocks to control structures.  */
1812
1813 static void
1814 fixup_gotos (struct control *node, struct control *bb_to_cs[],
1815              struct control *next, basic_block break_dest,
1816              basic_block cont_dest)
1817 {
1818   struct control *s;
1819   basic_block fall, bb;
1820   edge e_then, e_else, e;
1821
1822   switch (node->type)
1823     {
1824     case CS_TOP:
1825       for (s = node->lay_head; s; s = s->lay_next)
1826         fixup_gotos (s, bb_to_cs, s->lay_next, NULL, NULL);
1827       break;
1828
1829     case CS_WHILE_LOOP:
1830     case CS_DO_WHILE_LOOP:
1831     case CS_INFINITE_LOOP:
1832       break_dest = next ? first_cs_bb (next) : NULL;
1833       cont_dest = first_cs_bb (node->lay_head);
1834       for (s = node->lay_head; s; s = s->lay_next)
1835         fixup_gotos (s, bb_to_cs, s->lay_next ? s->lay_next : node->lay_head,
1836                      break_dest, cont_dest);
1837       break;
1838
1839     case CS_IF_THEN:
1840     case CS_IF_ELSE:
1841       node->lay_head->fa_then = node->lay_head->fa_else = ADD_GOTO;
1842       for (s = node->lay_head->lay_next; s; s = s->lay_next)
1843         fixup_gotos (s, bb_to_cs, s->lay_next ? s->lay_next : next,
1844                      break_dest, cont_dest);
1845       break;
1846
1847     case CS_IF_THEN_ELSE:
1848       node->lay_head->fa_then = node->lay_head->fa_else = ADD_GOTO;
1849       for (s = node->lay_head->lay_next; s != node->else_node; s = s->lay_next)
1850         fixup_gotos (s, bb_to_cs,
1851                      s->lay_next != node->else_node ? s->lay_next : next,
1852                      break_dest, cont_dest);
1853       for (; s; s = s->lay_next)
1854         fixup_gotos (s, bb_to_cs, s->lay_next ? s->lay_next : next,
1855                      break_dest, cont_dest);
1856       break;
1857
1858     case CS_BB:
1859       bb = node->header;
1860       if (!bb->succ)
1861         break;
1862
1863       if (!bb->succ->succ_next)
1864         {
1865           e_then = bb->succ;
1866           e_else = NULL;
1867         }
1868       else
1869         {
1870           e_then = e_else = NULL;
1871           for (e = bb->succ; e; e = e->succ_next)
1872             if (e->flags & EDGE_TRUE_VALUE)
1873               e_then = e;
1874             else if (e->flags & EDGE_FALSE_VALUE)
1875               e_else = e;
1876             else if (e->flags & EDGE_FALLTHRU)
1877               e_then = e;
1878
1879           if (!e_then && !e_else)
1880             break;
1881         }
1882
1883       fall = next ? first_cs_bb (next) : NULL;
1884       if (e_then)
1885         node->fa_then = decide_final_action (e_then->dest, fall, break_dest,
1886                                              cont_dest, bb_to_cs);
1887       if (e_else)
1888         node->fa_else = decide_final_action (e_else->dest, fall, break_dest,
1889                                              cont_dest, bb_to_cs);
1890       break;
1891
1892     default:
1893       abort ();
1894     }
1895 }
1896
1897 /* Decides how to replace goto to basic block BB.  FALL is the block to that
1898    it would fallthru, BREAK_DEST and CONT_DEST are destinations of break and
1899    continue statements.  BB_TO_CS maps basic blocks to control structures.  */
1900
1901 static enum fa
1902 decide_final_action (basic_block bb, basic_block fall, basic_block break_dest,
1903                      basic_block cont_dest, struct control *bb_to_cs[])
1904 {
1905   struct control *s;
1906   block_stmt_iterator bsi;
1907
1908   if (bb == fall || bb == EXIT_BLOCK_PTR)
1909     return MAKE_FALLTHRU;
1910   else if (bb == break_dest)
1911     return ADD_BREAK;
1912   else if (bb == cont_dest)
1913     return ADD_CONTINUE;
1914   else
1915     {
1916       s = bb_to_cs[bb->index];
1917       bsi = bsi_start (bb);
1918
1919       if (!s->artificial_label
1920           && (!bsi_stmt (bsi)
1921               || TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR))
1922         s->artificial_label = build_new_label ();
1923
1924       return ADD_GOTO;
1925     }
1926 }
1927
1928 /* Create a structured program from structrure description and layout
1929    in NODE.  BB_TO_CS maps basic blocks to control structures.  */
1930
1931 static tree
1932 reconstruct_tree (struct control *node, struct control *bb_to_cs[])
1933 {
1934   tree b = NULL_TREE, tmp, *stmt, b1;
1935   tree_stmt_iterator tsi = tsi_start (&b), atsi;
1936   block_stmt_iterator bsi;
1937   struct control *s;
1938   basic_block bb;
1939   edge e, e_then, e_else;
1940
1941   switch (node->type)
1942     {
1943     case CS_TOP:
1944       for (s = node->lay_head; s; s = s->lay_next)
1945         {
1946           tmp = reconstruct_tree (s, bb_to_cs);
1947           tsi_link_chain_after (&tsi, tmp, TSI_CONTINUE_LINKING);
1948         }
1949       return build (BIND_EXPR, void_type_node,
1950                     NULL,
1951                     b,
1952                     NULL);
1953
1954     case CS_WHILE_LOOP:
1955     case CS_DO_WHILE_LOOP:
1956     case CS_INFINITE_LOOP:
1957       for (s = node->lay_head; s; s = s->lay_next)
1958         {
1959           tmp = reconstruct_tree (s, bb_to_cs);
1960           tsi_link_chain_after (&tsi, tmp, TSI_CONTINUE_LINKING);
1961         }
1962       return build (LOOP_EXPR, void_type_node, b);
1963
1964     case CS_IF_THEN:
1965     case CS_IF_ELSE:
1966       for (s = node->lay_head->lay_next; s; s = s->lay_next)
1967         {
1968           tmp = reconstruct_tree (s, bb_to_cs);
1969           tsi_link_chain_after (&tsi, tmp, TSI_CONTINUE_LINKING);
1970         }
1971       tmp = reconstruct_tree (node->lay_head, bb_to_cs);
1972       for (atsi = tsi_start (&tmp); !tsi_one_before_end_p (atsi);
1973            tsi_next (&atsi))
1974         continue;
1975       stmt = tsi_stmt_ptr (atsi);
1976       if (TREE_CODE (*stmt) != COND_EXPR)
1977         abort ();
1978
1979       if (node->type == CS_IF_THEN)
1980         {
1981           *stmt = build (COND_EXPR, void_type_node,
1982                          COND_EXPR_COND (*stmt), b,
1983                          (node->follow
1984                           ? NULL_TREE
1985                           : COND_EXPR_ELSE (*stmt)));
1986         }
1987       else
1988         {
1989           *stmt = build (COND_EXPR, void_type_node,
1990                          COND_EXPR_COND (*stmt),
1991                          (node->follow
1992                           ? NULL_TREE
1993                           : COND_EXPR_THEN (*stmt)),
1994                          b);
1995         }
1996       return tmp;
1997
1998     case CS_IF_THEN_ELSE:
1999       for (s = node->lay_head->lay_next; s != node->else_node; s = s->lay_next)
2000         {
2001           tmp = reconstruct_tree (s, bb_to_cs);
2002           tsi_link_chain_after (&tsi, tmp, TSI_CONTINUE_LINKING);
2003         }
2004       b1 = b;
2005
2006       b = NULL_TREE;
2007       tsi = tsi_start (&b);
2008       for (; s; s = s->lay_next)
2009         {
2010           tmp = reconstruct_tree (s, bb_to_cs);
2011           tsi_link_chain_after (&tsi, tmp, TSI_CONTINUE_LINKING);
2012         }
2013
2014       tmp = reconstruct_tree (node->lay_head, bb_to_cs);
2015       for (atsi = tsi_start (&tmp); !tsi_one_before_end_p (atsi);
2016            tsi_next (&atsi))
2017         continue;
2018       stmt = tsi_stmt_ptr (atsi);
2019       if (TREE_CODE (*stmt) != COND_EXPR)
2020         abort ();
2021
2022       *stmt = build (COND_EXPR, void_type_node,
2023                      COND_EXPR_COND (*stmt), b1, b);
2024       return tmp;
2025
2026     case CS_BB:
2027       bb = node->header;
2028       if (node->artificial_label)
2029         tsi_link_after (&tsi, build1 (LABEL_EXPR, void_type_node,
2030                                       s->artificial_label), TSI_NEW_STMT);
2031       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2032         {
2033           if (TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR
2034               || TREE_CODE (bsi_stmt (bsi)) == COND_EXPR)
2035             break;
2036           tsi_link_after (&tsi, bsi_stmt (bsi), TSI_NEW_STMT);
2037         }
2038       tmp = bsi_end_p (bsi) ? NULL_TREE : bsi_stmt (bsi);
2039       if (tmp && TREE_CODE (tmp) == COND_EXPR)
2040         tmp = build (COND_EXPR, void_type_node, COND_EXPR_COND (tmp),
2041                      COND_EXPR_THEN (tmp), COND_EXPR_ELSE (tmp));
2042
2043       if (bb->succ)
2044         {
2045           if (!bb->succ->succ_next)
2046             {
2047               e_then = bb->succ;
2048               e_else = NULL;
2049             }
2050           else
2051             {
2052               e_then = e_else = NULL;
2053               for (e = bb->succ; e; e = e->succ_next)
2054                 if (e->flags & EDGE_TRUE_VALUE)
2055                   e_then = e;
2056                 else if (e->flags & EDGE_FALSE_VALUE)
2057                   e_else = e;
2058                 else if (e->flags & EDGE_FALLTHRU)
2059                   e_then = e;
2060             }
2061
2062           if (e_then)
2063             {
2064               if (tmp && TREE_CODE (tmp) == COND_EXPR)
2065                 stmt = &COND_EXPR_THEN (tmp);
2066               else
2067                 stmt = &tmp;
2068               establish_gotos (stmt, node->fa_then,
2069                                bb_to_cs[e_then->dest->index]);
2070             }
2071
2072           if (e_else)
2073             establish_gotos (&COND_EXPR_ELSE (tmp), node->fa_else,
2074                              bb_to_cs[e_else->dest->index]);
2075
2076           if (tmp)
2077             tsi_link_after (&tsi, tmp, TSI_NEW_STMT);
2078         }
2079       if (!b)
2080         b = build_empty_stmt ();
2081
2082       return b;
2083
2084     default:
2085       abort ();
2086     }
2087 }
2088
2089 /* Set gotos of STMT according to ACTION; the jump goes to DEST.  */
2090
2091 static void
2092 establish_gotos (tree *stmt, enum fa action, struct control *dest)
2093 {
2094   basic_block dst;
2095
2096   switch (action)
2097     {
2098     case MAKE_FALLTHRU:
2099       *stmt = NULL_TREE;
2100       break;
2101
2102     case ADD_GOTO:
2103       if (*stmt)
2104         break;
2105
2106       dst = dest->header;
2107       if (dest->artificial_label)
2108         *stmt = build1 (GOTO_EXPR, void_type_node, dest->artificial_label);
2109       else
2110         *stmt = build1 (GOTO_EXPR, void_type_node, tree_block_label (dst));
2111
2112       break;
2113
2114     case ADD_BREAK:
2115       *stmt = build (BREAK_EXPR, void_type_node);
2116       break;
2117
2118     case ADD_CONTINUE:
2119       *stmt = build (CONTINUE_EXPR, void_type_node);
2120       break;
2121     }
2122 }
2123
2124 /* Checks whether BB belongs to NODE according to BB_TO_CS.  */
2125
2126 static bool
2127 inside_cs (basic_block bb, struct control *node, struct control *bb_to_cs[])
2128 {
2129   struct control *a = bb_to_cs[bb->index];
2130
2131   while (a != node && a)
2132     a = a->outer;
2133
2134   return a == node;
2135 }
2136
2137 /* Returns the superstructure of NODE on level L.  */
2138
2139 static struct control *
2140 lift (struct control *node, int l)
2141 {
2142   while (node->level > l)
2143     node = node->outer;
2144
2145   return node;
2146 }
2147
2148 /* Returns first basic block of the NODE.  */
2149
2150 static basic_block
2151 first_cs_bb (struct control *node)
2152 {
2153   while (node->type != CS_BB)
2154     node = node->lay_head;
2155
2156   return node->header;
2157 }
2158
2159 /* Add structure nodes for basic blocks, using BB_TO_CS array.  */
2160
2161 static void
2162 add_bb_cs_nodes (struct control *bb_to_cs[])
2163 {
2164   basic_block bb, follow;
2165   struct control *nw;
2166   edge e;
2167
2168   FOR_EACH_BB (bb)
2169     {
2170       for (e = bb->succ; e; e = e->succ_next)
2171         if (e->flags & EDGE_FALLTHRU)
2172           break;
2173       if (e && e->dest != EXIT_BLOCK_PTR)
2174         follow = e->dest;
2175       else
2176         follow = NULL;
2177       nw = make_control_node (CS_BB, bb_to_cs[bb->index], bb, NULL, follow);
2178       bb_to_cs[bb->index] = nw;
2179     }
2180 }
2181
2182 /* Assign level L to NODE and propagate the levels to its subnodes.  */
2183
2184 static void
2185 assign_levels (struct control *node, int l)
2186 {
2187   struct control *son;
2188
2189   node->level = l;
2190   son = node->son;
2191   if (!son)
2192     return;
2193
2194   do
2195     {
2196       assign_levels (son, l + 1);
2197       son = son->next;
2198     }
2199   while (son != node->son);
2200 }
2201
2202 /* Compute exits from the structures using the BB_TO_CS array.  */
2203
2204 static void
2205 compute_structure_exits (struct control *bb_to_cs[])
2206 {
2207   basic_block bb;
2208   edge e;
2209   struct control *cs, *ct;
2210
2211   FOR_EACH_BB (bb)
2212     {
2213       for (e = bb->succ; e; e = e->succ_next)
2214         {
2215           if (e->dest == EXIT_BLOCK_PTR)
2216             continue;
2217
2218           cs = bb_to_cs[bb->index];
2219           ct = bb_to_cs[e->dest->index];
2220
2221           while (ct->level > cs->level)
2222             ct = ct->outer;
2223           while (cs->level > ct->level)
2224             cs = cs->outer;
2225           while (ct->outer != cs->outer)
2226             {
2227               cs = cs->outer;
2228               ct = ct->outer;
2229             }
2230
2231           VARRAY_PUSH_GENERIC_PTR (cs->exits, ct);
2232         }
2233     }
2234 }
2235
2236 /* Layout substructures of NODE in dfs order preferring the follow edges,
2237    using the BB_TO_CS array.  */
2238
2239 static void
2240 layout_structures (struct control *node, struct control *bb_to_cs[])
2241 {
2242   struct control *header_node, *latch_node, *then_node, *else_node, *son;
2243   edge e_then, e_else, e;
2244
2245   if (node->type == CS_BB)
2246     return;
2247
2248   header_node = lift (bb_to_cs[node->header->index], node->level + 1);
2249   if (node->latch)
2250     latch_node = lift (bb_to_cs[node->latch->index], node->level + 1);
2251   else
2252     latch_node = NULL;
2253
2254   switch (node->type)
2255     {
2256     case CS_TOP:
2257     case CS_DO_WHILE_LOOP:
2258     case CS_INFINITE_LOOP:
2259     case CS_WHILE_LOOP:
2260     case CS_IF_THEN:
2261     case CS_IF_ELSE:
2262       layout_structure (header_node, latch_node, bb_to_cs);
2263       if (latch_node && latch_node != header_node)
2264         add_to_layout (latch_node);
2265       break;
2266     case CS_IF_THEN_ELSE:
2267       e_then = e_else = NULL;
2268       for (e = node->header->succ; e; e = e->succ_next)
2269         {
2270           if (e->flags & EDGE_TRUE_VALUE)
2271             e_then = e;
2272           if (e->flags & EDGE_FALSE_VALUE)
2273             e_else = e;
2274         }
2275       then_node = lift (bb_to_cs[e_then->dest->index], node->level + 1);
2276       else_node = lift (bb_to_cs[e_else->dest->index], node->level + 1);
2277       node->else_node = else_node;
2278
2279       add_to_layout (header_node);
2280       layout_structure (then_node, NULL, bb_to_cs);
2281       layout_structure (else_node, NULL, bb_to_cs);
2282       break;
2283
2284     default:
2285       abort ();
2286     }
2287
2288   if (node->type != CS_TOP)
2289     finish_layout (node);
2290
2291   son = node->son;
2292   do
2293     {
2294       layout_structures (son, bb_to_cs);
2295       son = son->next;
2296     }
2297   while (son != node->son);
2298 }
2299
2300 /* Layout area reachable by dfs from HEADER, excluding the LATCH.  Uses
2301    the BB_TO_CS array.  */
2302
2303 static void
2304 layout_structure (struct control *header, struct control *latch,
2305                   struct control *bb_to_cs[])
2306 {
2307   int i;
2308   struct control *cs;
2309
2310   add_to_layout (header);
2311
2312   if (header->follow
2313       && inside_cs (header->follow, header->outer, bb_to_cs))
2314     {
2315       cs = lift (bb_to_cs[header->follow->index], header->level);
2316       header->follow_node = cs;
2317       if (cs != latch && !cs->visited)
2318         layout_structure (cs, latch, bb_to_cs);
2319     }
2320
2321   for (i = 0; i < (int) VARRAY_ACTIVE_SIZE (header->exits); i++)
2322     {
2323       cs = VARRAY_GENERIC_PTR (header->exits, i);
2324
2325       if (cs == latch
2326           || cs->visited)
2327         continue;
2328
2329       layout_structure (cs, latch, bb_to_cs);
2330     }
2331 }
2332
2333 /* Add a NODE at the end of current layout.  */
2334
2335 static void
2336 add_to_layout (struct control *node)
2337 {
2338   struct control *f = node->outer;
2339
2340   if (f->lay_last
2341       && f->lay_last->follow_node != node)
2342     f->lay_last->follow_node = NULL;
2343
2344   node->lay_next = NULL;
2345   if (f->lay_last)
2346     f->lay_last->lay_next = node;
2347   else
2348     f->lay_head = node;
2349   f->lay_last = node;
2350
2351   node->visited = true;
2352 }
2353
2354 /* Perform actions when NODE's substructures layout is fully determined.  */
2355
2356 static void
2357 finish_layout (struct control *node)
2358 {
2359   if (node->lay_last)
2360     node->lay_last->follow_node = NULL;
2361 }
2362
2363 /* Creates a new control node of type TYPE with father node OUTER, entry node
2364    HEADER, latch node LATCH and follow node FOLLOW.  */
2365
2366 static struct control *
2367 make_control_node (enum cs_type type, struct control *outer,
2368                    basic_block header, basic_block latch, basic_block follow)
2369 {
2370   struct control *nw = xcalloc (1, sizeof (struct control));
2371
2372   nw->type = type;
2373   nw->son = NULL;
2374   nw->outer = outer;
2375   if (outer)
2376     {
2377       nw->next = outer->son;
2378       if (outer->son)
2379         nw->prev = outer->son->prev;
2380       else
2381         nw->prev = nw;
2382
2383       nw->prev->next = nw;
2384       nw->next->prev = nw;
2385       outer->son = nw;
2386     }
2387   else
2388     nw->next = nw->prev = NULL;
2389
2390   nw->header = header;
2391   nw->latch = latch;
2392   nw->follow = follow;
2393   VARRAY_GENERIC_PTR_INIT (nw->exits, 2, "node_exits");
2394
2395   return nw;
2396 }
2397
2398 /* Checks whether NODE is a substructure of OLD but not NW.  If so,
2399    move it to NW.  */
2400
2401 static void
2402 try_move_control_node (struct control *node, struct control *old,
2403                        struct control *nw)
2404 {
2405   while (node->outer != old)
2406     node = node->outer;
2407
2408   if (node != nw)
2409     move_control_node (node, nw);
2410 }
2411
2412 /* Makes TO an outer node of NODE.  */
2413
2414 static void
2415 move_control_node (struct control *node, struct control *to)
2416 {
2417   if (node->outer->son == node)
2418     node->outer->son = node->next;
2419
2420   if (node->outer->son == node)
2421     node->outer->son = NULL;
2422
2423   node->prev->next = node->next;
2424   node->next->prev = node->prev;
2425
2426   node->outer = to;
2427   node->next = to->son;
2428
2429   if (to->son)
2430     node->prev = to->son->prev;
2431   else
2432     node->prev = node;
2433
2434   node->prev->next = node;
2435   node->next->prev = node;
2436   to->son = node;
2437 }
2438
2439 /* Dump CFG statistics on FILE.  */
2440
2441 void
2442 dump_cfg_stats (FILE *file)
2443 {
2444   static long max_num_merged_cases = 0;
2445   static long max_num_merged_labels = 0;
2446   unsigned long size, total = 0;
2447   long n_edges;
2448   basic_block bb;
2449   const char * const fmt_str   = "%-30s%-13s%12s\n";
2450   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
2451   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2452   const char *funcname
2453     = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
2454
2455
2456   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2457
2458   fprintf (file, "---------------------------------------------------------\n");
2459   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2460   fprintf (file, fmt_str, "", "  instances  ", "used ");
2461   fprintf (file, "---------------------------------------------------------\n");
2462
2463   size = n_basic_blocks * sizeof (struct basic_block_def);
2464   total += size;
2465   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks, SCALE (size),
2466            LABEL (size));
2467
2468   n_edges = 0;
2469   FOR_EACH_BB (bb)
2470     {
2471       edge e;
2472       for (e = bb->succ; e; e = e->succ_next)
2473         n_edges++;
2474     }
2475   size = n_edges * sizeof (struct edge_def);
2476   total += size;
2477   fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
2478
2479   size = n_basic_blocks * sizeof (struct bb_ann_d);
2480   total += size;
2481   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
2482            SCALE (size), LABEL (size));
2483
2484   fprintf (file, "---------------------------------------------------------\n");
2485   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2486            LABEL (total));
2487   fprintf (file, "---------------------------------------------------------\n");
2488   fprintf (file, "\n");
2489
2490   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2491     max_num_merged_labels = cfg_stats.num_merged_labels;
2492
2493   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2494            cfg_stats.num_merged_labels, max_num_merged_labels);
2495
2496
2497   if (cfg_stats.num_merged_cases > max_num_merged_cases)
2498     max_num_merged_cases = cfg_stats.num_merged_cases;
2499
2500   fprintf (file, "Coalesced case label blocks: %ld (Max so far: %ld)\n",
2501            cfg_stats.num_merged_cases, max_num_merged_cases);
2502
2503   fprintf (file, "Number of unnecessary blocks created due to lexical scopes: %ld (%.0f%%)\n",
2504            cfg_stats.num_failed_bind_expr_merges,
2505            PERCENT (cfg_stats.num_failed_bind_expr_merges, n_basic_blocks));
2506
2507   fprintf (file, "\n");
2508 }
2509
2510
2511 /* Dump CFG statistics on stderr.  */
2512
2513 void
2514 debug_cfg_stats (void)
2515 {
2516   dump_cfg_stats (stderr);
2517 }
2518
2519
2520 /* Dump the flowgraph to a .dot FILE.  */
2521
2522 void
2523 tree_cfg2dot (FILE *file)
2524 {
2525   edge e;
2526   basic_block bb;
2527   const char *funcname
2528     = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
2529
2530   /* Write the file header.  */
2531   fprintf (file, "digraph %s\n{\n", funcname);
2532
2533   /* Write blocks and edges.  */
2534   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
2535     {
2536       fprintf (file, "\tENTRY -> %d", e->dest->index);
2537
2538       if (e->flags & EDGE_FAKE)
2539         fprintf (file, " [weight=0, style=dotted]");
2540
2541       fprintf (file, ";\n");
2542     }
2543   fputc ('\n', file);
2544
2545   FOR_EACH_BB (bb)
2546     {
2547       enum tree_code head_code, end_code;
2548       const char *head_name, *end_name;
2549       int head_line = 0;
2550       int end_line = 0;
2551       tree first = first_stmt (bb);
2552       tree last = last_stmt (bb);
2553
2554       if (first)
2555         {
2556           head_code = TREE_CODE (first);
2557           head_name = tree_code_name[head_code];
2558           head_line = get_lineno (bb->head_tree->stmt);
2559         }
2560       else
2561         head_name = "no-statement";
2562
2563       if (last)
2564         {
2565           end_code = TREE_CODE (last);
2566           end_name = tree_code_name[end_code];
2567           end_line = get_lineno (bb->end_tree->stmt);
2568         }
2569       else
2570         end_name = "no-statement";
2571
2572
2573       fprintf (file, "\t%d [label=\"#%d\\n%s (%d)\\n%s (%d)\"];\n",
2574                bb->index, bb->index, head_name, head_line, end_name,
2575                end_line);
2576
2577       for (e = bb->succ; e; e = e->succ_next)
2578         {
2579           if (e->dest == EXIT_BLOCK_PTR)
2580             fprintf (file, "\t%d -> EXIT", bb->index);
2581           else
2582             fprintf (file, "\t%d -> %d", bb->index, e->dest->index);
2583
2584           if (e->flags & EDGE_FAKE)
2585             fprintf (file, " [weight=0, style=dotted]");
2586
2587           fprintf (file, ";\n");
2588         }
2589
2590       if (bb->next_bb != EXIT_BLOCK_PTR)
2591         fputc ('\n', file);
2592     }
2593
2594   fputs ("}\n\n", file);
2595 }
2596
2597
2598
2599 /*---------------------------------------------------------------------------
2600                              Miscellaneous helpers
2601 ---------------------------------------------------------------------------*/
2602
2603
2604 /* Return true if T represents a stmt that always transfers control.  */
2605
2606 bool
2607 is_ctrl_stmt (tree t)
2608 {
2609   return (TREE_CODE (t) == COND_EXPR
2610           || TREE_CODE (t) == SWITCH_EXPR
2611           || TREE_CODE (t) == GOTO_EXPR
2612           || TREE_CODE (t) == RETURN_EXPR
2613           || TREE_CODE (t) == RESX_EXPR);
2614 }
2615
2616 /* Return true if T is a stmt that may or may not alter the flow of control
2617    (i.e., a call to a non-returning function).  */
2618
2619 bool
2620 is_ctrl_altering_stmt (tree t)
2621 {
2622   tree call = t;
2623
2624 #if defined ENABLE_CHECKING
2625   if (t == NULL)
2626     abort ();
2627 #endif
2628
2629   switch (TREE_CODE (t))
2630     {
2631     case MODIFY_EXPR:
2632       /* A MODIFY_EXPR with a rhs of a call has the characteristics
2633          of the call.  */
2634       call = TREE_OPERAND (t, 1);
2635       if (TREE_CODE (call) != CALL_EXPR)
2636         break;
2637       /* FALLTHRU */
2638
2639     case CALL_EXPR:
2640       /* A CALL_EXPR alters flow control if the current function has
2641          nonlocal labels.  */
2642       if (FUNCTION_RECEIVES_NONLOCAL_GOTO (current_function_decl))
2643         return true;
2644
2645       /* A CALL_EXPR also alters flow control if it does not return.  */
2646       if (call_expr_flags (call) & (ECF_NORETURN | ECF_LONGJMP))
2647         return true;
2648       break;
2649
2650     default:
2651       return false;
2652     }
2653
2654   /* If a statement can throw, it alters control flow.  */
2655   return tree_can_throw_internal (t);
2656 }
2657
2658
2659 /* Return flags associated with the function called by T (see ECF_* in
2660    tree.h)  */
2661
2662 int
2663 call_expr_flags (tree t)
2664 {
2665   int flags;
2666   tree decl = get_callee_fndecl (t);
2667
2668   if (decl)
2669     flags = flags_from_decl_or_type (decl);
2670   else
2671     {
2672       t = TREE_OPERAND (t, 0);
2673       flags = flags_from_decl_or_type (TREE_TYPE (TREE_TYPE (t)));
2674     }
2675
2676   return flags;
2677 }
2678
2679
2680 /* Return true if T is a computed goto.  */
2681
2682 bool
2683 is_computed_goto (tree t)
2684 {
2685   return (TREE_CODE (t) == GOTO_EXPR
2686           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2687 }
2688
2689 /* Return true if T should start a new basic block.  PREV_T is the
2690    statement preceding T.  It is used when T is a label or a case label.
2691    Labels should only start a new basic block if their previous statement
2692    wasn't a label.  Otherwise, sequence of labels would generate
2693    unnecessary basic blocks that only contain a single label.  */
2694
2695 static inline bool
2696 stmt_starts_bb_p (tree t, tree prev_t)
2697 {
2698   enum tree_code code;
2699
2700   if (t == NULL_TREE)
2701     return false;
2702
2703   /* LABEL_EXPRs and CASE_LABEL_EXPRs start a new basic block only if the
2704      preceding statement wasn't a label of the same type.  This prevents
2705      the creation of consecutive blocks that have nothing but a single
2706      label.  */
2707   code = TREE_CODE (t);
2708   if (code == LABEL_EXPR || code == CASE_LABEL_EXPR)
2709     {
2710       /* Nonlocal and computed GOTO targets always start a new block.  */
2711       if (code == LABEL_EXPR
2712           && (NONLOCAL_LABEL (LABEL_EXPR_LABEL (t))
2713               || FORCED_LABEL (LABEL_EXPR_LABEL (t))))
2714         return true;
2715
2716       if (prev_t && TREE_CODE (prev_t) == code)
2717         {
2718           if (code == LABEL_EXPR)
2719             cfg_stats.num_merged_labels++;
2720           else
2721             cfg_stats.num_merged_cases++;
2722
2723           return false;
2724         }
2725       else
2726         return true;
2727     }
2728
2729   return false;
2730 }
2731
2732
2733 /* Return true if T should end a basic block.  */
2734
2735 static inline bool
2736 stmt_ends_bb_p (tree t)
2737 {
2738   return (is_ctrl_stmt (t)
2739           || is_ctrl_altering_stmt (t));
2740 }
2741
2742
2743 /* Remove all the blocks and edges that make up the flowgraph.  */
2744
2745 void
2746 delete_tree_cfg (void)
2747 {
2748   if (n_basic_blocks > 0)
2749     free_blocks_annotations ();
2750
2751   free_basic_block_vars (0);
2752 }
2753
2754
2755 /* Return the first statement in basic block BB, stripped of any NOP
2756    containers.  */
2757
2758 tree
2759 first_stmt (basic_block bb)
2760 {
2761   block_stmt_iterator i;
2762
2763   if (bb == ENTRY_BLOCK_PTR
2764       || bb == EXIT_BLOCK_PTR)
2765     return NULL_TREE;
2766
2767   i = bsi_start (bb);
2768   return (!bsi_end_p (i)) ? bsi_stmt (i) : NULL_TREE;
2769 }
2770
2771 /* Finds a label in basic block BB or creates one if it does not exit.  */
2772 tree
2773 tree_block_label (basic_block bb)
2774 {
2775   tree label = first_stmt (bb);
2776
2777   if (!label || TREE_CODE (label) != LABEL_EXPR)
2778     {
2779       block_stmt_iterator first = bsi_start (bb);
2780       tree label_decl = build_new_label ();
2781
2782       label = build1 (LABEL_EXPR, void_type_node, label_decl);
2783       bsi_insert_before (&first, label, BSI_NEW_STMT);
2784     }
2785
2786   return LABEL_EXPR_LABEL (label);
2787 }
2788
2789 /* Return the last statement in basic block BB.  */
2790
2791 tree
2792 last_stmt (basic_block bb)
2793 {
2794   block_stmt_iterator b;
2795
2796   if (bb == ENTRY_BLOCK_PTR
2797       || bb == EXIT_BLOCK_PTR)
2798     return NULL_TREE;
2799
2800   b = bsi_last (bb);
2801   return (!bsi_end_p (b)) ? bsi_stmt (b) : NULL_TREE;
2802 }
2803
2804 /* Return the pointer to last statement in basic block BB.  */
2805
2806 tree *
2807 last_stmt_ptr (basic_block bb)
2808 {
2809   block_stmt_iterator b;
2810
2811   b = bsi_last (bb);
2812   return (!bsi_end_p (b)) ? bsi_stmt_ptr (b) : NULL;
2813 }
2814
2815 /* Similar to tsi_start() but initializes the iterator at the first
2816    statement in basic block BB which isn't an empty statement node.
2817
2818    NULL is returned if there are no such statements.  */
2819
2820 block_stmt_iterator
2821 bsi_start (basic_block bb)
2822 {
2823   block_stmt_iterator i;
2824
2825   i.bb = bb;
2826   if (bb && bb->index != INVALID_BLOCK)
2827     i.curr_stmt = bb->head_tree;
2828   else
2829     i.curr_stmt = NULL;
2830
2831   return i;
2832 }
2833
2834 /* Returns bsi positioned so that insering before it will insert after the
2835    labels in the basic block bb.  */
2836
2837 block_stmt_iterator
2838 bsi_real_start (basic_block bb)
2839 {
2840   block_stmt_iterator bsi = bsi_start (bb);
2841
2842   for (; !bsi_end_p (bsi); bsi_next (&bsi))
2843     if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
2844       break;
2845
2846   return bsi;
2847 }
2848
2849 /* This routine will return a block iterator which points to the last stmt in
2850    a basic block, if there is one.  */
2851
2852 block_stmt_iterator
2853 bsi_last (basic_block bb)
2854 {
2855   block_stmt_iterator i;
2856
2857   i.bb = bb;
2858   if (bb && bb->index != INVALID_BLOCK)
2859     i.curr_stmt = bb->end_tree;
2860   else
2861     i.curr_stmt = NULL;
2862
2863   return i;
2864 }
2865
2866
2867 /* Find the previous iterator value.  */
2868
2869 void
2870 bsi_prev (block_stmt_iterator *i)
2871 {
2872   i->curr_stmt = i->curr_stmt->prev;
2873 }
2874
2875 /* Insert statement T into basic block BB.  */
2876
2877 void
2878 set_bb_for_stmt (tree t, basic_block bb)
2879 {
2880   stmt_ann_t ann;
2881
2882   if (no_bb_for_stmt)
2883     return;
2884
2885   /* If the statement is a label, add the label to block-to-labels map
2886      so that we can speed up edge creation for GOTO_EXPRs.  */
2887   if (TREE_CODE (t) == LABEL_EXPR)
2888     {
2889       LABEL_DECL_INDEX (LABEL_EXPR_LABEL (t))
2890               = VARRAY_ACTIVE_SIZE (label_to_block_map);
2891       VARRAY_PUSH_BB (label_to_block_map, bb);
2892     }
2893
2894   ann = get_stmt_ann (t);
2895   ann->bb = bb;
2896 }
2897
2898
2899 /* Insert routines.  */
2900
2901 /* This routine inserts a stmt after the stmt iterator passed in.
2902    The final parameter determines whether the statement iterator
2903    is updated to point to the new stmt, or left pointing to the original
2904    statement.  */
2905
2906 void
2907 bsi_insert_after (block_stmt_iterator *curr_bsi, tree t,
2908                   enum bsi_iterator_update mode)
2909 {
2910   basic_block bb = curr_bsi->bb;
2911   tree_cell curr, nw = tree_cell_alloc (t);
2912
2913   set_bb_for_stmt (t, bb);
2914   curr = bsi_cell (*curr_bsi);
2915
2916   if (!curr)
2917     {
2918       /* Inserting after end of bb.  Only valid if the bb is empty.  */
2919       if (bb->head_tree)
2920         abort ();
2921
2922       nw->prev = nw->next = NULL;
2923       bb->head_tree = bb->end_tree = nw;
2924       *curr_bsi = bsi_start (bb);
2925       return;
2926     }
2927
2928   nw->next = curr->next;
2929   if (!curr->next)
2930     bb->end_tree = nw;
2931   else
2932     nw->next->prev = nw;
2933   curr->next = nw;
2934   nw->prev = curr;
2935
2936   if (mode == BSI_NEW_STMT)
2937     bsi_next (curr_bsi);
2938
2939   /* Now update the required SSA bits.  */
2940   modify_stmt (t);
2941
2942   return;
2943 }
2944
2945
2946 /* This routine inserts a stmt before the stmt iterator passed in.
2947    The final parameter determines whether the statement iterator
2948    is updated to point to the new stmt, or left pointing to the original
2949    statement.  */
2950 void
2951 bsi_insert_before (block_stmt_iterator *curr_bsi, tree t,
2952                    enum bsi_iterator_update mode)
2953 {
2954   basic_block bb = curr_bsi->bb;
2955   tree_cell curr, nw = tree_cell_alloc (t);
2956
2957   set_bb_for_stmt (t, bb);
2958   curr = bsi_cell (*curr_bsi);
2959
2960   if (!curr)
2961     {
2962       /* Inserting just after end of the basic block.  */
2963
2964       nw->prev = bb->end_tree;
2965       nw->next = NULL;
2966       if (!bb->head_tree)
2967         bb->head_tree = nw;
2968       else
2969         nw->prev->next = nw;
2970       bb->end_tree = nw;
2971
2972       if (mode == BSI_NEW_STMT)
2973         curr_bsi->curr_stmt = nw;
2974       return;
2975     }
2976
2977   nw->prev = curr->prev;
2978   if (!nw->prev)
2979     bb->head_tree = nw;
2980   else
2981     nw->prev->next = nw;
2982   curr->prev = nw;
2983   nw->next = curr;
2984
2985   if (mode == BSI_NEW_STMT)
2986     bsi_prev (curr_bsi);
2987
2988   /* Now update the required SSA bits.  */
2989   modify_stmt (t);
2990 }
2991
2992 /* This routine inserts a stmt on an edge. Every attempt is made to place the
2993    stmt in an existing basic block, but sometimes that isn't possible.  When
2994    it isn't possible, a new basic block is created, edges updated, and the
2995    stmt is added to the new block.  An iterator to the new stmt is returned.
2996    If a pointer to a BSI is passed in, and the stmt is inserted before or after
2997    an existing stmt in a block, old_bsi will be returned with an iterator for
2998    that stmt (The equivalent of BSI_SAME_STMT on an insert_before or after.
2999    If a created_block is passed in, and the edge is split, the new block is
3000    returned through this parameter.  */
3001
3002 block_stmt_iterator
3003 bsi_insert_on_edge_immediate (edge e, tree stmt, block_stmt_iterator *old_bsi,
3004                               basic_block *created_block)
3005 {
3006   basic_block src, dest, new_bb;
3007   block_stmt_iterator bsi, tmp;
3008   int num_exit, num_entry;
3009   tree last;
3010   bb_ann_t ann;
3011   edge e2;
3012
3013   if (old_bsi)
3014     old_bsi->curr_stmt = NULL;
3015   if (created_block)
3016     *created_block = (basic_block)NULL;
3017
3018   src = e->src;
3019   dest = e->dest;
3020
3021   /* Cannot insert on an abnormal edge.  */
3022   if (e->flags & EDGE_ABNORMAL)
3023     abort ();
3024
3025   /* No immediate edge insertion if there are already pending inserts.  */
3026   if (PENDING_STMT (e))
3027     abort ();
3028
3029   num_exit = num_entry = 0;
3030
3031   for (e2 = src->succ; e2; e2 = e2->succ_next)
3032     num_exit++;
3033
3034   for (e2 = dest->pred; e2; e2 = e2->pred_next)
3035     num_entry++;
3036
3037   /* If src is a single-exit block, and it isn't the entry block, then
3038      insert at the end of the block, if we can.  */
3039
3040   if (num_exit == 1 && src != ENTRY_BLOCK_PTR)
3041     {
3042       bsi = bsi_last (src);
3043       /* If it is an empty block, simply insert after this bsi, and the new stmt
3044          will become the only stmt in the block.  */
3045       if (bsi_end_p (bsi))
3046         {
3047           bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3048           return bsi;
3049         }
3050       last = bsi_stmt (bsi);
3051
3052       /* If the last stmt isn't a control altering stmt, then we can simply
3053          append this stmt to the basic block. This should mean the edge is
3054          a fallthrough edge.  */
3055
3056       if (!is_ctrl_stmt (last) && !is_ctrl_altering_stmt (last))
3057         {
3058           bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
3059           if (old_bsi)
3060             *old_bsi = bsi;
3061           bsi_next (&bsi);
3062           return bsi;
3063         }
3064
3065       /* If the last stmt is a GOTO, the we can simply insert before it.  */
3066       if (TREE_CODE (last) == GOTO_EXPR)
3067         {
3068           bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3069           if (old_bsi)
3070             {
3071               *old_bsi = bsi;
3072               bsi_next (old_bsi);
3073             }
3074           return bsi;
3075         }
3076     }
3077
3078   /* If dest is a single entry destination, and it isn't the exit block, the new
3079      stmt can be inserted at the beginning of the destination block.  */
3080
3081   if (num_entry == 1 && dest != EXIT_BLOCK_PTR)
3082     {
3083       bsi = bsi_start (dest);
3084       /* If it is an empty block, simply insert after this bsi, and the new stmt
3085          will become the only stmt in the block.  */
3086       if (bsi_end_p (bsi))
3087         {
3088           bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3089           return bsi;
3090         }
3091
3092       /* Skip any labels, and insert before the first non-label.  */
3093       for (tmp = bsi, bsi_next (&bsi); !bsi_end_p (bsi); bsi_next (&bsi))
3094         {
3095           if (!is_label_stmt (bsi_stmt (bsi)))
3096             {
3097               bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3098               if (old_bsi)
3099                 {
3100                   *old_bsi = bsi;
3101                   bsi_next (old_bsi);
3102                 }
3103               return bsi;
3104             }
3105           tmp = bsi;
3106         }
3107
3108       /* If this point is reached, then the block consists of nothing but
3109          labels, and tmp points to the last one. Insert after it.  */
3110       bsi_insert_after (&tmp, stmt, BSI_SAME_STMT);
3111       if (old_bsi)
3112         *old_bsi = tmp;
3113       bsi_next (&tmp);
3114       return tmp;
3115     }
3116
3117   /* Otherwise, create a new basic block, and split this edge.  */
3118   new_bb = split_edge (e);
3119   ann = bb_ann (new_bb);
3120
3121   if (created_block)
3122     *created_block = new_bb;
3123
3124   bsi = bsi_start (new_bb);
3125   if (bsi_stmt (bsi)
3126       && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
3127     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3128   else
3129     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3130
3131   return bsi;
3132 }
3133
3134 /* This routine will commit all pending edge insertions, creating any new
3135    basic blocks which are necessary. The number of edges which were inserted
3136    is returned.  If the flag update_annotations is true, then new bitmaps are
3137    created for the dominator children, and they are updated.  If specified,
3138    new_blocks returned a count of the number of new basic blocks which were
3139    created.  */
3140
3141 int
3142 bsi_commit_edge_inserts (int update_annotations, int *new_blocks)
3143 {
3144   basic_block bb;
3145   block_stmt_iterator bsi, ret;
3146   edge e;
3147   tree stmt, next_stmt;
3148   int blocks, count = 0;
3149
3150   blocks = n_basic_blocks;
3151
3152   FOR_EACH_BB (bb)
3153     {
3154       for (e = bb->succ; e; e = e->succ_next)
3155         if (PENDING_STMT (e))
3156           {
3157             stmt = PENDING_STMT (e);
3158             SET_PENDING_STMT (e, NULL_TREE);
3159             next_stmt = TREE_CHAIN (stmt);
3160             /* The first insert will create a new basic block if needed.  */
3161             ret = bsi = bsi_insert_on_edge_immediate (e, stmt, NULL, NULL);
3162             count++;
3163             stmt = next_stmt;
3164             for ( ; stmt; stmt = next_stmt)
3165               {
3166                 /* All further inserts can simply follow the first one.  */
3167                 next_stmt = TREE_CHAIN (stmt);
3168                 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3169                 count++;
3170               }
3171
3172           }
3173     }
3174
3175   if (new_blocks)
3176     *new_blocks = n_basic_blocks - blocks;
3177
3178   /* Expand arrays if we created new blocks and need to update them.  */
3179   if (update_annotations && blocks != n_basic_blocks)
3180     {
3181       abort ();
3182       /* TODO. Unimplemented at the moment.  */
3183     }
3184
3185   return count;
3186 }
3187
3188 /* This routine adds a stmt to the pending list on an edge. No actual
3189    insertion is made until a call to bsi_commit_edge_inserts () is made.  */
3190
3191 void
3192 bsi_insert_on_edge (edge e, tree stmt)
3193 {
3194   tree t;
3195
3196   t = PENDING_STMT (e);
3197   if (!t)
3198     SET_PENDING_STMT (e, stmt);
3199   else
3200     {
3201       for ( ; TREE_CHAIN (t); t = TREE_CHAIN (t))
3202         continue;
3203       TREE_CHAIN (t) = stmt;
3204       TREE_CHAIN (stmt) = NULL_TREE;
3205     }
3206
3207 }
3208
3209 /* Replace the statement TP1 with the statement TP2.  */
3210
3211 static void
3212 replace_stmt (tree_cell tp1, tree t)
3213 {
3214   basic_block bb;
3215
3216   /* Relocate annotations for the replacement statement.  */
3217   SET_EXPR_LOCUS (t, EXPR_LOCUS (tp1->stmt));
3218   bb = bb_for_stmt (tp1->stmt);
3219   tp1->stmt = t;
3220   set_bb_for_stmt (t, bb);
3221 }
3222
3223 /*---------------------------------------------------------------------------
3224             Tree specific functions for the cfg loop optimizer
3225 ---------------------------------------------------------------------------*/
3226
3227 /* Split a (typically critical) edge.  Return the new block.
3228    Abort on abnormal edges.  */
3229
3230 basic_block
3231 tree_split_edge (edge edge_in)
3232 {
3233   basic_block new_bb, dest;
3234   edge new_edge;
3235   tree phi;
3236   int i, num_elem;
3237
3238   /* Abnormal edges cannot be split.  */
3239   if (edge_in->flags & EDGE_ABNORMAL)
3240     abort ();
3241
3242   dest = edge_in->dest;
3243   new_bb = create_bb ();
3244
3245   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3246   /* Find all the PHI arguments on the original edge, and change them to
3247      the new edge.  Do it now, since redirect_edge_and_branch would cancel
3248      the args otherwise.  */
3249   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
3250     {
3251       num_elem = PHI_NUM_ARGS (phi);
3252       for (i = 0; i < num_elem; i++)
3253         if (PHI_ARG_EDGE (phi, i) == edge_in)
3254           {
3255             PHI_ARG_EDGE (phi, i) = new_edge;
3256             break;
3257           }
3258     }
3259
3260   if (!redirect_edge_and_branch (edge_in, new_bb))
3261     abort ();
3262   tree_cleanup_block_edges (new_bb, false);
3263
3264
3265   return new_bb;
3266 }
3267
3268 /* Splits the basic block BB into two after BSI and returns the created
3269    fallthru edge.  */
3270 edge
3271 tree_split_block (basic_block bb, block_stmt_iterator bsi)
3272 {
3273   basic_block new_bb = create_bb ();
3274   edge e;
3275   int end;
3276
3277   /* Place the new block in front of the old one.  */
3278   unlink_block (new_bb);
3279   link_block (new_bb, bb->prev_bb);
3280
3281   new_bb->head_tree = bb->head_tree;
3282   new_bb->end_tree = bsi_cell (bsi);
3283
3284   end = bsi_end_p (bsi);
3285   if (!end)
3286     {
3287       bsi_next (&bsi);
3288       end = bsi_end_p (bsi);
3289     }
3290
3291   if (end)
3292     {
3293       /* Unless the block has only a fallthru edge, splitting the block
3294          would be wrong, as the edges coming from the control flow altering
3295          statement would be on the wrong place.  */
3296       if (!bb->succ
3297           || bb->succ->succ_next
3298           || !(bb->flags & EDGE_FALLTHRU))
3299         abort ();
3300
3301       new_bb->end_tree = bb->end_tree;
3302       bb->head_tree = NULL;
3303       bb->end_tree = NULL;
3304     }
3305   else
3306     {
3307       bb->head_tree = bsi_cell (bsi);
3308       new_bb->end_tree->next = NULL;
3309       bb->head_tree->prev = NULL;
3310     }
3311
3312   new_bb->pred = bb->pred;
3313   bb->pred = NULL;
3314   for (e = new_bb->pred; e; e = e->pred_next)
3315     e->dest = new_bb;
3316
3317   return make_edge (new_bb, bb, EDGE_FALLTHRU);
3318 }
3319
3320 /* Moves basic block BB after block AFTER.  */
3321 void
3322 tree_move_block_after (basic_block bb, basic_block after, int no_false_fallthru)
3323 {
3324   basic_block prev = bb->prev_bb;
3325
3326   if (bb->prev_bb == after)
3327     return;
3328
3329   unlink_block (bb);
3330   link_block (bb, after);
3331
3332   /* Fix up fallthru edges.  */
3333   if (prev && prev != ENTRY_BLOCK_PTR)
3334     tree_cleanup_block_edges (prev, no_false_fallthru);
3335   tree_cleanup_block_edges (bb, no_false_fallthru);
3336   tree_cleanup_block_edges (after, no_false_fallthru);
3337 }
3338
3339 /* Verifies that the flow information is OK.  */
3340
3341 static int
3342 tree_verify_flow_info (void)
3343 {
3344   basic_block bb;
3345   tree_cell stmt, last;
3346   tree t, l, label, phi;
3347   block_stmt_iterator si;
3348   edge e, le, te, fe;
3349   int err = 0, degree;
3350
3351   FOR_EACH_BB (bb)
3352     {
3353       if (!bb->head_tree)
3354         continue;
3355
3356       last = NULL;
3357       for (stmt = bb->head_tree; stmt; last = stmt, stmt = stmt->next)
3358         {
3359           if (stmt->prev != last)
3360             {
3361               fprintf (stderr, "chain inconsistent in bb %d\n", bb->index);
3362               err = 1;
3363             }
3364
3365           if (last
3366               && stmt_ends_bb_p (last->stmt))
3367             {
3368               fprintf (stderr, "control statement in the middle of bb %d\n",
3369                        bb->index);
3370               err = 1;
3371             }
3372
3373           if (TREE_CODE (stmt->stmt) == COMPOUND_EXPR
3374               || TREE_CODE (stmt->stmt) == CASE_LABEL_EXPR
3375               || TREE_CODE (stmt->stmt) == BIND_EXPR)
3376             {
3377               fprintf (stderr, "forbidden statement in the middle of bb %d\n",
3378                        bb->index);
3379               err = 1;
3380             }
3381
3382           if (bb_for_stmt (stmt->stmt) != bb)
3383             {
3384               fprintf (stderr, "bb_for_stmt inconsistent in bb %d\n",
3385                        bb->index);
3386               err = 1;
3387             }
3388         }
3389       if (last != bb->end_tree)
3390         {
3391           fprintf (stderr, "end_tree inconsistent in bb %d\n",
3392                    bb->index);
3393           err = 1;
3394         }
3395
3396       last = NULL;
3397       for (stmt = bb->end_tree; stmt; last = stmt, stmt = stmt->prev)
3398         if (stmt->next != last)
3399           {
3400             fprintf (stderr, "chain inconsistent in bb %d\n", bb->index);
3401             err = 1;
3402           }
3403       if (last != bb->head_tree)
3404         {
3405           fprintf (stderr, "head_tree inconsistent in bb %d\n",
3406                    bb->index);
3407           err = 1;
3408         }
3409
3410       t = last_stmt (bb);
3411       if (t)
3412         {
3413           switch (TREE_CODE (t))
3414             {
3415             case GOTO_EXPR:
3416               if (!bb->succ)
3417                 {
3418                   fprintf (stderr, "goto without successors %d\n", bb->index);
3419                   err = 1;
3420                 }
3421               if (is_computed_goto (t)
3422                   || nonlocal_goto_p (t))
3423                 break;
3424
3425               le = NULL;
3426               for (e = bb->succ; e; e = e->succ_next)
3427                 {
3428                   if (!(e->flags & EDGE_ABNORMAL))
3429                     {
3430                       if (le)
3431                         {
3432                           fprintf (stderr, "goto with more than one successor %d\n",
3433                                    bb->index);
3434                           err = 1;
3435                         }
3436                       else
3437                         le = e;
3438                     }
3439
3440                   if (e->flags & EDGE_FALLTHRU)
3441                     {
3442                       fprintf (stderr, "goto with fallthru %d\n", bb->index);
3443                       err = 1;
3444                     }
3445                 }
3446               if (!le)
3447                 {
3448                   fprintf (stderr, "goto without successors %d\n", bb->index);
3449                   err = 1;
3450                 }
3451
3452               label = GOTO_DESTINATION (t);
3453               for (si = bsi_start (le->dest);
3454                    !bsi_end_p (si);
3455                    bsi_next (&si))
3456                 {
3457                   l = bsi_stmt (si);
3458                   if (TREE_CODE (l) == LABEL_EXPR
3459                       && LABEL_EXPR_LABEL (l) == label)
3460                     break;
3461                 }
3462               if (bsi_end_p (si))
3463                 {
3464                   fprintf (stderr, "%d: goto label not in dest block %d\n",
3465                            bb->index, le->dest->index);
3466                   err = 1;
3467                 }
3468               break;
3469
3470             case COND_EXPR:
3471               if (!bb->succ || !bb->succ->succ_next)
3472                 {
3473                   fprintf (stderr, "condition with less than 2 successors %d\n",
3474                            bb->index);
3475                   err = 1;
3476                 }
3477
3478               te = fe = NULL;
3479               for (e = bb->succ; e; e = e->succ_next)
3480                 {
3481                   if (e->flags & EDGE_FALLTHRU)
3482                     {
3483                       fprintf (stderr, "condition with fallthru %d\n", bb->index);
3484                       err = 1;
3485                     }
3486                   if (e->flags & EDGE_ABNORMAL)
3487                     continue;
3488
3489                   if (e->flags & EDGE_TRUE_VALUE)
3490                     {
3491                       if (te)
3492                         {
3493                           fprintf (stderr, "more than one true edge %d\n",
3494                                    bb->index);
3495                           err = 1;
3496                         }
3497                       else
3498                         te = e;
3499                     }
3500
3501                   if (e->flags & EDGE_FALSE_VALUE)
3502                     {
3503                       if (fe)
3504                         {
3505                           fprintf (stderr, "more than one false edge %d\n",
3506                                    bb->index);
3507                           err = 1;
3508                         }
3509                       else
3510                         fe = e;
3511                     }
3512                 }
3513               if (!te)
3514                 {
3515                   fprintf (stderr, "condition with no true edge %d\n",
3516                            bb->index);
3517                   err = 1;
3518                 }
3519               if (!fe)
3520                 {
3521                   fprintf (stderr, "condition with no false edge %d\n",
3522                            bb->index);
3523                   err = 1;
3524                 }
3525
3526               label = GOTO_DESTINATION (COND_EXPR_THEN (t));
3527               for (si = bsi_start (te->dest); !bsi_end_p (si); bsi_next (&si))
3528                 {
3529                   l = bsi_stmt (si);
3530                   if (TREE_CODE (l) == LABEL_EXPR
3531                       && LABEL_EXPR_LABEL (l) == label)
3532                     break;
3533                 }
3534               if (bsi_end_p (si))
3535                 {
3536                   fprintf (stderr, "%d: goto label not in dest block %d\n",
3537                            bb->index, te->dest->index);
3538                   err = 1;
3539                 }
3540
3541               label = GOTO_DESTINATION (COND_EXPR_ELSE (t));
3542               for (si = bsi_start (fe->dest); !bsi_end_p (si); bsi_next (&si))
3543                 {
3544                   l = bsi_stmt (si);
3545                   if (TREE_CODE (l) == LABEL_EXPR
3546                       && LABEL_EXPR_LABEL (l) == label)
3547                     break;
3548                 }
3549               if (bsi_end_p (si))
3550                 {
3551                   fprintf (stderr, "%d: goto label not in dest block %d\n",
3552                            bb->index, fe->dest->index);
3553                   err = 1;
3554                 }
3555               break;
3556
3557             default: ;
3558             }
3559         }
3560
3561       degree = 0;
3562       for (e = bb->pred; e; e = e->pred_next)
3563         {
3564           for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3565             if (phi_arg_from_edge (phi, e) < 0)
3566               {
3567                 fprintf (stderr,
3568                          "No entry for edge in phi node: %d\n", bb->index);
3569                 err = 1;
3570               }
3571           degree++;
3572         }
3573       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3574         if (PHI_NUM_ARGS (phi) != degree)
3575           {
3576             fprintf (stderr,
3577                      "Superfluous entries in phi node: %d\n", bb->index);
3578             err = 1;
3579           }
3580     }
3581
3582   /* Entry block should have just one successor.  Exit block should have
3583      at most one fallthru predecessor.  */
3584   if (!ENTRY_BLOCK_PTR->succ
3585       || ENTRY_BLOCK_PTR->succ->succ_next)
3586     {
3587       fprintf (stderr, "Wrong amount of edges from entry\n");
3588       err = 1;
3589     }
3590
3591   if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_FALLTHRU))
3592     {
3593       fprintf (stderr, "Entry is not fallthru\n");
3594       err = 1;
3595     }
3596
3597   le = NULL;
3598   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
3599     if (e->flags & EDGE_FALLTHRU)
3600       {
3601         if (le)
3602           {
3603             fprintf (stderr, "More than one fallthru to exit\n");
3604             err = 1;
3605             break;
3606           }
3607         le = e;
3608       }
3609
3610   return err;
3611 }
3612
3613
3614 /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
3615    marked as latch into entry part, analogically for REDIRECT_NONLATCH.
3616    In both of these cases, ignore edge EXCEPT.  If CONN_LATCH, set edge
3617    between created entry part and BB as latch one.  Return created entry
3618    part.  */
3619
3620 static basic_block
3621 tree_make_forwarder_block (basic_block bb, int redirect_latch,
3622                            int redirect_nonlatch, edge except, int conn_latch)
3623 {
3624   edge e, next_e, fallthru;
3625   basic_block dummy;
3626
3627   /* Create the new basic block.  */
3628   dummy = create_bb ();
3629   dummy->count = bb->count;
3630   dummy->frequency = bb->frequency;
3631   dummy->loop_depth = bb->loop_depth;
3632   dummy->head_tree = NULL;
3633   dummy->end_tree = NULL;
3634
3635   /* Redirect the incoming edges.  */
3636   dummy->pred = bb->pred;
3637   bb->pred = NULL;
3638   for (e = dummy->pred; e; e = e->pred_next)
3639     e->dest = dummy;
3640
3641   fallthru = make_edge (dummy, bb, 0);
3642
3643   HEADER_BLOCK (dummy) = 0;
3644   HEADER_BLOCK (bb) = 1;
3645
3646   /* Redirect back edges we want to keep.  */
3647   for (e = dummy->pred; e; e = next_e)
3648     {
3649       next_e = e->pred_next;
3650       if (e == except
3651           || !((redirect_latch && LATCH_EDGE (e))
3652                || (redirect_nonlatch && !LATCH_EDGE (e))))
3653         {
3654           dummy->frequency -= EDGE_FREQUENCY (e);
3655           dummy->count -= e->count;
3656           if (dummy->frequency < 0)
3657             dummy->frequency = 0;
3658           if (dummy->count < 0)
3659             dummy->count = 0;
3660           redirect_edge_succ (e, bb);
3661         }
3662     }
3663
3664   alloc_aux_for_edge (fallthru, sizeof (int));
3665   LATCH_EDGE (fallthru) = conn_latch;
3666
3667   return dummy;
3668 }
3669
3670 /* Cleanup the cfg -- edges correspondence for a single block BB.  If
3671    NO_FALSE_FALLTHRU, just remove false fallthru edges.  */
3672 void
3673 tree_cleanup_block_edges (basic_block bb, int no_false_fallthru)
3674 {
3675   edge e, e_true, e_false, next;
3676   block_stmt_iterator bsi;
3677   tree stmt;
3678   tree_stmt_iterator alt;
3679
3680   if (bb == ENTRY_BLOCK_PTR)
3681     return;
3682
3683 redo:
3684   stmt = last_stmt (bb);
3685   bsi = bsi_last (bb);
3686
3687   if (!stmt
3688       || !stmt_ends_bb_p (stmt)
3689       || no_false_fallthru)
3690     {
3691       for (e = bb->succ; e; e = e->succ_next)
3692         if (e->flags & EDGE_FALLTHRU)
3693           break;
3694
3695       if (e && e->dest != bb->next_bb && e->dest != EXIT_BLOCK_PTR)
3696         {
3697           tree label = tree_block_label (e->dest);
3698
3699           bsi_insert_after (&bsi,
3700                             build1 (GOTO_EXPR, void_type_node, label),
3701                             BSI_NEW_STMT);
3702           e->flags &= ~EDGE_FALLTHRU;
3703           goto redo;
3704         }
3705     }
3706
3707   if (!stmt
3708       || no_false_fallthru)
3709     return;
3710
3711   switch (TREE_CODE (stmt))
3712     {
3713     case GOTO_EXPR:
3714       if (is_computed_goto (stmt)
3715           || nonlocal_goto_p (stmt))
3716         break;
3717
3718       e_true = NULL;
3719       for (e = bb->succ; e; e = e->succ_next)
3720         {
3721           if (e->flags & EDGE_ABNORMAL)
3722             continue;
3723
3724           if (e_true)
3725             abort ();
3726
3727           e_true = e;
3728         }
3729
3730       if (!e_true)
3731         break;
3732
3733       if (e_true->dest == bb->next_bb)
3734         {
3735           bsi_remove (&bsi);
3736           e_true->flags |= EDGE_FALLTHRU;
3737         }
3738       break;
3739
3740     case COND_EXPR:
3741       e_true = e_false = NULL;
3742
3743       for (e = bb->succ; e; e = e->succ_next)
3744         {
3745           if (e->flags & EDGE_TRUE_VALUE)
3746             {
3747               if (e_true)
3748                 abort ();
3749               e_true = e;
3750             }
3751           if (e->flags & EDGE_FALSE_VALUE)
3752             {
3753               if (e_false)
3754                 abort ();
3755               e_false = e;
3756             }
3757         }
3758
3759       /* During cfg generation it may happen that both branches of COND_EXPR
3760          lead to the same target.  */
3761       if (e_true == e_false)
3762         e_false = NULL;
3763
3764       if ((!e_true && !e_false)
3765           || (e_true && e_false))
3766         break;
3767
3768       if (!e_true)
3769         bsi_replace (bsi, COND_EXPR_ELSE (stmt));
3770       else if (!e_false)
3771         bsi_replace (bsi, COND_EXPR_THEN (stmt));
3772
3773       /* Try optimizing the resulting goto.  */
3774       goto redo;
3775
3776     case SWITCH_EXPR:
3777       if (!bb->succ)
3778         break;
3779
3780       alt = CASE_START (stmt);
3781       if (bb->succ->succ_next)
3782         {
3783           /* If there are more edges, but only one matches, we may proceed
3784              anyway.  */
3785           e_true = find_taken_edge (bb, SWITCH_COND (stmt));
3786           if (!e_true)
3787             break;
3788           for (; !CASE_END_P (alt); CASE_NEXT (alt))
3789             if (CASE_EDGE (alt) == e_true)
3790               break;
3791           if (CASE_END_P (alt))
3792             abort ();
3793
3794           for (e = bb->succ; e; e = next)
3795             {
3796               next = e->succ_next;
3797               if (e == e_true
3798                   || (e->flags & EDGE_ABNORMAL))
3799                 continue;
3800
3801               ssa_remove_edge (e);
3802             }
3803         }
3804
3805       bsi_replace (bsi, CASE_GOTO (alt));
3806       goto redo;
3807
3808     default: ;
3809     }
3810 }
3811
3812 /* Cleanup the cfg -- edges correspondence damaged by previous passes.
3813    Edges could be removed while unreachable jumps from their control
3814    statemens were not.  */
3815 static void
3816 tree_cleanup_edges ()
3817 {
3818   basic_block bb;
3819
3820   FOR_EACH_BB (bb)
3821     {
3822       tree_cleanup_block_edges (bb, false);
3823     }
3824 }
3825
3826 /* Initialization of functions specific to the tree IR.  */
3827
3828 void
3829 tree_register_cfg_hooks ()
3830 {
3831   cfg_hooks = &tree_cfg_hooks;
3832 }
3833
3834 /* Dumps information about tree_cell chain START to stderr.  */
3835 void
3836 debug_tree_chain (tree_cell start)
3837 {
3838   for (; start; start = start->next)
3839     debug_generic_stmt (start->stmt);
3840 }
3841
3842 /* Initialize loop optimizer.  */
3843
3844 static struct loops *
3845 tree_loop_optimizer_init (FILE *dumpfile)
3846 {
3847   struct loops *loops = xcalloc (1, sizeof (struct loops));
3848
3849   /* Find the loops.  */
3850   if (flow_loops_find (loops, LOOP_TREE) <= 1)
3851     {
3852       /* No loops.  */
3853       flow_loops_free (loops);
3854       free (loops);
3855       return NULL;
3856     }
3857
3858   /* Not going to update these.  */
3859   free (loops->cfg.rc_order);
3860   loops->cfg.rc_order = NULL;
3861   free (loops->cfg.dfs_order);
3862   loops->cfg.dfs_order = NULL;
3863
3864   /* Force all latches to have only single successor.  */
3865   force_single_succ_latches (loops);
3866
3867   /* Mark irreducible loops.  */
3868   mark_irreducible_loops (loops);
3869
3870   /* Dump loops.  */
3871   flow_loops_dump (loops, dumpfile, NULL, 1);
3872
3873 #ifdef ENABLE_CHECKING
3874   verify_dominators (loops->cfg.dom);
3875   verify_loop_structure (loops);
3876 #endif
3877
3878   return loops;
3879 }
3880
3881 /* Finalize loop optimizer.  */
3882 static void
3883 tree_loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
3884 {
3885   if (loops == NULL)
3886     return;
3887
3888   /* Another dump.  */
3889   flow_loops_dump (loops, dumpfile, NULL, 1);
3890
3891   /* Clean up.  */
3892   flow_loops_free (loops);
3893   free (loops);
3894
3895   /* Checking.  */
3896 #ifdef ENABLE_CHECKING
3897   verify_flow_info ();
3898 #endif
3899 }
3900
3901 /* Ensures that there are not useless labels.  It makes all jumps to
3902    the block to target one label (non-artificial ones are preferred),
3903    and removes all other artificial labels (the named ones are left
3904    for debugging purposes.  */
3905 static void
3906 remove_superfluous_labels ()
3907 {
3908   basic_block bb;
3909   edge e;
3910   block_stmt_iterator bsi;
3911   tree stmt, label;
3912   tree_stmt_iterator alt;
3913   int preserve;
3914
3915   FOR_EACH_BB (bb)
3916     {
3917       bsi = bsi_start (bb);
3918       stmt = first_stmt (bb);
3919
3920       if (!stmt || TREE_CODE (stmt) != LABEL_EXPR)
3921         continue;
3922
3923       /* Try to find a label that must stay anyway.  */
3924       label = LABEL_EXPR_LABEL (stmt);
3925       for (;
3926            DECL_ARTIFICIAL (label) && !FORCED_LABEL (label) && !bsi_end_p (bsi);
3927            bsi_next (&bsi))
3928         {
3929           stmt = bsi_stmt (bsi);
3930           if (TREE_CODE (stmt) != LABEL_EXPR)
3931             break;
3932
3933           label = LABEL_EXPR_LABEL (stmt);
3934         }
3935
3936       /* Replace to it within all jumps to the block.  */
3937       preserve = false;
3938       for (e = bb->pred; e; e = e->pred_next)
3939         {
3940           if ((e->flags & EDGE_ABNORMAL)
3941               || (e->flags & EDGE_FALLTHRU))
3942             continue;
3943
3944           stmt = last_stmt (e->src);
3945           if (TREE_CODE (stmt) == SWITCH_EXPR)
3946             {
3947               for (alt = CASE_START (stmt);
3948                    !CASE_END_P (alt);
3949                    CASE_NEXT (alt))
3950                 if (CASE_EDGE (alt) == e)
3951                   CASE_DESTINATION (alt) = label;
3952             }
3953           else
3954             {
3955               stmt = find_edge_goto (last_stmt (e->src), e);
3956               if (!stmt)
3957                 abort ();
3958               GOTO_DESTINATION (stmt) = label;
3959             }
3960
3961           preserve = true;
3962         }
3963
3964       if (!preserve)
3965         label = NULL_TREE;
3966
3967       /* Remove unnecesary labels.  Due to way we have chosen the label to
3968          keep, the kept label will then be the first one of the block,
3969          therefore the one returned by tree_block_label, which is fine.  */
3970       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3971         {
3972           stmt = bsi_stmt (bsi);
3973           if (TREE_CODE (stmt) != LABEL_EXPR)
3974             break;
3975
3976           if (LABEL_EXPR_LABEL (stmt) == label
3977               || !DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt))
3978               || FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
3979             {
3980               bsi_next (&bsi);
3981               continue;
3982             }
3983
3984           bsi_remove (&bsi);
3985         }
3986     }
3987 }
3988
3989 /* Checks whether the basic block BB does nothing except for jump.  */
3990 static bool
3991 tree_forwarder_block_p (basic_block bb)
3992 {
3993   block_stmt_iterator bsi;
3994
3995   if (!bb->succ
3996       || bb->succ->succ_next
3997       || (bb->succ->flags & EDGE_ABNORMAL)
3998       || bb == ENTRY_BLOCK_PTR)
3999     return false;
4000
4001   if (phi_nodes (bb))
4002     return false;
4003
4004   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4005     switch (TREE_CODE (bsi_stmt (bsi)))
4006       {
4007       case LABEL_EXPR:
4008       case GOTO_EXPR:
4009         break;
4010
4011       default:
4012         return false;
4013       }
4014
4015   return true;
4016 }
4017
4018 /* Threads jumps over empty statements.  Later we may add threading over
4019    equivalent conditions.  */
4020 static void
4021 thread_jumps ()
4022 {
4023   edge e, next, last, old;
4024   basic_block bb, dest, slow;
4025   int set_slow;
4026   tree phi, val1, val2;
4027   int arg;
4028
4029   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
4030     {
4031       /* Don't waste time on unreachable blocks.  */
4032       if (!bb->pred)
4033         continue;
4034
4035       /* Nor on forwarders.  */
4036       if (tree_forwarder_block_p (bb))
4037         continue;
4038
4039       for (e = bb->succ; e; e = next)
4040         {
4041           next = e->succ_next;
4042
4043           if ((e->flags & EDGE_ABNORMAL)
4044               || e->dest == EXIT_BLOCK_PTR
4045               || !tree_forwarder_block_p (e->dest)
4046               || e->dest->succ->dest == EXIT_BLOCK_PTR)
4047             continue;
4048
4049           slow = e->dest;
4050           set_slow = 0;
4051
4052           last = e->dest->succ;
4053           for (dest = e->dest->succ->dest;
4054                tree_forwarder_block_p (dest);
4055                last = dest->succ,
4056                dest = dest->succ->dest,
4057                set_slow ^= 1)
4058             {
4059               /* Infinite loop detected.  */
4060               if (slow == dest)
4061                 break;
4062               if (set_slow)
4063                 slow = slow->succ->dest;
4064
4065               if (dest->succ->dest == EXIT_BLOCK_PTR)
4066                 break;
4067             }
4068
4069           if (dest == e->dest)
4070             continue;
4071
4072           old = find_edge (bb, dest);
4073           if (old)
4074             {
4075               /* If there already is an edge, check whether the values of
4076                  in phi nodes differ.  */
4077               for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
4078                 {
4079                   val1 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, last));
4080                   val2 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, old));
4081
4082                   if (!operand_equal_p (val1, val2, false))
4083                     break;
4084                 }
4085               if (phi)
4086                 {
4087                   /* The previous block is forwarder, so there are no
4088                      phi nodes to update.  */
4089                   dest = last->src;
4090                 }
4091             }
4092
4093           if (dest == e->dest)
4094             continue;
4095
4096           if (redirect_edge_and_branch (e, dest)
4097               && !old)
4098             {
4099               /* Update phi nodes.  */
4100               for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
4101                 {
4102                   arg = phi_arg_from_edge (phi, last);
4103                   if (arg < 0)
4104                     abort ();
4105                   add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
4106                 }
4107             }
4108         }
4109     }
4110 }
4111
4112 /* Returns a GOTO_EXPR for edge E found in STMT.  */
4113 static tree
4114 find_edge_goto (tree stmt, edge e)
4115 {
4116   if (!stmt)
4117     return NULL_TREE;
4118
4119   switch (TREE_CODE (stmt))
4120     {
4121     case SWITCH_EXPR:
4122       /* Using this function for switch_exprs is dangerous, since there
4123          may be more than one goto to the one edge.  */
4124       abort ();
4125
4126     case COND_EXPR:
4127       if (e->flags & EDGE_TRUE_VALUE)
4128         return COND_EXPR_THEN (stmt);
4129       else if (e->flags & EDGE_FALSE_VALUE)
4130         return COND_EXPR_ELSE (stmt);
4131       else
4132         abort ();
4133
4134     case GOTO_EXPR:
4135       return stmt;
4136
4137     default:
4138       return NULL_TREE;
4139     }
4140 }
4141
4142 /* Merges blocks if possible.  */
4143 static void
4144 merge_seq_blocks ()
4145 {
4146   basic_block bb;
4147
4148   for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; )
4149     {
4150       if (
4151           /* It must have a single succesor.  */
4152           bb->succ
4153           && !bb->succ->succ_next
4154           && !(bb->succ->flags & EDGE_ABNORMAL)
4155           && bb->succ->dest != EXIT_BLOCK_PTR
4156           && bb->succ->dest != bb
4157           /* That has a single predecessor.  */
4158           && !bb->succ->dest->pred->pred_next)
4159         {
4160           /* Merge the blocks and retry.  */
4161           merge_blocks (bb, bb->succ->dest);
4162           continue;
4163         }
4164
4165       bb = bb->next_bb;
4166     }
4167 }
4168
4169 /* Non-cfg cleanup.  */
4170
4171 /* Walk the function tree removing unnecessary statements and
4172    variables.
4173
4174      * Empty statement nodes are removed
4175
4176      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
4177
4178      * Unnecessary COND_EXPRs are removed
4179
4180      * Some unnecessary BIND_EXPRs are removed
4181
4182    Clearly more work could be done.  The trick is doing the analysis
4183    and removal fast enough to be a net improvement in compile times.
4184
4185    Note that when we remove a control structure such as a COND_EXPR
4186    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
4187    to ensure we eliminate all the useless code.  */
4188
4189 struct rusv_data
4190 {
4191   bool repeat;
4192   bool remove_unused_vars;
4193   bool may_throw;
4194   bool may_branch;
4195 };
4196
4197 static void remove_useless_stmts_and_vars_1 (tree *, struct rusv_data *);
4198
4199 static void
4200 remove_useless_stmts_and_vars_cond (tree *stmt_p, struct rusv_data *data)
4201 {
4202   tree then_clause, else_clause, cond;
4203
4204   remove_useless_stmts_and_vars_1 (&COND_EXPR_THEN (*stmt_p), data);
4205   remove_useless_stmts_and_vars_1 (&COND_EXPR_ELSE (*stmt_p), data);
4206
4207   then_clause = COND_EXPR_THEN (*stmt_p);
4208   else_clause = COND_EXPR_ELSE (*stmt_p);
4209   cond = COND_EXPR_COND (*stmt_p);
4210
4211   /* We may not have been able to completely optimize away the condition
4212      previously due to the existence of a label in one arm.  If the label
4213      has since become unreachable then we may be able to zap the entire
4214      conditional here.  If so, replace the COND_EXPR and set up to repeat
4215      this optimization pass.  */
4216   if (integer_nonzerop (cond) && IS_EMPTY_STMT (else_clause))
4217     {
4218       *stmt_p = then_clause;
4219        data->repeat = true;
4220     }
4221   else if (integer_zerop (cond) && IS_EMPTY_STMT (then_clause))
4222     {
4223       *stmt_p = else_clause;
4224       data->repeat = true;
4225     }
4226
4227   /* Notice branches to a common destination.  */
4228   else if (TREE_CODE (then_clause) == GOTO_EXPR
4229            && TREE_CODE (else_clause) == GOTO_EXPR
4230            && (GOTO_DESTINATION (then_clause)
4231                == GOTO_DESTINATION (else_clause)))
4232     {
4233       *stmt_p = then_clause;
4234       data->repeat = true;
4235     }
4236
4237   /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
4238      which is already known to contain that value, then remove the useless
4239      THEN/ELSE clause.  */
4240   else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
4241     {
4242       if (TREE_CODE (else_clause) == MODIFY_EXPR
4243           && TREE_OPERAND (else_clause, 0) == cond
4244           && integer_zerop (TREE_OPERAND (else_clause, 1)))
4245         COND_EXPR_ELSE (*stmt_p) = build_empty_stmt ();
4246     }
4247   else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
4248            && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
4249                || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
4250            && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
4251     {
4252       tree clause = (TREE_CODE (cond) == EQ_EXPR
4253                      ? then_clause : else_clause);
4254       tree *location = (TREE_CODE (cond) == EQ_EXPR
4255                         ? &COND_EXPR_THEN (*stmt_p)
4256                         : &COND_EXPR_ELSE (*stmt_p));
4257
4258       if (TREE_CODE (clause) == MODIFY_EXPR
4259           && TREE_OPERAND (clause, 0) == TREE_OPERAND (cond, 0)
4260           && TREE_OPERAND (clause, 1) == TREE_OPERAND (cond, 1))
4261         *location = build_empty_stmt ();
4262     }
4263 }
4264
4265 static void
4266 remove_useless_stmts_and_vars_tf (tree *stmt_p, struct rusv_data *data)
4267 {
4268   bool save_may_branch, save_may_throw;
4269   bool this_may_branch, this_may_throw;
4270
4271   /* Collect may_branch and may_throw information for the body only.  */
4272   save_may_branch = data->may_branch;
4273   save_may_throw = data->may_throw;
4274   data->may_branch = false;
4275   data->may_throw = false;
4276
4277   remove_useless_stmts_and_vars_1 (&TREE_OPERAND (*stmt_p, 0), data);
4278
4279   this_may_branch = data->may_branch;
4280   this_may_throw = data->may_throw;
4281   data->may_branch |= save_may_branch;
4282   data->may_throw |= save_may_throw;
4283
4284   remove_useless_stmts_and_vars_1 (&TREE_OPERAND (*stmt_p, 1), data);
4285
4286   /* If the body is empty, then we can emit the FINALLY block without
4287      the enclosing TRY_FINALLY_EXPR.  */
4288   if (IS_EMPTY_STMT (TREE_OPERAND (*stmt_p, 0)))
4289     {
4290       *stmt_p = TREE_OPERAND (*stmt_p, 1);
4291       data->repeat = true;
4292     }
4293
4294   /* If the handler is empty, then we can emit the TRY block without
4295      the enclosing TRY_FINALLY_EXPR.  */
4296   else if (IS_EMPTY_STMT (TREE_OPERAND (*stmt_p, 1)))
4297     {
4298       *stmt_p = TREE_OPERAND (*stmt_p, 0);
4299       data->repeat = true;
4300     }
4301
4302   /* If the body neither throws, nor branches, then we can safely string
4303      the TRY and FINALLY blocks together.  We'll reassociate this in the
4304      main body of remove_useless_stmts_and_vars.  */
4305   else if (!this_may_branch && !this_may_throw)
4306     TREE_SET_CODE (*stmt_p, COMPOUND_EXPR);
4307 }
4308
4309 static void
4310 remove_useless_stmts_and_vars_tc (tree *stmt_p, struct rusv_data *data)
4311 {
4312   bool save_may_throw, this_may_throw;
4313   tree_stmt_iterator i;
4314   tree stmt;
4315
4316   /* Collect may_throw information for the body only.  */
4317   save_may_throw = data->may_throw;
4318   data->may_throw = false;
4319
4320   remove_useless_stmts_and_vars_1 (&TREE_OPERAND (*stmt_p, 0), data);
4321
4322   this_may_throw = data->may_throw;
4323   data->may_throw = save_may_throw;
4324
4325   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
4326   if (!this_may_throw)
4327     {
4328       *stmt_p = TREE_OPERAND (*stmt_p, 0);
4329       data->repeat = true;
4330       return;
4331     }
4332
4333   /* Process the catch clause specially.  We may be able to tell that
4334      no exceptions propagate past this point.  */
4335
4336   this_may_throw = true;
4337   i = tsi_start (&TREE_OPERAND (*stmt_p, 1));
4338   stmt = tsi_stmt (i);
4339
4340   switch (TREE_CODE (stmt))
4341     {
4342     case CATCH_EXPR:
4343       for (; !tsi_end_p (i); tsi_next (&i))
4344         {
4345           stmt = tsi_stmt (i);
4346           /* If we catch all exceptions, then the body does not
4347              propagate exceptions past this point.  */
4348           if (CATCH_TYPES (stmt) == NULL)
4349             this_may_throw = false;
4350           remove_useless_stmts_and_vars_1 (&CATCH_BODY (stmt), data);
4351         }
4352       break;
4353
4354     case EH_FILTER_EXPR:
4355       if (EH_FILTER_MUST_NOT_THROW (stmt))
4356         this_may_throw = false;
4357       else if (EH_FILTER_TYPES (stmt) == NULL)
4358         this_may_throw = false;
4359       remove_useless_stmts_and_vars_1 (&EH_FILTER_FAILURE (stmt), data);
4360       break;
4361
4362     default:
4363       /* Otherwise this is a cleanup.  */
4364       remove_useless_stmts_and_vars_1 (&TREE_OPERAND (*stmt_p, 1), data);
4365
4366       /* If the cleanup is empty, then we can emit the TRY block without
4367          the enclosing TRY_CATCH_EXPR.  */
4368       if (IS_EMPTY_STMT (TREE_OPERAND (*stmt_p, 1)))
4369         {
4370           *stmt_p = TREE_OPERAND (*stmt_p, 0);
4371           data->repeat = true;
4372         }
4373       break;
4374     }
4375   data->may_throw |= this_may_throw;
4376 }
4377
4378 static void
4379 remove_useless_stmts_and_vars_bind (tree *stmt_p, struct rusv_data *data)
4380 {
4381   tree block;
4382
4383   /* First remove anything underneath the BIND_EXPR.  */
4384   remove_useless_stmts_and_vars_1 (&BIND_EXPR_BODY (*stmt_p), data);
4385
4386   /* If the BIND_EXPR has no variables, then we can pull everything
4387      up one level and remove the BIND_EXPR, unless this is the toplevel
4388      BIND_EXPR for the current function or an inlined function.
4389
4390      When this situation occurs we will want to apply this
4391      optimization again.  */
4392   block = BIND_EXPR_BLOCK (*stmt_p);
4393   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
4394       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
4395       && (! block
4396           || ! BLOCK_ABSTRACT_ORIGIN (block)
4397           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
4398               != FUNCTION_DECL)))
4399     {
4400       *stmt_p = BIND_EXPR_BODY (*stmt_p);
4401       data->repeat = true;
4402     }
4403   else if (data->remove_unused_vars)
4404     {
4405       /* If we were unable to completely eliminate the BIND_EXPR,
4406          go ahead and prune out any unused variables.  We do not
4407          want to expand them as that is a waste of time.  If we
4408          happen to remove all the variables, then we may be able
4409          to eliminate the BIND_EXPR as well.  */
4410       tree vars, prev_var;
4411
4412       /* Walk all the variables associated with the BIND_EXPR.  */
4413       for (prev_var = NULL, vars = BIND_EXPR_VARS (*stmt_p);
4414            vars;
4415            vars = TREE_CHAIN (vars))
4416         {
4417           struct var_ann_d *ann;
4418
4419           /* We could have function declarations and the like
4420              on this list.  Ignore them.  */
4421           if (TREE_CODE (vars) != VAR_DECL)
4422             {
4423               prev_var = vars;
4424               continue;
4425             }
4426
4427           /* Remove all unused, unaliased temporaries.  Also remove
4428              unused, unaliased local variables during highly
4429              optimizing compilations.  */
4430           ann = var_ann (vars);
4431           if (ann
4432               && ! ann->may_aliases
4433               && ! ann->used
4434               && ! ann->has_hidden_use
4435               && ! TREE_ADDRESSABLE (vars)
4436               && (DECL_ARTIFICIAL (vars) || optimize >= 2))
4437             {
4438               /* Remove the variable from the BLOCK structures.  */
4439               if (block)
4440                 remove_decl (vars,
4441                              (block
4442                               ? block
4443                               : DECL_INITIAL (current_function_decl)));
4444
4445               /* And splice the variable out of BIND_EXPR_VARS.  */
4446               if (prev_var)
4447                 TREE_CHAIN (prev_var) = TREE_CHAIN (vars);
4448               else
4449                 BIND_EXPR_VARS (*stmt_p) = TREE_CHAIN (vars);
4450             }
4451           else
4452             prev_var = vars;
4453         }
4454
4455       /* If there are no variables left after removing unused
4456          variables, then go ahead and remove this BIND_EXPR.  */
4457       if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
4458           && *stmt_p != DECL_SAVED_TREE (current_function_decl)
4459           && (! block
4460               || ! BLOCK_ABSTRACT_ORIGIN (block)
4461               || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
4462                   != FUNCTION_DECL)))
4463         {
4464           *stmt_p = BIND_EXPR_BODY (*stmt_p);
4465           data->repeat = true;
4466         }
4467     }
4468 }
4469
4470 static void
4471 remove_useless_stmts_and_vars_goto (tree_stmt_iterator i, tree *stmt_p,
4472                                     struct rusv_data *data)
4473 {
4474   tree_stmt_iterator tsi = i;
4475
4476   /* Step past the GOTO_EXPR statement.  */
4477   tsi_next (&tsi);
4478   if (! tsi_end_p (tsi))
4479     {
4480       /* If we are not at the end of this tree, then see if
4481          we are at the target label.  If so, then this jump
4482          is not needed.  */
4483       tree label;
4484
4485       label = tsi_stmt (tsi);
4486       if (TREE_CODE (label) == LABEL_EXPR
4487           && LABEL_EXPR_LABEL (label) == GOTO_DESTINATION (*stmt_p))
4488         {
4489           data->repeat = true;
4490           *stmt_p = build_empty_stmt ();
4491           return;
4492         }
4493     }
4494
4495   data->may_branch = true;
4496 }
4497
4498 static void
4499 remove_useless_stmts_and_vars_1 (tree *first_p, struct rusv_data *data)
4500 {
4501   tree_stmt_iterator i;
4502
4503   for (i = tsi_start (first_p); !tsi_end_p (i); tsi_next (&i))
4504     {
4505       tree *container_p = tsi_container (i);
4506       tree *stmt_p;
4507       enum tree_code code;
4508
4509       while (TREE_CODE (*container_p) == COMPOUND_EXPR)
4510         {
4511           /* If either operand of a COMPOUND_EXPR is an empty statement,
4512              then remove the empty statement and the COMPOUND_EXPR itself.  */
4513           if (IS_EMPTY_STMT (TREE_OPERAND (*container_p, 1)))
4514             *container_p = TREE_OPERAND (*container_p, 0);
4515           else if (IS_EMPTY_STMT (TREE_OPERAND (*container_p, 0)))
4516             *container_p = TREE_OPERAND (*container_p, 1);
4517           else
4518             break;
4519         }
4520
4521       /* Dive into control structures.  */
4522       stmt_p = tsi_stmt_ptr (i);
4523       code = TREE_CODE (*stmt_p);
4524       switch (code)
4525         {
4526         case COND_EXPR:
4527           remove_useless_stmts_and_vars_cond (stmt_p, data);
4528           break;
4529         case SWITCH_EXPR:
4530           remove_useless_stmts_and_vars_1 (&SWITCH_BODY (*stmt_p), data);
4531           break;
4532         case TRY_FINALLY_EXPR:
4533           remove_useless_stmts_and_vars_tf (stmt_p, data);
4534           break;
4535         case TRY_CATCH_EXPR:
4536           remove_useless_stmts_and_vars_tc (stmt_p, data);
4537           break;
4538         case BIND_EXPR:
4539           remove_useless_stmts_and_vars_bind (stmt_p, data);
4540           break;
4541         case GOTO_EXPR:
4542           remove_useless_stmts_and_vars_goto (i, stmt_p, data);
4543           break;
4544         case RETURN_EXPR:
4545           data->may_branch = true;
4546           break;
4547         case MODIFY_EXPR:
4548         case CALL_EXPR:
4549           if (tree_could_throw_p (*stmt_p))
4550             data->may_throw = true;
4551           break;
4552         default:
4553           break;
4554         }
4555
4556       /* We need to keep the tree in gimple form, so we may have to
4557          re-rationalize COMPOUND_EXPRs.  */
4558       if (TREE_CODE (*container_p) == COMPOUND_EXPR
4559           && TREE_CODE (TREE_OPERAND (*container_p, 0)) == COMPOUND_EXPR)
4560         *container_p = rationalize_compound_expr (*container_p);
4561     }
4562 }
4563
4564 void
4565 remove_useless_stmts_and_vars (tree *first_p, bool remove_unused_vars)
4566 {
4567   struct rusv_data data;
4568   do
4569     {
4570       memset (&data, 0, sizeof (data));
4571       data.remove_unused_vars = remove_unused_vars;
4572       remove_unused_vars = false;
4573
4574       remove_useless_stmts_and_vars_1 (first_p, &data);
4575     }
4576   while (data.repeat);
4577 }
4578
4579 /* Splits critical edges in the cfg.  */
4580
4581 void
4582 split_critical_edges ()
4583 {
4584   struct edge_list *el = create_edge_list ();
4585   int i;
4586   edge e;
4587
4588   for (i = 0; i < NUM_EDGES (el); i++)
4589     {
4590       e = INDEX_EDGE (el, i);
4591       if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
4592         split_edge (e);
4593     }
4594   free_edge_list (el);
4595 }