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