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