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
  39
  40 /* A subroutine of expand_gimple_basic_block.  Expand one COND_EXPR.
  41    Returns a new basic block if we've terminated the current basic
  42    block and created a new one.  */
  43
  44 static basic_block
  45 expand_gimple_cond_expr (basic_block bb, tree stmt)
  46 {
  47   basic_block new_bb, dest;
  48   edge new_edge;
  49   edge true_edge;
  50   edge false_edge;
  51   tree pred = COND_EXPR_COND (stmt);
  52   tree then_exp = COND_EXPR_THEN (stmt);
  53   tree else_exp = COND_EXPR_ELSE (stmt);
  54   rtx last;
  55
  56   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
  57   if (EXPR_LOCUS (stmt))
  58     {
  59       emit_line_note (*(EXPR_LOCUS (stmt)));
  60       record_block_change (TREE_BLOCK (stmt));
  61     }
  62
  63   /* These flags have no purpose in RTL land.  */
  64   true_edge->flags &= ~EDGE_TRUE_VALUE;
  65   false_edge->flags &= ~EDGE_FALSE_VALUE;
  66
  67   /* We can either have a pure conditional jump with one fallthru edge or
  68      two-way jump that needs to be decomposed into two basic blocks.  */
  69   if (TREE_CODE (then_exp) == GOTO_EXPR && IS_EMPTY_STMT (else_exp))
  70     {
  71       jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
  72       return NULL;
  73     }
  74   if (TREE_CODE (else_exp) == GOTO_EXPR && IS_EMPTY_STMT (then_exp))
  75     {
  76       jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
  77       return NULL;
  78     }
  79   if (TREE_CODE (then_exp) != GOTO_EXPR || TREE_CODE (else_exp) != GOTO_EXPR)
  80     abort ();
  81
  82   jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
  83   last = get_last_insn ();
  84   expand_expr (else_exp, const0_rtx, VOIDmode, 0);
  85
  86   BB_END (bb) = last;
  87   if (BARRIER_P (BB_END (bb)))
  88     BB_END (bb) = PREV_INSN (BB_END (bb));
  89   update_bb_for_insn (bb);
  90
  91   new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
  92   dest = false_edge->dest;
  93   redirect_edge_succ (false_edge, new_bb);
  94   false_edge->flags |= EDGE_FALLTHRU;
  95   new_bb->count = false_edge->count;
  96   new_bb->frequency = EDGE_FREQUENCY (false_edge);
  97   new_edge = make_edge (new_bb, dest, 0);
  98   new_edge->probability = REG_BR_PROB_BASE;
  99   new_edge->count = new_bb->count;
 100   if (BARRIER_P (BB_END (new_bb)))
 101     BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
 102   update_bb_for_insn (new_bb);
 103
 104   if (dump_file)
 105     {
 106       dump_bb (bb, dump_file, 0);
 107       dump_bb (new_bb, dump_file, 0);
 108     }
 109
 110   return new_bb;
 111 }
 112
 113 /* A subroutine of expand_gimple_basic_block.  Expand one CALL_EXPR
 114    that has CALL_EXPR_TAILCALL set.  Returns a new basic block if we've
 115    terminated the current basic block and created a new one.  */
 116
 117 static basic_block
 118 expand_gimple_tailcall (basic_block bb, tree stmt)
 119 {
 120   rtx last = get_last_insn ();
 121
 122   expand_expr_stmt (stmt);
 123
 124   for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
 125     {
 126       if (CALL_P (last) && SIBLING_CALL_P (last))
 127         {
 128           edge e;
 129           int probability = 0;
 130           gcov_type count = 0;
 131
 132           do_pending_stack_adjust ();
 133           e = bb->succ;
 134           while (e)
 135             {
 136               edge next = e->succ_next;
 137
 138               if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 139                 {
 140                   if (e->dest != EXIT_BLOCK_PTR)
 141                     {
 142                       e->dest->count -= e->count;
 143                       e->dest->frequency -= EDGE_FREQUENCY (e);
 144                       if (e->dest->count < 0)
 145                         e->dest->count = 0;
 146                       if (e->dest->frequency < 0)
 147                         e->dest->frequency = 0;
 148                     }
 149                   count += e->count;
 150                   probability += e->probability;
 151                   remove_edge (e);
 152                 }
 153
 154               e = next;
 155             }
 156
 157           /* This is somewhat ugly: the call_expr expander often emits
 158              instructions after the sibcall (to perform the function
 159              return).  These confuse the find_sub_basic_blocks code,
 160              so we need to get rid of these.  */
 161           last = NEXT_INSN (last);
 162           if (!BARRIER_P (last))
 163             abort ();
 164           while (NEXT_INSN (last))
 165             {
 166               /* For instance an sqrt builtin expander expands if with
 167                  sibcall in the then and label for `else`.  */
 168               if (LABEL_P (NEXT_INSN (last)))
 169                 break;
 170               delete_insn (NEXT_INSN (last));
 171             }
 172           e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
 173           e->probability += probability;
 174           e->count += count;
 175           BB_END (bb) = last;
 176           update_bb_for_insn (bb);
 177           if (NEXT_INSN (last))
 178             bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 179           else
 180             return bb;
 181         }
 182     }
 183
 184   return NULL;
 185 }
 186
 187 /* Expand basic block BB from GIMPLE trees to RTL.  */
 188
 189 static basic_block
 190 expand_gimple_basic_block (basic_block bb, FILE * dump_file)
 191 {
 192   block_stmt_iterator bsi = bsi_start (bb);
 193   tree stmt = NULL;
 194   rtx note, last;
 195   edge e;
 196
 197   if (dump_file)
 198     {
 199       tree_register_cfg_hooks ();
 200       dump_bb (bb, dump_file, 0);
 201       rtl_register_cfg_hooks ();
 202     }
 203
 204   if (!bsi_end_p (bsi))
 205     stmt = bsi_stmt (bsi);
 206
 207   if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
 208     {
 209       last = get_last_insn ();
 210
 211       expand_expr_stmt (stmt);
 212
 213       /* Java emits line number notes in the top of labels.
 214          ??? Make this go away once line number notes are obsoleted.  */
 215       BB_HEAD (bb) = NEXT_INSN (last);
 216       if (NOTE_P (BB_HEAD (bb)))
 217         BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
 218       bsi_next (&bsi);
 219       note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
 220     }
 221   else
 222     note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
 223
 224   NOTE_BASIC_BLOCK (note) = bb;
 225
 226   e = bb->succ;
 227   while (e)
 228     {
 229       edge next = e->succ_next;
 230
 231       /* Clear EDGE_EXECUTABLE.  This flag is never used in the backend.  */
 232       e->flags &= ~EDGE_EXECUTABLE;
 233
 234       /* At the moment not all abnormal edges match the RTL representation.
 235          It is safe to remove them here as find_sub_basic_blocks will
 236          rediscover them.  In the future we should get this fixed properly.  */
 237       if (e->flags & EDGE_ABNORMAL)
 238         remove_edge (e);
 239
 240       e = next;
 241     }
 242
 243   for (; !bsi_end_p (bsi); bsi_next (&bsi))
 244     {
 245       tree stmt = bsi_stmt (bsi);
 246       basic_block new_bb = NULL;
 247
 248       if (!stmt)
 249         continue;
 250
 251       /* Expand this statement, then evaluate the resulting RTL and
 252          fixup the CFG accordingly.  */
 253       if (TREE_CODE (stmt) == COND_EXPR)
 254         new_bb = expand_gimple_cond_expr (bb, stmt);
 255       else
 256         {
 257           tree call = get_call_expr_in (stmt);
 258           if (call && CALL_EXPR_TAILCALL (call))
 259             new_bb = expand_gimple_tailcall (bb, stmt);
 260           else
 261             expand_expr_stmt (stmt);
 262         }
 263
 264       if (new_bb)
 265         return new_bb;
 266     }
 267
 268   do_pending_stack_adjust ();
 269
 270   /* Find the the block tail.  The last insn is the block is the insn
 271      before a barrier and/or table jump insn.  */
 272   last = get_last_insn ();
 273   if (BARRIER_P (last))
 274     last = PREV_INSN (last);
 275   if (JUMP_TABLE_DATA_P (last))
 276     last = PREV_INSN (PREV_INSN (last));
 277   BB_END (bb) = last;
 278
 279   if (dump_file)
 280     dump_bb (bb, dump_file, 0);
 281   update_bb_for_insn (bb);
 282
 283   return bb;
 284 }
 285
 286
 287 /* Create a basic block for initialization code.  */
 288
 289 static basic_block
 290 construct_init_block (void)
 291 {
 292   basic_block init_block, first_block;
 293   edge e;
 294
 295   expand_start_bindings_and_block (0, NULL_TREE);
 296
 297   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 298     if (e->dest == ENTRY_BLOCK_PTR->next_bb)
 299       break;
 300
 301   init_block = create_basic_block (NEXT_INSN (get_insns ()),
 302                                    get_last_insn (),
 303                                    ENTRY_BLOCK_PTR);
 304   init_block->frequency = ENTRY_BLOCK_PTR->frequency;
 305   init_block->count = ENTRY_BLOCK_PTR->count;
 306   if (e)
 307     {
 308       first_block = e->dest;
 309       redirect_edge_succ (e, init_block);
 310       e = make_edge (init_block, first_block, EDGE_FALLTHRU);
 311     }
 312   else
 313     e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 314   e->probability = REG_BR_PROB_BASE;
 315   e->count = ENTRY_BLOCK_PTR->count;
 316
 317   update_bb_for_insn (init_block);
 318   return init_block;
 319 }
 320
 321
 322 /* Create a block containing landing pads and similar stuff.  */
 323
 324 static void
 325 construct_exit_block (void)
 326 {
 327   rtx head = get_last_insn ();
 328   rtx end;
 329   basic_block exit_block;
 330   edge e, e2, next;
 331
 332   /* Make sure the locus is set to the end of the function, so that
 333      epilogue line numbers and warnings are set properly.  */
 334 #ifdef USE_MAPPED_LOCATION
 335   if (cfun->function_end_locus != UNKNOWN_LOCATION)
 336 #else
 337   if (cfun->function_end_locus.file)
 338 #endif
 339     input_location = cfun->function_end_locus;
 340
 341   /* The following insns belong to the top scope.  */
 342   record_block_change (DECL_INITIAL (current_function_decl));
 343
 344   expand_end_bindings (NULL_TREE, 1, 0);
 345
 346   /* Generate rtl for function exit.  */
 347   expand_function_end ();
 348
 349   end = get_last_insn ();
 350   if (head == end)
 351     return;
 352   while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
 353     head = NEXT_INSN (head);
 354   exit_block = create_basic_block (NEXT_INSN (head), end,
 355                                    EXIT_BLOCK_PTR->prev_bb);
 356   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 357   exit_block->count = EXIT_BLOCK_PTR->count;
 358   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 359     {
 360       next = e->pred_next;
 361       if (!(e->flags & EDGE_ABNORMAL))
 362         redirect_edge_succ (e, exit_block);
 363     }
 364   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 365   e->probability = REG_BR_PROB_BASE;
 366   e->count = EXIT_BLOCK_PTR->count;
 367   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 368     if (e2 != e)
 369       {
 370         e->count -= e2->count;
 371         exit_block->count -= e2->count;
 372         exit_block->frequency -= EDGE_FREQUENCY (e2);
 373       }
 374   if (e->count < 0)
 375     e->count = 0;
 376   if (exit_block->count < 0)
 377     exit_block->count = 0;
 378   if (exit_block->frequency < 0)
 379     exit_block->frequency = 0;
 380   update_bb_for_insn (exit_block);
 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   /* Prepare the rtl middle end to start recording block changes.  */
 407   reset_block_changes ();
 408
 409   /* Expand the variables recorded during gimple lowering.  This must
 410      occur before the call to expand_function_start to ensure that
 411      all used variables are expanded before we expand anything on the
 412      PENDING_SIZES list.  */
 413   expand_used_vars ();
 414
 415   /* Set up parameters and prepare for return, for the function.  */
 416   expand_function_start (current_function_decl);
 417
 418   /* If this function is `main', emit a call to `__main'
 419      to run global initializers, etc.  */
 420   if (DECL_NAME (current_function_decl)
 421       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 422       && DECL_FILE_SCOPE_P (current_function_decl))
 423     expand_main_function ();
 424
 425   /* Write the flowgraph to a dot file.  */
 426   rtl_register_cfg_hooks ();
 427
 428   init_block = construct_init_block ();
 429
 430   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 431     bb = expand_gimple_basic_block (bb, dump_file);
 432
 433   construct_exit_block ();
 434
 435   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 436      sorts of eh initialization.  Delay this until after the
 437      initial rtl dump so that we can see the original nesting.  */
 438   convert_from_eh_region_ranges ();
 439
 440   rebuild_jump_labels (get_insns ());
 441   find_exception_handler_labels ();
 442
 443   blocks = sbitmap_alloc (last_basic_block);
 444   sbitmap_ones (blocks);
 445   find_many_sub_basic_blocks (blocks);
 446   purge_all_dead_edges (0);
 447   sbitmap_free (blocks);
 448
 449   compact_blocks ();
 450 #ifdef ENABLE_CHECKING
 451   verify_flow_info();
 452 #endif
 453 }
 454
 455 struct tree_opt_pass pass_expand =
 456 {
 457   "expand",                             /* name */
 458   NULL,                                 /* gate */
 459   tree_expand_cfg,                      /* execute */
 460   NULL,                                 /* sub */
 461   NULL,                                 /* next */
 462   0,                                    /* static_pass_number */
 463   TV_EXPAND,                            /* tv_id */
 464   /* ??? If TER is enabled, we actually receive GENERIC.  */
 465   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 466   PROP_rtl,                             /* properties_provided */
 467   PROP_gimple_leh,                      /* properties_destroyed */
 468   0,                                    /* todo_flags_start */
 469   0                                     /* todo_flags_finish */
 470 };