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