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     case SWITCH_EXPR:
 282       /* Easy cases.  If the last statement of the block implies
 283          control transfer, then we can't fall through.  */
 284       return false;
 285
 286     case COND_EXPR:
 287       if (block_may_fallthru (COND_EXPR_THEN (stmt)))
 288         return true;
 289       return block_may_fallthru (COND_EXPR_ELSE (stmt));
 290
 291     case BIND_EXPR:
 292       return block_may_fallthru (BIND_EXPR_BODY (stmt));
 293
 294     case TRY_FINALLY_EXPR:
 295       return block_may_fallthru (TREE_OPERAND (stmt, 1));
 296
 297     case MODIFY_EXPR:
 298       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
 299         stmt = TREE_OPERAND (stmt, 1);
 300       else
 301         return true;
 302       /* FALLTHRU */
 303
 304     case CALL_EXPR:
 305       /* Functions that do not return do not fall through.  */
 306       return (call_expr_flags (stmt) & ECF_NORETURN) == 0;
 307
 308     default:
 309       return true;
 310     }
 311 }
 312
 313 /* Lowers a cond_expr TSI.  DATA is passed through the recursion.  */
 314
 315 static void
 316 lower_cond_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 317 {
 318   tree stmt = tsi_stmt (*tsi);
 319   bool then_is_goto, else_is_goto;
 320   tree then_branch, else_branch;
 321   tree then_goto, else_goto;
 322
 323   then_branch = COND_EXPR_THEN (stmt);
 324   else_branch = COND_EXPR_ELSE (stmt);
 325
 326   lower_stmt_body (then_branch, data);
 327   lower_stmt_body (else_branch, data);
 328
 329   then_goto = expr_only (then_branch);
 330   then_is_goto = then_goto && simple_goto_p (then_goto);
 331
 332   else_goto = expr_only (else_branch);
 333   else_is_goto = else_goto && simple_goto_p (else_goto);
 334
 335   if (!then_is_goto || !else_is_goto)
 336     {
 337       tree then_label, else_label, end_label, t;
 338
 339       then_label = NULL_TREE;
 340       else_label = NULL_TREE;
 341       end_label = NULL_TREE;
 342
 343       /* Replace the cond_expr with explicit gotos.  */
 344       if (!then_is_goto)
 345         {
 346           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 347           if (TREE_SIDE_EFFECTS (then_branch))
 348             then_label = t;
 349           else
 350             end_label = t;
 351           then_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 352         }
 353
 354       if (!else_is_goto)
 355         {
 356           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 357           if (TREE_SIDE_EFFECTS (else_branch))
 358             else_label = t;
 359           else
 360             {
 361               /* Both THEN and ELSE can be no-ops if one or both contained an
 362                  empty BIND_EXPR that was associated with the toplevel block
 363                  of an inlined function.  In that case remove_useless_stmts
 364                  can't have cleaned things up for us; kill the whole
 365                  conditional now.  */
 366               if (end_label)
 367                 {
 368                   tsi_delink (tsi);
 369                   return;
 370                 }
 371               else
 372                 end_label = t;
 373             }
 374           else_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 375         }
 376
 377       if (then_label)
 378         {
 379           bool may_fallthru = block_may_fallthru (then_branch);
 380
 381           tsi_link_after (tsi, then_label, TSI_CONTINUE_LINKING);
 382           tsi_link_after (tsi, then_branch, TSI_CONTINUE_LINKING);
 383
 384           if (else_label && may_fallthru)
 385             {
 386               end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 387               t = build_and_jump (&LABEL_EXPR_LABEL (end_label));
 388               tsi_link_after (tsi, t, TSI_CONTINUE_LINKING);
 389             }
 390         }
 391
 392       if (else_label)
 393         {
 394           tsi_link_after (tsi, else_label, TSI_CONTINUE_LINKING);
 395           tsi_link_after (tsi, else_branch, TSI_CONTINUE_LINKING);
 396         }
 397
 398       if (end_label)
 399         tsi_link_after (tsi, end_label, TSI_CONTINUE_LINKING);
 400     }
 401
 402   COND_EXPR_THEN (stmt) = then_goto;
 403   COND_EXPR_ELSE (stmt) = else_goto;
 404
 405   tsi_next (tsi);
 406 }
 407
 408 static void
 409 lower_return_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 410 {
 411   tree stmt = tsi_stmt (*tsi);
 412   tree value, t, label;
 413
 414   /* Extract the value being returned.  */
 415   value = TREE_OPERAND (stmt, 0);
 416   if (value && TREE_CODE (value) == MODIFY_EXPR)
 417     value = TREE_OPERAND (value, 1);
 418
 419   /* Match this up with an existing return statement that's been created.  */
 420   for (t = data->return_statements; t ; t = TREE_CHAIN (t))
 421     {
 422       tree tvalue = TREE_OPERAND (TREE_VALUE (t), 0);
 423       if (tvalue && TREE_CODE (tvalue) == MODIFY_EXPR)
 424         tvalue = TREE_OPERAND (tvalue, 1);
 425
 426       if (value == tvalue)
 427         {
 428           label = TREE_PURPOSE (t);
 429           goto found;
 430         }
 431     }
 432
 433   /* Not found.  Create a new label and record the return statement.  */
 434   label = create_artificial_label ();
 435   data->return_statements = tree_cons (label, stmt, data->return_statements);
 436
 437   /* Generate a goto statement and remove the return statement.  */
 438  found:
 439   t = build (GOTO_EXPR, void_type_node, label);
 440   SET_EXPR_LOCUS (t, EXPR_LOCUS (stmt));
 441   tsi_link_before (tsi, t, TSI_SAME_STMT);
 442   tsi_delink (tsi);
 443 }
 444 \f
 445
 446 /* Record the variables in VARS.  */
 447
 448 void
 449 record_vars (tree vars)
 450 {
 451   for (; vars; vars = TREE_CHAIN (vars))
 452     {
 453       tree var = vars;
 454
 455       /* Nothing to do in this case.  */
 456       if (DECL_EXTERNAL (var))
 457         continue;
 458       if (TREE_CODE (var) == FUNCTION_DECL)
 459         continue;
 460
 461       /* Record the variable.  */
 462       cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
 463                                              cfun->unexpanded_var_list);
 464     }
 465 }
 466
 467 /* Check whether to expand a variable VAR.  */
 468
 469 static bool
 470 expand_var_p (tree var)
 471 {
 472   struct var_ann_d *ann;
 473
 474   if (TREE_CODE (var) != VAR_DECL)
 475     return true;
 476
 477   /* Leave statics and externals alone.  */
 478   if (TREE_STATIC (var) || DECL_EXTERNAL (var))
 479     return true;
 480
 481   /* Remove all unused local variables.  */
 482   ann = var_ann (var);
 483   if (!ann || !ann->used)
 484     return false;
 485
 486   return true;
 487 }
 488
 489 /* Throw away variables that are unused.  */
 490
 491 static void
 492 remove_useless_vars (void)
 493 {
 494   tree var, *cell;
 495   FILE *df = NULL;
 496
 497   if (dump_file && (dump_flags & TDF_DETAILS))
 498     {
 499       df = dump_file;
 500       fputs ("Discarding as unused:\n", df);
 501     }
 502
 503   for (cell = &cfun->unexpanded_var_list; *cell; )
 504     {
 505       var = TREE_VALUE (*cell);
 506
 507       if (!expand_var_p (var))
 508         {
 509           if (df)
 510             {
 511               fputs ("  ", df);
 512               print_generic_expr (df, var, dump_flags);
 513               fputc ('\n', df);
 514             }
 515
 516           *cell = TREE_CHAIN (*cell);
 517           continue;
 518         }
 519
 520       cell = &TREE_CHAIN (*cell);
 521     }
 522
 523   if (df)
 524     fputc ('\n', df);
 525 }
 526
 527 struct tree_opt_pass pass_remove_useless_vars =
 528 {
 529   "vars",                               /* name */
 530   NULL,                                 /* gate */
 531   remove_useless_vars,                  /* execute */
 532   NULL,                                 /* sub */
 533   NULL,                                 /* next */
 534   0,                                    /* static_pass_number */
 535   0,                                    /* tv_id */
 536   0,                                    /* properties_required */
 537   0,                                    /* properties_provided */
 538   0,                                    /* properties_destroyed */
 539   0,                                    /* todo_flags_start */
 540   TODO_dump_func,                       /* todo_flags_finish */
 541   0                                     /* letter */
 542 };
 543
 544 /* Mark BLOCK used if it has a used variable in it, then recurse over its
 545    subblocks.  */
 546
 547 static void
 548 mark_blocks_with_used_vars (tree block)
 549 {
 550   tree var;
 551   tree subblock;
 552
 553   if (!TREE_USED (block))
 554     {
 555       for (var = BLOCK_VARS (block);
 556            var;
 557            var = TREE_CHAIN (var))
 558         {
 559           if (TREE_USED (var))
 560             {
 561               TREE_USED (block) = true;
 562               break;
 563             }
 564         }
 565     }
 566   for (subblock = BLOCK_SUBBLOCKS (block);
 567        subblock;
 568        subblock = BLOCK_CHAIN (subblock))
 569     mark_blocks_with_used_vars (subblock);
 570 }
 571
 572 /* Mark the used attribute on blocks correctly.  */
 573
 574 static void
 575 mark_used_blocks (void)
 576 {
 577   mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl));
 578 }
 579
 580
 581 struct tree_opt_pass pass_mark_used_blocks =
 582 {
 583   "blocks",                             /* name */
 584   NULL,                                 /* gate */
 585   mark_used_blocks,                     /* execute */
 586   NULL,                                 /* sub */
 587   NULL,                                 /* next */
 588   0,                                    /* static_pass_number */
 589   0,                                    /* tv_id */
 590   0,                                    /* properties_required */
 591   0,                                    /* properties_provided */
 592   0,                                    /* properties_destroyed */
 593   0,                                    /* todo_flags_start */
 594   TODO_dump_func,                       /* todo_flags_finish */
 595   0                                     /* letter */
 596 };