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 non-null if we actually
 115    generated a tail call (something that might be denied by the ABI
 116    rules governing the call; see calls.c).  */
 117
 118 static basic_block
 119 expand_gimple_tailcall (basic_block bb, tree stmt)
 120 {
 121   rtx last = get_last_insn ();
 122   edge e;
 123   int probability;
 124   gcov_type count;
 125
 126   expand_expr_stmt (stmt);
 127
 128   for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
 129     if (CALL_P (last) && SIBLING_CALL_P (last))
 130       goto found;
 131
 132   return NULL;
 133
 134  found:
 135   /* ??? Wouldn't it be better to just reset any pending stack adjust?
 136      Any instructions emitted here are about to be deleted.  */
 137   do_pending_stack_adjust ();
 138
 139   /* Remove any non-eh, non-abnormal edges that don't go to exit.  */
 140   /* ??? I.e. the fallthrough edge.  HOWEVER!  If there were to be
 141      EH or abnormal edges, we shouldn't have created a tail call in
 142      the first place.  So it seems to me we should just be removing
 143      all edges here, or redirecting the existing fallthru edge to
 144      the exit block.  */
 145
 146   e = bb->succ;
 147   probability = 0;
 148   count = 0;
 149   while (e)
 150     {
 151       edge next = e->succ_next;
 152
 153       if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 154         {
 155           if (e->dest != EXIT_BLOCK_PTR)
 156             {
 157               e->dest->count -= e->count;
 158               e->dest->frequency -= EDGE_FREQUENCY (e);
 159               if (e->dest->count < 0)
 160                 e->dest->count = 0;
 161               if (e->dest->frequency < 0)
 162                 e->dest->frequency = 0;
 163             }
 164           count += e->count;
 165           probability += e->probability;
 166           remove_edge (e);
 167         }
 168
 169       e = next;
 170     }
 171
 172   /* This is somewhat ugly: the call_expr expander often emits instructions
 173      after the sibcall (to perform the function return).  These confuse the
 174      find_sub_basic_blocks code, so we need to get rid of these.  */
 175   last = NEXT_INSN (last);
 176   if (!BARRIER_P (last))
 177     abort ();
 178   while (NEXT_INSN (last))
 179     {
 180       /* For instance an sqrt builtin expander expands if with
 181          sibcall in the then and label for `else`.  */
 182       if (LABEL_P (NEXT_INSN (last)))
 183         break;
 184       delete_insn (NEXT_INSN (last));
 185     }
 186
 187   e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
 188   e->probability += probability;
 189   e->count += count;
 190   BB_END (bb) = last;
 191   update_bb_for_insn (bb);
 192
 193   if (NEXT_INSN (last))
 194     {
 195       bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
 196
 197       last = BB_END (bb);
 198       if (BARRIER_P (last))
 199         BB_END (bb) = PREV_INSN (last);
 200     }
 201
 202   return bb;
 203 }
 204
 205 /* Expand basic block BB from GIMPLE trees to RTL.  */
 206
 207 static basic_block
 208 expand_gimple_basic_block (basic_block bb, FILE * dump_file)
 209 {
 210   block_stmt_iterator bsi = bsi_start (bb);
 211   tree stmt = NULL;
 212   rtx note, last;
 213   edge e;
 214
 215   if (dump_file)
 216     {
 217       tree_register_cfg_hooks ();
 218       dump_bb (bb, dump_file, 0);
 219       rtl_register_cfg_hooks ();
 220     }
 221
 222   if (!bsi_end_p (bsi))
 223     stmt = bsi_stmt (bsi);
 224
 225   if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
 226     {
 227       last = get_last_insn ();
 228
 229       expand_expr_stmt (stmt);
 230
 231       /* Java emits line number notes in the top of labels.
 232          ??? Make this go away once line number notes are obsoleted.  */
 233       BB_HEAD (bb) = NEXT_INSN (last);
 234       if (NOTE_P (BB_HEAD (bb)))
 235         BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
 236       bsi_next (&bsi);
 237       note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
 238     }
 239   else
 240     note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
 241
 242   NOTE_BASIC_BLOCK (note) = bb;
 243
 244   e = bb->succ;
 245   while (e)
 246     {
 247       edge next = e->succ_next;
 248
 249       /* Clear EDGE_EXECUTABLE.  This flag is never used in the backend.  */
 250       e->flags &= ~EDGE_EXECUTABLE;
 251
 252       /* At the moment not all abnormal edges match the RTL representation.
 253          It is safe to remove them here as find_sub_basic_blocks will
 254          rediscover them.  In the future we should get this fixed properly.  */
 255       if (e->flags & EDGE_ABNORMAL)
 256         remove_edge (e);
 257
 258       e = next;
 259     }
 260
 261   for (; !bsi_end_p (bsi); bsi_next (&bsi))
 262     {
 263       tree stmt = bsi_stmt (bsi);
 264       basic_block new_bb = NULL;
 265
 266       if (!stmt)
 267         continue;
 268
 269       /* Expand this statement, then evaluate the resulting RTL and
 270          fixup the CFG accordingly.  */
 271       if (TREE_CODE (stmt) == COND_EXPR)
 272         new_bb = expand_gimple_cond_expr (bb, stmt);
 273       else
 274         {
 275           tree call = get_call_expr_in (stmt);
 276           if (call && CALL_EXPR_TAILCALL (call))
 277             new_bb = expand_gimple_tailcall (bb, stmt);
 278           else
 279             expand_expr_stmt (stmt);
 280         }
 281
 282       if (new_bb)
 283         return new_bb;
 284     }
 285
 286   do_pending_stack_adjust ();
 287
 288   /* Find the the block tail.  The last insn is the block is the insn
 289      before a barrier and/or table jump insn.  */
 290   last = get_last_insn ();
 291   if (BARRIER_P (last))
 292     last = PREV_INSN (last);
 293   if (JUMP_TABLE_DATA_P (last))
 294     last = PREV_INSN (PREV_INSN (last));
 295   BB_END (bb) = last;
 296
 297   if (dump_file)
 298     dump_bb (bb, dump_file, 0);
 299   update_bb_for_insn (bb);
 300
 301   return bb;
 302 }
 303
 304
 305 /* Create a basic block for initialization code.  */
 306
 307 static basic_block
 308 construct_init_block (void)
 309 {
 310   basic_block init_block, first_block;
 311   edge e;
 312
 313   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 314     if (e->dest == ENTRY_BLOCK_PTR->next_bb)
 315       break;
 316
 317   init_block = create_basic_block (NEXT_INSN (get_insns ()),
 318                                    get_last_insn (),
 319                                    ENTRY_BLOCK_PTR);
 320   init_block->frequency = ENTRY_BLOCK_PTR->frequency;
 321   init_block->count = ENTRY_BLOCK_PTR->count;
 322   if (e)
 323     {
 324       first_block = e->dest;
 325       redirect_edge_succ (e, init_block);
 326       e = make_edge (init_block, first_block, EDGE_FALLTHRU);
 327     }
 328   else
 329     e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 330   e->probability = REG_BR_PROB_BASE;
 331   e->count = ENTRY_BLOCK_PTR->count;
 332
 333   update_bb_for_insn (init_block);
 334   return init_block;
 335 }
 336
 337
 338 /* Create a block containing landing pads and similar stuff.  */
 339
 340 static void
 341 construct_exit_block (void)
 342 {
 343   rtx head = get_last_insn ();
 344   rtx end;
 345   basic_block exit_block;
 346   edge e, e2, next;
 347
 348   /* Make sure the locus is set to the end of the function, so that
 349      epilogue line numbers and warnings are set properly.  */
 350 #ifdef USE_MAPPED_LOCATION
 351   if (cfun->function_end_locus != UNKNOWN_LOCATION)
 352 #else
 353   if (cfun->function_end_locus.file)
 354 #endif
 355     input_location = cfun->function_end_locus;
 356
 357   /* The following insns belong to the top scope.  */
 358   record_block_change (DECL_INITIAL (current_function_decl));
 359
 360   /* Generate rtl for function exit.  */
 361   expand_function_end ();
 362
 363   end = get_last_insn ();
 364   if (head == end)
 365     return;
 366   while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
 367     head = NEXT_INSN (head);
 368   exit_block = create_basic_block (NEXT_INSN (head), end,
 369                                    EXIT_BLOCK_PTR->prev_bb);
 370   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 371   exit_block->count = EXIT_BLOCK_PTR->count;
 372   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 373     {
 374       next = e->pred_next;
 375       if (!(e->flags & EDGE_ABNORMAL))
 376         redirect_edge_succ (e, exit_block);
 377     }
 378   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 379   e->probability = REG_BR_PROB_BASE;
 380   e->count = EXIT_BLOCK_PTR->count;
 381   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 382     if (e2 != e)
 383       {
 384         e->count -= e2->count;
 385         exit_block->count -= e2->count;
 386         exit_block->frequency -= EDGE_FREQUENCY (e2);
 387       }
 388   if (e->count < 0)
 389     e->count = 0;
 390   if (exit_block->count < 0)
 391     exit_block->count = 0;
 392   if (exit_block->frequency < 0)
 393     exit_block->frequency = 0;
 394   update_bb_for_insn (exit_block);
 395 }
 396
 397 /* Translate the intermediate representation contained in the CFG
 398    from GIMPLE trees to RTL.
 399
 400    We do conversion per basic block and preserve/update the tree CFG.
 401    This implies we have to do some magic as the CFG can simultaneously
 402    consist of basic blocks containing RTL and GIMPLE trees.  This can
 403    confuse the CFG hooks, so be careful to not manipulate CFG during
 404    the expansion.  */
 405
 406 static void
 407 tree_expand_cfg (void)
 408 {
 409   basic_block bb, init_block;
 410   sbitmap blocks;
 411
 412   if (dump_file)
 413     {
 414       fprintf (dump_file, "\n;; Function %s",
 415                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 416       fprintf (dump_file, " (%s)\n",
 417                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 418     }
 419
 420   /* Prepare the rtl middle end to start recording block changes.  */
 421   reset_block_changes ();
 422
 423   /* Expand the variables recorded during gimple lowering.  This must
 424      occur before the call to expand_function_start to ensure that
 425      all used variables are expanded before we expand anything on the
 426      PENDING_SIZES list.  */
 427   expand_used_vars ();
 428
 429   /* Set up parameters and prepare for return, for the function.  */
 430   expand_function_start (current_function_decl);
 431
 432   /* If this function is `main', emit a call to `__main'
 433      to run global initializers, etc.  */
 434   if (DECL_NAME (current_function_decl)
 435       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 436       && DECL_FILE_SCOPE_P (current_function_decl))
 437     expand_main_function ();
 438
 439   /* Write the flowgraph to a dot file.  */
 440   rtl_register_cfg_hooks ();
 441
 442   init_block = construct_init_block ();
 443
 444   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 445     bb = expand_gimple_basic_block (bb, dump_file);
 446
 447   construct_exit_block ();
 448
 449   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 450      sorts of eh initialization.  Delay this until after the
 451      initial rtl dump so that we can see the original nesting.  */
 452   convert_from_eh_region_ranges ();
 453
 454   rebuild_jump_labels (get_insns ());
 455   find_exception_handler_labels ();
 456
 457   blocks = sbitmap_alloc (last_basic_block);
 458   sbitmap_ones (blocks);
 459   find_many_sub_basic_blocks (blocks);
 460   purge_all_dead_edges (0);
 461   sbitmap_free (blocks);
 462
 463   compact_blocks ();
 464 #ifdef ENABLE_CHECKING
 465   verify_flow_info();
 466 #endif
 467 }
 468
 469 struct tree_opt_pass pass_expand =
 470 {
 471   "expand",                             /* name */
 472   NULL,                                 /* gate */
 473   tree_expand_cfg,                      /* execute */
 474   NULL,                                 /* sub */
 475   NULL,                                 /* next */
 476   0,                                    /* static_pass_number */
 477   TV_EXPAND,                            /* tv_id */
 478   /* ??? If TER is enabled, we actually receive GENERIC.  */
 479   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 480   PROP_rtl,                             /* properties_provided */
 481   PROP_gimple_leh,                      /* properties_destroyed */
 482   0,                                    /* todo_flags_start */
 483   0                                     /* todo_flags_finish */
 484 };