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   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 296     if (e->dest == ENTRY_BLOCK_PTR->next_bb)
 297       break;
 298
 299   init_block = create_basic_block (NEXT_INSN (get_insns ()),
 300                                    get_last_insn (),
 301                                    ENTRY_BLOCK_PTR);
 302   init_block->frequency = ENTRY_BLOCK_PTR->frequency;
 303   init_block->count = ENTRY_BLOCK_PTR->count;
 304   if (e)
 305     {
 306       first_block = e->dest;
 307       redirect_edge_succ (e, init_block);
 308       e = make_edge (init_block, first_block, EDGE_FALLTHRU);
 309     }
 310   else
 311     e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 312   e->probability = REG_BR_PROB_BASE;
 313   e->count = ENTRY_BLOCK_PTR->count;
 314
 315   update_bb_for_insn (init_block);
 316   return init_block;
 317 }
 318
 319
 320 /* Create a block containing landing pads and similar stuff.  */
 321
 322 static void
 323 construct_exit_block (void)
 324 {
 325   rtx head = get_last_insn ();
 326   rtx end;
 327   basic_block exit_block;
 328   edge e, e2, next;
 329
 330   /* Make sure the locus is set to the end of the function, so that
 331      epilogue line numbers and warnings are set properly.  */
 332 #ifdef USE_MAPPED_LOCATION
 333   if (cfun->function_end_locus != UNKNOWN_LOCATION)
 334 #else
 335   if (cfun->function_end_locus.file)
 336 #endif
 337     input_location = cfun->function_end_locus;
 338
 339   /* The following insns belong to the top scope.  */
 340   record_block_change (DECL_INITIAL (current_function_decl));
 341
 342   /* Generate rtl for function exit.  */
 343   expand_function_end ();
 344
 345   end = get_last_insn ();
 346   if (head == end)
 347     return;
 348   while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
 349     head = NEXT_INSN (head);
 350   exit_block = create_basic_block (NEXT_INSN (head), end,
 351                                    EXIT_BLOCK_PTR->prev_bb);
 352   exit_block->frequency = EXIT_BLOCK_PTR->frequency;
 353   exit_block->count = EXIT_BLOCK_PTR->count;
 354   for (e = EXIT_BLOCK_PTR->pred; e; e = next)
 355     {
 356       next = e->pred_next;
 357       if (!(e->flags & EDGE_ABNORMAL))
 358         redirect_edge_succ (e, exit_block);
 359     }
 360   e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 361   e->probability = REG_BR_PROB_BASE;
 362   e->count = EXIT_BLOCK_PTR->count;
 363   for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
 364     if (e2 != e)
 365       {
 366         e->count -= e2->count;
 367         exit_block->count -= e2->count;
 368         exit_block->frequency -= EDGE_FREQUENCY (e2);
 369       }
 370   if (e->count < 0)
 371     e->count = 0;
 372   if (exit_block->count < 0)
 373     exit_block->count = 0;
 374   if (exit_block->frequency < 0)
 375     exit_block->frequency = 0;
 376   update_bb_for_insn (exit_block);
 377 }
 378
 379 /* Translate the intermediate representation contained in the CFG
 380    from GIMPLE trees to RTL.
 381
 382    We do conversion per basic block and preserve/update the tree CFG.
 383    This implies we have to do some magic as the CFG can simultaneously
 384    consist of basic blocks containing RTL and GIMPLE trees.  This can
 385    confuse the CFG hooks, so be careful to not manipulate CFG during
 386    the expansion.  */
 387
 388 static void
 389 tree_expand_cfg (void)
 390 {
 391   basic_block bb, init_block;
 392   sbitmap blocks;
 393
 394   if (dump_file)
 395     {
 396       fprintf (dump_file, "\n;; Function %s",
 397                (*lang_hooks.decl_printable_name) (current_function_decl, 2));
 398       fprintf (dump_file, " (%s)\n",
 399                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
 400     }
 401
 402   /* Prepare the rtl middle end to start recording block changes.  */
 403   reset_block_changes ();
 404
 405   /* Expand the variables recorded during gimple lowering.  This must
 406      occur before the call to expand_function_start to ensure that
 407      all used variables are expanded before we expand anything on the
 408      PENDING_SIZES list.  */
 409   expand_used_vars ();
 410
 411   /* Set up parameters and prepare for return, for the function.  */
 412   expand_function_start (current_function_decl);
 413
 414   /* If this function is `main', emit a call to `__main'
 415      to run global initializers, etc.  */
 416   if (DECL_NAME (current_function_decl)
 417       && MAIN_NAME_P (DECL_NAME (current_function_decl))
 418       && DECL_FILE_SCOPE_P (current_function_decl))
 419     expand_main_function ();
 420
 421   /* Write the flowgraph to a dot file.  */
 422   rtl_register_cfg_hooks ();
 423
 424   init_block = construct_init_block ();
 425
 426   FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
 427     bb = expand_gimple_basic_block (bb, dump_file);
 428
 429   construct_exit_block ();
 430
 431   /* Convert from NOTE_INSN_EH_REGION style notes, and do other
 432      sorts of eh initialization.  Delay this until after the
 433      initial rtl dump so that we can see the original nesting.  */
 434   convert_from_eh_region_ranges ();
 435
 436   rebuild_jump_labels (get_insns ());
 437   find_exception_handler_labels ();
 438
 439   blocks = sbitmap_alloc (last_basic_block);
 440   sbitmap_ones (blocks);
 441   find_many_sub_basic_blocks (blocks);
 442   purge_all_dead_edges (0);
 443   sbitmap_free (blocks);
 444
 445   compact_blocks ();
 446 #ifdef ENABLE_CHECKING
 447   verify_flow_info();
 448 #endif
 449 }
 450
 451 struct tree_opt_pass pass_expand =
 452 {
 453   "expand",                             /* name */
 454   NULL,                                 /* gate */
 455   tree_expand_cfg,                      /* execute */
 456   NULL,                                 /* sub */
 457   NULL,                                 /* next */
 458   0,                                    /* static_pass_number */
 459   TV_EXPAND,                            /* tv_id */
 460   /* ??? If TER is enabled, we actually receive GENERIC.  */
 461   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 462   PROP_rtl,                             /* properties_provided */
 463   PROP_gimple_leh,                      /* properties_destroyed */
 464   0,                                    /* todo_flags_start */
 465   0                                     /* todo_flags_finish */
 466 };