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