gcc/cfgexpand.c

   1 /* A pass for lowering trees to RTL.
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "function.h"
  30 #include "expr.h"
  31 #include "langhooks.h"
  32 #include "tree-flow.h"
  33 #include "timevar.h"
  34 #include "tree-dump.h"
  35 #include "tree-pass.h"
  36 #include "except.h"
  37 #include "flags.h"
  38 /* Expand basic block BB from GIMPLE trees to RTL.  */
  39
  40 static basic_block
  41 expand_block (basic_block bb, FILE * dump_file)
  42 {
  43   block_stmt_iterator bsi = bsi_start (bb);
  44   tree stmt = NULL;
  45   rtx note, last;
  46   edge e;
  47
  48   if (dump_file)
  49     {
  50       tree_register_cfg_hooks ();
  51       dump_bb (bb, dump_file, 0);
  52       rtl_register_cfg_hooks ();
  53     }
  54
  55   if (!bsi_end_p (bsi))
  56     stmt = bsi_stmt (bsi);
  57
  58   if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
  59     {
  60       last = get_last_insn ();
  61
  62       expand_expr_stmt (stmt);
  63
  64       /* Java emits line number notes in the top of labels.
  65          ??? Make this go away once line number notes are obsoleted.  */
  66       BB_HEAD (bb) = NEXT_INSN (last);
  67       if (GET_CODE (BB_HEAD (bb)) == NOTE)
  68         BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
  69       bsi_next (&bsi);
  70       note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
  71     }
  72   else
  73     note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
  74
  75   NOTE_BASIC_BLOCK (note) = bb;
  76
  77   e = bb->succ;
  78   while (e)
  79     {
  80       edge next = e->succ_next;
  81
  82       /* Clear EDGE_EXECUTABLE.  This flag is never used in the backend.  */
  83       e->flags &= ~EDGE_EXECUTABLE;
  84
  85       /* At the moment not all abnormal edges match the RTL representation.
  86          It is safe to remove them here as find_sub_basic_blocks will
  87          rediscover them.  In the future we should get this fixed properly.  */
  88       if (e->flags & EDGE_ABNORMAL)
  89         remove_edge (e);
  90
  91       e = next;
  92     }
  93
  94   for (; !bsi_end_p (bsi); bsi_next (&bsi))
  95     {
  96       tree stmt = bsi_stmt (bsi);
  97
  98       last = get_last_insn ();
  99
 100       if (!stmt)
 101         continue;
 102
 103       /* Expand this statement, then evaluate the resulting RTL and
 104          fixup the CFG accordingly.  */
 105       switch (TREE_CODE (stmt))
 106         {
 107         case COND_EXPR:
 108           {
 109             basic_block new_bb, dest;
 110             edge new_edge;
 111             edge true_edge;
 112             edge false_edge;
 113             tree pred = COND_EXPR_COND (stmt);
 114             tree then_exp = COND_EXPR_THEN (stmt);
 115             tree else_exp = COND_EXPR_ELSE (stmt);
 116             rtx last = get_last_insn ();
 117
 118             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 119             if (EXPR_LOCUS (stmt))
 120               {
 121                 emit_line_note (*(EXPR_LOCUS (stmt)));
 122                 record_block_change (TREE_BLOCK (stmt));
 123               }
 124
 125             /* These flags have no purpose in RTL land.  */
 126             true_edge->flags &= ~EDGE_TRUE_VALUE;
 127             false_edge->flags &= ~EDGE_FALSE_VALUE;
 128
 129             /* We can either have a pure conditional jump with one fallthru
 130                edge or two-way jump that needs to be decomposed into two
 131                basic blocks.  */
 132             if (TREE_CODE (then_exp) == GOTO_EXPR
 133                 && TREE_CODE (else_exp) == NOP_EXPR)
 134               {
 135                 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
 136                 break;
 137               }
 138             if (TREE_CODE (else_exp) == GOTO_EXPR
 139                 && TREE_CODE (then_exp) == NOP_EXPR)
 140               {
 141                 jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
 142                 break;
 143               }
 144             if (TREE_CODE (then_exp) != GOTO_EXPR
 145                 || TREE_CODE (else_exp) != GOTO_EXPR)
 146               abort ();
 147
 148             jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
 149             last = get_last_insn ();
 150             expand_expr (else_exp, const0_rtx, VOIDmode, 0);
 151
 152             BB_END (bb) = last;
 153             if (GET_CODE (BB_END (bb)) == BARRIER)
 154               BB_END (bb) = PREV_INSN (BB_END (bb));
 155             update_bb_for_insn (bb);
 156
 157             new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 158             dest = false_edge->dest;
 159             redirect_edge_succ (false_edge, new_bb);
 160             false_edge->flags |= EDGE_FALLTHRU;
 161             new_bb->count = false_edge->count;
 162             new_bb->frequency = EDGE_FREQUENCY (false_edge);
 163             new_edge = make_edge (new_bb, dest, 0);
 164             new_edge->probability = REG_BR_PROB_BASE;
 165             new_edge->count = new_bb->count;
 166             if (GET_CODE (BB_END (new_bb)) == BARRIER)
 167               BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
 168             update_bb_for_insn (new_bb);
 169
 170             if (dump_file)
 171               {
 172                 dump_bb (bb, dump_file, 0);
 173                 dump_bb (new_bb, dump_file, 0);
 174               }
 175             return new_bb;
 176           }
 177
 178         /* Update after expansion of sibling call.  */
 179         case CALL_EXPR:
 180         case MODIFY_EXPR:
 181         case RETURN_EXPR:
 182           expand_expr_stmt (stmt);
 183           for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
 184             {
 185               if (GET_CODE (last) == CALL_INSN && SIBLING_CALL_P (last))
 186                 {
 187                   edge e;
 188                   int probability = 0;
 189                   gcov_type count = 0;
 190
 191                   do_pending_stack_adjust ();
 192                   e = bb->succ;
 193                   while (e)
 194                     {
 195                       edge next = e->succ_next;
 196
 197                       if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 198                         {
 199                           if (e->dest != EXIT_BLOCK_PTR)
 200                             {
 201                               e->dest->count -= e->count;
 202                               e->dest->frequency -= EDGE_FREQUENCY (e);
 203                               if (e->dest->count < 0)
 204                                 e->dest->count = 0;
 205                               if (e->dest->frequency < 0)
 206                                 e->dest->frequency = 0;
 207                             }
 208                           count += e->count;
 209                           probability += e->probability;
 210                           remove_edge (e);
 211                         }
 212
 213                       e = next;
 214                     }
 215
 216                   /* This is somewhat ugly:  the call_expr expander often emits instructions
 217                      after the sibcall (to perform the function return).  These confuse the
 218                      find_sub_basic_blocks code, so we need to get rid of these.  */
 219                   last = NEXT_INSN (last);
 220                   if (GET_CODE (last) != BARRIER)
 221                     abort ();
 222                   while (NEXT_INSN (last))
 223                     {
 224                       /* For instance an sqrt builtin expander expands if with
 225                          sibcall in the then and label for `else`.  */
 226                       if (GET_CODE (NEXT_INSN (last)) == CODE_LABEL)
 227                         break;
 228                       delete_insn (NEXT_INSN (last));
 229                     }
 230                   e = make_edge (bb, EXIT_BLOCK_PTR,
 231                                      EDGE_ABNORMAL | EDGE_SIBCALL);
 232                   e->probability += probability;
 233                   e->count += count;
 234                   BB_END (bb) = last;
 235                   update_bb_for_insn (bb);
 236                   if (NEXT_INSN (last))
 237                     bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 238                   else
 239                     return bb;
 240                 }
 241             }
 242           break;
 243
 244         default:
 245           expand_expr_stmt (stmt);
 246           break;
 247         }
 248     }
 249
 250   do_pending_stack_adjust ();
 251
 252   /* Find the the block tail.  The last insn is the block is the insn
 253      before a barrier and/or table jump insn.  */
 254   last = get_last_insn ();
 255   if (GET_CODE (last) == BARRIER)
 256     last = PREV_INSN (last);
 257   if (JUMP_TABLE_DATA_P (last))
 258     last = PREV_INSN (PREV_INSN (last));
 259   BB_END (bb) = last;
 260
 261   if (dump_file)
 262     dump_bb (bb, dump_file, 0);
 263   update_bb_for_insn (bb);
 264   return bb;
 265 }
 266
 267
 268 /* Create a basic block for initialization code.  */
 269
 270 static basic_block
 271 construct_init_block (void)
 272 {
 273   basic_block init_block, first_block;
 274   edge e;
 275
 276   expand_start_bindings_and_block (0, NULL_TREE);
 277
 278   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 279     if (e->dest == ENTRY_BLOCK_PTR->next_bb)
 280       break;
 281
 282   init_block = create_basic_block (NEXT_INSN (get_insns ()),
 283                                    get_last_insn (),
 284                                    ENTRY_BLOCK_PTR);
 285   init_block->frequency = ENTRY_BLOCK_PTR->frequency;
 286   init_block->count = ENTRY_BLOCK_PTR->count;
 287   if (e)
 288     {
 289       first_block = e->dest;
 290       redirect_edge_succ (e, init_block);
 291       e = make_edge (init_block, first_block, EDGE_FALLTHRU);
 292     }
 293   else
 294     e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 295   e->probability = REG_BR_PROB_BASE;
 296   e->count = ENTRY_BLOCK_PTR->count;
 297
 298   update_bb_for_insn (init_block);
 299   return init_block;
 300 }
 301
 302
 303 /* Create a block containing landing pads and similar stuff.  */
 304
 305 static void
 306 construct_exit_block (void)
 307 {
 308   rtx head = get_last_insn ();
 309   rtx end;
 310   basic_block exit_block;
 311   edge e, e2, next;
 312
 313   /* Make sure the locus is set to the end of the function, so that
 314      epilogue line numbers and warnings are set properly.  */
 315 #ifdef USE_MAPPED_LOCATION
 316   if (cfun->function_end_locus != UNKNOWN_LOCATION)
 317 #else
 318   if (cfun->function_end_locus.file)
 319 #endif
 320     input_location = cfun->function_end_locus;
 321
 322   /* The following insns belong to the top scope.  */
 323   record_block_change (DECL_INITIAL (current_function_decl));
 324
 325   expand_end_bindings (NULL_TREE, 1, 0);
 326
 327   /* Generate rtl for function exit.  */
 328   expand_function_end ();
 329
 330   end = get_last_insn ();
 331   if (head == end)
 332     return;
 333   while (NEXT_INSN (head) && GET_CODE (NEXT_INSN (head)) == NOTE)
 334     head = NEXT_INSN (head);
 335   exit_block = create_basic_block (NEXT_INSN (head), end, EXIT_BLOCK_PTR->prev_bb);
 336   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 337   exit_block->count = EXIT_BLOCK_PTR->count;
 338   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 339     {
 340       next = e->pred_next;
 341       if (!(e->flags & EDGE_ABNORMAL))
 342         redirect_edge_succ (e, exit_block);
 343     }
 344   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 345   e->probability = REG_BR_PROB_BASE;
 346   e->count = EXIT_BLOCK_PTR->count;
 347   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 348     if (e2 != e)
 349       {
 350         e->count -= e2->count;
 351         exit_block->count -= e2->count;
 352         exit_block->frequency -= EDGE_FREQUENCY (e2);
 353       }
 354   if (e->count < 0)
 355     e->count = 0;
 356   if (exit_block->count < 0)
 357     exit_block->count = 0;
 358   if (exit_block->frequency < 0)
 359     exit_block->frequency = 0;
 360   update_bb_for_insn (exit_block);
 361 }
 362
 363 /* Translate the intermediate representation contained in the CFG
 364    from GIMPLE trees to RTL.
 365
 366    We do conversion per basic block and preserve/update the tree CFG.
 367    This implies we have to do some magic as the CFG can simultaneously
 368    consist of basic blocks containing RTL and GIMPLE trees.  This can
 369    confuse the CFG hooks, so be careful to not manipulate CFG during
 370    the expansion.  */
 371
 372 static void
 373 tree_expand_cfg (void)
 374 {
 375   basic_block bb, init_block;
 376   sbitmap blocks;
 377
 378   if (dump_file)
 379     {
 380       fprintf (dump_file, "\n;; Function %s",
 381                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 382       fprintf (dump_file, " (%s)\n",
 383                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 384     }
 385
 386   /* Prepare the rtl middle end to start recording block changes.  */
 387   reset_block_changes ();
 388
 389   /* Expand the variables recorded during gimple lowering.  This must
 390      occur before the call to expand_function_start to ensure that
 391      all used variables are expanded before we expand anything on the
 392      PENDING_SIZES list.  */
 393   expand_used_vars ();
 394
 395   /* Set up parameters and prepare for return, for the function.  */
 396   expand_function_start (current_function_decl);
 397
 398   /* If this function is `main', emit a call to `__main'
 399      to run global initializers, etc.  */
 400   if (DECL_NAME (current_function_decl)
 401       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 402       && DECL_FILE_SCOPE_P (current_function_decl))
 403     expand_main_function ();
 404
 405   /* Write the flowgraph to a dot file.  */
 406   rtl_register_cfg_hooks ();
 407
 408   init_block = construct_init_block ();
 409
 410   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 411     bb = expand_block (bb, dump_file);
 412
 413   construct_exit_block ();
 414
 415   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 416      sorts of eh initialization.  Delay this until after the
 417      initial rtl dump so that we can see the original nesting.  */
 418   convert_from_eh_region_ranges ();
 419
 420   rebuild_jump_labels (get_insns ());
 421   find_exception_handler_labels ();
 422
 423   blocks = sbitmap_alloc (last_basic_block);
 424   sbitmap_ones (blocks);
 425   find_many_sub_basic_blocks (blocks);
 426   purge_all_dead_edges (0);
 427   sbitmap_free (blocks);
 428
 429   compact_blocks ();
 430 #ifdef ENABLE_CHECKING
 431   verify_flow_info();
 432 #endif
 433 }
 434
 435 struct tree_opt_pass pass_expand =
 436 {
 437   "expand",                             /* name */
 438   NULL,                                 /* gate */
 439   tree_expand_cfg,                      /* execute */
 440   NULL,                                 /* sub */
 441   NULL,                                 /* next */
 442   0,                                    /* static_pass_number */
 443   TV_EXPAND,                            /* tv_id */
 444   /* ??? If TER is enabled, we actually receive GENERIC.  */
 445   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 446   PROP_rtl,                             /* properties_provided */
 447   PROP_gimple_leh,                      /* properties_destroyed */
 448   0,                                    /* todo_flags_start */
 449   0                                     /* todo_flags_finish */
 450 };
 451