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