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   /* We hard-wired immediate_size_expand to zero above.
 315      expand_function_end will decrement this variable.  So, we set the
 316      variable to one here, so that after the decrement it will remain
 317      zero.  */
 318   immediate_size_expand = 1;
 319
 320   /* Make sure the locus is set to the end of the function, so that
 321      epilogue line numbers and warnings are set properly.  */
 322   if (cfun->function_end_locus.file)
 323     input_location = cfun->function_end_locus;
 324
 325   /* The following insns belong to the top scope.  */
 326   record_block_change (DECL_INITIAL (current_function_decl));
 327
 328   expand_end_bindings (NULL_TREE, 1, 0);
 329
 330   /* Generate rtl for function exit.  */
 331   expand_function_end ();
 332
 333   end = get_last_insn ();
 334   if (head == end)
 335     return;
 336   while (NEXT_INSN (head) && GET_CODE (NEXT_INSN (head)) == NOTE)
 337     head = NEXT_INSN (head);
 338   exit_block = create_basic_block (NEXT_INSN (head), end, EXIT_BLOCK_PTR->prev_bb);
 339   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 340   exit_block->count = EXIT_BLOCK_PTR->count;
 341   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 342     {
 343       next = e->pred_next;
 344       if (!(e->flags & EDGE_ABNORMAL))
 345         redirect_edge_succ (e, exit_block);
 346     }
 347   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 348   e->probability = REG_BR_PROB_BASE;
 349   e->count = EXIT_BLOCK_PTR->count;
 350   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 351     if (e2 != e)
 352       {
 353         e->count -= e2->count;
 354         exit_block->count -= e2->count;
 355         exit_block->frequency -= EDGE_FREQUENCY (e2);
 356       }
 357   if (e->count < 0)
 358     e->count = 0;
 359   if (exit_block->count < 0)
 360     exit_block->count = 0;
 361   if (exit_block->frequency < 0)
 362     exit_block->frequency = 0;
 363   update_bb_for_insn (exit_block);
 364 }
 365
 366 /* Called to move the SAVE_EXPRs for parameter declarations in a
 367    nested function into the nested function.  DATA is really the
 368    nested FUNCTION_DECL.  */
 369
 370 static tree
 371 set_save_expr_context (tree *tp,
 372                        int *walk_subtrees,
 373                        void *data)
 374 {
 375   if (TREE_CODE (*tp) == SAVE_EXPR && !SAVE_EXPR_CONTEXT (*tp))
 376     SAVE_EXPR_CONTEXT (*tp) = (tree) data;
 377   /* Do not walk back into the SAVE_EXPR_CONTEXT; that will cause
 378      circularity.  */
 379   else if (DECL_P (*tp))
 380     *walk_subtrees = 0;
 381
 382   return NULL;
 383 }
 384
 385
 386 /* Translate the intermediate representation contained in the CFG
 387    from GIMPLE trees to RTL.
 388
 389    We do conversion per basic block and preserve/update the tree CFG.
 390    This implies we have to do some magic as the CFG can simultaneously
 391    consist of basic blocks containing RTL and GIMPLE trees.  This can
 392    confuse the CFG hooks, so be curefull to not manipulate CFG during
 393    the expansion.  */
 394
 395 static void
 396 tree_expand_cfg (void)
 397 {
 398   basic_block bb, init_block;
 399   sbitmap blocks;
 400
 401   if (dump_file)
 402     {
 403       fprintf (dump_file, "\n;; Function %s",
 404                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 405       fprintf (dump_file, " (%s)\n",
 406                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 407     }
 408
 409   /* If the function has a variably modified type, there may be
 410      SAVE_EXPRs in the parameter types.  Their context must be set to
 411      refer to this function; they cannot be expanded in the containing
 412      function.  */
 413   if (decl_function_context (current_function_decl) == current_function_decl
 414       && variably_modified_type_p (TREE_TYPE (current_function_decl)))
 415     walk_tree (&TREE_TYPE (current_function_decl), set_save_expr_context,
 416                current_function_decl, NULL);
 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, 0);
 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