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    To handle bind_exprs and eh handling, there is kept a tree of blocks
  81    (block_tree).  Some basic blocks are entry blocks of such constructs.
  82    They must be kept unless the whole construct is to be removed.  One of
  83    the entry edges may be marked with EDGE_CONSTRUCT_ENTRY flag; it then
  84    is assumed to be the entry and it will be turned into fallthru when
  85    the constructs are recreated.  All other edges should come from
  86    inside of the construct.  */
  87
  88 /* Local declarations.  */
  89
  90 /* Initial capacity for the basic block array.  */
  91 static const int initial_cfg_capacity = 20;
  92
  93 /* Dump files and flags.  */
  94 static FILE *dump_file;         /* CFG dump file. */
  95 static int dump_flags;          /* CFG dump flags.  */
  96
  97 /* Mapping of labels to their associated blocks.  This can greatly speed up
  98    building of the CFG in code with lots of gotos.  */
  99 static varray_type label_to_block_map;
 100
 101 /* Set if we no longer want bb_for_stmt to be kept.  */
 102 int no_bb_for_stmt;
 103
 104 /* CFG statistics.  */
 105 struct cfg_stats_d
 106 {
 107   long num_merged_cases;
 108   long num_merged_labels;
 109   long num_failed_bind_expr_merges;
 110 };
 111
 112 static dominance_info pdom_info = NULL;
 113
 114 static struct cfg_stats_d cfg_stats;
 115
 116 struct block_tree *block_tree;
 117 static struct block_tree *block_tree_curr;
 118
 119 static struct obstack block_tree_obstack;
 120
 121 static struct obstack block_ann_obstack;
 122 static void *first_block_ann_obj = 0;
 123
 124 /* Basic blocks and flowgraphs.  */
 125 static void make_blocks (tree_cell);
 126 static inline void append_stmt_to_bb (tree_cell, basic_block);
 127 extern void debug_tree_chain (tree_cell);
 128 static void create_blocks_annotations (void);
 129 static void create_block_annotation (basic_block);
 130 static void free_blocks_annotations (void);
 131 static void clear_blocks_annotations (void);
 132
 133 /* Edges.  */
 134 static void make_edges (void);
 135 static void make_ctrl_stmt_edges (basic_block);
 136 static void make_exit_edges (basic_block);
 137 static void make_cond_expr_edges (basic_block);
 138 static void make_goto_expr_edges (basic_block);
 139 static void make_switch_expr_edges (basic_block);
 140 static bool tree_redirect_edge_and_branch (edge, basic_block);
 141
 142 /* Various helpers.  */
 143 static struct block_tree *block_tree_alloc (struct block_tree *);
 144 static inline bool stmt_starts_bb_p (tree, tree);
 145 static inline bool stmt_ends_bb_p (tree);
 146 static int tree_verify_flow_info (void);
 147 static basic_block tree_make_forwarder_block (basic_block, int, int, edge, int);
 148 static void replace_stmt (tree_cell, tree);
 149 static struct loops *tree_loop_optimizer_init (FILE *);
 150 static void tree_loop_optimizer_finalize (struct loops *, FILE *);
 151
 152 /* Flowgraph optimization and cleanup.  */
 153 static void remove_bb (basic_block);
 154 static void tree_merge_blocks (basic_block, basic_block);
 155 static void remove_stmt (tree_cell, basic_block, bool);
 156 static edge find_taken_edge_cond_expr (basic_block, tree);
 157 static edge find_taken_edge_switch_expr (basic_block, tree);
 158 static tree find_edge_goto (tree, edge);
 159 static bool value_matches_label (edge, tree, tree, edge *);
 160 static void tree_cleanup_edges (void);
 161 static void dump_block_tree_id (FILE *, struct block_tree *);
 162 static void assign_vars_to_scope (struct block_tree *);
 163 static void remove_superfluous_labels (void);
 164 static void thread_jumps (void);
 165 static bool tree_forwarder_block_p (basic_block);
 166 static void merge_seq_blocks (void);
 167 static tree CASE_GOTO (tree_stmt_iterator);
 168
 169 /* Location to track pending stmt for edge insertion.  */
 170 #define PENDING_STMT(e) ((tree)(e->insns))
 171
 172 /* Set the pending stmt field.  */
 173 #define SET_PENDING_STMT(e, t)  ((e->insns) = (rtx)t)
 174
 175 /* Accessors for switch statement case list.  */
 176 #define CASE_START(STMT) tsi_start (&SWITCH_BODY (STMT))
 177 #define CASE_NEXT(TSI) tsi_next (&TSI), tsi_next (&TSI)
 178 #define CASE_END_P(TSI) tsi_end_p (TSI)
 179 static tree
 180 CASE_GOTO (tree_stmt_iterator tsi)
 181 {
 182   tsi_next (&tsi);
 183   return tsi_stmt (tsi);
 184 }
 185 #define CASE_DESTINATION(TSI) (GOTO_DESTINATION (CASE_GOTO (TSI)))
 186 #define CASE_CASE(TSI) (tsi_stmt(TSI))
 187 #define CASE_EDGE(TSI) (get_stmt_ann (CASE_CASE (TSI))->case_edge)
 188
 189 /* FIXME These need to be filled in with appropriate pointers.  But this
 190    implies an ABI change in some functions.  */
 191 struct cfg_hooks tree_cfg_hooks = {
 192   tree_verify_flow_info,
 193   NULL,                         /* dump_bb  */
 194   NULL,                         /* create_basic_block  */
 195   tree_redirect_edge_and_branch, /* redirect_edge_and_branch  */
 196   NULL,                         /* redirect_edge_and_branch_force  */
 197   remove_bb,                    /* delete_basic_block  */
 198   NULL,                         /* split_block  */
 199   NULL,                         /* can_merge_blocks_p  */
 200   tree_merge_blocks,            /* merge_blocks  */
 201   tree_split_edge,              /* cfgh_split_edge  */
 202   tree_make_forwarder_block,    /* cfgh_make_forward_block  */
 203   tree_cleanup_edges,           /* cfgh_tidy_fallthru_edges  */
 204   tree_loop_optimizer_init,     /* cfgh_loop_optimizer_init  */
 205   tree_loop_optimizer_finalize  /* cfgh_loop_optimizer_finalize  */
 206 };
 207
 208 /*---------------------------------------------------------------------------
 209                               Create basic blocks
 210 ---------------------------------------------------------------------------*/
 211
 212 /* Entry point to the CFG builder for trees.  FNBODY is the body of the
 213    function to process.  */
 214
 215 void
 216 build_tree_cfg (tree_cell fnbody)
 217 {
 218   timevar_push (TV_TREE_CFG);
 219
 220   /* Register specific tree functions.  */
 221   tree_register_cfg_hooks ();
 222
 223   /* Initialize the basic block array.  */
 224   n_basic_blocks = 0;
 225   last_basic_block = 0;
 226   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
 227   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 228   no_bb_for_stmt = false;
 229
 230   /* Build a mapping of labels to their associated blocks.  */
 231   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
 232                   "label to block map");
 233
 234   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 235   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 236
 237   /* Find the basic blocks for the flowgraph.  Ignore empty functions.  */
 238   if (!fnbody)
 239     {
 240       timevar_pop (TV_TREE_CFG);
 241       return;
 242     }
 243
 244   gcc_obstack_init (&block_tree_obstack);
 245   block_tree = NULL;
 246   block_tree_curr = NULL;
 247
 248   /* Create block annotations.  */
 249   create_blocks_annotations ();
 250
 251   make_blocks (fnbody);
 252   if (block_tree_curr)
 253     abort ();
 254
 255   if (n_basic_blocks > 0)
 256     {
 257       /* Adjust the size of the array.  */
 258       VARRAY_GROW (basic_block_info, n_basic_blocks);
 259
 260       /* Create the edges of the flowgraph.  */
 261       make_edges ();
 262     }
 263
 264 #if 0
 265   {
 266     /* The loop analyzer should be initialized right after the CFG
 267        construction because some loops will need latch blocks, and these
 268        need to be added before we do anything else.  If you use this
 269        structure you'll have to ensure that optimizers don't invalidate the
 270        information gathered in the loops structure via modifications to the
 271        underlying structure: the CFG.  */
 272     struct loops *loops = loop_optimizer_init (NULL);
 273
 274     /* Once initialized, it's not really necessary to keep the loop data
 275        structures around.  They may be rescanned using flow_loops_find.  */
 276     loop_optimizer_finalize (loops, NULL);
 277   }
 278 #endif
 279
 280   timevar_pop (TV_TREE_CFG);
 281
 282   cleanup_tree_cfg (true);
 283 #if defined ENABLE_CHECKING
 284   verify_flow_info ();
 285 #endif
 286
 287   /* Debugging dumps.  */
 288   if (n_basic_blocks > 0)
 289     {
 290       /* Write the flowgraph to a dot file.  */
 291       dump_file = dump_begin (TDI_dot, &dump_flags);
 292       if (dump_file)
 293         {
 294           tree_cfg2dot (dump_file);
 295           dump_end (TDI_dot, dump_file);
 296         }
 297
 298       /* Dump a textual representation of the flowgraph.  */
 299       dump_file = dump_begin (TDI_cfg, &dump_flags);
 300       if (dump_file)
 301         {
 302           dump_tree_cfg (dump_file, dump_flags);
 303           dump_end (TDI_cfg, dump_file);
 304         }
 305     }
 306 }
 307
 308 /* Create annotations for all the basic blocks.  */
 309
 310 static void create_blocks_annotations (void)
 311 {
 312   basic_block bb;
 313   static int initialized;
 314
 315   if (!initialized)
 316     {
 317       gcc_obstack_init (&block_ann_obstack);
 318       initialized = 1;
 319     }
 320   /* Check whether TREE_ANNOTATIONS data are still allocated.  */
 321   else if (first_block_ann_obj)
 322     abort ();
 323
 324   first_block_ann_obj = obstack_alloc (&block_ann_obstack, 0);
 325
 326   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 327     create_block_annotation (bb);
 328 }
 329
 330 /* Create annotations for a single basic block.  */
 331
 332 static void create_block_annotation (basic_block bb)
 333 {
 334   /* Verify that the tree_annotations field is clear.  */
 335   if (bb->tree_annotations || !first_block_ann_obj)
 336     abort ();
 337   bb->tree_annotations = obstack_alloc (&block_ann_obstack,
 338                                         sizeof (struct bb_ann_d));
 339   memset (bb->tree_annotations, 0, sizeof (struct bb_ann_d));
 340 }
 341
 342 /* Free the annotations for all the basic blocks.  */
 343
 344 static void free_blocks_annotations (void)
 345 {
 346   if (!first_block_ann_obj)
 347     abort ();
 348   obstack_free (&block_ann_obstack, first_block_ann_obj);
 349   first_block_ann_obj = NULL;
 350
 351   clear_blocks_annotations ();
 352 }
 353
 354 /* Clear the annotations for all the basic blocks.  */
 355
 356 static void
 357 clear_blocks_annotations (void)
 358 {
 359   basic_block bb;
 360
 361   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 362     bb->tree_annotations = NULL;
 363 }
 364
 365 /* Build a flowgraph for the statements starting at the statement STMT.  */
 366
 367 static void
 368 make_blocks (tree_cell stmt)
 369 {
 370   tree_cell act, next;
 371   basic_block bb = NULL;
 372   tree prev_stmt;
 373   struct block_tree *eht;
 374
 375   if (stmt == NULL
 376       || stmt->stmt == error_mark_node)
 377     return;
 378
 379   for (act = stmt; act; act = next)
 380     {
 381       next = act->next;
 382
 383       if (act->note != TCN_STATEMENT)
 384         {
 385           if (bb && bb->end_tree)
 386             bb->end_tree->next = NULL;
 387           if (act->next)
 388             act->next->prev = NULL;
 389           bb = create_bb ();
 390
 391           switch (act->note)
 392             {
 393             case TCN_BIND:
 394               eht = block_tree_alloc (block_tree_curr);
 395               eht->entry = bb;
 396               eht->bind = act->stmt;
 397               block_tree_curr = eht;
 398               bb_ann (bb)->block = block_tree_curr;
 399               break;
 400
 401             case TCN_UNBIND:
 402               bb_ann (bb)->block = block_tree_curr;
 403               block_tree_curr = block_tree_curr->outer;
 404               break;
 405
 406             default:
 407               abort ();
 408             }
 409           bb = NULL;
 410           continue;
 411         }
 412
 413       prev_stmt = act->prev ? act->prev->stmt : NULL_TREE;
 414       if (!bb || stmt_starts_bb_p (act->stmt, prev_stmt))
 415         {
 416           if (act->prev)
 417             act->prev->next = NULL;
 418           act->prev = NULL;
 419           bb = create_bb ();
 420           bb_ann (bb)->block = block_tree_curr;
 421         }
 422
 423       append_stmt_to_bb (act, bb);
 424
 425       if (stmt_ends_bb_p (act->stmt))
 426         {
 427           bb = NULL;
 428           act->next = NULL;
 429         }
 430     }
 431 }
 432
 433 /* Add statement STMT to basic block BB and update BB's
 434    boundaries accordingly.  */
 435
 436 static inline void
 437 append_stmt_to_bb (tree_cell stmt, basic_block bb)
 438 {
 439   set_bb_for_stmt (stmt->stmt, bb);
 440
 441   /* Update the head and tail of the block.  */
 442   if (bb->head_tree == NULL)
 443     bb->head_tree = stmt;
 444
 445   bb->end_tree = stmt;
 446 }
 447
 448 /* Create and return a new basic block.  */
 449
 450 basic_block
 451 create_bb (void)
 452 {
 453   basic_block bb;
 454
 455   /* Create and initialize a new basic block.  */
 456   bb = alloc_block ();
 457   memset (bb, 0, sizeof (*bb));
 458   create_block_annotation (bb);
 459
 460   bb->index = last_basic_block;
 461   bb->flags = BB_NEW;
 462
 463   /* Add the new block to the linked list of blocks.  */
 464   link_block (bb, EXIT_BLOCK_PTR->prev_bb);
 465
 466   /* Grow the basic block array if needed.  */
 467   if ((size_t) n_basic_blocks == VARRAY_SIZE (basic_block_info))
 468     VARRAY_GROW (basic_block_info, n_basic_blocks + (n_basic_blocks + 3) / 4);
 469
 470   /* Add the newly created block to the array.  */
 471   BASIC_BLOCK (n_basic_blocks) = bb;
 472   n_basic_blocks++;
 473   last_basic_block++;
 474
 475   return bb;
 476 }
 477
 478 /*---------------------------------------------------------------------------
 479                                  Edge creation
 480 ---------------------------------------------------------------------------*/
 481
 482 /* Join all the blocks in the flowgraph.  */
 483
 484 static void
 485 make_edges (void)
 486 {
 487   basic_block bb;
 488   struct block_tree *bti;
 489   edge e;
 490
 491   /* Create an edge from entry to the first block with executable
 492      statements in it.  */
 493   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
 494
 495   /* Traverse basic block array placing edges.  */
 496   FOR_EACH_BB (bb)
 497     {
 498       tree first = first_stmt (bb);
 499       tree last = last_stmt (bb);
 500
 501       if (first)
 502         {
 503           /* Edges for statements that always alter flow control.  */
 504           if (is_ctrl_stmt (last))
 505             make_ctrl_stmt_edges (bb);
 506
 507           /* Edges for statements that sometimes alter flow control.  */
 508           if (is_ctrl_altering_stmt (last))
 509             make_exit_edges (bb);
 510         }
 511
 512       /* Finally, if no edges were created above, this is a regular
 513          basic block that only needs a fallthru edge.  */
 514       if (bb->succ == NULL)
 515         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 516     }
 517
 518   /* We do not care about fake edges, so remove any that the CFG
 519      builder inserted for completeness.  */
 520   remove_fake_edges ();
 521
 522   /* Mark special edges of constructs.  */
 523   for (bti = bti_start (); !bti_end_p (bti); bti_next (&bti))
 524     if (bti->entry)
 525       {
 526         for (e = bti->entry->pred; e; e = e->pred_next)
 527           if (e->flags & EDGE_FALLTHRU)
 528             break;
 529
 530         if (e)
 531           e->flags |= EDGE_CONSTRUCT_ENTRY;
 532       }
 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   /* If it is a special block of a block structure, remove the
 985      reference.  */
 986   if (bb_ann (bb)->block->entry == bb)
 987     bb_ann (bb)->block->entry = NULL;
 988
 989   /* Remove the basic block from the array.  */
 990   expunge_block (bb);
 991 }
 992
 993 /* Merges block B into block A.  */
 994 static void
 995 tree_merge_blocks (basic_block a, basic_block b)
 996 {
 997   block_stmt_iterator bsi;
 998   edge e;
 999   tree phi, stmt;
1000
1001   /* Ensure that b follows a.  */
1002   if (a->next_bb != b)
1003     tree_move_block_after (b, a, false);
1004
1005   if (!(a->succ->flags & EDGE_FALLTHRU))
1006     abort ();
1007
1008   if (last_stmt (a)
1009       && stmt_ends_bb_p (last_stmt (a)))
1010     abort ();
1011
1012   /* Turn phi nodes into assignments.  */
1013   bsi = bsi_last (a);
1014   for (phi = phi_nodes (b); phi; phi = TREE_CHAIN (phi))
1015     {
1016       tree src = PHI_ARG_DEF (phi, 0);
1017       tree dest = PHI_RESULT (phi);
1018
1019       if (virtual_op_p (SSA_NAME_VAR (dest)))
1020         {
1021           tree vdef;
1022
1023           stmt = build_empty_stmt ();
1024           get_stmt_ann (stmt);
1025           add_vdef (SSA_NAME_VAR (dest), stmt, NULL);
1026           vdef = VARRAY_TREE (vdef_ops (stmt), 0);
1027           VDEF_RESULT (vdef) = dest;
1028           VDEF_OP (vdef) = src;
1029         }
1030       else
1031         stmt = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
1032
1033       SSA_NAME_DEF_STMT (dest) = stmt;
1034       bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1035     }
1036
1037   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1038   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1039     {
1040       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1041         bsi_remove (&bsi);
1042       else
1043         {
1044           set_bb_for_stmt (bsi_stmt (bsi), a);
1045           bsi_next (&bsi);
1046         }
1047     }
1048
1049   remove_edge (a->succ);
1050
1051   /* Merge the chains.  */
1052   if (a->end_tree)
1053     a->end_tree->next = b->head_tree;
1054   else
1055     a->head_tree = b->head_tree;
1056   if (b->head_tree)
1057     {
1058       b->head_tree->prev = a->end_tree;
1059       a->end_tree = b->end_tree;
1060     }
1061   b->head_tree = b->end_tree = NULL;
1062
1063   /* Redirect the edges.  */
1064   a->succ = b->succ;
1065   b->succ = NULL;
1066   for (e = a->succ; e; e = e->succ_next)
1067     e->src = a;
1068
1069   if (bb_ann (b)->block->entry == b)
1070     abort ();
1071
1072   /* Remove B.  */
1073   delete_basic_block (b);
1074 }
1075
1076 /* Remove statement pointed by iterator I.  */
1077
1078 void
1079 bsi_remove (block_stmt_iterator *i)
1080 {
1081   tree_cell cell = bsi_cell (*i);
1082
1083   bsi_next (i);
1084
1085   remove_stmt (cell, i->bb, true);
1086 }
1087
1088 /* Remove statement pointed by iterator I, but leave the annotations.  */
1089
1090 void
1091 bsi_remove_leave_annot (block_stmt_iterator *i)
1092 {
1093   tree_cell cell = bsi_cell (*i);
1094
1095   bsi_next (i);
1096
1097   remove_stmt (cell, i->bb, false);
1098 }
1099
1100 /* Move the statement at FROM so it comes right after the statement at
1101    TO.  */
1102 void
1103 bsi_move_after (block_stmt_iterator from, block_stmt_iterator to)
1104 {
1105   tree stmt = bsi_stmt (from);
1106   bsi_remove_leave_annot (&from);
1107   bsi_insert_after (&to, stmt, BSI_SAME_STMT);
1108 }
1109
1110 /* Move the statement at FROM so it comes right before the statement
1111    at TO.  */
1112 void
1113 bsi_move_before (block_stmt_iterator from, block_stmt_iterator to)
1114 {
1115   tree stmt = bsi_stmt (from);
1116   bsi_remove_leave_annot (&from);
1117   bsi_insert_before (&to, stmt, BSI_SAME_STMT);
1118 }
1119
1120 /* Move the statement at FROM to the end of basic block BB, */
1121 void
1122 bsi_move_to_bb_end (block_stmt_iterator from, basic_block bb)
1123 {
1124   block_stmt_iterator last = bsi_last (bb);
1125
1126   /* Have to check bsi_end_p because it could be an empty block.  */
1127   if (!bsi_end_p (last)
1128       && is_ctrl_stmt (bsi_stmt (last)))
1129     {
1130       bsi_move_before (from, last);
1131     }
1132   else
1133     {
1134       bsi_move_after (from, last);
1135     }
1136 }
1137
1138 /* Replace the contents of a stmt with another. The replacement cannot be
1139    a COMPOUND_EXPR node, only a gimple stmt.  */
1140
1141 void
1142 bsi_replace (block_stmt_iterator bsi, tree stmt)
1143 {
1144   if (TREE_CODE (stmt) == COMPOUND_EXPR)
1145     abort ();
1146
1147   replace_stmt (bsi_cell (bsi), stmt);
1148   modify_stmt (bsi_stmt (bsi));
1149 }
1150
1151 /* Remove statement CELL in basic block BB.  Reset the annotations if
1152    REMOVE_ANNOTATIONS is true.  */
1153
1154 static void
1155 remove_stmt (tree_cell cell, basic_block bb, bool remove_annotations)
1156 {
1157   varray_type vdefs;
1158   size_t i;
1159   varray_type defs;
1160   tree stmt = cell->stmt;
1161
1162   /* If the statement is a LABEL_EXPR, remove the LABEL_DECL from
1163      the symbol table.  */
1164   if (TREE_CODE (stmt) == LABEL_EXPR)
1165     remove_decl (LABEL_EXPR_LABEL (stmt), DECL_INITIAL (current_function_decl));
1166
1167   if (remove_annotations)
1168     {
1169       /* If the statement is already in SSA form, mark all the
1170          definitions made in the statement invalid.
1171
1172          FIXME: We should probably traverse all the def-use edges
1173          originating at this statement to update each use of the
1174          definitions made here, but that is expensive and can easily
1175          be checked by every pass by checking if SSA_NAME_DEF_STMT is
1176          a nop.  */
1177       defs = def_ops (stmt);
1178       for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
1179         {
1180           tree *def_p = VARRAY_GENERIC_PTR (defs, i);
1181           if (TREE_CODE (*def_p) == SSA_NAME)
1182             SSA_NAME_DEF_STMT (*def_p) = build_empty_stmt ();
1183         }
1184
1185       vdefs = vdef_ops (stmt);
1186       for (i = 0; vdefs && i < VARRAY_ACTIVE_SIZE (vdefs); i++)
1187         {
1188           tree vdef = VDEF_RESULT (VARRAY_TREE (vdefs, i));
1189           if (TREE_CODE (vdef) == SSA_NAME)
1190             SSA_NAME_DEF_STMT (vdef) = build_empty_stmt ();
1191         }
1192
1193       stmt->common.ann = NULL;
1194     }
1195
1196   /* The RHS of a MODIFY_EXPR has an annotation for the benefit of
1197      SSA-PRE.  Make sure to remove that annotation as well.
1198
1199      We're somewhat conservative here in that we do not remove all
1200      annotations on the RHS of the MODIFY_EXPR, just those of type
1201      TREE_ANN_COMMON.  If the annotation had another type such
1202      as VAR_ANN other code may still need it and it'll get removed
1203      when we remove all the VAR_ANNs as we tear down the SSA form.  */
1204   if (TREE_CODE (stmt) == MODIFY_EXPR
1205       && TREE_OPERAND (stmt, 1)->common.ann
1206       && TREE_OPERAND (stmt, 1)->common.ann->common.type == TREE_ANN_COMMON)
1207     TREE_OPERAND (stmt, 1)->common.ann = NULL;
1208
1209   if (cell->prev)
1210     cell->prev->next = cell->next;
1211   else
1212     bb->head_tree = cell->next;
1213
1214   if (cell->next)
1215     cell->next->prev = cell->prev;
1216   else
1217     bb->end_tree = cell->prev;
1218
1219   cell->prev = cell->next = NULL;
1220 }
1221
1222 /* Given a control block BB and a constant value VAL, return the edge that
1223    will be taken out of the block.  If VAL does not match a unique edge,
1224    NULL is returned.  */
1225
1226 edge
1227 find_taken_edge (basic_block bb, tree val)
1228 {
1229   tree stmt;
1230
1231   stmt = last_stmt (bb);
1232
1233 #if defined ENABLE_CHECKING
1234   if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
1235     abort ();
1236 #endif
1237
1238   /* If VAL is not a constant, we can't determine which edge might
1239      be taken.  */
1240   if (val == NULL || !really_constant_p (val))
1241     return NULL;
1242
1243   if (TREE_CODE (stmt) == COND_EXPR)
1244     return find_taken_edge_cond_expr (bb, val);
1245
1246   if (TREE_CODE (stmt) == SWITCH_EXPR)
1247     return find_taken_edge_switch_expr (bb, val);
1248
1249   return bb->succ;
1250 }
1251
1252
1253 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1254    statement, determine which of the two edges will be taken out of the
1255    block.  Return NULL if either edge may be taken.  */
1256
1257 static edge
1258 find_taken_edge_cond_expr (basic_block bb, tree val)
1259 {
1260   bool always_false;
1261   bool always_true;
1262   edge e;
1263
1264   /* Determine which branch of the if() will be taken.  */
1265   always_false = (simple_cst_equal (val, integer_zero_node) == 1);
1266   always_true = (simple_cst_equal (val, integer_one_node) == 1);
1267
1268   /* If VAL is a constant but it can't be reduced to a 0 or a 1, then
1269      we don't really know which edge will be taken at runtime.  This
1270      may happen when comparing addresses (e.g., if (&var1 == 4))  */
1271   if (!always_false && !always_true)
1272     return NULL;
1273
1274   for (e = bb->succ; e; e = e->succ_next)
1275     if (((e->flags & EDGE_TRUE_VALUE) && always_true)
1276         || ((e->flags & EDGE_FALSE_VALUE) && always_false))
1277       return e;
1278
1279   return NULL;
1280 }
1281
1282
1283 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
1284    statement, determine which edge will be taken out of the block.  Return
1285    NULL if any edge may be taken.  */
1286
1287 static edge
1288 find_taken_edge_switch_expr (basic_block bb, tree val)
1289 {
1290   edge e, default_edge;
1291   tree case_label;
1292   tree_stmt_iterator case_entry;
1293
1294   /* See if the switch() value matches one of the case labels.  */
1295   default_edge = NULL;
1296   for (case_entry = CASE_START (last_stmt (bb));
1297        !CASE_END_P (case_entry);
1298        CASE_NEXT (case_entry))
1299     {
1300       e = CASE_EDGE (case_entry);
1301       case_label = CASE_CASE (case_entry);
1302
1303       if (value_matches_label (e, val, case_label, &default_edge))
1304         return e;
1305     }
1306
1307   /* If no case exists for the value used in the switch(), we use the
1308      default label.  */
1309   if (!default_edge)
1310     abort ();
1311
1312   return default_edge;
1313 }
1314
1315 /* Return true if VAL matches the LABEL.  If one of the LABEL is the DEFAULT
1316    label, DEST_EDGE is stored into *DEFAULT_EDGE_P to indicate that this edge
1317    goes to the DEFAULT label.  This is used by the caller when no other case
1318    label is found to match VAL.  */
1319
1320 static bool
1321 value_matches_label (edge dest_edge, tree val, tree label, edge *default_edge_p)
1322 {
1323   if (TREE_CODE (label) != CASE_LABEL_EXPR)
1324     abort ();
1325
1326   /* Remember that we found a default label, just in case no other
1327      label matches the switch() value.  */
1328   if (CASE_LOW (label) == NULL_TREE)
1329     *default_edge_p = dest_edge;
1330   else
1331     {
1332       /* If we found a match, we are done.  */
1333       tree label_val = CASE_LOW (label);
1334       if (simple_cst_equal (label_val, val) == 1)
1335         return true;
1336     }
1337
1338   return false;
1339 }
1340
1341 /*---------------------------------------------------------------------------
1342                               Debugging functions
1343 ---------------------------------------------------------------------------*/
1344
1345 /* Dump a basic block to a file.  */
1346
1347 void
1348 dump_tree_bb (FILE *outf, const char *prefix, basic_block bb, int indent)
1349 {
1350   edge e;
1351   char *s_indent;
1352   block_stmt_iterator si;
1353   tree phi;
1354
1355   s_indent = (char *) alloca ((size_t) indent + 1);
1356   memset ((void *) s_indent, ' ', (size_t) indent);
1357   s_indent[indent] = '\0';
1358
1359   fprintf (outf, "%s%sBLOCK       %d\n", s_indent, prefix, bb->index);
1360
1361   fprintf (outf, "%s%sPRED:      ", s_indent, prefix);
1362   for (e = bb->pred; e; e = e->pred_next)
1363     dump_edge_info (outf, e, 0);
1364   putc ('\n', outf);
1365
1366   fprintf (outf, "%s%sSUCC:      ", s_indent, prefix);
1367   for (e = bb->succ; e; e = e->succ_next)
1368     dump_edge_info (outf, e, 1);
1369   putc ('\n', outf);
1370
1371   fprintf (outf, "%s%sLOOP DEPTH: %d\n", s_indent, prefix, bb->loop_depth);
1372
1373   fprintf (outf, "%s%sNEXT BLOCK: ", s_indent, prefix);
1374   if (bb->next_bb)
1375     fprintf (outf, "%d\n", bb->next_bb->index);
1376   else
1377     fprintf (outf, "nil\n");
1378
1379   fprintf (outf, "%s%sPREV BLOCK: ", s_indent, prefix);
1380   if (bb->prev_bb)
1381     fprintf (outf, "%d\n", bb->prev_bb->index);
1382   else
1383     fprintf (outf, "nil\n");
1384
1385   if (bb->tree_annotations)
1386     for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1387       {
1388         fprintf (outf, "%s%s# ", s_indent, prefix);
1389         print_generic_stmt (outf, phi, 0);
1390       }
1391
1392   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1393     {
1394       fprintf (outf, "%s%s%d  ", s_indent, prefix, get_lineno (bsi_stmt (si)));
1395       print_generic_stmt (outf, bsi_stmt (si), 0);
1396       fprintf (outf, "\n");
1397     }
1398 }
1399
1400
1401 /* Dump a basic block on stderr.  */
1402
1403 void
1404 debug_tree_bb (basic_block bb)
1405 {
1406   dump_tree_bb (stderr, "", bb, 0);
1407 }
1408
1409 /* Dump a basic block N on stderr.  */
1410
1411 basic_block
1412 debug_tree_bb_n (int n)
1413 {
1414   debug_tree_bb (BASIC_BLOCK (n));
1415   return BASIC_BLOCK (n);
1416 }
1417
1418 /* Dump the CFG on stderr.
1419
1420    FLAGS are the same used by the tree dumping functions
1421    (see TDF_* in tree.h).  */
1422
1423 void
1424 debug_tree_cfg (int flags)
1425 {
1426   dump_tree_cfg (stderr, flags);
1427 }
1428
1429
1430 /* Dump the program showing basic block boundaries on the given FILE.
1431
1432    FLAGS are the same used by the tree dumping functions (see TDF_* in
1433    tree.h).  */
1434
1435 void
1436 dump_tree_cfg (FILE *file, int flags)
1437 {
1438   basic_block bb;
1439
1440   if (flags & TDF_DETAILS)
1441     {
1442       const char *funcname
1443         = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
1444
1445       fputc ('\n', file);
1446       fprintf (file, ";; Function %s\n\n", funcname);
1447       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n",
1448                n_basic_blocks, n_edges, last_basic_block);
1449
1450       FOR_EACH_BB (bb)
1451         {
1452           dump_tree_bb (file, "", bb, 0);
1453           fputc ('\n', file);
1454         }
1455     }
1456
1457   if (flags & TDF_STATS)
1458     dump_cfg_stats (file);
1459
1460   if (n_basic_blocks > 0)
1461     dump_cfg_function_to_file (current_function_decl, file, flags|TDF_BLOCKS);
1462 }
1463
1464 /* Dumps function FN to FILE, with details given by FLAGS.  Function body is
1465    taken from cfg.  */
1466 void
1467 dump_cfg_function_to_file (tree fn, FILE *file, int flags)
1468 {
1469   basic_block bb;
1470   tree arg, phi;
1471   block_stmt_iterator si;
1472   edge e;
1473   int show_bb_headers = flags & TDF_BLOCKS;
1474
1475   flags &= ~TDF_BLOCKS;
1476
1477   fprintf (file, "\n;; Function %s",
1478             (*lang_hooks.decl_printable_name) (fn, 2));
1479   fprintf (file, " (%s)\n",
1480             IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fn)));
1481   fprintf (file, "\n");
1482
1483   if (show_bb_headers)
1484     {
1485       fprintf (file, "\n# Block tree:\n");
1486       dump_block_tree (file, 3, block_tree);
1487       fprintf (file, "\n");
1488     }
1489
1490   fprintf (file, "%s (", (*lang_hooks.decl_printable_name) (fn, 2));
1491
1492   arg = DECL_ARGUMENTS (fn);
1493   while (arg)
1494     {
1495       print_generic_expr (file, arg, 0);
1496       if (TREE_CHAIN (arg))
1497         fprintf (file, ", ");
1498       arg = TREE_CHAIN (arg);
1499     }
1500   fprintf (file, ")\n{\n");
1501
1502   FOR_EACH_BB (bb)
1503     {
1504       if (show_bb_headers)
1505         {
1506           fprintf (file, "# BLOCK %d\n# CONSTRUCT ", bb->index);
1507           dump_block_tree_id (file, bb_ann (bb)->block);
1508           if (bb_ann (bb)->block->entry == bb)
1509             fprintf (file, "(entry)");
1510           fprintf (file, "\n# PRED");
1511           for (e = bb->pred; e; e = e->pred_next)
1512             dump_edge_info (file, e, 0);
1513           putc ('\n', file);
1514         }
1515       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1516         {
1517           fprintf (file, "\t# ");
1518           print_generic_stmt (file, phi, flags);
1519           fprintf (file, "\n");
1520         }
1521
1522       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1523         {
1524           fprintf (file, "%d\t", get_lineno (bsi_stmt (si)));
1525           print_generic_stmt (file, bsi_stmt (si), flags & ~TDF_VOPS);
1526           fprintf (file, "\n");
1527         }
1528
1529       if (show_bb_headers)
1530         {
1531           fprintf (file, "# SUCC");
1532           for (e = bb->succ; e; e = e->succ_next)
1533             dump_edge_info (file, e, 1);
1534           fprintf (file, "\n\n");
1535         }
1536     }
1537   fprintf (file, "}\n\n");
1538 }
1539
1540 /* Dump CFG statistics on FILE.  */
1541
1542 void
1543 dump_cfg_stats (FILE *file)
1544 {
1545   static long max_num_merged_cases = 0;
1546   static long max_num_merged_labels = 0;
1547   unsigned long size, total = 0;
1548   long n_edges;
1549   basic_block bb;
1550   const char * const fmt_str   = "%-30s%-13s%12s\n";
1551   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
1552   const char * const fmt_str_3 = "%-43s%11lu%c\n";
1553   const char *funcname
1554     = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
1555
1556
1557   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
1558
1559   fprintf (file, "---------------------------------------------------------\n");
1560   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
1561   fprintf (file, fmt_str, "", "  instances  ", "used ");
1562   fprintf (file, "---------------------------------------------------------\n");
1563
1564   size = n_basic_blocks * sizeof (struct basic_block_def);
1565   total += size;
1566   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks, SCALE (size),
1567            LABEL (size));
1568
1569   n_edges = 0;
1570   FOR_EACH_BB (bb)
1571     {
1572       edge e;
1573       for (e = bb->succ; e; e = e->succ_next)
1574         n_edges++;
1575     }
1576   size = n_edges * sizeof (struct edge_def);
1577   total += size;
1578   fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
1579
1580   size = n_basic_blocks * sizeof (struct bb_ann_d);
1581   total += size;
1582   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
1583            SCALE (size), LABEL (size));
1584
1585   fprintf (file, "---------------------------------------------------------\n");
1586   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
1587            LABEL (total));
1588   fprintf (file, "---------------------------------------------------------\n");
1589   fprintf (file, "\n");
1590
1591   if (cfg_stats.num_merged_labels > max_num_merged_labels)
1592     max_num_merged_labels = cfg_stats.num_merged_labels;
1593
1594   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
1595            cfg_stats.num_merged_labels, max_num_merged_labels);
1596
1597
1598   if (cfg_stats.num_merged_cases > max_num_merged_cases)
1599     max_num_merged_cases = cfg_stats.num_merged_cases;
1600
1601   fprintf (file, "Coalesced case label blocks: %ld (Max so far: %ld)\n",
1602            cfg_stats.num_merged_cases, max_num_merged_cases);
1603
1604   fprintf (file, "Number of unnecessary blocks created due to lexical scopes: %ld (%.0f%%)\n",
1605            cfg_stats.num_failed_bind_expr_merges,
1606            PERCENT (cfg_stats.num_failed_bind_expr_merges, n_basic_blocks));
1607
1608   fprintf (file, "\n");
1609 }
1610
1611
1612 /* Dump CFG statistics on stderr.  */
1613
1614 void
1615 debug_cfg_stats (void)
1616 {
1617   dump_cfg_stats (stderr);
1618 }
1619
1620
1621 /* Dump the flowgraph to a .dot FILE.  */
1622
1623 void
1624 tree_cfg2dot (FILE *file)
1625 {
1626   edge e;
1627   basic_block bb;
1628   const char *funcname
1629     = (*lang_hooks.decl_printable_name) (current_function_decl, 2);
1630
1631   /* Write the file header.  */
1632   fprintf (file, "digraph %s\n{\n", funcname);
1633
1634   /* Write blocks and edges.  */
1635   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
1636     {
1637       fprintf (file, "\tENTRY -> %d", e->dest->index);
1638
1639       if (e->flags & EDGE_FAKE)
1640         fprintf (file, " [weight=0, style=dotted]");
1641
1642       fprintf (file, ";\n");
1643     }
1644   fputc ('\n', file);
1645
1646   FOR_EACH_BB (bb)
1647     {
1648       enum tree_code head_code, end_code;
1649       const char *head_name, *end_name;
1650       int head_line = 0;
1651       int end_line = 0;
1652       tree first = first_stmt (bb);
1653       tree last = last_stmt (bb);
1654
1655       if (first)
1656         {
1657           head_code = TREE_CODE (first);
1658           head_name = tree_code_name[head_code];
1659           head_line = get_lineno (bb->head_tree->stmt);
1660         }
1661       else
1662         head_name = "no-statement";
1663
1664       if (last)
1665         {
1666           end_code = TREE_CODE (last);
1667           end_name = tree_code_name[end_code];
1668           end_line = get_lineno (bb->end_tree->stmt);
1669         }
1670       else
1671         end_name = "no-statement";
1672
1673
1674       fprintf (file, "\t%d [label=\"#%d\\n%s (%d)\\n%s (%d)\"];\n",
1675                bb->index, bb->index, head_name, head_line, end_name,
1676                end_line);
1677
1678       for (e = bb->succ; e; e = e->succ_next)
1679         {
1680           if (e->dest == EXIT_BLOCK_PTR)
1681             fprintf (file, "\t%d -> EXIT", bb->index);
1682           else
1683             fprintf (file, "\t%d -> %d", bb->index, e->dest->index);
1684
1685           if (e->flags & EDGE_FAKE)
1686             fprintf (file, " [weight=0, style=dotted]");
1687
1688           fprintf (file, ";\n");
1689         }
1690
1691       if (bb->next_bb != EXIT_BLOCK_PTR)
1692         fputc ('\n', file);
1693     }
1694
1695   fputs ("}\n\n", file);
1696 }
1697
1698
1699
1700 /*---------------------------------------------------------------------------
1701                              Miscellaneous helpers
1702 ---------------------------------------------------------------------------*/
1703
1704
1705 /* Return true if T represents a stmt that always transfers control.  */
1706
1707 bool
1708 is_ctrl_stmt (tree t)
1709 {
1710   return (TREE_CODE (t) == COND_EXPR
1711           || TREE_CODE (t) == SWITCH_EXPR
1712           || TREE_CODE (t) == GOTO_EXPR
1713           || TREE_CODE (t) == RETURN_EXPR
1714           || TREE_CODE (t) == RESX_EXPR);
1715 }
1716
1717 /* Return true if T is a stmt that may or may not alter the flow of control
1718    (i.e., a call to a non-returning function).  */
1719
1720 bool
1721 is_ctrl_altering_stmt (tree t)
1722 {
1723   tree call = t;
1724
1725 #if defined ENABLE_CHECKING
1726   if (t == NULL)
1727     abort ();
1728 #endif
1729
1730   switch (TREE_CODE (t))
1731     {
1732     case MODIFY_EXPR:
1733       /* A MODIFY_EXPR with a rhs of a call has the characteristics
1734          of the call.  */
1735       call = TREE_OPERAND (t, 1);
1736       if (TREE_CODE (call) != CALL_EXPR)
1737         break;
1738       /* FALLTHRU */
1739
1740     case CALL_EXPR:
1741       /* A CALL_EXPR alters flow control if the current function has
1742          nonlocal labels.  */
1743       if (FUNCTION_RECEIVES_NONLOCAL_GOTO (current_function_decl))
1744         return true;
1745
1746       /* A CALL_EXPR also alters flow control if it does not return.  */
1747       if (call_expr_flags (call) & (ECF_NORETURN | ECF_LONGJMP))
1748         return true;
1749       break;
1750
1751     default:
1752       return false;
1753     }
1754
1755   /* If a statement can throw, it alters control flow.  */
1756   return tree_can_throw_internal (t);
1757 }
1758
1759
1760 /* Return flags associated with the function called by T (see ECF_* in
1761    tree.h)  */
1762
1763 int
1764 call_expr_flags (tree t)
1765 {
1766   int flags;
1767   tree decl = get_callee_fndecl (t);
1768
1769   if (decl)
1770     flags = flags_from_decl_or_type (decl);
1771   else
1772     {
1773       t = TREE_OPERAND (t, 0);
1774       flags = flags_from_decl_or_type (TREE_TYPE (TREE_TYPE (t)));
1775     }
1776
1777   return flags;
1778 }
1779
1780
1781 /* Return true if T is a computed goto.  */
1782
1783 bool
1784 is_computed_goto (tree t)
1785 {
1786   return (TREE_CODE (t) == GOTO_EXPR
1787           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
1788 }
1789
1790 /* Allocates a block_tree node with outer node OUTER.  */
1791 static struct block_tree *
1792 block_tree_alloc (struct block_tree *outer)
1793 {
1794   struct block_tree *nw = obstack_alloc (&block_tree_obstack,
1795                                          sizeof (struct block_tree));
1796
1797   nw->outer = outer;
1798   nw->subtree = NULL;
1799   nw->entry = NULL;
1800   nw->bind = NULL_TREE;
1801
1802   if (outer)
1803     {
1804       nw->next = outer->subtree;
1805       outer->subtree = nw;
1806       nw->level = outer->level + 1;
1807     }
1808   else
1809     {
1810       block_tree = nw;
1811       nw->next = NULL;
1812       nw->level = 0;
1813     }
1814
1815   return nw;
1816 }
1817
1818 /* Releases the block_tree obstack.  */
1819 void
1820 block_tree_free ()
1821 {
1822   obstack_free (&block_tree_obstack, NULL);
1823 }
1824
1825 /* Return true if T should start a new basic block.  PREV_T is the
1826    statement preceding T.  It is used when T is a label or a case label.
1827    Labels should only start a new basic block if their previous statement
1828    wasn't a label.  Otherwise, sequence of labels would generate
1829    unnecessary basic blocks that only contain a single label.  */
1830
1831 static inline bool
1832 stmt_starts_bb_p (tree t, tree prev_t)
1833 {
1834   enum tree_code code;
1835
1836   if (t == NULL_TREE)
1837     return false;
1838
1839   /* LABEL_EXPRs and CASE_LABEL_EXPRs start a new basic block only if the
1840      preceding statement wasn't a label of the same type.  This prevents
1841      the creation of consecutive blocks that have nothing but a single
1842      label.  */
1843   code = TREE_CODE (t);
1844   if (code == LABEL_EXPR || code == CASE_LABEL_EXPR)
1845     {
1846       /* Nonlocal and computed GOTO targets always start a new block.  */
1847       if (code == LABEL_EXPR
1848           && (NONLOCAL_LABEL (LABEL_EXPR_LABEL (t))
1849               || FORCED_LABEL (LABEL_EXPR_LABEL (t))))
1850         return true;
1851
1852       if (prev_t && TREE_CODE (prev_t) == code)
1853         {
1854           if (code == LABEL_EXPR)
1855             cfg_stats.num_merged_labels++;
1856           else
1857             cfg_stats.num_merged_cases++;
1858
1859           return false;
1860         }
1861       else
1862         return true;
1863     }
1864
1865   return false;
1866 }
1867
1868
1869 /* Return true if T should end a basic block.  */
1870
1871 static inline bool
1872 stmt_ends_bb_p (tree t)
1873 {
1874   return (is_ctrl_stmt (t)
1875           || is_ctrl_altering_stmt (t));
1876 }
1877
1878
1879 /* Remove all the blocks and edges that make up the flowgraph.  */
1880
1881 void
1882 delete_tree_cfg (void)
1883 {
1884   if (n_basic_blocks > 0)
1885     free_blocks_annotations ();
1886
1887   free_basic_block_vars (0);
1888 }
1889
1890
1891 /* Return the first statement in basic block BB, stripped of any NOP
1892    containers.  */
1893
1894 tree
1895 first_stmt (basic_block bb)
1896 {
1897   block_stmt_iterator i;
1898
1899   if (bb == ENTRY_BLOCK_PTR
1900       || bb == EXIT_BLOCK_PTR)
1901     return NULL_TREE;
1902
1903   i = bsi_start (bb);
1904   return (!bsi_end_p (i)) ? bsi_stmt (i) : NULL_TREE;
1905 }
1906
1907 /* Finds a label in basic block BB or creates one if it does not exit.  */
1908 tree
1909 tree_block_label (basic_block bb)
1910 {
1911   tree label = first_stmt (bb);
1912
1913   if (!label || TREE_CODE (label) != LABEL_EXPR)
1914     {
1915       block_stmt_iterator first = bsi_start (bb);
1916       tree label_decl = build_new_label ();
1917
1918       label = build1 (LABEL_EXPR, void_type_node, label_decl);
1919       bsi_insert_before (&first, label, BSI_NEW_STMT);
1920     }
1921
1922   return LABEL_EXPR_LABEL (label);
1923 }
1924
1925 /* Return the last statement in basic block BB.  */
1926
1927 tree
1928 last_stmt (basic_block bb)
1929 {
1930   block_stmt_iterator b;
1931
1932   if (bb == ENTRY_BLOCK_PTR
1933       || bb == EXIT_BLOCK_PTR)
1934     return NULL_TREE;
1935
1936   b = bsi_last (bb);
1937   return (!bsi_end_p (b)) ? bsi_stmt (b) : NULL_TREE;
1938 }
1939
1940 /* Return the pointer to last statement in basic block BB.  */
1941
1942 tree *
1943 last_stmt_ptr (basic_block bb)
1944 {
1945   block_stmt_iterator b;
1946
1947   b = bsi_last (bb);
1948   return (!bsi_end_p (b)) ? bsi_stmt_ptr (b) : NULL;
1949 }
1950
1951 /* Similar to tsi_start() but initializes the iterator at the first
1952    statement in basic block BB which isn't an empty statement node.
1953
1954    NULL is returned if there are no such statements.  */
1955
1956 block_stmt_iterator
1957 bsi_start (basic_block bb)
1958 {
1959   block_stmt_iterator i;
1960
1961   i.bb = bb;
1962   if (bb && bb->index != INVALID_BLOCK)
1963     i.curr_stmt = bb->head_tree;
1964   else
1965     i.curr_stmt = NULL;
1966
1967   return i;
1968 }
1969
1970 /* This routine will return a block iterator which points to the last stmt in
1971    a basic block, if there is one.  */
1972
1973 block_stmt_iterator
1974 bsi_last (basic_block bb)
1975 {
1976   block_stmt_iterator i;
1977
1978   i.bb = bb;
1979   if (bb && bb->index != INVALID_BLOCK)
1980     i.curr_stmt = bb->end_tree;
1981   else
1982     i.curr_stmt = NULL;
1983
1984   return i;
1985 }
1986
1987
1988 /* Find the previous iterator value.  */
1989
1990 void
1991 bsi_prev (block_stmt_iterator *i)
1992 {
1993   i->curr_stmt = i->curr_stmt->prev;
1994 }
1995
1996 /* Insert statement T into basic block BB.  */
1997
1998 void
1999 set_bb_for_stmt (tree t, basic_block bb)
2000 {
2001   stmt_ann_t ann;
2002
2003   if (no_bb_for_stmt)
2004     return;
2005
2006   /* If the statement is a label, add the label to block-to-labels map
2007      so that we can speed up edge creation for GOTO_EXPRs.  */
2008   if (TREE_CODE (t) == LABEL_EXPR)
2009     {
2010       LABEL_DECL_INDEX (LABEL_EXPR_LABEL (t))
2011               = VARRAY_ACTIVE_SIZE (label_to_block_map);
2012       VARRAY_PUSH_BB (label_to_block_map, bb);
2013     }
2014
2015   ann = get_stmt_ann (t);
2016   ann->bb = bb;
2017 }
2018
2019
2020 /* Insert routines.  */
2021
2022 /* This routine inserts a stmt after the stmt iterator passed in.
2023    The final parameter determines whether the statement iterator
2024    is updated to point to the new stmt, or left pointing to the original
2025    statement.  */
2026
2027 void
2028 bsi_insert_after (block_stmt_iterator *curr_bsi, tree t,
2029                   enum bsi_iterator_update mode)
2030 {
2031   basic_block bb = curr_bsi->bb;
2032   tree_cell curr, nw = ggc_alloc (sizeof (struct tree_container));
2033
2034   set_bb_for_stmt (t, bb);
2035   curr = bsi_cell (*curr_bsi);
2036   nw->stmt = t;
2037
2038   if (!curr)
2039     {
2040       /* Inserting after end of bb.  Only valid if the bb is empty.  */
2041       if (bb->head_tree)
2042         abort ();
2043
2044       nw->prev = nw->next = NULL;
2045       bb->head_tree = bb->end_tree = nw;
2046       *curr_bsi = bsi_start (bb);
2047       return;
2048     }
2049
2050   nw->next = curr->next;
2051   if (!curr->next)
2052     bb->end_tree = nw;
2053   else
2054     nw->next->prev = nw;
2055   curr->next = nw;
2056   nw->prev = curr;
2057
2058   if (mode == BSI_NEW_STMT)
2059     bsi_next (curr_bsi);
2060
2061   /* Now update the required SSA bits.  */
2062   modify_stmt (t);
2063
2064   return;
2065 }
2066
2067
2068 /* This routine inserts a stmt before the stmt iterator passed in.
2069    The final parameter determines whether the statement iterator
2070    is updated to point to the new stmt, or left pointing to the original
2071    statement.  */
2072 void
2073 bsi_insert_before (block_stmt_iterator *curr_bsi, tree t,
2074                    enum bsi_iterator_update mode)
2075 {
2076   basic_block bb = curr_bsi->bb;
2077   tree_cell curr, nw = xmalloc (sizeof (struct tree_container));
2078
2079   set_bb_for_stmt (t, bb);
2080   curr = bsi_cell (*curr_bsi);
2081   nw->stmt = t;
2082
2083   if (!curr)
2084     {
2085       /* Inserting before start of bb.  Only valid if the bb is empty.  */
2086       if (bb->head_tree)
2087         abort ();
2088
2089       nw->prev = nw->next = NULL;
2090       bb->head_tree = bb->end_tree = nw;
2091       *curr_bsi = bsi_start (bb);
2092       return;
2093     }
2094
2095   nw->prev = curr->prev;
2096   if (!nw->prev)
2097     bb->head_tree = nw;
2098   else
2099     nw->prev->next = nw;
2100   curr->prev = nw;
2101   nw->next = curr;
2102
2103   if (mode == BSI_NEW_STMT)
2104     bsi_prev (curr_bsi);
2105
2106   /* Now update the required SSA bits.  */
2107   modify_stmt (t);
2108 }
2109
2110 /* This routine inserts a stmt on an edge. Every attempt is made to place the
2111    stmt in an existing basic block, but sometimes that isn't possible.  When
2112    it isn't possible, a new basic block is created, edges updated, and the
2113    stmt is added to the new block.  An iterator to the new stmt is returned.
2114    If a pointer to a BSI is passed in, and the stmt is inserted before or after
2115    an existing stmt in a block, old_bsi will be returned with an iterator for
2116    that stmt (The equivalent of BSI_SAME_STMT on an insert_before or after.
2117    If a created_block is passed in, and the edge is split, the new block is
2118    returned through this parameter.  */
2119
2120 block_stmt_iterator
2121 bsi_insert_on_edge_immediate (edge e, tree stmt, block_stmt_iterator *old_bsi,
2122                               basic_block *created_block)
2123 {
2124   basic_block src, dest, new_bb;
2125   block_stmt_iterator bsi, tmp;
2126   int num_exit, num_entry;
2127   tree last;
2128   bb_ann_t ann;
2129   edge e2;
2130
2131   if (old_bsi)
2132     old_bsi->curr_stmt = NULL;
2133   if (created_block)
2134     *created_block = (basic_block)NULL;
2135
2136   src = e->src;
2137   dest = e->dest;
2138
2139   /* Cannot insert on an abnormal edge.  */
2140   if (e->flags & EDGE_ABNORMAL)
2141     abort ();
2142
2143   /* No immediate edge insertion if there are already pending inserts.  */
2144   if (PENDING_STMT (e))
2145     abort ();
2146
2147   num_exit = num_entry = 0;
2148
2149   for (e2 = src->succ; e2; e2 = e2->succ_next)
2150     num_exit++;
2151
2152   for (e2 = dest->pred; e2; e2 = e2->pred_next)
2153     num_entry++;
2154
2155   /* If src is a single-exit block, and it isn't the entry block, then
2156      insert at the end of the block, if we can.  */
2157
2158   if (num_exit == 1 && src != ENTRY_BLOCK_PTR)
2159     {
2160       bsi = bsi_last (src);
2161       /* If it is an empty block, simply insert after this bsi, and the new stmt
2162          will become the only stmt in the block.  */
2163       if (bsi_end_p (bsi))
2164         {
2165           bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2166           return bsi;
2167         }
2168       last = bsi_stmt (bsi);
2169
2170       /* If this is a fallthrough edge, then we can simply append this stmt
2171          to the basic block.  */
2172       if (e->flags & EDGE_FALLTHRU)
2173         {
2174 #ifdef ENABLE_CHECKING
2175           /* Control statement edges should not be marked FALLTHRU.  */
2176           if (is_ctrl_stmt (bsi_stmt (bsi)))
2177             abort ();
2178 #endif
2179
2180           /* If the last stmt isn't a control altering stmt, then we can simply
2181              append this stmt to the basic block. This should mean the edge is
2182              a fallthrough edge.  */
2183
2184           if (!is_ctrl_stmt (last) && !is_ctrl_altering_stmt (last))
2185             {
2186               bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
2187               if (old_bsi)
2188                 *old_bsi = bsi;
2189               bsi_next (&bsi);
2190               return bsi;
2191             }
2192
2193           /* If the last stmt is a GOTO, the we can simply insert before it.  */
2194           if (TREE_CODE (last) == GOTO_EXPR)
2195             {
2196               bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2197               if (old_bsi)
2198                 {
2199                   *old_bsi = bsi;
2200                   bsi_next (old_bsi);
2201                 }
2202               return bsi;
2203             }
2204         }
2205     }
2206
2207   /* If dest is a single entry destination, and it isn't the exit block, the new
2208      stmt can be inserted at the beginning of the destination block.  */
2209
2210   if (num_entry == 1 && dest != EXIT_BLOCK_PTR)
2211     {
2212       bsi = bsi_start (dest);
2213       /* If it is an empty block, simply insert after this bsi, and the new stmt
2214          will become the only stmt in the block.  */
2215       if (bsi_end_p (bsi))
2216         {
2217           bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2218           return bsi;
2219         }
2220
2221       /* Skip any labels, and insert before the first non-label.  */
2222       for (tmp = bsi, bsi_next (&bsi); !bsi_end_p (bsi); bsi_next (&bsi))
2223         {
2224           if (!is_label_stmt (bsi_stmt (bsi)))
2225             {
2226               bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2227               if (old_bsi)
2228                 {
2229                   *old_bsi = bsi;
2230                   bsi_next (old_bsi);
2231                 }
2232               return bsi;
2233             }
2234           tmp = bsi;
2235         }
2236
2237       /* If this point is reached, then the block consists of nothing but
2238          labels, and tmp points to the last one. Insert after it.  */
2239       bsi_insert_after (&tmp, stmt, BSI_SAME_STMT);
2240       if (old_bsi)
2241         *old_bsi = tmp;
2242       bsi_next (&tmp);
2243       return tmp;
2244     }
2245
2246   /* Otherwise, create a new basic block, and split this edge.  */
2247   new_bb = split_edge (e);
2248   ann = bb_ann (new_bb);
2249
2250   if (created_block)
2251     *created_block = new_bb;
2252
2253   bsi = bsi_start (new_bb);
2254   if (bsi_stmt (bsi)
2255       && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
2256     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2257   else
2258     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2259
2260   return bsi;
2261 }
2262
2263 /* This routine will commit all pending edge insertions, creating any new
2264    basic blocks which are necessary. The number of edges which were inserted
2265    is returned.  If the flag update_annotations is true, then new bitmaps are
2266    created for the dominator children, and they are updated.  If specified,
2267    new_blocks returned a count of the number of new basic blocks which were
2268    created.  */
2269
2270 int
2271 bsi_commit_edge_inserts (int update_annotations, int *new_blocks)
2272 {
2273   basic_block bb;
2274   block_stmt_iterator bsi, ret;
2275   edge e;
2276   tree stmt, next_stmt;
2277   int blocks, count = 0;
2278
2279   blocks = n_basic_blocks;
2280
2281   FOR_EACH_BB (bb)
2282     {
2283       for (e = bb->succ; e; e = e->succ_next)
2284         if (PENDING_STMT (e))
2285           {
2286             stmt = PENDING_STMT (e);
2287             SET_PENDING_STMT (e, NULL_TREE);
2288             next_stmt = TREE_CHAIN (stmt);
2289             /* The first insert will create a new basic block if needed.  */
2290             ret = bsi = bsi_insert_on_edge_immediate (e, stmt, NULL, NULL);
2291             count++;
2292             stmt = next_stmt;
2293             for ( ; stmt; stmt = next_stmt)
2294               {
2295                 /* All further inserts can simply follow the first one.  */
2296                 next_stmt = TREE_CHAIN (stmt);
2297                 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2298                 count++;
2299               }
2300
2301           }
2302     }
2303
2304   if (new_blocks)
2305     *new_blocks = n_basic_blocks - blocks;
2306
2307   /* Expand arrays if we created new blocks and need to update them.  */
2308   if (update_annotations && blocks != n_basic_blocks)
2309     {
2310       abort ();
2311       /* TODO. Unimplemented at the moment.  */
2312     }
2313
2314   return count;
2315 }
2316
2317 /* This routine adds a stmt to the pending list on an edge. No actual
2318    insertion is made until a call to bsi_commit_edge_inserts () is made.  */
2319
2320 void
2321 bsi_insert_on_edge (edge e, tree stmt)
2322 {
2323   tree t;
2324
2325   t = PENDING_STMT (e);
2326   if (!t)
2327     SET_PENDING_STMT (e, stmt);
2328   else
2329     {
2330       for ( ; TREE_CHAIN (t); t = TREE_CHAIN (t))
2331         continue;
2332       TREE_CHAIN (t) = stmt;
2333       TREE_CHAIN (stmt) = NULL_TREE;
2334     }
2335
2336 }
2337
2338 /* Replace the statement TP1 with the statement TP2.  */
2339
2340 static void
2341 replace_stmt (tree_cell tp1, tree t)
2342 {
2343   basic_block bb;
2344
2345   /* Relocate annotations for the replacement statement.  */
2346   SET_EXPR_LOCUS (t, EXPR_LOCUS (tp1->stmt));
2347   bb = bb_for_stmt (tp1->stmt);
2348   tp1->stmt = t;
2349   set_bb_for_stmt (t, bb);
2350 }
2351
2352 /*---------------------------------------------------------------------------
2353             Tree specific functions for the cfg loop optimizer
2354 ---------------------------------------------------------------------------*/
2355
2356 /* Split a (typically critical) edge.  Return the new block.
2357    Abort on abnormal edges.  */
2358
2359 basic_block
2360 tree_split_edge (edge edge_in)
2361 {
2362   basic_block new_bb, dest;
2363   edge new_edge;
2364   tree phi;
2365   int i, num_elem;
2366
2367   /* Abnormal edges cannot be split.  */
2368   if (edge_in->flags & EDGE_ABNORMAL)
2369     abort ();
2370
2371   dest = edge_in->dest;
2372   new_bb = create_bb ();
2373   bb_ann (new_bb)->block = bb_ann (edge_in->src)->block;
2374
2375   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2376   /* Find all the PHI arguments on the original edge, and change them to
2377      the new edge.  Do it now, since redirect_edge_and_branch would cancel
2378      the args otherwise.  */
2379   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
2380     {
2381       num_elem = PHI_NUM_ARGS (phi);
2382       for (i = 0; i < num_elem; i++)
2383         if (PHI_ARG_EDGE (phi, i) == edge_in)
2384           {
2385             PHI_ARG_EDGE (phi, i) = new_edge;
2386             break;
2387           }
2388     }
2389
2390   if (!redirect_edge_and_branch (edge_in, new_bb))
2391     abort ();
2392   tree_cleanup_block_edges (new_bb, false);
2393
2394
2395   return new_bb;
2396 }
2397
2398 /* Splits the basic block BB into two after BSI and returns the created
2399    fallthru edge.  */
2400 edge
2401 tree_split_block (basic_block bb, block_stmt_iterator bsi)
2402 {
2403   basic_block new_bb = create_bb ();
2404   edge e;
2405   int end;
2406
2407   /* Place the new block in front of the old one.  */
2408   unlink_block (new_bb);
2409   link_block (new_bb, bb->prev_bb);
2410
2411   new_bb->head_tree = bb->head_tree;
2412   new_bb->end_tree = bsi_cell (bsi);
2413
2414   end = bsi_end_p (bsi);
2415   if (!end)
2416     {
2417       bsi_next (&bsi);
2418       end = bsi_end_p (bsi);
2419     }
2420
2421   if (end)
2422     {
2423       /* Unless the block has only a fallthru edge, splitting the block
2424          would be wrong, as the edges coming from the control flow altering
2425          statement would be on the wrong place.  */
2426       if (!bb->succ
2427           || bb->succ->succ_next
2428           || !(bb->flags & EDGE_FALLTHRU))
2429         abort ();
2430
2431       new_bb->end_tree = bb->end_tree;
2432       bb->head_tree = NULL;
2433       bb->end_tree = NULL;
2434     }
2435   else
2436     {
2437       bb->head_tree = bsi_cell (bsi);
2438       new_bb->end_tree->next = NULL;
2439       bb->head_tree->prev = NULL;
2440     }
2441
2442   new_bb->pred = bb->pred;
2443   bb->pred = NULL;
2444   for (e = new_bb->pred; e; e = e->pred_next)
2445     e->dest = new_bb;
2446
2447   bb_ann (new_bb)->block = bb_ann (bb)->block;
2448
2449   return make_edge (new_bb, bb, EDGE_FALLTHRU);
2450 }
2451
2452 /* Moves basic block BB after block AFTER.  */
2453 void
2454 tree_move_block_after (basic_block bb, basic_block after, int no_false_fallthru)
2455 {
2456   basic_block prev = bb->prev_bb;
2457
2458   if (bb->prev_bb == after)
2459     return;
2460
2461   unlink_block (bb);
2462   link_block (bb, after);
2463
2464   /* Fix up fallthru edges.  */
2465   if (prev && prev != ENTRY_BLOCK_PTR)
2466     tree_cleanup_block_edges (prev, no_false_fallthru);
2467   tree_cleanup_block_edges (bb, no_false_fallthru);
2468   tree_cleanup_block_edges (after, no_false_fallthru);
2469 }
2470
2471 /* Verifies that the flow information is OK.  */
2472
2473 static int
2474 tree_verify_flow_info (void)
2475 {
2476   basic_block bb;
2477   tree_cell stmt, last;
2478   tree t, l, label, phi;
2479   block_stmt_iterator si;
2480   edge e, le, te, fe;
2481   struct block_tree *bti;
2482   int err = 0, degree;
2483
2484   FOR_EACH_BB (bb)
2485     {
2486       if (!bb->head_tree)
2487         continue;
2488
2489       last = NULL;
2490       for (stmt = bb->head_tree; stmt; last = stmt, stmt = stmt->next)
2491         {
2492           if (stmt->prev != last)
2493             {
2494               fprintf (stderr, "chain inconsistent in bb %d\n", bb->index);
2495               err = 1;
2496             }
2497
2498           if (last
2499               && stmt_ends_bb_p (last->stmt))
2500             {
2501               fprintf (stderr, "control statement in the middle of bb %d\n",
2502                        bb->index);
2503               err = 1;
2504             }
2505
2506           if (TREE_CODE (stmt->stmt) == COMPOUND_EXPR
2507               || TREE_CODE (stmt->stmt) == CASE_LABEL_EXPR
2508               || TREE_CODE (stmt->stmt) == BIND_EXPR)
2509             {
2510               fprintf (stderr, "forbidden statement in the middle of bb %d\n",
2511                        bb->index);
2512               err = 1;
2513             }
2514
2515           if (bb_for_stmt (stmt->stmt) != bb)
2516             {
2517               fprintf (stderr, "bb_for_stmt inconsistent in bb %d\n",
2518                        bb->index);
2519               err = 1;
2520             }
2521         }
2522       if (last != bb->end_tree)
2523         {
2524           fprintf (stderr, "end_tree inconsistent in bb %d\n",
2525                    bb->index);
2526           err = 1;
2527         }
2528
2529       last = NULL;
2530       for (stmt = bb->end_tree; stmt; last = stmt, stmt = stmt->prev)
2531         if (stmt->next != last)
2532           {
2533             fprintf (stderr, "chain inconsistent in bb %d\n", bb->index);
2534             err = 1;
2535           }
2536       if (last != bb->head_tree)
2537         {
2538           fprintf (stderr, "head_tree inconsistent in bb %d\n",
2539                    bb->index);
2540           err = 1;
2541         }
2542
2543       t = last_stmt (bb);
2544       if (t)
2545         {
2546           switch (TREE_CODE (t))
2547             {
2548             case GOTO_EXPR:
2549               if (!bb->succ)
2550                 {
2551                   fprintf (stderr, "goto without successors %d\n", bb->index);
2552                   err = 1;
2553                 }
2554               if (is_computed_goto (t)
2555                   || nonlocal_goto_p (t))
2556                 break;
2557
2558               le = NULL;
2559               for (e = bb->succ; e; e = e->succ_next)
2560                 {
2561                   if (!(e->flags & EDGE_ABNORMAL))
2562                     {
2563                       if (le)
2564                         {
2565                           fprintf (stderr, "goto with more than one successor %d\n",
2566                                    bb->index);
2567                           err = 1;
2568                         }
2569                       else
2570                         le = e;
2571                     }
2572
2573                   if (e->flags & EDGE_FALLTHRU)
2574                     {
2575                       fprintf (stderr, "goto with fallthru %d\n", bb->index);
2576                       err = 1;
2577                     }
2578                 }
2579               if (!le)
2580                 {
2581                   fprintf (stderr, "goto without successors %d\n", bb->index);
2582                   err = 1;
2583                 }
2584
2585               label = GOTO_DESTINATION (t);
2586               for (si = bsi_start (le->dest);
2587                    !bsi_end_p (si);
2588                    bsi_next (&si))
2589                 {
2590                   l = bsi_stmt (si);
2591                   if (TREE_CODE (l) == LABEL_EXPR
2592                       && LABEL_EXPR_LABEL (l) == label)
2593                     break;
2594                 }
2595               if (bsi_end_p (si))
2596                 {
2597                   fprintf (stderr, "%d: goto label not in dest block %d\n",
2598                            bb->index, le->dest->index);
2599                   err = 1;
2600                 }
2601               break;
2602
2603             case COND_EXPR:
2604               if (!bb->succ || !bb->succ->succ_next)
2605                 {
2606                   fprintf (stderr, "condition with less than 2 successors %d\n",
2607                            bb->index);
2608                   err = 1;
2609                 }
2610
2611               te = fe = NULL;
2612               for (e = bb->succ; e; e = e->succ_next)
2613                 {
2614                   if (e->flags & EDGE_FALLTHRU)
2615                     {
2616                       fprintf (stderr, "condition with fallthru %d\n", bb->index);
2617                       err = 1;
2618                     }
2619                   if (e->flags & EDGE_ABNORMAL)
2620                     continue;
2621
2622                   if (e->flags & EDGE_TRUE_VALUE)
2623                     {
2624                       if (te)
2625                         {
2626                           fprintf (stderr, "more than one true edge %d\n",
2627                                    bb->index);
2628                           err = 1;
2629                         }
2630                       else
2631                         te = e;
2632                     }
2633
2634                   if (e->flags & EDGE_FALSE_VALUE)
2635                     {
2636                       if (fe)
2637                         {
2638                           fprintf (stderr, "more than one false edge %d\n",
2639                                    bb->index);
2640                           err = 1;
2641                         }
2642                       else
2643                         fe = e;
2644                     }
2645                 }
2646               if (!te)
2647                 {
2648                   fprintf (stderr, "condition with no true edge %d\n",
2649                            bb->index);
2650                   err = 1;
2651                 }
2652               if (!fe)
2653                 {
2654                   fprintf (stderr, "condition with no false edge %d\n",
2655                            bb->index);
2656                   err = 1;
2657                 }
2658
2659               label = GOTO_DESTINATION (COND_EXPR_THEN (t));
2660               for (si = bsi_start (te->dest); !bsi_end_p (si); bsi_next (&si))
2661                 {
2662                   l = bsi_stmt (si);
2663                   if (TREE_CODE (l) == LABEL_EXPR
2664                       && LABEL_EXPR_LABEL (l) == label)
2665                     break;
2666                 }
2667               if (bsi_end_p (si))
2668                 {
2669                   fprintf (stderr, "%d: goto label not in dest block %d\n",
2670                            bb->index, te->dest->index);
2671                   err = 1;
2672                 }
2673
2674               label = GOTO_DESTINATION (COND_EXPR_ELSE (t));
2675               for (si = bsi_start (fe->dest); !bsi_end_p (si); bsi_next (&si))
2676                 {
2677                   l = bsi_stmt (si);
2678                   if (TREE_CODE (l) == LABEL_EXPR
2679                       && LABEL_EXPR_LABEL (l) == label)
2680                     break;
2681                 }
2682               if (bsi_end_p (si))
2683                 {
2684                   fprintf (stderr, "%d: goto label not in dest block %d\n",
2685                            bb->index, fe->dest->index);
2686                   err = 1;
2687                 }
2688               break;
2689
2690             default: ;
2691             }
2692         }
2693
2694       degree = 0;
2695       for (e = bb->pred; e; e = e->pred_next)
2696         {
2697           if (bb != bb_ann (bb)->block->entry
2698               && (e->flags & EDGE_CONSTRUCT_ENTRY))
2699             {
2700               fprintf (stderr,
2701                        "Construct entry edge not entering construct entry: %d\n",
2702                        bb->index);
2703               err = 1;
2704             }
2705
2706           for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
2707             if (phi_arg_from_edge (phi, e) < 0)
2708               {
2709                 fprintf (stderr,
2710                          "No entry for edge in phi node: %d\n", bb->index);
2711                 err = 1;
2712               }
2713           degree++;
2714         }
2715       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
2716         if (PHI_NUM_ARGS (phi) != degree)
2717           {
2718             fprintf (stderr,
2719                      "Superfluous entries in phi node: %d\n", bb->index);
2720             err = 1;
2721           }
2722     }
2723
2724   /* Entry block should have just one successor.  Exit block should have
2725      at most one fallthru predecessor.  */
2726   if (!ENTRY_BLOCK_PTR->succ
2727       || ENTRY_BLOCK_PTR->succ->succ_next)
2728     {
2729       fprintf (stderr, "Wrong amount of edges from entry\n");
2730       err = 1;
2731     }
2732
2733   if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_FALLTHRU))
2734     {
2735       fprintf (stderr, "Entry is not fallthru\n");
2736       err = 1;
2737     }
2738
2739   le = NULL;
2740   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
2741     if (e->flags & EDGE_FALLTHRU)
2742       {
2743         if (le)
2744           {
2745             fprintf (stderr, "More than one fallthru to exit\n");
2746             err = 1;
2747             break;
2748           }
2749         le = e;
2750       }
2751
2752   /* Check special edges of constructs.  */
2753   for (bti = bti_start (); !bti_end_p (bti); bti_next (&bti))
2754     if (bti->entry)
2755       {
2756         le = NULL;
2757         for (e = bti->entry->pred; e; e = e->pred_next)
2758           if (e->flags & EDGE_CONSTRUCT_ENTRY)
2759             {
2760               if (le)
2761                 {
2762                   fprintf (stderr, "More than one construct %p entry\n",
2763                            (void *) bti);
2764                   err = 1;
2765                   break;
2766                 }
2767               le = e;
2768             }
2769       }
2770
2771   return err;
2772 }
2773
2774
2775 /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
2776    marked as latch into entry part, analogically for REDIRECT_NONLATCH.
2777    In both of these cases, ignore edge EXCEPT.  If CONN_LATCH, set edge
2778    between created entry part and BB as latch one.  Return created entry
2779    part.  */
2780
2781 static basic_block
2782 tree_make_forwarder_block (basic_block bb, int redirect_latch,
2783                            int redirect_nonlatch, edge except, int conn_latch)
2784 {
2785   edge e, next_e, fallthru;
2786   basic_block dummy;
2787
2788   /* Create the new basic block.  */
2789   dummy = create_bb ();
2790   dummy->count = bb->count;
2791   dummy->frequency = bb->frequency;
2792   dummy->loop_depth = bb->loop_depth;
2793   dummy->head_tree = NULL;
2794   dummy->end_tree = NULL;
2795
2796   /* Redirect the incoming edges.  */
2797   dummy->pred = bb->pred;
2798   bb->pred = NULL;
2799   for (e = dummy->pred; e; e = e->pred_next)
2800     e->dest = dummy;
2801
2802   fallthru = make_edge (dummy, bb, 0);
2803
2804   HEADER_BLOCK (dummy) = 0;
2805   HEADER_BLOCK (bb) = 1;
2806
2807   /* Redirect back edges we want to keep.  */
2808   for (e = dummy->pred; e; e = next_e)
2809     {
2810       next_e = e->pred_next;
2811       if (e == except
2812           || !((redirect_latch && LATCH_EDGE (e))
2813                || (redirect_nonlatch && !LATCH_EDGE (e))))
2814         {
2815           dummy->frequency -= EDGE_FREQUENCY (e);
2816           dummy->count -= e->count;
2817           if (dummy->frequency < 0)
2818             dummy->frequency = 0;
2819           if (dummy->count < 0)
2820             dummy->count = 0;
2821           redirect_edge_succ (e, bb);
2822         }
2823     }
2824
2825   alloc_aux_for_edge (fallthru, sizeof (int));
2826   LATCH_EDGE (fallthru) = conn_latch;
2827
2828   return dummy;
2829 }
2830
2831 /* Cleanup the cfg -- edges correspondence for a single block BB.  If
2832    NO_FALSE_FALLTHRU, just remove false fallthru edges.  */
2833 void
2834 tree_cleanup_block_edges (basic_block bb, int no_false_fallthru)
2835 {
2836   edge e, e_true, e_false, next;
2837   block_stmt_iterator bsi;
2838   tree stmt;
2839   tree_stmt_iterator alt;
2840
2841   if (bb == ENTRY_BLOCK_PTR)
2842     return;
2843
2844 redo:
2845   stmt = last_stmt (bb);
2846   bsi = bsi_last (bb);
2847
2848   if (!stmt
2849       || !stmt_ends_bb_p (stmt)
2850       || no_false_fallthru)
2851     {
2852       for (e = bb->succ; e; e = e->succ_next)
2853         if (e->flags & EDGE_FALLTHRU)
2854           break;
2855
2856       if (e && e->dest != bb->next_bb && e->dest != EXIT_BLOCK_PTR)
2857         {
2858           tree label = tree_block_label (e->dest);
2859
2860           bsi_insert_after (&bsi,
2861                             build1 (GOTO_EXPR, void_type_node, label),
2862                             BSI_NEW_STMT);
2863           e->flags &= ~EDGE_FALLTHRU;
2864           goto redo;
2865         }
2866     }
2867
2868   if (!stmt
2869       || no_false_fallthru)
2870     return;
2871
2872   switch (TREE_CODE (stmt))
2873     {
2874     case GOTO_EXPR:
2875       if (is_computed_goto (stmt)
2876           || nonlocal_goto_p (stmt))
2877         break;
2878
2879       e_true = NULL;
2880       for (e = bb->succ; e; e = e->succ_next)
2881         {
2882           if (e->flags & EDGE_ABNORMAL)
2883             continue;
2884
2885           if (e_true)
2886             abort ();
2887
2888           e_true = e;
2889         }
2890
2891       if (!e_true)
2892         break;
2893
2894       if (e_true->dest == bb->next_bb)
2895         {
2896           bsi_remove (&bsi);
2897           e_true->flags |= EDGE_FALLTHRU;
2898         }
2899       break;
2900
2901     case COND_EXPR:
2902       e_true = e_false = NULL;
2903
2904       for (e = bb->succ; e; e = e->succ_next)
2905         {
2906           if (e->flags & EDGE_TRUE_VALUE)
2907             {
2908               if (e_true)
2909                 abort ();
2910               e_true = e;
2911             }
2912           if (e->flags & EDGE_FALSE_VALUE)
2913             {
2914               if (e_false)
2915                 abort ();
2916               e_false = e;
2917             }
2918         }
2919
2920       /* During cfg generation it may happen that both branches of COND_EXPR
2921          lead to the same target.  */
2922       if (e_true == e_false)
2923         e_false = NULL;
2924
2925       if ((!e_true && !e_false)
2926           || (e_true && e_false))
2927         break;
2928
2929       if (!e_true)
2930         bsi_replace (bsi, COND_EXPR_ELSE (stmt));
2931       else if (!e_false)
2932         bsi_replace (bsi, COND_EXPR_THEN (stmt));
2933
2934       /* Try optimizing the resulting goto.  */
2935       goto redo;
2936
2937     case SWITCH_EXPR:
2938       if (!bb->succ)
2939         break;
2940
2941       alt = CASE_START (stmt);
2942       if (bb->succ->succ_next)
2943         {
2944           /* If there are more edges, but only one matches, we may proceed
2945              anyway.  */
2946           e_true = find_taken_edge (bb, SWITCH_COND (stmt));
2947           if (!e_true)
2948             break;
2949           for (; !CASE_END_P (alt); CASE_NEXT (alt))
2950             if (CASE_EDGE (alt) == e_true)
2951               break;
2952           if (CASE_END_P (alt))
2953             abort ();
2954
2955           for (e = bb->succ; e; e = next)
2956             {
2957               next = e->succ_next;
2958               if (e == e_true
2959                   || (e->flags & EDGE_ABNORMAL))
2960                 continue;
2961
2962               ssa_remove_edge (e);
2963             }
2964         }
2965
2966       bsi_replace (bsi, CASE_GOTO (alt));
2967       goto redo;
2968
2969     default: ;
2970     }
2971 }
2972
2973 /* Cleanup the cfg -- edges correspondence damaged by previous passes.
2974    Edges could be removed while unreachable jumps from their control
2975    statemens were not.  */
2976 static void
2977 tree_cleanup_edges ()
2978 {
2979   basic_block bb;
2980
2981   FOR_EACH_BB (bb)
2982     {
2983       tree_cleanup_block_edges (bb, false);
2984     }
2985 }
2986
2987 /* Initialization of functions specific to the tree IR.  */
2988
2989 void
2990 tree_register_cfg_hooks ()
2991 {
2992   cfg_hooks = &tree_cfg_hooks;
2993 }
2994
2995 /* Dumps information about tree_cell chain START to stderr.  */
2996 void
2997 debug_tree_chain (tree_cell start)
2998 {
2999   tree op;
3000
3001   for (; start; start = start->next)
3002     {
3003       switch (start->note)
3004         {
3005         case TCN_STATEMENT:
3006           debug_generic_stmt (start->stmt);
3007           break;
3008
3009         case TCN_BIND:
3010           fprintf (stderr, "{\n");
3011           for (op = BIND_EXPR_VARS (start->stmt); op; op = TREE_CHAIN (op))
3012             debug_generic_stmt (op);
3013           break;
3014
3015         case TCN_UNBIND:
3016           fprintf (stderr, "}\n");
3017           break;
3018
3019         default:
3020           abort ();
3021         }
3022     }
3023 }
3024
3025 /* Dumps identification of BLOCK to FILE.  */
3026 static void
3027 dump_block_tree_id (FILE *file, struct block_tree *block)
3028 {
3029   fprintf (file, "BIND %p", (void *) block);
3030 }
3031
3032 /* Dumps information about block tree BLOCK to FILE, indenting INDENT spaces.  */
3033 void
3034 dump_block_tree (FILE *file, int indent, struct block_tree *block)
3035 {
3036   int i;
3037   tree var;
3038
3039   for (i = 0; i < indent; i++)
3040     fprintf (file, " ");
3041   dump_block_tree_id (file, block);
3042
3043   fprintf (file, " vars");
3044   for (var = BIND_EXPR_VARS (block->bind); var; var = TREE_CHAIN (var))
3045     {
3046       fprintf (file, " ");
3047       print_generic_stmt (file, var, 0);
3048     }
3049
3050   if (block->entry)
3051     fprintf (file, " entry %d", block->entry->index);
3052
3053   fprintf (file, "\n");
3054   for (block = block->subtree; block; block = block->next)
3055     dump_block_tree (file, indent + 2, block);
3056 }
3057
3058 /* Initialize loop optimizer.  */
3059
3060 static struct loops *
3061 tree_loop_optimizer_init (FILE *dumpfile)
3062 {
3063   struct loops *loops = xcalloc (1, sizeof (struct loops));
3064
3065   /* Find the loops.  */
3066   if (flow_loops_find (loops, LOOP_TREE) <= 1)
3067     {
3068       /* No loops.  */
3069       flow_loops_free (loops);
3070       free (loops);
3071       return NULL;
3072     }
3073
3074   /* Not going to update these.  */
3075   free (loops->cfg.rc_order);
3076   loops->cfg.rc_order = NULL;
3077   free (loops->cfg.dfs_order);
3078   loops->cfg.dfs_order = NULL;
3079
3080   /* Force all latches to have only single successor.  */
3081   force_single_succ_latches (loops);
3082
3083   /* Mark irreducible loops.  */
3084   mark_irreducible_loops (loops);
3085
3086   /* Dump loops.  */
3087   flow_loops_dump (loops, dumpfile, NULL, 1);
3088
3089 #ifdef ENABLE_CHECKING
3090   verify_dominators (loops->cfg.dom);
3091   verify_loop_structure (loops);
3092 #endif
3093
3094   return loops;
3095 }
3096
3097 /* Finalize loop optimizer.  */
3098 static void
3099 tree_loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
3100 {
3101   if (loops == NULL)
3102     return;
3103
3104   /* Another dump.  */
3105   flow_loops_dump (loops, dumpfile, NULL, 1);
3106
3107   /* Clean up.  */
3108   flow_loops_free (loops);
3109   free (loops);
3110
3111   /* Checking.  */
3112 #ifdef ENABLE_CHECKING
3113   verify_flow_info ();
3114 #endif
3115 }
3116
3117 /* Assigns a scope to variables defined in block SCOPE.  */
3118 static void
3119 assign_vars_to_scope (struct block_tree *scope)
3120 {
3121   tree var;
3122
3123   for (var = BIND_EXPR_VARS (scope->bind); var; var = TREE_CHAIN (var))
3124     get_var_ann (var)->scope = scope;
3125 }
3126
3127 /* Assigns a scope in that it is defined to each variable.  */
3128 void
3129 assign_vars_to_scopes ()
3130 {
3131   struct block_tree *act;
3132
3133   for (act = bti_start (); !bti_end_p (act); bti_next (&act))
3134     assign_vars_to_scope (act);
3135 }
3136
3137 /* Ensures that there are not useless labels.  It makes all jumps to
3138    the block to target one label (non-artificial ones are preferred),
3139    and removes all other artificial labels (the named ones are left
3140    for debugging purposes.  */
3141 static void
3142 remove_superfluous_labels ()
3143 {
3144   basic_block bb;
3145   edge e;
3146   block_stmt_iterator bsi;
3147   tree stmt, label;
3148   tree_stmt_iterator alt;
3149   int preserve;
3150
3151   FOR_EACH_BB (bb)
3152     {
3153       bsi = bsi_start (bb);
3154       stmt = first_stmt (bb);
3155
3156       if (!stmt || TREE_CODE (stmt) != LABEL_EXPR)
3157         continue;
3158
3159       /* Try to find a label that must stay anyway.  */
3160       label = LABEL_EXPR_LABEL (stmt);
3161       for (;
3162            DECL_ARTIFICIAL (label) && !FORCED_LABEL (label) && !bsi_end_p (bsi);
3163            bsi_next (&bsi))
3164         {
3165           stmt = bsi_stmt (bsi);
3166           if (TREE_CODE (stmt) != LABEL_EXPR)
3167             break;
3168
3169           label = LABEL_EXPR_LABEL (stmt);
3170         }
3171
3172       /* Replace to it within all jumps to the block.  */
3173       preserve = false;
3174       for (e = bb->pred; e; e = e->pred_next)
3175         {
3176           if ((e->flags & EDGE_ABNORMAL)
3177               || (e->flags & EDGE_FALLTHRU))
3178             continue;
3179
3180           stmt = last_stmt (e->src);
3181           if (TREE_CODE (stmt) == SWITCH_EXPR)
3182             {
3183               for (alt = CASE_START (stmt);
3184                    !CASE_END_P (alt);
3185                    CASE_NEXT (alt))
3186                 if (CASE_EDGE (alt) == e)
3187                   CASE_DESTINATION (alt) = label;
3188             }
3189           else
3190             {
3191               stmt = find_edge_goto (last_stmt (e->src), e);
3192               if (!stmt)
3193                 abort ();
3194               GOTO_DESTINATION (stmt) = label;
3195             }
3196
3197           preserve = true;
3198         }
3199
3200       if (!preserve)
3201         label = NULL_TREE;
3202
3203       /* Remove unnecesary labels.  Due to way we have chosen the label to
3204          keep, the kept label will then be the first one of the block,
3205          therefore the one returned by tree_block_label, which is fine.  */
3206       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3207         {
3208           stmt = bsi_stmt (bsi);
3209           if (TREE_CODE (stmt) != LABEL_EXPR)
3210             break;
3211
3212           if (LABEL_EXPR_LABEL (stmt) == label
3213               || !DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt))
3214               || FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
3215             {
3216               bsi_next (&bsi);
3217               continue;
3218             }
3219
3220           bsi_remove (&bsi);
3221         }
3222     }
3223 }
3224
3225 /* Checks whether the basic block BB does nothing except for jump.  */
3226 static bool
3227 tree_forwarder_block_p (basic_block bb)
3228 {
3229   block_stmt_iterator bsi;
3230
3231   if (!bb->succ
3232       || bb->succ->succ_next
3233       || (bb->succ->flags & EDGE_ABNORMAL)
3234       || (bb->succ->flags & EDGE_CONSTRUCT_ENTRY)
3235       || bb == ENTRY_BLOCK_PTR)
3236     return false;
3237
3238   if (phi_nodes (bb))
3239     return false;
3240
3241   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3242     switch (TREE_CODE (bsi_stmt (bsi)))
3243       {
3244       case LABEL_EXPR:
3245       case GOTO_EXPR:
3246         break;
3247
3248       default:
3249         return false;
3250       }
3251
3252   return true;
3253 }
3254
3255 /* Threads jumps over empty statements.  Later we may add threading over
3256    equivalent conditions.  */
3257 static void
3258 thread_jumps ()
3259 {
3260   edge e, next, last, old;
3261   basic_block bb, dest, slow;
3262   int set_slow;
3263   tree phi, val1, val2;
3264   int arg;
3265
3266   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3267     {
3268       /* Don't waste time on unreachable blocks.  */
3269       if (!bb->pred)
3270         continue;
3271
3272       /* Nor on forwarders.  */
3273       if (tree_forwarder_block_p (bb))
3274         continue;
3275
3276       for (e = bb->succ; e; e = next)
3277         {
3278           next = e->succ_next;
3279
3280           if ((e->flags & EDGE_ABNORMAL)
3281               || (e->flags & EDGE_CONSTRUCT_ENTRY)
3282               || e->dest == EXIT_BLOCK_PTR
3283               || !tree_forwarder_block_p (e->dest)
3284               || e->dest->succ->dest == EXIT_BLOCK_PTR)
3285             continue;
3286
3287           slow = e->dest;
3288           set_slow = 0;
3289
3290           last = e->dest->succ;
3291           for (dest = e->dest->succ->dest;
3292                tree_forwarder_block_p (dest);
3293                last = dest->succ,
3294                dest = dest->succ->dest,
3295                set_slow ^= 1)
3296             {
3297               /* Infinite loop detected.  */
3298               if (slow == dest)
3299                 break;
3300               if (set_slow)
3301                 slow = slow->succ->dest;
3302
3303               if (dest->succ->dest == EXIT_BLOCK_PTR)
3304                 break;
3305             }
3306
3307           if (dest == e->dest)
3308             continue;
3309
3310           old = find_edge (bb, dest);
3311           if (old)
3312             {
3313               /* If there already is an edge, check whether the values of
3314                  in phi nodes differ.  */
3315               for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
3316                 {
3317                   val1 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, last));
3318                   val2 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, old));
3319
3320                   if (!operand_equal_p (val1, val2, false))
3321                     break;
3322                 }
3323               if (phi)
3324                 {
3325                   /* The previous block is forwarder, so there are no
3326                      phi nodes to update.  */
3327                   dest = last->src;
3328                 }
3329             }
3330
3331           if (dest == e->dest)
3332             continue;
3333
3334           if (redirect_edge_and_branch (e, dest)
3335               && !old)
3336             {
3337               /* Update phi nodes.  */
3338               for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
3339                 {
3340                   arg = phi_arg_from_edge (phi, last);
3341                   if (arg < 0)
3342                     abort ();
3343                   add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
3344                 }
3345             }
3346         }
3347     }
3348 }
3349
3350 /* Returns a GOTO_EXPR for edge E found in STMT.  */
3351 static tree
3352 find_edge_goto (tree stmt, edge e)
3353 {
3354   if (!stmt)
3355     return NULL_TREE;
3356
3357   switch (TREE_CODE (stmt))
3358     {
3359     case SWITCH_EXPR:
3360       /* Using this function for switch_exprs is dangerous, since there
3361          may be more than one goto to the one edge.  */
3362       abort ();
3363
3364     case COND_EXPR:
3365       if (e->flags & EDGE_TRUE_VALUE)
3366         return COND_EXPR_THEN (stmt);
3367       else if (e->flags & EDGE_FALSE_VALUE)
3368         return COND_EXPR_ELSE (stmt);
3369       else
3370         abort ();
3371
3372     case GOTO_EXPR:
3373       return stmt;
3374
3375     default:
3376       return NULL_TREE;
3377     }
3378 }
3379
3380 /* Removes unneccesary variables.  */
3381 void
3382 remove_useless_stmts_and_vars ()
3383 {
3384   struct block_tree *bti;
3385   tree vars, prev;
3386   struct var_ann_d *ann;
3387
3388   for (bti = bti_start (); !bti_end_p (bti); bti_next (&bti))
3389     {
3390       prev = NULL_TREE;
3391       for (vars = BIND_EXPR_VARS (bti->bind);
3392            vars;
3393            vars = TREE_CHAIN (vars))
3394         {
3395           /* We could have function declarations and the like
3396              on this list.  Ignore them.  */
3397           if (TREE_CODE (vars) != VAR_DECL)
3398             {
3399               prev = vars;
3400               continue;
3401             }
3402
3403           /* Remove all unused, unaliased temporaries.  Also remove
3404              unused, unaliased local variables during highly
3405              optimizing compilations.  */
3406           ann = var_ann (vars);
3407           if (ann
3408               && ! ann->may_aliases
3409               && ! ann->used
3410               && ! ann->has_hidden_use
3411               && ! TREE_ADDRESSABLE (vars)
3412               && (DECL_ARTIFICIAL (vars) || optimize >= 2))
3413             {
3414               tree block = BIND_EXPR_BLOCK (bti->bind);
3415
3416               if (block)
3417                 remove_decl (vars, block);
3418               else
3419                 remove_decl (vars, DECL_INITIAL (current_function_decl));
3420
3421               if (prev)
3422                 TREE_CHAIN (prev) = TREE_CHAIN (vars);
3423               else
3424                 BIND_EXPR_VARS (bti->bind) = TREE_CHAIN (vars);
3425             }
3426           else
3427             prev = vars;
3428         }
3429     }
3430 }
3431
3432 /* Merges blocks if possible.  */
3433 static void
3434 merge_seq_blocks ()
3435 {
3436   basic_block bb;
3437
3438   for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; )
3439     {
3440       if (
3441           /* It must have a single succesor.  */
3442           bb->succ
3443           && !bb->succ->succ_next
3444           && !(bb->succ->flags & EDGE_ABNORMAL)
3445           && !(bb->succ->flags & EDGE_CONSTRUCT_ENTRY)
3446           && bb->succ->dest != EXIT_BLOCK_PTR
3447           && bb->succ->dest != bb
3448           /* That has a single predecessor.  */
3449           && !bb->succ->dest->pred->pred_next
3450           /* Don't merge blocks from different contexts.  */
3451           && bb_ann (bb)->block == bb_ann (bb->succ->dest)->block)
3452         {
3453           /* Merge the blocks and retry.  */
3454           merge_blocks (bb, bb->succ->dest);
3455           continue;
3456         }
3457
3458       bb = bb->next_bb;
3459     }
3460 }