gcc/gimple-low.c

   1 /* Tree lowering pass.  Lowers GIMPLE into unstructured form.
   2
   3    Copyright (C) 2003, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "errors.h"
  29 #include "varray.h"
  30 #include "tree-gimple.h"
  31 #include "tree-inline.h"
  32 #include "diagnostic.h"
  33 #include "langhooks.h"
  34 #include "langhooks-def.h"
  35 #include "tree-flow.h"
  36 #include "timevar.h"
  37 #include "except.h"
  38 #include "hashtab.h"
  39 #include "flags.h"
  40 #include "function.h"
  41 #include "expr.h"
  42 #include "toplev.h"
  43 #include "tree-pass.h"
  44
  45 struct lower_data
  46 {
  47   /* Block the current statement belongs to.  */
  48   tree block;
  49
  50   /* A TREE_LIST of label and return statements to be moved to the end
  51      of the function.  */
  52   tree return_statements;
  53 };
  54
  55 static void lower_stmt (tree_stmt_iterator *, struct lower_data *);
  56 static void lower_bind_expr (tree_stmt_iterator *, struct lower_data *);
  57 static void lower_cond_expr (tree_stmt_iterator *, struct lower_data *);
  58 static void lower_return_expr (tree_stmt_iterator *, struct lower_data *);
  59 static bool expand_var_p (tree);
  60
  61 /* Lowers the body of current_function_decl.  */
  62
  63 static void
  64 lower_function_body (void)
  65 {
  66   struct lower_data data;
  67   tree *body_p = &DECL_SAVED_TREE (current_function_decl);
  68   tree bind = *body_p;
  69   tree_stmt_iterator i;
  70   tree t, x;
  71
  72   gcc_assert (TREE_CODE (bind) == BIND_EXPR);
  73
  74   data.block = DECL_INITIAL (current_function_decl);
  75   BLOCK_SUBBLOCKS (data.block) = NULL_TREE;
  76   BLOCK_CHAIN (data.block) = NULL_TREE;
  77   TREE_ASM_WRITTEN (data.block) = 1;
  78
  79   data.return_statements = NULL_TREE;
  80
  81   *body_p = alloc_stmt_list ();
  82   i = tsi_start (*body_p);
  83   tsi_link_after (&i, bind, TSI_NEW_STMT);
  84   lower_bind_expr (&i, &data);
  85
  86   i = tsi_last (*body_p);
  87
  88   /* If the function falls off the end, we need a null return statement.
  89      If we've already got one in the return_statements list, we don't
  90      need to do anything special.  Otherwise build one by hand.  */
  91   if (block_may_fallthru (*body_p)
  92       && (data.return_statements == NULL
  93           || TREE_OPERAND (TREE_VALUE (data.return_statements), 0) != NULL))
  94     {
  95       x = build (RETURN_EXPR, void_type_node, NULL);
  96       SET_EXPR_LOCATION (x, cfun->function_end_locus);
  97       tsi_link_after (&i, x, TSI_CONTINUE_LINKING);
  98     }
  99
 100   /* If we lowered any return statements, emit the representative
 101      at the end of the function.  */
 102   for (t = data.return_statements ; t ; t = TREE_CHAIN (t))
 103     {
 104       x = build (LABEL_EXPR, void_type_node, TREE_PURPOSE (t));
 105       tsi_link_after (&i, x, TSI_CONTINUE_LINKING);
 106
 107       /* Remove the line number from the representative return statement.
 108          It now fills in for many such returns.  Failure to remove this
 109          will result in incorrect results for coverage analysis.  */
 110       x = TREE_VALUE (t);
 111 #ifdef USE_MAPPED_LOCATION
 112       SET_EXPR_LOCATION (x, UNKNOWN_LOCATION);
 113 #else
 114       SET_EXPR_LOCUS (x, NULL);
 115 #endif
 116       tsi_link_after (&i, x, TSI_CONTINUE_LINKING);
 117     }
 118
 119   gcc_assert (data.block == DECL_INITIAL (current_function_decl));
 120   BLOCK_SUBBLOCKS (data.block)
 121     = blocks_nreverse (BLOCK_SUBBLOCKS (data.block));
 122
 123   clear_block_marks (data.block);
 124 }
 125
 126 struct tree_opt_pass pass_lower_cf =
 127 {
 128   "lower",                              /* name */
 129   NULL,                                 /* gate */
 130   lower_function_body,                  /* execute */
 131   NULL,                                 /* sub */
 132   NULL,                                 /* next */
 133   0,                                    /* static_pass_number */
 134   0,                                    /* tv_id */
 135   PROP_gimple_any,                      /* properties_required */
 136   PROP_gimple_lcf,                      /* properties_provided */
 137   PROP_gimple_any,                      /* properties_destroyed */
 138   0,                                    /* todo_flags_start */
 139   TODO_dump_func,                       /* todo_flags_finish */
 140   0                                     /* letter */
 141 };
 142
 143
 144 /* Lowers the EXPR.  Unlike gimplification the statements are not relowered
 145    when they are changed -- if this has to be done, the lowering routine must
 146    do it explicitly.  DATA is passed through the recursion.  */
 147
 148 void
 149 lower_stmt_body (tree expr, struct lower_data *data)
 150 {
 151   tree_stmt_iterator tsi;
 152
 153   for (tsi = tsi_start (expr); !tsi_end_p (tsi); )
 154     lower_stmt (&tsi, data);
 155 }
 156
 157 /* Lowers statement TSI.  DATA is passed through the recursion.  */
 158
 159 static void
 160 lower_stmt (tree_stmt_iterator *tsi, struct lower_data *data)
 161 {
 162   tree stmt = tsi_stmt (*tsi);
 163
 164   if (EXPR_HAS_LOCATION (stmt) && data)
 165     TREE_BLOCK (stmt) = data->block;
 166
 167   switch (TREE_CODE (stmt))
 168     {
 169     case BIND_EXPR:
 170       lower_bind_expr (tsi, data);
 171       return;
 172     case COND_EXPR:
 173       lower_cond_expr (tsi, data);
 174       return;
 175     case RETURN_EXPR:
 176       lower_return_expr (tsi, data);
 177       return;
 178
 179     case TRY_FINALLY_EXPR:
 180     case TRY_CATCH_EXPR:
 181       lower_stmt_body (TREE_OPERAND (stmt, 0), data);
 182       lower_stmt_body (TREE_OPERAND (stmt, 1), data);
 183       break;
 184     case CATCH_EXPR:
 185       lower_stmt_body (CATCH_BODY (stmt), data);
 186       break;
 187     case EH_FILTER_EXPR:
 188       lower_stmt_body (EH_FILTER_FAILURE (stmt), data);
 189       break;
 190
 191     case NOP_EXPR:
 192     case ASM_EXPR:
 193     case MODIFY_EXPR:
 194     case CALL_EXPR:
 195     case GOTO_EXPR:
 196     case LABEL_EXPR:
 197     case SWITCH_EXPR:
 198       break;
 199
 200     default:
 201 #ifdef ENABLE_CHECKING
 202       print_node_brief (stderr, "", stmt, 0);
 203       internal_error ("unexpected node");
 204 #endif
 205     case COMPOUND_EXPR:
 206       gcc_unreachable ();
 207     }
 208
 209   tsi_next (tsi);
 210 }
 211
 212 /* Lowers a bind_expr TSI.  DATA is passed through the recursion.  */
 213
 214 static void
 215 lower_bind_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 216 {
 217   tree old_block = data->block;
 218   tree stmt = tsi_stmt (*tsi);
 219   tree new_block = BIND_EXPR_BLOCK (stmt);
 220
 221   if (new_block)
 222     {
 223       if (new_block == old_block)
 224         {
 225           /* The outermost block of the original function may not be the
 226              outermost statement chain of the gimplified function.  So we
 227              may see the outermost block just inside the function.  */
 228           gcc_assert (new_block == DECL_INITIAL (current_function_decl));
 229           new_block = NULL;
 230         }
 231       else
 232         {
 233           /* We do not expect to handle duplicate blocks.  */
 234           gcc_assert (!TREE_ASM_WRITTEN (new_block));
 235           TREE_ASM_WRITTEN (new_block) = 1;
 236
 237           /* Block tree may get clobbered by inlining.  Normally this would
 238              be fixed in rest_of_decl_compilation using block notes, but
 239              since we are not going to emit them, it is up to us.  */
 240           BLOCK_CHAIN (new_block) = BLOCK_SUBBLOCKS (old_block);
 241           BLOCK_SUBBLOCKS (old_block) = new_block;
 242           BLOCK_SUBBLOCKS (new_block) = NULL_TREE;
 243           BLOCK_SUPERCONTEXT (new_block) = old_block;
 244
 245           data->block = new_block;
 246         }
 247     }
 248
 249   record_vars (BIND_EXPR_VARS (stmt));
 250   lower_stmt_body (BIND_EXPR_BODY (stmt), data);
 251
 252   if (new_block)
 253     {
 254       gcc_assert (data->block == new_block);
 255
 256       BLOCK_SUBBLOCKS (new_block)
 257         = blocks_nreverse (BLOCK_SUBBLOCKS (new_block));
 258       data->block = old_block;
 259     }
 260
 261   /* The BIND_EXPR no longer carries any useful information -- kill it.  */
 262   tsi_link_before (tsi, BIND_EXPR_BODY (stmt), TSI_SAME_STMT);
 263   tsi_delink (tsi);
 264 }
 265
 266 /* Try to determine if we can fall out of the bottom of BLOCK.  This guess
 267    need not be 100% accurate; simply be conservative and return true if we
 268    don't know.  This is used only to avoid stupidly generating extra code.
 269    If we're wrong, we'll just delete the extra code later.  */
 270
 271 bool
 272 block_may_fallthru (tree block)
 273 {
 274   tree stmt = expr_last (block);
 275
 276   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
 277     {
 278     case GOTO_EXPR:
 279     case RETURN_EXPR:
 280     case RESX_EXPR:
 281       /* Easy cases.  If the last statement of the block implies
 282          control transfer, then we can't fall through.  */
 283       return false;
 284
 285     case SWITCH_EXPR:
 286       /* If SWITCH_LABELS is set, this is lowered, and represents a
 287          branch to a selected label and hence can not fall through.
 288          Otherwise SWITCH_BODY is set, and the switch can fall
 289          through.  */
 290       return SWITCH_LABELS (stmt) != NULL_TREE;
 291
 292     case COND_EXPR:
 293       if (block_may_fallthru (COND_EXPR_THEN (stmt)))
 294         return true;
 295       return block_may_fallthru (COND_EXPR_ELSE (stmt));
 296
 297     case BIND_EXPR:
 298       return block_may_fallthru (BIND_EXPR_BODY (stmt));
 299
 300     case TRY_FINALLY_EXPR:
 301       return block_may_fallthru (TREE_OPERAND (stmt, 1));
 302
 303     case MODIFY_EXPR:
 304       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
 305         stmt = TREE_OPERAND (stmt, 1);
 306       else
 307         return true;
 308       /* FALLTHRU */
 309
 310     case CALL_EXPR:
 311       /* Functions that do not return do not fall through.  */
 312       return (call_expr_flags (stmt) & ECF_NORETURN) == 0;
 313
 314     default:
 315       return true;
 316     }
 317 }
 318
 319 /* Lowers a cond_expr TSI.  DATA is passed through the recursion.  */
 320
 321 static void
 322 lower_cond_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 323 {
 324   tree stmt = tsi_stmt (*tsi);
 325   bool then_is_goto, else_is_goto;
 326   tree then_branch, else_branch;
 327   tree then_goto, else_goto;
 328
 329   then_branch = COND_EXPR_THEN (stmt);
 330   else_branch = COND_EXPR_ELSE (stmt);
 331
 332   lower_stmt_body (then_branch, data);
 333   lower_stmt_body (else_branch, data);
 334
 335   then_goto = expr_only (then_branch);
 336   then_is_goto = then_goto && simple_goto_p (then_goto);
 337
 338   else_goto = expr_only (else_branch);
 339   else_is_goto = else_goto && simple_goto_p (else_goto);
 340
 341   if (!then_is_goto || !else_is_goto)
 342     {
 343       tree then_label, else_label, end_label, t;
 344
 345       then_label = NULL_TREE;
 346       else_label = NULL_TREE;
 347       end_label = NULL_TREE;
 348
 349       /* Replace the cond_expr with explicit gotos.  */
 350       if (!then_is_goto)
 351         {
 352           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 353           if (TREE_SIDE_EFFECTS (then_branch))
 354             then_label = t;
 355           else
 356             end_label = t;
 357           then_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 358         }
 359
 360       if (!else_is_goto)
 361         {
 362           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 363           if (TREE_SIDE_EFFECTS (else_branch))
 364             else_label = t;
 365           else
 366             {
 367               /* Both THEN and ELSE can be no-ops if one or both contained an
 368                  empty BIND_EXPR that was associated with the toplevel block
 369                  of an inlined function.  In that case remove_useless_stmts
 370                  can't have cleaned things up for us; kill the whole
 371                  conditional now.  */
 372               if (end_label)
 373                 {
 374                   tsi_delink (tsi);
 375                   return;
 376                 }
 377               else
 378                 end_label = t;
 379             }
 380           else_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 381         }
 382
 383       if (then_label)
 384         {
 385           bool may_fallthru = block_may_fallthru (then_branch);
 386
 387           tsi_link_after (tsi, then_label, TSI_CONTINUE_LINKING);
 388           tsi_link_after (tsi, then_branch, TSI_CONTINUE_LINKING);
 389
 390           if (else_label && may_fallthru)
 391             {
 392               end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 393               t = build_and_jump (&LABEL_EXPR_LABEL (end_label));
 394               tsi_link_after (tsi, t, TSI_CONTINUE_LINKING);
 395             }
 396         }
 397
 398       if (else_label)
 399         {
 400           tsi_link_after (tsi, else_label, TSI_CONTINUE_LINKING);
 401           tsi_link_after (tsi, else_branch, TSI_CONTINUE_LINKING);
 402         }
 403
 404       if (end_label)
 405         tsi_link_after (tsi, end_label, TSI_CONTINUE_LINKING);
 406     }
 407
 408   COND_EXPR_THEN (stmt) = then_goto;
 409   COND_EXPR_ELSE (stmt) = else_goto;
 410
 411   tsi_next (tsi);
 412 }
 413
 414 static void
 415 lower_return_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 416 {
 417   tree stmt = tsi_stmt (*tsi);
 418   tree value, t, label;
 419
 420   /* Extract the value being returned.  */
 421   value = TREE_OPERAND (stmt, 0);
 422   if (value && TREE_CODE (value) == MODIFY_EXPR)
 423     value = TREE_OPERAND (value, 1);
 424
 425   /* Match this up with an existing return statement that's been created.  */
 426   for (t = data->return_statements; t ; t = TREE_CHAIN (t))
 427     {
 428       tree tvalue = TREE_OPERAND (TREE_VALUE (t), 0);
 429       if (tvalue && TREE_CODE (tvalue) == MODIFY_EXPR)
 430         tvalue = TREE_OPERAND (tvalue, 1);
 431
 432       if (value == tvalue)
 433         {
 434           label = TREE_PURPOSE (t);
 435           goto found;
 436         }
 437     }
 438
 439   /* Not found.  Create a new label and record the return statement.  */
 440   label = create_artificial_label ();
 441   data->return_statements = tree_cons (label, stmt, data->return_statements);
 442
 443   /* Generate a goto statement and remove the return statement.  */
 444  found:
 445   t = build (GOTO_EXPR, void_type_node, label);
 446   SET_EXPR_LOCUS (t, EXPR_LOCUS (stmt));
 447   tsi_link_before (tsi, t, TSI_SAME_STMT);
 448   tsi_delink (tsi);
 449 }
 450 \f
 451
 452 /* Record the variables in VARS.  */
 453
 454 void
 455 record_vars (tree vars)
 456 {
 457   for (; vars; vars = TREE_CHAIN (vars))
 458     {
 459       tree var = vars;
 460
 461       /* Nothing to do in this case.  */
 462       if (DECL_EXTERNAL (var))
 463         continue;
 464       if (TREE_CODE (var) == FUNCTION_DECL)
 465         continue;
 466
 467       /* Record the variable.  */
 468       cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
 469                                              cfun->unexpanded_var_list);
 470     }
 471 }
 472
 473 /* Check whether to expand a variable VAR.  */
 474
 475 static bool
 476 expand_var_p (tree var)
 477 {
 478   struct var_ann_d *ann;
 479
 480   if (TREE_CODE (var) != VAR_DECL)
 481     return true;
 482
 483   /* Leave statics and externals alone.  */
 484   if (TREE_STATIC (var) || DECL_EXTERNAL (var))
 485     return true;
 486
 487   /* Remove all unused local variables.  */
 488   ann = var_ann (var);
 489   if (!ann || !ann->used)
 490     return false;
 491
 492   return true;
 493 }
 494
 495 /* Throw away variables that are unused.  */
 496
 497 static void
 498 remove_useless_vars (void)
 499 {
 500   tree var, *cell;
 501   FILE *df = NULL;
 502
 503   if (dump_file && (dump_flags & TDF_DETAILS))
 504     {
 505       df = dump_file;
 506       fputs ("Discarding as unused:\n", df);
 507     }
 508
 509   for (cell = &cfun->unexpanded_var_list; *cell; )
 510     {
 511       var = TREE_VALUE (*cell);
 512
 513       if (!expand_var_p (var))
 514         {
 515           if (df)
 516             {
 517               fputs ("  ", df);
 518               print_generic_expr (df, var, dump_flags);
 519               fputc ('\n', df);
 520             }
 521
 522           *cell = TREE_CHAIN (*cell);
 523           continue;
 524         }
 525
 526       cell = &TREE_CHAIN (*cell);
 527     }
 528
 529   if (df)
 530     fputc ('\n', df);
 531 }
 532
 533 struct tree_opt_pass pass_remove_useless_vars =
 534 {
 535   "vars",                               /* name */
 536   NULL,                                 /* gate */
 537   remove_useless_vars,                  /* execute */
 538   NULL,                                 /* sub */
 539   NULL,                                 /* next */
 540   0,                                    /* static_pass_number */
 541   0,                                    /* tv_id */
 542   0,                                    /* properties_required */
 543   0,                                    /* properties_provided */
 544   0,                                    /* properties_destroyed */
 545   0,                                    /* todo_flags_start */
 546   TODO_dump_func,                       /* todo_flags_finish */
 547   0                                     /* letter */
 548 };
 549
 550 /* Mark BLOCK used if it has a used variable in it, then recurse over its
 551    subblocks.  */
 552
 553 static void
 554 mark_blocks_with_used_vars (tree block)
 555 {
 556   tree var;
 557   tree subblock;
 558
 559   if (!TREE_USED (block))
 560     {
 561       for (var = BLOCK_VARS (block);
 562            var;
 563            var = TREE_CHAIN (var))
 564         {
 565           if (TREE_USED (var))
 566             {
 567               TREE_USED (block) = true;
 568               break;
 569             }
 570         }
 571     }
 572   for (subblock = BLOCK_SUBBLOCKS (block);
 573        subblock;
 574        subblock = BLOCK_CHAIN (subblock))
 575     mark_blocks_with_used_vars (subblock);
 576 }
 577
 578 /* Mark the used attribute on blocks correctly.  */
 579
 580 static void
 581 mark_used_blocks (void)
 582 {
 583   mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl));
 584 }
 585
 586
 587 struct tree_opt_pass pass_mark_used_blocks =
 588 {
 589   "blocks",                             /* name */
 590   NULL,                                 /* gate */
 591   mark_used_blocks,                     /* execute */
 592   NULL,                                 /* sub */
 593   NULL,                                 /* next */
 594   0,                                    /* static_pass_number */
 595   0,                                    /* tv_id */
 596   0,                                    /* properties_required */
 597   0,                                    /* properties_provided */
 598   0,                                    /* properties_destroyed */
 599   0,                                    /* todo_flags_start */
 600   TODO_dump_func,                       /* todo_flags_finish */
 601   0                                     /* letter */
 602 };