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 /* Called to move the SAVE_EXPRs for parameter declarations in a
 364    nested function into the nested function.  DATA is really the
 365    nested FUNCTION_DECL.  */
 366
 367 static tree
 368 set_save_expr_context (tree *tp,
 369                        int *walk_subtrees,
 370                        void *data)
 371 {
 372   if (TREE_CODE (*tp) == SAVE_EXPR && !SAVE_EXPR_CONTEXT (*tp))
 373     SAVE_EXPR_CONTEXT (*tp) = (tree) data;
 374   /* Do not walk back into the SAVE_EXPR_CONTEXT; that will cause
 375      circularity.  */
 376   else if (DECL_P (*tp))
 377     *walk_subtrees = 0;
 378
 379   return NULL;
 380 }
 381
 382
 383 /* Translate the intermediate representation contained in the CFG
 384    from GIMPLE trees to RTL.
 385
 386    We do conversion per basic block and preserve/update the tree CFG.
 387    This implies we have to do some magic as the CFG can simultaneously
 388    consist of basic blocks containing RTL and GIMPLE trees.  This can
 389    confuse the CFG hooks, so be careful to not manipulate CFG during
 390    the expansion.  */
 391
 392 static void
 393 tree_expand_cfg (void)
 394 {
 395   basic_block bb, init_block;
 396   sbitmap blocks;
 397
 398   if (dump_file)
 399     {
 400       fprintf (dump_file, "\n;; Function %s",
 401                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 402       fprintf (dump_file, " (%s)\n",
 403                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 404     }
 405
 406   /* If the function has a variably modified type, there may be
 407      SAVE_EXPRs in the parameter types.  Their context must be set to
 408      refer to this function; they cannot be expanded in the containing
 409      function.  */
 410   if (decl_function_context (current_function_decl) == current_function_decl
 411       && variably_modified_type_p (TREE_TYPE (current_function_decl)))
 412     walk_tree (&TREE_TYPE (current_function_decl), set_save_expr_context,
 413                current_function_decl, NULL);
 414
 415   /* Prepare the rtl middle end to start recording block changes.  */
 416   reset_block_changes ();
 417
 418   /* Expand the variables recorded during gimple lowering.  This must
 419      occur before the call to expand_function_start to ensure that
 420      all used variables are expanded before we expand anything on the
 421      PENDING_SIZES list.  */
 422   expand_used_vars ();
 423
 424   /* Set up parameters and prepare for return, for the function.  */
 425   expand_function_start (current_function_decl);
 426
 427   /* If this function is `main', emit a call to `__main'
 428      to run global initializers, etc.  */
 429   if (DECL_NAME (current_function_decl)
 430       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 431       && DECL_FILE_SCOPE_P (current_function_decl))
 432     expand_main_function ();
 433
 434   /* Write the flowgraph to a dot file.  */
 435   rtl_register_cfg_hooks ();
 436
 437   init_block = construct_init_block ();
 438
 439   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 440     bb = expand_block (bb, dump_file);
 441
 442   construct_exit_block ();
 443
 444   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 445      sorts of eh initialization.  Delay this until after the
 446      initial rtl dump so that we can see the original nesting.  */
 447   convert_from_eh_region_ranges ();
 448
 449   rebuild_jump_labels (get_insns ());
 450   find_exception_handler_labels ();
 451
 452   blocks = sbitmap_alloc (last_basic_block);
 453   sbitmap_ones (blocks);
 454   find_many_sub_basic_blocks (blocks);
 455   purge_all_dead_edges (0);
 456   sbitmap_free (blocks);
 457
 458   compact_blocks ();
 459 #ifdef ENABLE_CHECKING
 460   verify_flow_info();
 461 #endif
 462 }
 463
 464 struct tree_opt_pass pass_expand =
 465 {
 466   "expand",                             /* name */
 467   NULL,                                 /* gate */
 468   tree_expand_cfg,                      /* execute */
 469   NULL,                                 /* sub */
 470   NULL,                                 /* next */
 471   0,                                    /* static_pass_number */
 472   TV_EXPAND,                            /* tv_id */
 473   /* ??? If TER is enabled, we actually receive GENERIC.  */
 474   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 475   PROP_rtl,                             /* properties_provided */
 476   PROP_gimple_leh,                      /* properties_destroyed */
 477   0,                                    /* todo_flags_start */
 478   0                                     /* todo_flags_finish */
 479 };
 480