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_value (stmt, 0, 0);
  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                 if (cfun->dont_emit_block_notes)
 123                   record_block_change (TREE_BLOCK (stmt));
 124               }
 125
 126             /* These flags have no purpose in RTL land.  */
 127             true_edge->flags &= ~EDGE_TRUE_VALUE;
 128             false_edge->flags &= ~EDGE_FALSE_VALUE;
 129
 130             /* We can either have a pure conditional jump with one fallthru
 131                edge or two-way jump that needs to be decomposed into two
 132                basic blocks.  */
 133             if (TREE_CODE (then_exp) == GOTO_EXPR
 134                 && TREE_CODE (else_exp) == NOP_EXPR)
 135               {
 136                 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
 137                 break;
 138               }
 139             if (TREE_CODE (else_exp) == GOTO_EXPR
 140                 && TREE_CODE (then_exp) == NOP_EXPR)
 141               {
 142                 jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
 143                 break;
 144               }
 145             if (TREE_CODE (then_exp) != GOTO_EXPR
 146                 || TREE_CODE (else_exp) != GOTO_EXPR)
 147               abort ();
 148
 149             jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
 150             last = get_last_insn ();
 151             expand_expr (else_exp, const0_rtx, VOIDmode, 0);
 152
 153             BB_END (bb) = last;
 154             if (GET_CODE (BB_END (bb)) == BARRIER)
 155               BB_END (bb) = PREV_INSN (BB_END (bb));
 156             update_bb_for_insn (bb);
 157
 158             new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 159             dest = false_edge->dest;
 160             redirect_edge_succ (false_edge, new_bb);
 161             false_edge->flags |= EDGE_FALLTHRU;
 162             new_bb->count = false_edge->count;
 163             new_bb->frequency = EDGE_FREQUENCY (false_edge);
 164             new_edge = make_edge (new_bb, dest, 0);
 165             new_edge->probability = REG_BR_PROB_BASE;
 166             new_edge->count = new_bb->count;
 167             if (GET_CODE (BB_END (new_bb)) == BARRIER)
 168               BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
 169             update_bb_for_insn (new_bb);
 170
 171             if (dump_file)
 172               {
 173                 dump_bb (bb, dump_file, 0);
 174                 dump_bb (new_bb, dump_file, 0);
 175               }
 176             return new_bb;
 177           }
 178
 179         /* Update after expansion of sibling call.  */
 180         case CALL_EXPR:
 181         case MODIFY_EXPR:
 182         case RETURN_EXPR:
 183           expand_expr_stmt_value (stmt, 0, 0);
 184           for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
 185             {
 186               if (GET_CODE (last) == CALL_INSN && SIBLING_CALL_P (last))
 187                 {
 188                   edge e;
 189                   int probability = 0;
 190                   gcov_type count = 0;
 191
 192                   do_pending_stack_adjust ();
 193                   e = bb->succ;
 194                   while (e)
 195                     {
 196                       edge next = e->succ_next;
 197
 198                       if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 199                         {
 200                           if (e->dest != EXIT_BLOCK_PTR)
 201                             {
 202                               e->dest->count -= e->count;
 203                               e->dest->frequency -= EDGE_FREQUENCY (e);
 204                               if (e->dest->count < 0)
 205                                 e->dest->count = 0;
 206                               if (e->dest->frequency < 0)
 207                                 e->dest->frequency = 0;
 208                             }
 209                           count += e->count;
 210                           probability += e->probability;
 211                           remove_edge (e);
 212                         }
 213
 214                       e = next;
 215                     }
 216
 217                   /* This is somewhat ugly:  the call_expr expander often emits instructions
 218                      after the sibcall (to perform the function return).  These confuse the
 219                      find_sub_basic_blocks code, so we need to get rid of these.  */
 220                   last = NEXT_INSN (last);
 221                   if (GET_CODE (last) != BARRIER)
 222                     abort ();
 223                   while (NEXT_INSN (last))
 224                     {
 225                       /* For instance an sqrt builtin expander expands if with
 226                          sibcall in the then and label for `else`.  */
 227                       if (GET_CODE (NEXT_INSN (last)) == CODE_LABEL)
 228                         break;
 229                       delete_insn (NEXT_INSN (last));
 230                     }
 231                   e = make_edge (bb, EXIT_BLOCK_PTR,
 232                                      EDGE_ABNORMAL | EDGE_SIBCALL);
 233                   e->probability += probability;
 234                   e->count += count;
 235                   BB_END (bb) = last;
 236                   update_bb_for_insn (bb);
 237                   if (NEXT_INSN (last))
 238                     bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 239                   else
 240                     return bb;
 241                 }
 242             }
 243           break;
 244
 245         default:
 246           expand_expr_stmt_value (stmt, 0, 0);
 247           break;
 248         }
 249     }
 250
 251   do_pending_stack_adjust ();
 252
 253   /* Find the the block tail.  The last insn is the block is the insn
 254      before a barrier and/or table jump insn.  */
 255   last = get_last_insn ();
 256   if (GET_CODE (last) == BARRIER)
 257     last = PREV_INSN (last);
 258   if (JUMP_TABLE_DATA_P (last))
 259     last = PREV_INSN (PREV_INSN (last));
 260   BB_END (bb) = last;
 261
 262   if (dump_file)
 263     dump_bb (bb, dump_file, 0);
 264   update_bb_for_insn (bb);
 265   return bb;
 266 }
 267
 268
 269 /* Create a basic block for initialization code.  */
 270
 271 static basic_block
 272 construct_init_block (void)
 273 {
 274   basic_block init_block, first_block;
 275   edge e;
 276
 277   expand_start_bindings_and_block (0, NULL_TREE);
 278
 279   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 280     if (e->dest == ENTRY_BLOCK_PTR->next_bb)
 281       break;
 282
 283   init_block = create_basic_block (NEXT_INSN (get_insns ()),
 284                                    get_last_insn (),
 285                                    ENTRY_BLOCK_PTR);
 286   init_block->frequency = ENTRY_BLOCK_PTR->frequency;
 287   init_block->count = ENTRY_BLOCK_PTR->count;
 288   if (e)
 289     {
 290       first_block = e->dest;
 291       redirect_edge_succ (e, init_block);
 292       e = make_edge (init_block, first_block, EDGE_FALLTHRU);
 293     }
 294   else
 295     e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 296   e->probability = REG_BR_PROB_BASE;
 297   e->count = ENTRY_BLOCK_PTR->count;
 298
 299   update_bb_for_insn (init_block);
 300   return init_block;
 301 }
 302
 303
 304 /* Create a block containing landing pads and similar stuff.  */
 305
 306 static void
 307 construct_exit_block (void)
 308 {
 309   rtx head = get_last_insn ();
 310   rtx end;
 311   basic_block exit_block;
 312   edge e, e2, next;
 313
 314   /* Make sure the locus is set to the end of the function, so that
 315      epilogue line numbers and warnings are set properly.  */
 316 #ifdef USE_MAPPED_LOCATION
 317   if (cfun->function_end_locus != UNKNOWN_LOCATION)
 318 #else
 319   if (cfun->function_end_locus.file)
 320 #endif
 321     input_location = cfun->function_end_locus;
 322
 323   /* The following insns belong to the top scope.  */
 324   record_block_change (DECL_INITIAL (current_function_decl));
 325
 326   expand_end_bindings (NULL_TREE, 1, 0);
 327
 328   /* Generate rtl for function exit.  */
 329   expand_function_end ();
 330
 331   end = get_last_insn ();
 332   if (head == end)
 333     return;
 334   while (NEXT_INSN (head) && GET_CODE (NEXT_INSN (head)) == NOTE)
 335     head = NEXT_INSN (head);
 336   exit_block = create_basic_block (NEXT_INSN (head), end, EXIT_BLOCK_PTR->prev_bb);
 337   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 338   exit_block->count = EXIT_BLOCK_PTR->count;
 339   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 340     {
 341       next = e->pred_next;
 342       if (!(e->flags & EDGE_ABNORMAL))
 343         redirect_edge_succ (e, exit_block);
 344     }
 345   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 346   e->probability = REG_BR_PROB_BASE;
 347   e->count = EXIT_BLOCK_PTR->count;
 348   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 349     if (e2 != e)
 350       {
 351         e->count -= e2->count;
 352         exit_block->count -= e2->count;
 353         exit_block->frequency -= EDGE_FREQUENCY (e2);
 354       }
 355   if (e->count < 0)
 356     e->count = 0;
 357   if (exit_block->count < 0)
 358     exit_block->count = 0;
 359   if (exit_block->frequency < 0)
 360     exit_block->frequency = 0;
 361   update_bb_for_insn (exit_block);
 362 }
 363
 364 /* Called to move the SAVE_EXPRs for parameter declarations in a
 365    nested function into the nested function.  DATA is really the
 366    nested FUNCTION_DECL.  */
 367
 368 static tree
 369 set_save_expr_context (tree *tp,
 370                        int *walk_subtrees,
 371                        void *data)
 372 {
 373   if (TREE_CODE (*tp) == SAVE_EXPR && !SAVE_EXPR_CONTEXT (*tp))
 374     SAVE_EXPR_CONTEXT (*tp) = (tree) data;
 375   /* Do not walk back into the SAVE_EXPR_CONTEXT; that will cause
 376      circularity.  */
 377   else if (DECL_P (*tp))
 378     *walk_subtrees = 0;
 379
 380   return NULL;
 381 }
 382
 383
 384 /* Translate the intermediate representation contained in the CFG
 385    from GIMPLE trees to RTL.
 386
 387    We do conversion per basic block and preserve/update the tree CFG.
 388    This implies we have to do some magic as the CFG can simultaneously
 389    consist of basic blocks containing RTL and GIMPLE trees.  This can
 390    confuse the CFG hooks, so be careful to not manipulate CFG during
 391    the expansion.  */
 392
 393 static void
 394 tree_expand_cfg (void)
 395 {
 396   basic_block bb, init_block;
 397   sbitmap blocks;
 398
 399   if (dump_file)
 400     {
 401       fprintf (dump_file, "\n;; Function %s",
 402                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 403       fprintf (dump_file, " (%s)\n",
 404                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 405     }
 406
 407   /* If the function has a variably modified type, there may be
 408      SAVE_EXPRs in the parameter types.  Their context must be set to
 409      refer to this function; they cannot be expanded in the containing
 410      function.  */
 411   if (decl_function_context (current_function_decl) == current_function_decl
 412       && variably_modified_type_p (TREE_TYPE (current_function_decl)))
 413     walk_tree (&TREE_TYPE (current_function_decl), set_save_expr_context,
 414                current_function_decl, NULL);
 415
 416   /* Expand the variables recorded during gimple lowering.  This must
 417      occur before the call to expand_function_start to ensure that
 418      all used variables are expanded before we expand anything on the
 419      PENDING_SIZES list.  */
 420   expand_used_vars ();
 421
 422   /* Set up parameters and prepare for return, for the function.  */
 423   expand_function_start (current_function_decl, 0);
 424
 425   /* If this function is `main', emit a call to `__main'
 426      to run global initializers, etc.  */
 427   if (DECL_NAME (current_function_decl)
 428       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 429       && DECL_FILE_SCOPE_P (current_function_decl))
 430     expand_main_function ();
 431
 432   /* Write the flowgraph to a dot file.  */
 433   rtl_register_cfg_hooks ();
 434
 435   init_block = construct_init_block ();
 436
 437   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 438     bb = expand_block (bb, dump_file);
 439
 440   construct_exit_block ();
 441
 442   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 443      sorts of eh initialization.  Delay this until after the
 444      initial rtl dump so that we can see the original nesting.  */
 445   convert_from_eh_region_ranges ();
 446
 447   rebuild_jump_labels (get_insns ());
 448   find_exception_handler_labels ();
 449
 450   blocks = sbitmap_alloc (last_basic_block);
 451   sbitmap_ones (blocks);
 452   find_many_sub_basic_blocks (blocks);
 453   purge_all_dead_edges (0);
 454   sbitmap_free (blocks);
 455
 456   compact_blocks ();
 457 #ifdef ENABLE_CHECKING
 458   verify_flow_info();
 459 #endif
 460 }
 461
 462 struct tree_opt_pass pass_expand =
 463 {
 464   "expand",                             /* name */
 465   NULL,                                 /* gate */
 466   tree_expand_cfg,                      /* execute */
 467   NULL,                                 /* sub */
 468   NULL,                                 /* next */
 469   0,                                    /* static_pass_number */
 470   TV_EXPAND,                            /* tv_id */
 471   /* ??? If TER is enabled, we actually receive GENERIC.  */
 472   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 473   PROP_rtl,                             /* properties_provided */
 474   PROP_gimple_leh,                      /* properties_destroyed */
 475   0,                                    /* todo_flags_start */
 476   0                                     /* todo_flags_finish */
 477 };
 478