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