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