OSDN Git Service

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