58592751d6e3af9f4a0903321b1a9330ebd5fc7e
[gcc.git] / gcc / cfgexpand.c
1 /* A pass for lowering trees to RTL.
2 Copyright (C) 2004 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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 "tm_p.h"
28 #include "basic-block.h"
29 #include "function.h"
30 #include "expr.h"
31 #include "langhooks.h"
32 #include "tree-flow.h"
33 #include "timevar.h"
34 #include "tree-dump.h"
35 #include "tree-pass.h"
36 #include "except.h"
37 #include "flags.h"
38 /* Expand basic block BB from GIMPLE trees to RTL. */
39
40 static basic_block
41 expand_block (basic_block bb, FILE * dump_file)
42 {
43 block_stmt_iterator bsi = bsi_start (bb);
44 tree stmt = NULL;
45 rtx note, last;
46 edge e;
47
48 if (dump_file)
49 {
50 tree_register_cfg_hooks ();
51 dump_bb (bb, dump_file, 0);
52 rtl_register_cfg_hooks ();
53 }
54
55 if (!bsi_end_p (bsi))
56 stmt = bsi_stmt (bsi);
57
58 if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
59 {
60 last = get_last_insn ();
61
62 expand_expr_stmt_value (stmt, 0, 0);
63
64 /* Java emits line number notes in the top of labels.
65 ??? Make this go away once line number notes are obsoleted. */
66 BB_HEAD (bb) = NEXT_INSN (last);
67 if (GET_CODE (BB_HEAD (bb)) == NOTE)
68 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
69 bsi_next (&bsi);
70 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
71 }
72 else
73 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
74
75 NOTE_BASIC_BLOCK (note) = bb;
76
77 e = bb->succ;
78 while (e)
79 {
80 edge next = e->succ_next;
81
82 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
83 e->flags &= ~EDGE_EXECUTABLE;
84
85 /* At the moment not all abnormal edges match the RTL representation.
86 It is safe to remove them here as find_sub_basic_blocks will
87 rediscover them. In the future we should get this fixed properly. */
88 if (e->flags & EDGE_ABNORMAL)
89 remove_edge (e);
90
91 e = next;
92 }
93
94 for (; !bsi_end_p (bsi); bsi_next (&bsi))
95 {
96 tree stmt = bsi_stmt (bsi);
97
98 last = get_last_insn ();
99
100 if (!stmt)
101 continue;
102
103 /* Expand this statement, then evaluate the resulting RTL and
104 fixup the CFG accordingly. */
105 switch (TREE_CODE (stmt))
106 {
107 case COND_EXPR:
108 {
109 basic_block new_bb, dest;
110 edge new_edge;
111 edge true_edge;
112 edge false_edge;
113 tree pred = COND_EXPR_COND (stmt);
114 tree then_exp = COND_EXPR_THEN (stmt);
115 tree else_exp = COND_EXPR_ELSE (stmt);
116 rtx last = get_last_insn ();
117
118 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
119 if (EXPR_LOCUS (stmt))
120 {
121 emit_line_note (*(EXPR_LOCUS (stmt)));
122 if (cfun->dont_emit_block_notes)
123 record_block_change (TREE_BLOCK (stmt));
124 }
125
126 /* These flags have no purpose in RTL land. */
127 true_edge->flags &= ~EDGE_TRUE_VALUE;
128 false_edge->flags &= ~EDGE_FALSE_VALUE;
129
130 /* We can either have a pure conditional jump with one fallthru
131 edge or two-way jump that needs to be decomposed into two
132 basic blocks. */
133 if (TREE_CODE (then_exp) == GOTO_EXPR
134 && TREE_CODE (else_exp) == NOP_EXPR)
135 {
136 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
137 break;
138 }
139 if (TREE_CODE (else_exp) == GOTO_EXPR
140 && TREE_CODE (then_exp) == NOP_EXPR)
141 {
142 jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
143 break;
144 }
145 if (TREE_CODE (then_exp) != GOTO_EXPR
146 || TREE_CODE (else_exp) != GOTO_EXPR)
147 abort ();
148
149 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
150 last = get_last_insn ();
151 expand_expr (else_exp, const0_rtx, VOIDmode, 0);
152
153 BB_END (bb) = last;
154 if (GET_CODE (BB_END (bb)) == BARRIER)
155 BB_END (bb) = PREV_INSN (BB_END (bb));
156 update_bb_for_insn (bb);
157
158 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
159 dest = false_edge->dest;
160 redirect_edge_succ (false_edge, new_bb);
161 false_edge->flags |= EDGE_FALLTHRU;
162 new_bb->count = false_edge->count;
163 new_bb->frequency = EDGE_FREQUENCY (false_edge);
164 new_edge = make_edge (new_bb, dest, 0);
165 new_edge->probability = REG_BR_PROB_BASE;
166 new_edge->count = new_bb->count;
167 if (GET_CODE (BB_END (new_bb)) == BARRIER)
168 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
169 update_bb_for_insn (new_bb);
170
171 if (dump_file)
172 {
173 dump_bb (bb, dump_file, 0);
174 dump_bb (new_bb, dump_file, 0);
175 }
176 return new_bb;
177 }
178
179 /* Update after expansion of sibling call. */
180 case CALL_EXPR:
181 case MODIFY_EXPR:
182 case RETURN_EXPR:
183 expand_expr_stmt_value (stmt, 0, 0);
184 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
185 {
186 if (GET_CODE (last) == CALL_INSN && SIBLING_CALL_P (last))
187 {
188 edge e;
189 int probability = 0;
190 gcov_type count = 0;
191
192 do_pending_stack_adjust ();
193 e = bb->succ;
194 while (e)
195 {
196 edge next = e->succ_next;
197
198 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
199 {
200 if (e->dest != EXIT_BLOCK_PTR)
201 {
202 e->dest->count -= e->count;
203 e->dest->frequency -= EDGE_FREQUENCY (e);
204 if (e->dest->count < 0)
205 e->dest->count = 0;
206 if (e->dest->frequency < 0)
207 e->dest->frequency = 0;
208 }
209 count += e->count;
210 probability += e->probability;
211 remove_edge (e);
212 }
213
214 e = next;
215 }
216
217 /* This is somewhat ugly: the call_expr expander often emits instructions
218 after the sibcall (to perform the function return). These confuse the
219 find_sub_basic_blocks code, so we need to get rid of these. */
220 last = NEXT_INSN (last);
221 if (GET_CODE (last) != BARRIER)
222 abort ();
223 while (NEXT_INSN (last))
224 {
225 /* For instance an sqrt builtin expander expands if with
226 sibcall in the then and label for `else`. */
227 if (GET_CODE (NEXT_INSN (last)) == CODE_LABEL)
228 break;
229 delete_insn (NEXT_INSN (last));
230 }
231 e = make_edge (bb, EXIT_BLOCK_PTR,
232 EDGE_ABNORMAL | EDGE_SIBCALL);
233 e->probability += probability;
234 e->count += count;
235 BB_END (bb) = last;
236 update_bb_for_insn (bb);
237 if (NEXT_INSN (last))
238 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
239 else
240 return bb;
241 }
242 }
243 break;
244
245 default:
246 expand_expr_stmt_value (stmt, 0, 0);
247 break;
248 }
249 }
250
251 do_pending_stack_adjust ();
252
253 /* Find the the block tail. The last insn is the block is the insn
254 before a barrier and/or table jump insn. */
255 last = get_last_insn ();
256 if (GET_CODE (last) == BARRIER)
257 last = PREV_INSN (last);
258 if (JUMP_TABLE_DATA_P (last))
259 last = PREV_INSN (PREV_INSN (last));
260 BB_END (bb) = last;
261
262 if (dump_file)
263 dump_bb (bb, dump_file, 0);
264 update_bb_for_insn (bb);
265 return bb;
266 }
267
268
269 /* Create a basic block for initialization code. */
270
271 static basic_block
272 construct_init_block (void)
273 {
274 basic_block init_block, first_block;
275 edge e;
276
277 expand_start_bindings_and_block (0, NULL_TREE);
278
279 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
280 if (e->dest == ENTRY_BLOCK_PTR->next_bb)
281 break;
282
283 init_block = create_basic_block (NEXT_INSN (get_insns ()),
284 get_last_insn (),
285 ENTRY_BLOCK_PTR);
286 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
287 init_block->count = ENTRY_BLOCK_PTR->count;
288 if (e)
289 {
290 first_block = e->dest;
291 redirect_edge_succ (e, init_block);
292 e = make_edge (init_block, first_block, EDGE_FALLTHRU);
293 }
294 else
295 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
296 e->probability = REG_BR_PROB_BASE;
297 e->count = ENTRY_BLOCK_PTR->count;
298
299 update_bb_for_insn (init_block);
300 return init_block;
301 }
302
303
304 /* Create a block containing landing pads and similar stuff. */
305
306 static void
307 construct_exit_block (void)
308 {
309 rtx head = get_last_insn ();
310 rtx end;
311 basic_block exit_block;
312 edge e, e2, next;
313
314 /* We hard-wired immediate_size_expand to zero above.
315 expand_function_end will decrement this variable. So, we set the
316 variable to one here, so that after the decrement it will remain
317 zero. */
318 immediate_size_expand = 1;
319
320 /* Make sure the locus is set to the end of the function, so that
321 epilogue line numbers and warnings are set properly. */
322 #ifdef USE_MAPPED_LOCATION
323 if (cfun->function_end_locus != UNKNOWN_LOCATION)
324 #else
325 if (cfun->function_end_locus.file)
326 #endif
327 input_location = cfun->function_end_locus;
328
329 /* The following insns belong to the top scope. */
330 record_block_change (DECL_INITIAL (current_function_decl));
331
332 expand_end_bindings (NULL_TREE, 1, 0);
333
334 /* Generate rtl for function exit. */
335 expand_function_end ();
336
337 end = get_last_insn ();
338 if (head == end)
339 return;
340 while (NEXT_INSN (head) && GET_CODE (NEXT_INSN (head)) == NOTE)
341 head = NEXT_INSN (head);
342 exit_block = create_basic_block (NEXT_INSN (head), end, EXIT_BLOCK_PTR->prev_bb);
343 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
344 exit_block->count = EXIT_BLOCK_PTR->count;
345 for (e = EXIT_BLOCK_PTR->pred; e; e = next)
346 {
347 next = e->pred_next;
348 if (!(e->flags & EDGE_ABNORMAL))
349 redirect_edge_succ (e, exit_block);
350 }
351 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
352 e->probability = REG_BR_PROB_BASE;
353 e->count = EXIT_BLOCK_PTR->count;
354 for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
355 if (e2 != e)
356 {
357 e->count -= e2->count;
358 exit_block->count -= e2->count;
359 exit_block->frequency -= EDGE_FREQUENCY (e2);
360 }
361 if (e->count < 0)
362 e->count = 0;
363 if (exit_block->count < 0)
364 exit_block->count = 0;
365 if (exit_block->frequency < 0)
366 exit_block->frequency = 0;
367 update_bb_for_insn (exit_block);
368 }
369
370 /* Called to move the SAVE_EXPRs for parameter declarations in a
371 nested function into the nested function. DATA is really the
372 nested FUNCTION_DECL. */
373
374 static tree
375 set_save_expr_context (tree *tp,
376 int *walk_subtrees,
377 void *data)
378 {
379 if (TREE_CODE (*tp) == SAVE_EXPR && !SAVE_EXPR_CONTEXT (*tp))
380 SAVE_EXPR_CONTEXT (*tp) = (tree) data;
381 /* Do not walk back into the SAVE_EXPR_CONTEXT; that will cause
382 circularity. */
383 else if (DECL_P (*tp))
384 *walk_subtrees = 0;
385
386 return NULL;
387 }
388
389
390 /* Translate the intermediate representation contained in the CFG
391 from GIMPLE trees to RTL.
392
393 We do conversion per basic block and preserve/update the tree CFG.
394 This implies we have to do some magic as the CFG can simultaneously
395 consist of basic blocks containing RTL and GIMPLE trees. This can
396 confuse the CFG hooks, so be careful to not manipulate CFG during
397 the expansion. */
398
399 static void
400 tree_expand_cfg (void)
401 {
402 basic_block bb, init_block;
403 sbitmap blocks;
404
405 if (dump_file)
406 {
407 fprintf (dump_file, "\n;; Function %s",
408 (*lang_hooks.decl_printable_name) (current_function_decl, 2));
409 fprintf (dump_file, " (%s)\n",
410 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
411 }
412
413 /* If the function has a variably modified type, there may be
414 SAVE_EXPRs in the parameter types. Their context must be set to
415 refer to this function; they cannot be expanded in the containing
416 function. */
417 if (decl_function_context (current_function_decl) == current_function_decl
418 && variably_modified_type_p (TREE_TYPE (current_function_decl)))
419 walk_tree (&TREE_TYPE (current_function_decl), set_save_expr_context,
420 current_function_decl, NULL);
421
422 /* Expand the variables recorded during gimple lowering. This must
423 occur before the call to expand_function_start to ensure that
424 all used variables are expanded before we expand anything on the
425 PENDING_SIZES list. */
426 expand_used_vars ();
427
428 /* Set up parameters and prepare for return, for the function. */
429 expand_function_start (current_function_decl, 0);
430
431 /* If this function is `main', emit a call to `__main'
432 to run global initializers, etc. */
433 if (DECL_NAME (current_function_decl)
434 && MAIN_NAME_P (DECL_NAME (current_function_decl))
435 && DECL_FILE_SCOPE_P (current_function_decl))
436 expand_main_function ();
437
438 /* Write the flowgraph to a dot file. */
439 rtl_register_cfg_hooks ();
440
441 init_block = construct_init_block ();
442
443 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
444 bb = expand_block (bb, dump_file);
445
446 construct_exit_block ();
447
448 /* Convert from NOTE_INSN_EH_REGION style notes, and do other
449 sorts of eh initialization. Delay this until after the
450 initial rtl dump so that we can see the original nesting. */
451 convert_from_eh_region_ranges ();
452
453 rebuild_jump_labels (get_insns ());
454 find_exception_handler_labels ();
455
456 blocks = sbitmap_alloc (last_basic_block);
457 sbitmap_ones (blocks);
458 find_many_sub_basic_blocks (blocks);
459 purge_all_dead_edges (0);
460 sbitmap_free (blocks);
461
462 compact_blocks ();
463 #ifdef ENABLE_CHECKING
464 verify_flow_info();
465 #endif
466 }
467
468 struct tree_opt_pass pass_expand =
469 {
470 "expand", /* name */
471 NULL, /* gate */
472 tree_expand_cfg, /* execute */
473 NULL, /* sub */
474 NULL, /* next */
475 0, /* static_pass_number */
476 TV_EXPAND, /* tv_id */
477 /* ??? If TER is enabled, we actually receive GENERIC. */
478 PROP_gimple_leh | PROP_cfg, /* properties_required */
479 PROP_rtl, /* properties_provided */
480 PROP_gimple_leh, /* properties_destroyed */
481 0, /* todo_flags_start */
482 0 /* todo_flags_finish */
483 };
484