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 whether a TRY_CATCH expression can fall through.
 267    This is a subroutine of block_may_fallthru.  */
 268
 269 static bool
 270 try_catch_may_fallthru (tree stmt)
 271 {
 272   tree_stmt_iterator i;
 273
 274   /* If the TRY block can fall through, the whole TRY_CATCH can
 275      fall through.  */
 276   if (block_may_fallthru (TREE_OPERAND (stmt, 0)))
 277     return true;
 278
 279   i = tsi_start (TREE_OPERAND (stmt, 1));
 280   switch (TREE_CODE (tsi_stmt (i)))
 281     {
 282     case CATCH_EXPR:
 283       /* We expect to see a sequence of CATCH_EXPR trees, each with a
 284          catch expression and a body.  The whole TRY_CATCH may fall
 285          through iff any of the catch bodies falls through.  */
 286       for (; !tsi_end_p (i); tsi_next (&i))
 287         {
 288           if (block_may_fallthru (CATCH_BODY (tsi_stmt (i))))
 289             return true;
 290         }
 291       return false;
 292
 293     case EH_FILTER_EXPR:
 294       /* If the exception does not match EH_FILTER_TYPES, we will
 295          execute EH_FILTER_FAILURE, and we will fall through if that
 296          falls through.  If the exception does match EH_FILTER_TYPES,
 297          we will fall through.  We don't know which exceptions may be
 298          generated, so we just check for EH_FILTER_TYPES being NULL,
 299          in which case we know that that the exception does not
 300          match.  */
 301       return (EH_FILTER_TYPES (tsi_stmt (i)) != NULL
 302               || block_may_fallthru (EH_FILTER_FAILURE (tsi_stmt (i))));
 303
 304     default:
 305       /* This case represents statements to be executed when an
 306          exception occurs.  Those statements are implicitly followed
 307          by a RESX_EXPR to resume execution after the exception.  So
 308          in this case the TRY_CATCH never falls through.  */
 309       return false;
 310     }
 311 }
 312
 313 /* Try to determine if we can fall out of the bottom of BLOCK.  This guess
 314    need not be 100% accurate; simply be conservative and return true if we
 315    don't know.  This is used only to avoid stupidly generating extra code.
 316    If we're wrong, we'll just delete the extra code later.  */
 317
 318 bool
 319 block_may_fallthru (tree block)
 320 {
 321   tree stmt = expr_last (block);
 322
 323   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
 324     {
 325     case GOTO_EXPR:
 326     case RETURN_EXPR:
 327     case RESX_EXPR:
 328       /* Easy cases.  If the last statement of the block implies
 329          control transfer, then we can't fall through.  */
 330       return false;
 331
 332     case SWITCH_EXPR:
 333       /* If SWITCH_LABELS is set, this is lowered, and represents a
 334          branch to a selected label and hence can not fall through.
 335          Otherwise SWITCH_BODY is set, and the switch can fall
 336          through.  */
 337       return SWITCH_LABELS (stmt) == NULL_TREE;
 338
 339     case COND_EXPR:
 340       if (block_may_fallthru (COND_EXPR_THEN (stmt)))
 341         return true;
 342       return block_may_fallthru (COND_EXPR_ELSE (stmt));
 343
 344     case BIND_EXPR:
 345       return block_may_fallthru (BIND_EXPR_BODY (stmt));
 346
 347     case TRY_CATCH_EXPR:
 348       return try_catch_may_fallthru (stmt);
 349
 350     case TRY_FINALLY_EXPR:
 351       return block_may_fallthru (TREE_OPERAND (stmt, 1));
 352
 353     case MODIFY_EXPR:
 354       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
 355         stmt = TREE_OPERAND (stmt, 1);
 356       else
 357         return true;
 358       /* FALLTHRU */
 359
 360     case CALL_EXPR:
 361       /* Functions that do not return do not fall through.  */
 362       return (call_expr_flags (stmt) & ECF_NORETURN) == 0;
 363
 364     default:
 365       return true;
 366     }
 367 }
 368
 369 /* Lowers a cond_expr TSI.  DATA is passed through the recursion.  */
 370
 371 static void
 372 lower_cond_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 373 {
 374   tree stmt = tsi_stmt (*tsi);
 375   bool then_is_goto, else_is_goto;
 376   tree then_branch, else_branch;
 377   tree then_goto, else_goto;
 378
 379   then_branch = COND_EXPR_THEN (stmt);
 380   else_branch = COND_EXPR_ELSE (stmt);
 381
 382   lower_stmt_body (then_branch, data);
 383   lower_stmt_body (else_branch, data);
 384
 385   then_goto = expr_only (then_branch);
 386   then_is_goto = then_goto && simple_goto_p (then_goto);
 387
 388   else_goto = expr_only (else_branch);
 389   else_is_goto = else_goto && simple_goto_p (else_goto);
 390
 391   if (!then_is_goto || !else_is_goto)
 392     {
 393       tree then_label, else_label, end_label, t;
 394
 395       then_label = NULL_TREE;
 396       else_label = NULL_TREE;
 397       end_label = NULL_TREE;
 398
 399       /* Replace the cond_expr with explicit gotos.  */
 400       if (!then_is_goto)
 401         {
 402           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 403           if (TREE_SIDE_EFFECTS (then_branch))
 404             then_label = t;
 405           else
 406             end_label = t;
 407           then_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 408         }
 409
 410       if (!else_is_goto)
 411         {
 412           t = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 413           if (TREE_SIDE_EFFECTS (else_branch))
 414             else_label = t;
 415           else
 416             {
 417               /* Both THEN and ELSE can be no-ops if one or both contained an
 418                  empty BIND_EXPR that was associated with the toplevel block
 419                  of an inlined function.  In that case remove_useless_stmts
 420                  can't have cleaned things up for us; kill the whole
 421                  conditional now.  */
 422               if (end_label)
 423                 {
 424                   tsi_delink (tsi);
 425                   return;
 426                 }
 427               else
 428                 end_label = t;
 429             }
 430           else_goto = build_and_jump (&LABEL_EXPR_LABEL (t));
 431         }
 432
 433       if (then_label)
 434         {
 435           bool may_fallthru = block_may_fallthru (then_branch);
 436
 437           tsi_link_after (tsi, then_label, TSI_CONTINUE_LINKING);
 438           tsi_link_after (tsi, then_branch, TSI_CONTINUE_LINKING);
 439
 440           if (else_label && may_fallthru)
 441             {
 442               end_label = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
 443               t = build_and_jump (&LABEL_EXPR_LABEL (end_label));
 444               tsi_link_after (tsi, t, TSI_CONTINUE_LINKING);
 445             }
 446         }
 447
 448       if (else_label)
 449         {
 450           tsi_link_after (tsi, else_label, TSI_CONTINUE_LINKING);
 451           tsi_link_after (tsi, else_branch, TSI_CONTINUE_LINKING);
 452         }
 453
 454       if (end_label)
 455         tsi_link_after (tsi, end_label, TSI_CONTINUE_LINKING);
 456     }
 457
 458   COND_EXPR_THEN (stmt) = then_goto;
 459   COND_EXPR_ELSE (stmt) = else_goto;
 460
 461   tsi_next (tsi);
 462 }
 463
 464 static void
 465 lower_return_expr (tree_stmt_iterator *tsi, struct lower_data *data)
 466 {
 467   tree stmt = tsi_stmt (*tsi);
 468   tree value, t, label;
 469
 470   /* Extract the value being returned.  */
 471   value = TREE_OPERAND (stmt, 0);
 472   if (value && TREE_CODE (value) == MODIFY_EXPR)
 473     value = TREE_OPERAND (value, 1);
 474
 475   /* Match this up with an existing return statement that's been created.  */
 476   for (t = data->return_statements; t ; t = TREE_CHAIN (t))
 477     {
 478       tree tvalue = TREE_OPERAND (TREE_VALUE (t), 0);
 479       if (tvalue && TREE_CODE (tvalue) == MODIFY_EXPR)
 480         tvalue = TREE_OPERAND (tvalue, 1);
 481
 482       if (value == tvalue)
 483         {
 484           label = TREE_PURPOSE (t);
 485           goto found;
 486         }
 487     }
 488
 489   /* Not found.  Create a new label and record the return statement.  */
 490   label = create_artificial_label ();
 491   data->return_statements = tree_cons (label, stmt, data->return_statements);
 492
 493   /* Generate a goto statement and remove the return statement.  */
 494  found:
 495   t = build (GOTO_EXPR, void_type_node, label);
 496   SET_EXPR_LOCUS (t, EXPR_LOCUS (stmt));
 497   tsi_link_before (tsi, t, TSI_SAME_STMT);
 498   tsi_delink (tsi);
 499 }
 500 \f
 501
 502 /* Record the variables in VARS.  */
 503
 504 void
 505 record_vars (tree vars)
 506 {
 507   for (; vars; vars = TREE_CHAIN (vars))
 508     {
 509       tree var = vars;
 510
 511       /* Nothing to do in this case.  */
 512       if (DECL_EXTERNAL (var))
 513         continue;
 514       if (TREE_CODE (var) == FUNCTION_DECL)
 515         continue;
 516
 517       /* Record the variable.  */
 518       cfun->unexpanded_var_list = tree_cons (NULL_TREE, var,
 519                                              cfun->unexpanded_var_list);
 520     }
 521 }
 522
 523 /* Check whether to expand a variable VAR.  */
 524
 525 static bool
 526 expand_var_p (tree var)
 527 {
 528   struct var_ann_d *ann;
 529
 530   if (TREE_CODE (var) != VAR_DECL)
 531     return true;
 532
 533   /* Leave statics and externals alone.  */
 534   if (TREE_STATIC (var) || DECL_EXTERNAL (var))
 535     return true;
 536
 537   /* Remove all unused local variables.  */
 538   ann = var_ann (var);
 539   if (!ann || !ann->used)
 540     return false;
 541
 542   return true;
 543 }
 544
 545 /* Throw away variables that are unused.  */
 546
 547 static void
 548 remove_useless_vars (void)
 549 {
 550   tree var, *cell;
 551   FILE *df = NULL;
 552
 553   if (dump_file && (dump_flags & TDF_DETAILS))
 554     {
 555       df = dump_file;
 556       fputs ("Discarding as unused:\n", df);
 557     }
 558
 559   for (cell = &cfun->unexpanded_var_list; *cell; )
 560     {
 561       var = TREE_VALUE (*cell);
 562
 563       if (!expand_var_p (var))
 564         {
 565           if (df)
 566             {
 567               fputs ("  ", df);
 568               print_generic_expr (df, var, dump_flags);
 569               fputc ('\n', df);
 570             }
 571
 572           *cell = TREE_CHAIN (*cell);
 573           continue;
 574         }
 575
 576       cell = &TREE_CHAIN (*cell);
 577     }
 578
 579   if (df)
 580     fputc ('\n', df);
 581 }
 582
 583 struct tree_opt_pass pass_remove_useless_vars =
 584 {
 585   "vars",                               /* name */
 586   NULL,                                 /* gate */
 587   remove_useless_vars,                  /* execute */
 588   NULL,                                 /* sub */
 589   NULL,                                 /* next */
 590   0,                                    /* static_pass_number */
 591   0,                                    /* tv_id */
 592   0,                                    /* properties_required */
 593   0,                                    /* properties_provided */
 594   0,                                    /* properties_destroyed */
 595   0,                                    /* todo_flags_start */
 596   TODO_dump_func,                       /* todo_flags_finish */
 597   0                                     /* letter */
 598 };
 599
 600 /* Mark BLOCK used if it has a used variable in it, then recurse over its
 601    subblocks.  */
 602
 603 static void
 604 mark_blocks_with_used_vars (tree block)
 605 {
 606   tree var;
 607   tree subblock;
 608
 609   if (!TREE_USED (block))
 610     {
 611       for (var = BLOCK_VARS (block);
 612            var;
 613            var = TREE_CHAIN (var))
 614         {
 615           if (TREE_USED (var))
 616             {
 617               TREE_USED (block) = true;
 618               break;
 619             }
 620         }
 621     }
 622   for (subblock = BLOCK_SUBBLOCKS (block);
 623        subblock;
 624        subblock = BLOCK_CHAIN (subblock))
 625     mark_blocks_with_used_vars (subblock);
 626 }
 627
 628 /* Mark the used attribute on blocks correctly.  */
 629
 630 static void
 631 mark_used_blocks (void)
 632 {
 633   mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl));
 634 }
 635
 636
 637 struct tree_opt_pass pass_mark_used_blocks =
 638 {
 639   "blocks",                             /* name */
 640   NULL,                                 /* gate */
 641   mark_used_blocks,                     /* execute */
 642   NULL,                                 /* sub */
 643   NULL,                                 /* next */
 644   0,                                    /* static_pass_number */
 645   0,                                    /* tv_id */
 646   0,                                    /* properties_required */
 647   0,                                    /* properties_provided */
 648   0,                                    /* properties_destroyed */
 649   0,                                    /* todo_flags_start */
 650   TODO_dump_func,                       /* todo_flags_finish */
 651   0                                     /* letter */
 652 };