gcc/gimple-low.c

   1 /* GIMPLE lowering pass.  Converts High GIMPLE into Low GIMPLE.
   2
   3    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "varray.h"
  28 #include "gimple.h"
  29 #include "tree-iterator.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 /* The differences between High GIMPLE and Low GIMPLE are the
  45    following:
  46
  47    1- Lexical scopes are removed (i.e., GIMPLE_BIND disappears).
  48
  49    2- GIMPLE_TRY and GIMPLE_CATCH are converted to abnormal control
  50       flow and exception regions are built as an on-the-side region
  51       hierarchy (See tree-eh.c:lower_eh_constructs).
  52
  53    3- Multiple identical return statements are grouped into a single
  54       return and gotos to the unique return site.  */
  55
  56 /* Match a return statement with a label.  During lowering, we identify
  57    identical return statements and replace duplicates with a jump to
  58    the corresponding label.  */
  59 struct return_statements_t
  60 {
  61   tree label;
  62   gimple stmt;
  63 };
  64 typedef struct return_statements_t return_statements_t;
  65
  66 DEF_VEC_O(return_statements_t);
  67 DEF_VEC_ALLOC_O(return_statements_t,heap);
  68
  69 struct lower_data
  70 {
  71   /* Block the current statement belongs to.  */
  72   tree block;
  73
  74   /* A vector of label and return statements to be moved to the end
  75      of the function.  */
  76   VEC(return_statements_t,heap) *return_statements;
  77
  78   /* True if the function calls __builtin_setjmp.  */
  79   bool calls_builtin_setjmp;
  80 };
  81
  82 static void lower_stmt (gimple_stmt_iterator *, struct lower_data *);
  83 static void lower_gimple_bind (gimple_stmt_iterator *, struct lower_data *);
  84 static void lower_gimple_return (gimple_stmt_iterator *, struct lower_data *);
  85 static void lower_builtin_setjmp (gimple_stmt_iterator *);
  86
  87
  88 /* Lower the body of current_function_decl from High GIMPLE into Low
  89    GIMPLE.  */
  90
  91 static unsigned int
  92 lower_function_body (void)
  93 {
  94   struct lower_data data;
  95   gimple_seq body = gimple_body (current_function_decl);
  96   gimple_seq lowered_body;
  97   gimple_stmt_iterator i;
  98   gimple bind;
  99   tree t;
 100   gimple x;
 101
 102   /* The gimplifier should've left a body of exactly one statement,
 103      namely a GIMPLE_BIND.  */
 104   gcc_assert (gimple_seq_first (body) == gimple_seq_last (body)
 105               && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND);
 106
 107   memset (&data, 0, sizeof (data));
 108   data.block = DECL_INITIAL (current_function_decl);
 109   BLOCK_SUBBLOCKS (data.block) = NULL_TREE;
 110   BLOCK_CHAIN (data.block) = NULL_TREE;
 111   TREE_ASM_WRITTEN (data.block) = 1;
 112   data.return_statements = VEC_alloc (return_statements_t, heap, 8);
 113
 114   bind = gimple_seq_first_stmt (body);
 115   lowered_body = NULL;
 116   gimple_seq_add_stmt (&lowered_body, bind);
 117   i = gsi_start (lowered_body);
 118   lower_gimple_bind (&i, &data);
 119
 120   /* Once the old body has been lowered, replace it with the new
 121      lowered sequence.  */
 122   gimple_set_body (current_function_decl, lowered_body);
 123
 124   i = gsi_last (lowered_body);
 125
 126   /* If the function falls off the end, we need a null return statement.
 127      If we've already got one in the return_statements vector, we don't
 128      need to do anything special.  Otherwise build one by hand.  */
 129   if (gimple_seq_may_fallthru (lowered_body)
 130       && (VEC_empty (return_statements_t, data.return_statements)
 131           || gimple_return_retval (VEC_last (return_statements_t,
 132                                    data.return_statements)->stmt) != NULL))
 133     {
 134       x = gimple_build_return (NULL);
 135       gimple_set_location (x, cfun->function_end_locus);
 136       gsi_insert_after (&i, x, GSI_CONTINUE_LINKING);
 137     }
 138
 139   /* If we lowered any return statements, emit the representative
 140      at the end of the function.  */
 141   while (!VEC_empty (return_statements_t, data.return_statements))
 142     {
 143       return_statements_t t;
 144
 145       /* Unfortunately, we can't use VEC_pop because it returns void for
 146          objects.  */
 147       t = *VEC_last (return_statements_t, data.return_statements);
 148       VEC_truncate (return_statements_t,
 149                     data.return_statements,
 150                     VEC_length (return_statements_t,
 151                                 data.return_statements) - 1);
 152
 153       x = gimple_build_label (t.label);
 154       gsi_insert_after (&i, x, GSI_CONTINUE_LINKING);
 155
 156       /* Remove the line number from the representative return statement.
 157          It now fills in for many such returns.  Failure to remove this
 158          will result in incorrect results for coverage analysis.  */
 159       gimple_set_location (t.stmt, UNKNOWN_LOCATION);
 160       gsi_insert_after (&i, t.stmt, GSI_CONTINUE_LINKING);
 161     }
 162
 163   /* If the function calls __builtin_setjmp, we need to emit the computed
 164      goto that will serve as the unique dispatcher for all the receivers.  */
 165   if (data.calls_builtin_setjmp)
 166     {
 167       tree disp_label, disp_var, arg;
 168
 169       /* Build 'DISP_LABEL:' and insert.  */
 170       disp_label = create_artificial_label ();
 171       /* This mark will create forward edges from every call site.  */
 172       DECL_NONLOCAL (disp_label) = 1;
 173       cfun->has_nonlocal_label = 1;
 174       x = gimple_build_label (disp_label);
 175       gsi_insert_after (&i, x, GSI_CONTINUE_LINKING);
 176
 177       /* Build 'DISP_VAR = __builtin_setjmp_dispatcher (DISP_LABEL);'
 178          and insert.  */
 179       disp_var = create_tmp_var (ptr_type_node, "setjmpvar");
 180       arg = build_addr (disp_label, current_function_decl);
 181       t = implicit_built_in_decls[BUILT_IN_SETJMP_DISPATCHER];
 182       x = gimple_build_call (t, 1, arg);
 183       gimple_call_set_lhs (x, disp_var);
 184
 185       /* Build 'goto DISP_VAR;' and insert.  */
 186       gsi_insert_after (&i, x, GSI_CONTINUE_LINKING);
 187       x = gimple_build_goto (disp_var);
 188       gsi_insert_after (&i, x, GSI_CONTINUE_LINKING);
 189     }
 190
 191   gcc_assert (data.block == DECL_INITIAL (current_function_decl));
 192   BLOCK_SUBBLOCKS (data.block)
 193     = blocks_nreverse (BLOCK_SUBBLOCKS (data.block));
 194
 195   clear_block_marks (data.block);
 196   VEC_free(return_statements_t, heap, data.return_statements);
 197   return 0;
 198 }
 199
 200 struct gimple_opt_pass pass_lower_cf =
 201 {
 202  {
 203   GIMPLE_PASS,
 204   "lower",                              /* name */
 205   NULL,                                 /* gate */
 206   lower_function_body,                  /* execute */
 207   NULL,                                 /* sub */
 208   NULL,                                 /* next */
 209   0,                                    /* static_pass_number */
 210   0,                                    /* tv_id */
 211   PROP_gimple_any,                      /* properties_required */
 212   PROP_gimple_lcf,                      /* properties_provided */
 213   0,                                    /* properties_destroyed */
 214   0,                                    /* todo_flags_start */
 215   TODO_dump_func                        /* todo_flags_finish */
 216  }
 217 };
 218
 219
 220 /* Lower sequence SEQ.  Unlike gimplification the statements are not relowered
 221    when they are changed -- if this has to be done, the lowering routine must
 222    do it explicitly.  DATA is passed through the recursion.  */
 223
 224 static void
 225 lower_sequence (gimple_seq seq, struct lower_data *data)
 226 {
 227   gimple_stmt_iterator gsi;
 228
 229   for (gsi = gsi_start (seq); !gsi_end_p (gsi); )
 230     lower_stmt (&gsi, data);
 231 }
 232
 233
 234 /* Lower the OpenMP directive statement pointed by GSI.  DATA is
 235    passed through the recursion.  */
 236
 237 static void
 238 lower_omp_directive (gimple_stmt_iterator *gsi, struct lower_data *data)
 239 {
 240   gimple stmt;
 241
 242   stmt = gsi_stmt (*gsi);
 243
 244   lower_sequence (gimple_omp_body (stmt), data);
 245   gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
 246   gsi_insert_seq_before (gsi, gimple_omp_body (stmt), GSI_SAME_STMT);
 247   gimple_omp_set_body (stmt, NULL);
 248   gsi_remove (gsi, false);
 249 }
 250
 251
 252 /* Lower statement GSI.  DATA is passed through the recursion.  */
 253
 254 static void
 255 lower_stmt (gimple_stmt_iterator *gsi, struct lower_data *data)
 256 {
 257   gimple stmt = gsi_stmt (*gsi);
 258
 259   gimple_set_block (stmt, data->block);
 260
 261   switch (gimple_code (stmt))
 262     {
 263     case GIMPLE_BIND:
 264       lower_gimple_bind (gsi, data);
 265       return;
 266
 267     case GIMPLE_COND:
 268       /* The gimplifier has already lowered this into gotos.  */
 269       break;
 270
 271     case GIMPLE_RETURN:
 272       lower_gimple_return (gsi, data);
 273       return;
 274
 275     case GIMPLE_TRY:
 276       lower_sequence (gimple_try_eval (stmt), data);
 277       lower_sequence (gimple_try_cleanup (stmt), data);
 278       break;
 279
 280     case GIMPLE_CATCH:
 281       lower_sequence (gimple_catch_handler (stmt), data);
 282       break;
 283
 284     case GIMPLE_EH_FILTER:
 285       lower_sequence (gimple_eh_filter_failure (stmt), data);
 286       break;
 287
 288     case GIMPLE_NOP:
 289     case GIMPLE_ASM:
 290     case GIMPLE_ASSIGN:
 291     case GIMPLE_GOTO:
 292     case GIMPLE_PREDICT:
 293     case GIMPLE_LABEL:
 294     case GIMPLE_SWITCH:
 295     case GIMPLE_CHANGE_DYNAMIC_TYPE:
 296     case GIMPLE_OMP_FOR:
 297     case GIMPLE_OMP_SECTIONS:
 298     case GIMPLE_OMP_SECTIONS_SWITCH:
 299     case GIMPLE_OMP_SECTION:
 300     case GIMPLE_OMP_SINGLE:
 301     case GIMPLE_OMP_MASTER:
 302     case GIMPLE_OMP_ORDERED:
 303     case GIMPLE_OMP_CRITICAL:
 304     case GIMPLE_OMP_RETURN:
 305     case GIMPLE_OMP_ATOMIC_LOAD:
 306     case GIMPLE_OMP_ATOMIC_STORE:
 307     case GIMPLE_OMP_CONTINUE:
 308       break;
 309
 310     case GIMPLE_CALL:
 311       {
 312         tree decl = gimple_call_fndecl (stmt);
 313
 314         if (decl
 315             && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
 316             && DECL_FUNCTION_CODE (decl) == BUILT_IN_SETJMP)
 317           {
 318             data->calls_builtin_setjmp = true;
 319             lower_builtin_setjmp (gsi);
 320             return;
 321           }
 322       }
 323       break;
 324
 325     case GIMPLE_OMP_PARALLEL:
 326     case GIMPLE_OMP_TASK:
 327       lower_omp_directive (gsi, data);
 328       return;
 329
 330     default:
 331       gcc_unreachable ();
 332     }
 333
 334   gsi_next (gsi);
 335 }
 336
 337 /* Lower a bind_expr TSI.  DATA is passed through the recursion.  */
 338
 339 static void
 340 lower_gimple_bind (gimple_stmt_iterator *gsi, struct lower_data *data)
 341 {
 342   tree old_block = data->block;
 343   gimple stmt = gsi_stmt (*gsi);
 344   tree new_block = gimple_bind_block (stmt);
 345
 346   if (new_block)
 347     {
 348       if (new_block == old_block)
 349         {
 350           /* The outermost block of the original function may not be the
 351              outermost statement chain of the gimplified function.  So we
 352              may see the outermost block just inside the function.  */
 353           gcc_assert (new_block == DECL_INITIAL (current_function_decl));
 354           new_block = NULL;
 355         }
 356       else
 357         {
 358           /* We do not expect to handle duplicate blocks.  */
 359           gcc_assert (!TREE_ASM_WRITTEN (new_block));
 360           TREE_ASM_WRITTEN (new_block) = 1;
 361
 362           /* Block tree may get clobbered by inlining.  Normally this would
 363              be fixed in rest_of_decl_compilation using block notes, but
 364              since we are not going to emit them, it is up to us.  */
 365           BLOCK_CHAIN (new_block) = BLOCK_SUBBLOCKS (old_block);
 366           BLOCK_SUBBLOCKS (old_block) = new_block;
 367           BLOCK_SUBBLOCKS (new_block) = NULL_TREE;
 368           BLOCK_SUPERCONTEXT (new_block) = old_block;
 369
 370           data->block = new_block;
 371         }
 372     }
 373
 374   record_vars (gimple_bind_vars (stmt));
 375   lower_sequence (gimple_bind_body (stmt), data);
 376
 377   if (new_block)
 378     {
 379       gcc_assert (data->block == new_block);
 380
 381       BLOCK_SUBBLOCKS (new_block)
 382         = blocks_nreverse (BLOCK_SUBBLOCKS (new_block));
 383       data->block = old_block;
 384     }
 385
 386   /* The GIMPLE_BIND no longer carries any useful information -- kill it.  */
 387   gsi_insert_seq_before (gsi, gimple_bind_body (stmt), GSI_SAME_STMT);
 388   gsi_remove (gsi, false);
 389 }
 390
 391 /* Try to determine whether a TRY_CATCH expression can fall through.
 392    This is a subroutine of block_may_fallthru.  */
 393
 394 static bool
 395 try_catch_may_fallthru (const_tree stmt)
 396 {
 397   tree_stmt_iterator i;
 398
 399   /* If the TRY block can fall through, the whole TRY_CATCH can
 400      fall through.  */
 401   if (block_may_fallthru (TREE_OPERAND (stmt, 0)))
 402     return true;
 403
 404   i = tsi_start (TREE_OPERAND (stmt, 1));
 405   switch (TREE_CODE (tsi_stmt (i)))
 406     {
 407     case CATCH_EXPR:
 408       /* We expect to see a sequence of CATCH_EXPR trees, each with a
 409          catch expression and a body.  The whole TRY_CATCH may fall
 410          through iff any of the catch bodies falls through.  */
 411       for (; !tsi_end_p (i); tsi_next (&i))
 412         {
 413           if (block_may_fallthru (CATCH_BODY (tsi_stmt (i))))
 414             return true;
 415         }
 416       return false;
 417
 418     case EH_FILTER_EXPR:
 419       /* The exception filter expression only matters if there is an
 420          exception.  If the exception does not match EH_FILTER_TYPES,
 421          we will execute EH_FILTER_FAILURE, and we will fall through
 422          if that falls through.  If the exception does match
 423          EH_FILTER_TYPES, the stack unwinder will continue up the
 424          stack, so we will not fall through.  We don't know whether we
 425          will throw an exception which matches EH_FILTER_TYPES or not,
 426          so we just ignore EH_FILTER_TYPES and assume that we might
 427          throw an exception which doesn't match.  */
 428       return block_may_fallthru (EH_FILTER_FAILURE (tsi_stmt (i)));
 429
 430     default:
 431       /* This case represents statements to be executed when an
 432          exception occurs.  Those statements are implicitly followed
 433          by a RESX_EXPR to resume execution after the exception.  So
 434          in this case the TRY_CATCH never falls through.  */
 435       return false;
 436     }
 437 }
 438
 439
 440 /* Same as above, but for a GIMPLE_TRY_CATCH.  */
 441
 442 static bool
 443 gimple_try_catch_may_fallthru (gimple stmt)
 444 {
 445   gimple_stmt_iterator i;
 446
 447   /* We don't handle GIMPLE_TRY_FINALLY.  */
 448   gcc_assert (gimple_try_kind (stmt) == GIMPLE_TRY_CATCH);
 449
 450   /* If the TRY block can fall through, the whole TRY_CATCH can
 451      fall through.  */
 452   if (gimple_seq_may_fallthru (gimple_try_eval (stmt)))
 453     return true;
 454
 455   i = gsi_start (gimple_try_cleanup (stmt));
 456   switch (gimple_code (gsi_stmt (i)))
 457     {
 458     case GIMPLE_CATCH:
 459       /* We expect to see a sequence of GIMPLE_CATCH stmts, each with a
 460          catch expression and a body.  The whole try/catch may fall
 461          through iff any of the catch bodies falls through.  */
 462       for (; !gsi_end_p (i); gsi_next (&i))
 463         {
 464           if (gimple_seq_may_fallthru (gimple_catch_handler (gsi_stmt (i))))
 465             return true;
 466         }
 467       return false;
 468
 469     case GIMPLE_EH_FILTER:
 470       /* The exception filter expression only matters if there is an
 471          exception.  If the exception does not match EH_FILTER_TYPES,
 472          we will execute EH_FILTER_FAILURE, and we will fall through
 473          if that falls through.  If the exception does match
 474          EH_FILTER_TYPES, the stack unwinder will continue up the
 475          stack, so we will not fall through.  We don't know whether we
 476          will throw an exception which matches EH_FILTER_TYPES or not,
 477          so we just ignore EH_FILTER_TYPES and assume that we might
 478          throw an exception which doesn't match.  */
 479       return gimple_seq_may_fallthru (gimple_eh_filter_failure (gsi_stmt (i)));
 480
 481     default:
 482       /* This case represents statements to be executed when an
 483          exception occurs.  Those statements are implicitly followed
 484          by a GIMPLE_RESX to resume execution after the exception.  So
 485          in this case the try/catch never falls through.  */
 486       return false;
 487     }
 488 }
 489
 490
 491 /* Try to determine if we can fall out of the bottom of BLOCK.  This guess
 492    need not be 100% accurate; simply be conservative and return true if we
 493    don't know.  This is used only to avoid stupidly generating extra code.
 494    If we're wrong, we'll just delete the extra code later.  */
 495
 496 bool
 497 block_may_fallthru (const_tree block)
 498 {
 499   /* This CONST_CAST is okay because expr_last returns it's argument
 500      unmodified and we assign it to a const_tree.  */
 501   const_tree stmt = expr_last (CONST_CAST_TREE(block));
 502
 503   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
 504     {
 505     case GOTO_EXPR:
 506     case RETURN_EXPR:
 507     case RESX_EXPR:
 508       /* Easy cases.  If the last statement of the block implies
 509          control transfer, then we can't fall through.  */
 510       return false;
 511
 512     case SWITCH_EXPR:
 513       /* If SWITCH_LABELS is set, this is lowered, and represents a
 514          branch to a selected label and hence can not fall through.
 515          Otherwise SWITCH_BODY is set, and the switch can fall
 516          through.  */
 517       return SWITCH_LABELS (stmt) == NULL_TREE;
 518
 519     case COND_EXPR:
 520       if (block_may_fallthru (COND_EXPR_THEN (stmt)))
 521         return true;
 522       return block_may_fallthru (COND_EXPR_ELSE (stmt));
 523
 524     case BIND_EXPR:
 525       return block_may_fallthru (BIND_EXPR_BODY (stmt));
 526
 527     case TRY_CATCH_EXPR:
 528       return try_catch_may_fallthru (stmt);
 529
 530     case TRY_FINALLY_EXPR:
 531       /* The finally clause is always executed after the try clause,
 532          so if it does not fall through, then the try-finally will not
 533          fall through.  Otherwise, if the try clause does not fall
 534          through, then when the finally clause falls through it will
 535          resume execution wherever the try clause was going.  So the
 536          whole try-finally will only fall through if both the try
 537          clause and the finally clause fall through.  */
 538       return (block_may_fallthru (TREE_OPERAND (stmt, 0))
 539               && block_may_fallthru (TREE_OPERAND (stmt, 1)));
 540
 541     case MODIFY_EXPR:
 542       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
 543         stmt = TREE_OPERAND (stmt, 1);
 544       else
 545         return true;
 546       /* FALLTHRU */
 547
 548     case CALL_EXPR:
 549       /* Functions that do not return do not fall through.  */
 550       return (call_expr_flags (stmt) & ECF_NORETURN) == 0;
 551
 552     case CLEANUP_POINT_EXPR:
 553       return block_may_fallthru (TREE_OPERAND (stmt, 0));
 554
 555     default:
 556       return true;
 557     }
 558 }
 559
 560
 561 /* Try to determine if we can continue executing the statement
 562    immediately following STMT.  This guess need not be 100% accurate;
 563    simply be conservative and return true if we don't know.  This is
 564    used only to avoid stupidly generating extra code. If we're wrong,
 565    we'll just delete the extra code later.  */
 566
 567 bool
 568 gimple_stmt_may_fallthru (gimple stmt)
 569 {
 570   if (!stmt)
 571     return true;
 572
 573   switch (gimple_code (stmt))
 574     {
 575     case GIMPLE_GOTO:
 576     case GIMPLE_RETURN:
 577     case GIMPLE_RESX:
 578       /* Easy cases.  If the last statement of the seq implies
 579          control transfer, then we can't fall through.  */
 580       return false;
 581
 582     case GIMPLE_SWITCH:
 583       /* Switch has already been lowered and represents a
 584          branch to a selected label and hence can not fall through.  */
 585       return true;
 586
 587     case GIMPLE_COND:
 588       /* GIMPLE_COND's are already lowered into a two-way branch.  They
 589          can't fall through.  */
 590       return false;
 591
 592     case GIMPLE_BIND:
 593       return gimple_seq_may_fallthru (gimple_bind_body (stmt));
 594
 595     case GIMPLE_TRY:
 596       if (gimple_try_kind (stmt) == GIMPLE_TRY_CATCH)
 597         return gimple_try_catch_may_fallthru (stmt);
 598
 599       /* It must be a GIMPLE_TRY_FINALLY.  */
 600
 601       /* The finally clause is always executed after the try clause,
 602          so if it does not fall through, then the try-finally will not
 603          fall through.  Otherwise, if the try clause does not fall
 604          through, then when the finally clause falls through it will
 605          resume execution wherever the try clause was going.  So the
 606          whole try-finally will only fall through if both the try
 607          clause and the finally clause fall through.  */
 608       return (gimple_seq_may_fallthru (gimple_try_eval (stmt))
 609               && gimple_seq_may_fallthru (gimple_try_cleanup (stmt)));
 610
 611     case GIMPLE_ASSIGN:
 612       return true;
 613
 614     case GIMPLE_CALL:
 615       /* Functions that do not return do not fall through.  */
 616       return (gimple_call_flags (stmt) & ECF_NORETURN) == 0;
 617
 618     default:
 619       return true;
 620     }
 621 }
 622
 623
 624 /* Same as gimple_stmt_may_fallthru, but for the gimple sequence SEQ.  */
 625
 626 bool
 627 gimple_seq_may_fallthru (gimple_seq seq)
 628 {
 629   return gimple_stmt_may_fallthru (gimple_seq_last_stmt (seq));
 630 }
 631
 632
 633 /* Lower a GIMPLE_RETURN GSI.  DATA is passed through the recursion.  */
 634
 635 static void
 636 lower_gimple_return (gimple_stmt_iterator *gsi, struct lower_data *data)
 637 {
 638   gimple stmt = gsi_stmt (*gsi);
 639   gimple t;
 640   int i;
 641   return_statements_t tmp_rs;
 642
 643   /* Match this up with an existing return statement that's been created.  */
 644   for (i = VEC_length (return_statements_t, data->return_statements) - 1;
 645        i >= 0; i--)
 646     {
 647       tmp_rs = *VEC_index (return_statements_t, data->return_statements, i);
 648
 649       if (gimple_return_retval (stmt) == gimple_return_retval (tmp_rs.stmt))
 650         goto found;
 651     }
 652
 653   /* Not found.  Create a new label and record the return statement.  */
 654   tmp_rs.label = create_artificial_label ();
 655   tmp_rs.stmt = stmt;
 656   VEC_safe_push (return_statements_t, heap, data->return_statements, &tmp_rs);
 657
 658   /* Generate a goto statement and remove the return statement.  */
 659  found:
 660   t = gimple_build_goto (tmp_rs.label);
 661   gimple_set_location (t, gimple_location (stmt));
 662   gsi_insert_before (gsi, t, GSI_SAME_STMT);
 663   gsi_remove (gsi, false);
 664 }
 665
 666 /* Lower a __builtin_setjmp TSI.
 667
 668    __builtin_setjmp is passed a pointer to an array of five words (not
 669    all will be used on all machines).  It operates similarly to the C
 670    library function of the same name, but is more efficient.
 671
 672    It is lowered into 3 other builtins, namely __builtin_setjmp_setup,
 673    __builtin_setjmp_dispatcher and __builtin_setjmp_receiver, but with
 674    __builtin_setjmp_dispatcher shared among all the instances; that's
 675    why it is only emitted at the end by lower_function_body.
 676
 677    After full lowering, the body of the function should look like:
 678
 679     {
 680       void * setjmpvar.0;
 681       int D.1844;
 682       int D.2844;
 683
 684       [...]
 685
 686       __builtin_setjmp_setup (&buf, &<D1847>);
 687       D.1844 = 0;
 688       goto <D1846>;
 689       <D1847>:;
 690       __builtin_setjmp_receiver (&<D1847>);
 691       D.1844 = 1;
 692       <D1846>:;
 693       if (D.1844 == 0) goto <D1848>; else goto <D1849>;
 694
 695       [...]
 696
 697       __builtin_setjmp_setup (&buf, &<D2847>);
 698       D.2844 = 0;
 699       goto <D2846>;
 700       <D2847>:;
 701       __builtin_setjmp_receiver (&<D2847>);
 702       D.2844 = 1;
 703       <D2846>:;
 704       if (D.2844 == 0) goto <D2848>; else goto <D2849>;
 705
 706       [...]
 707
 708       <D3850>:;
 709       return;
 710       <D3853>: [non-local];
 711       setjmpvar.0 = __builtin_setjmp_dispatcher (&<D3853>);
 712       goto setjmpvar.0;
 713     }
 714
 715    The dispatcher block will be both the unique destination of all the
 716    abnormal call edges and the unique source of all the abnormal edges
 717    to the receivers, thus keeping the complexity explosion localized.  */
 718
 719 static void
 720 lower_builtin_setjmp (gimple_stmt_iterator *gsi)
 721 {
 722   gimple stmt = gsi_stmt (*gsi);
 723   tree cont_label = create_artificial_label ();
 724   tree next_label = create_artificial_label ();
 725   tree dest, t, arg;
 726   gimple g;
 727
 728   /* NEXT_LABEL is the label __builtin_longjmp will jump to.  Its address is
 729      passed to both __builtin_setjmp_setup and __builtin_setjmp_receiver.  */
 730   FORCED_LABEL (next_label) = 1;
 731
 732   dest = gimple_call_lhs (stmt);
 733
 734   /* Build '__builtin_setjmp_setup (BUF, NEXT_LABEL)' and insert.  */
 735   arg = build_addr (next_label, current_function_decl);
 736   t = implicit_built_in_decls[BUILT_IN_SETJMP_SETUP];
 737   g = gimple_build_call (t, 2, gimple_call_arg (stmt, 0), arg);
 738   gimple_set_location (g, gimple_location (stmt));
 739   gsi_insert_before (gsi, g, GSI_SAME_STMT);
 740
 741   /* Build 'DEST = 0' and insert.  */
 742   if (dest)
 743     {
 744       g = gimple_build_assign (dest, fold_convert (TREE_TYPE (dest),
 745                                                    integer_zero_node));
 746       gimple_set_location (g, gimple_location (stmt));
 747       gsi_insert_before (gsi, g, GSI_SAME_STMT);
 748     }
 749
 750   /* Build 'goto CONT_LABEL' and insert.  */
 751   g = gimple_build_goto (cont_label);
 752   gsi_insert_before (gsi, g, TSI_SAME_STMT);
 753
 754   /* Build 'NEXT_LABEL:' and insert.  */
 755   g = gimple_build_label (next_label);
 756   gsi_insert_before (gsi, g, GSI_SAME_STMT);
 757
 758   /* Build '__builtin_setjmp_receiver (NEXT_LABEL)' and insert.  */
 759   arg = build_addr (next_label, current_function_decl);
 760   t = implicit_built_in_decls[BUILT_IN_SETJMP_RECEIVER];
 761   g = gimple_build_call (t, 1, arg);
 762   gimple_set_location (g, gimple_location (stmt));
 763   gsi_insert_before (gsi, g, GSI_SAME_STMT);
 764
 765   /* Build 'DEST = 1' and insert.  */
 766   if (dest)
 767     {
 768       g = gimple_build_assign (dest, fold_convert (TREE_TYPE (dest),
 769                                                    integer_one_node));
 770       gimple_set_location (g, gimple_location (stmt));
 771       gsi_insert_before (gsi, g, GSI_SAME_STMT);
 772     }
 773
 774   /* Build 'CONT_LABEL:' and insert.  */
 775   g = gimple_build_label (cont_label);
 776   gsi_insert_before (gsi, g, GSI_SAME_STMT);
 777
 778   /* Remove the call to __builtin_setjmp.  */
 779   gsi_remove (gsi, false);
 780 }
 781 \f
 782
 783 /* Record the variables in VARS into function FN.  */
 784
 785 void
 786 record_vars_into (tree vars, tree fn)
 787 {
 788   if (fn != current_function_decl)
 789     push_cfun (DECL_STRUCT_FUNCTION (fn));
 790
 791   for (; vars; vars = TREE_CHAIN (vars))
 792     {
 793       tree var = vars;
 794
 795       /* BIND_EXPRs contains also function/type/constant declarations
 796          we don't need to care about.  */
 797       if (TREE_CODE (var) != VAR_DECL)
 798         continue;
 799
 800       /* Nothing to do in this case.  */
 801       if (DECL_EXTERNAL (var))
 802         continue;
 803
 804       /* Record the variable.  */
 805       cfun->local_decls = tree_cons (NULL_TREE, var,
 806                                              cfun->local_decls);
 807     }
 808
 809   if (fn != current_function_decl)
 810     pop_cfun ();
 811 }
 812
 813
 814 /* Record the variables in VARS into current_function_decl.  */
 815
 816 void
 817 record_vars (tree vars)
 818 {
 819   record_vars_into (vars, current_function_decl);
 820 }
 821
 822
 823 /* Mark BLOCK used if it has a used variable in it, then recurse over its
 824    subblocks.  */
 825
 826 static void
 827 mark_blocks_with_used_vars (tree block)
 828 {
 829   tree var;
 830   tree subblock;
 831
 832   if (!TREE_USED (block))
 833     {
 834       for (var = BLOCK_VARS (block);
 835            var;
 836            var = TREE_CHAIN (var))
 837         {
 838           if (TREE_USED (var))
 839             {
 840               TREE_USED (block) = true;
 841               break;
 842             }
 843         }
 844     }
 845   for (subblock = BLOCK_SUBBLOCKS (block);
 846        subblock;
 847        subblock = BLOCK_CHAIN (subblock))
 848     mark_blocks_with_used_vars (subblock);
 849 }
 850
 851 /* Mark the used attribute on blocks correctly.  */
 852
 853 static unsigned int
 854 mark_used_blocks (void)
 855 {
 856   mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl));
 857   return 0;
 858 }
 859
 860
 861 struct gimple_opt_pass pass_mark_used_blocks =
 862 {
 863  {
 864   GIMPLE_PASS,
 865   "blocks",                             /* name */
 866   NULL,                                 /* gate */
 867   mark_used_blocks,                     /* execute */
 868   NULL,                                 /* sub */
 869   NULL,                                 /* next */
 870   0,                                    /* static_pass_number */
 871   0,                                    /* tv_id */
 872   0,                                    /* properties_required */
 873   0,                                    /* properties_provided */
 874   0,                                    /* properties_destroyed */
 875   0,                                    /* todo_flags_start */
 876   TODO_dump_func                        /* todo_flags_finish */
 877  }
 878 };