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