* arm.h (REVERSE_CONDITION): Define.
[official-gcc.git] / gcc / cfgexpand.c
blobb6ba991da743bce213c731961467a392e2b3d9a9
1 /* A pass for lowering trees to RTL.
2 Copyright (C) 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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. */
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"
40 /* Expand variables in the unexpanded_var_list. */
42 static void
43 expand_used_vars (void)
45 tree cell;
47 cfun->unexpanded_var_list = nreverse (cfun->unexpanded_var_list);
49 for (cell = cfun->unexpanded_var_list; cell; cell = TREE_CHAIN (cell))
50 expand_var (TREE_VALUE (cell));
52 cfun->unexpanded_var_list = NULL_TREE;
56 /* A subroutine of expand_gimple_basic_block. Expand one COND_EXPR.
57 Returns a new basic block if we've terminated the current basic
58 block and created a new one. */
60 static basic_block
61 expand_gimple_cond_expr (basic_block bb, tree stmt)
63 basic_block new_bb, dest;
64 edge new_edge;
65 edge true_edge;
66 edge false_edge;
67 tree pred = COND_EXPR_COND (stmt);
68 tree then_exp = COND_EXPR_THEN (stmt);
69 tree else_exp = COND_EXPR_ELSE (stmt);
70 rtx last;
72 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
73 if (EXPR_LOCUS (stmt))
75 emit_line_note (*(EXPR_LOCUS (stmt)));
76 record_block_change (TREE_BLOCK (stmt));
79 /* These flags have no purpose in RTL land. */
80 true_edge->flags &= ~EDGE_TRUE_VALUE;
81 false_edge->flags &= ~EDGE_FALSE_VALUE;
83 /* We can either have a pure conditional jump with one fallthru edge or
84 two-way jump that needs to be decomposed into two basic blocks. */
85 if (TREE_CODE (then_exp) == GOTO_EXPR && IS_EMPTY_STMT (else_exp))
87 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
88 return NULL;
90 if (TREE_CODE (else_exp) == GOTO_EXPR && IS_EMPTY_STMT (then_exp))
92 jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
93 return NULL;
95 if (TREE_CODE (then_exp) != GOTO_EXPR || TREE_CODE (else_exp) != GOTO_EXPR)
96 abort ();
98 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
99 last = get_last_insn ();
100 expand_expr (else_exp, const0_rtx, VOIDmode, 0);
102 BB_END (bb) = last;
103 if (BARRIER_P (BB_END (bb)))
104 BB_END (bb) = PREV_INSN (BB_END (bb));
105 update_bb_for_insn (bb);
107 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
108 dest = false_edge->dest;
109 redirect_edge_succ (false_edge, new_bb);
110 false_edge->flags |= EDGE_FALLTHRU;
111 new_bb->count = false_edge->count;
112 new_bb->frequency = EDGE_FREQUENCY (false_edge);
113 new_edge = make_edge (new_bb, dest, 0);
114 new_edge->probability = REG_BR_PROB_BASE;
115 new_edge->count = new_bb->count;
116 if (BARRIER_P (BB_END (new_bb)))
117 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
118 update_bb_for_insn (new_bb);
120 if (dump_file)
122 dump_bb (bb, dump_file, 0);
123 dump_bb (new_bb, dump_file, 0);
126 return new_bb;
129 /* A subroutine of expand_gimple_basic_block. Expand one CALL_EXPR
130 that has CALL_EXPR_TAILCALL set. Returns non-null if we actually
131 generated a tail call (something that might be denied by the ABI
132 rules governing the call; see calls.c).
134 Sets CAN_FALLTHRU if we generated a *conditional* tail call, and
135 can still reach the rest of BB. The case here is __builtin_sqrt,
136 where the NaN result goes through the external function (with a
137 tailcall) and the normal result happens via a sqrt instruction. */
139 static basic_block
140 expand_gimple_tailcall (basic_block bb, tree stmt, bool *can_fallthru)
142 rtx last = get_last_insn ();
143 edge e;
144 int probability;
145 gcov_type count;
147 expand_expr_stmt (stmt);
149 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
150 if (CALL_P (last) && SIBLING_CALL_P (last))
151 goto found;
153 *can_fallthru = true;
154 return NULL;
156 found:
157 /* ??? Wouldn't it be better to just reset any pending stack adjust?
158 Any instructions emitted here are about to be deleted. */
159 do_pending_stack_adjust ();
161 /* Remove any non-eh, non-abnormal edges that don't go to exit. */
162 /* ??? I.e. the fallthrough edge. HOWEVER! If there were to be
163 EH or abnormal edges, we shouldn't have created a tail call in
164 the first place. So it seems to me we should just be removing
165 all edges here, or redirecting the existing fallthru edge to
166 the exit block. */
168 e = bb->succ;
169 probability = 0;
170 count = 0;
171 while (e)
173 edge next = e->succ_next;
175 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
177 if (e->dest != EXIT_BLOCK_PTR)
179 e->dest->count -= e->count;
180 e->dest->frequency -= EDGE_FREQUENCY (e);
181 if (e->dest->count < 0)
182 e->dest->count = 0;
183 if (e->dest->frequency < 0)
184 e->dest->frequency = 0;
186 count += e->count;
187 probability += e->probability;
188 remove_edge (e);
191 e = next;
194 /* This is somewhat ugly: the call_expr expander often emits instructions
195 after the sibcall (to perform the function return). These confuse the
196 find_sub_basic_blocks code, so we need to get rid of these. */
197 last = NEXT_INSN (last);
198 if (!BARRIER_P (last))
199 abort ();
201 *can_fallthru = false;
202 while (NEXT_INSN (last))
204 /* For instance an sqrt builtin expander expands if with
205 sibcall in the then and label for `else`. */
206 if (LABEL_P (NEXT_INSN (last)))
208 *can_fallthru = true;
209 break;
211 delete_insn (NEXT_INSN (last));
214 e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
215 e->probability += probability;
216 e->count += count;
217 BB_END (bb) = last;
218 update_bb_for_insn (bb);
220 if (NEXT_INSN (last))
222 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
224 last = BB_END (bb);
225 if (BARRIER_P (last))
226 BB_END (bb) = PREV_INSN (last);
229 return bb;
232 /* Expand basic block BB from GIMPLE trees to RTL. */
234 static basic_block
235 expand_gimple_basic_block (basic_block bb, FILE * dump_file)
237 block_stmt_iterator bsi = bsi_start (bb);
238 tree stmt = NULL;
239 rtx note, last;
240 edge e;
242 if (dump_file)
244 tree_register_cfg_hooks ();
245 dump_bb (bb, dump_file, 0);
246 rtl_register_cfg_hooks ();
249 if (!bsi_end_p (bsi))
250 stmt = bsi_stmt (bsi);
252 if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
254 last = get_last_insn ();
256 expand_expr_stmt (stmt);
258 /* Java emits line number notes in the top of labels.
259 ??? Make this go away once line number notes are obsoleted. */
260 BB_HEAD (bb) = NEXT_INSN (last);
261 if (NOTE_P (BB_HEAD (bb)))
262 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
263 bsi_next (&bsi);
264 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
266 else
267 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
269 NOTE_BASIC_BLOCK (note) = bb;
271 e = bb->succ;
272 while (e)
274 edge next = e->succ_next;
276 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
277 e->flags &= ~EDGE_EXECUTABLE;
279 /* At the moment not all abnormal edges match the RTL representation.
280 It is safe to remove them here as find_sub_basic_blocks will
281 rediscover them. In the future we should get this fixed properly. */
282 if (e->flags & EDGE_ABNORMAL)
283 remove_edge (e);
285 e = next;
288 for (; !bsi_end_p (bsi); bsi_next (&bsi))
290 tree stmt = bsi_stmt (bsi);
291 basic_block new_bb;
293 if (!stmt)
294 continue;
296 /* Expand this statement, then evaluate the resulting RTL and
297 fixup the CFG accordingly. */
298 if (TREE_CODE (stmt) == COND_EXPR)
300 new_bb = expand_gimple_cond_expr (bb, stmt);
301 if (new_bb)
302 return new_bb;
304 else
306 tree call = get_call_expr_in (stmt);
307 if (call && CALL_EXPR_TAILCALL (call))
309 bool can_fallthru;
310 new_bb = expand_gimple_tailcall (bb, stmt, &can_fallthru);
311 if (new_bb)
313 if (can_fallthru)
314 bb = new_bb;
315 else
316 return new_bb;
319 else
320 expand_expr_stmt (stmt);
324 do_pending_stack_adjust ();
326 /* Find the the block tail. The last insn is the block is the insn
327 before a barrier and/or table jump insn. */
328 last = get_last_insn ();
329 if (BARRIER_P (last))
330 last = PREV_INSN (last);
331 if (JUMP_TABLE_DATA_P (last))
332 last = PREV_INSN (PREV_INSN (last));
333 BB_END (bb) = last;
335 if (dump_file)
336 dump_bb (bb, dump_file, 0);
337 update_bb_for_insn (bb);
339 return bb;
343 /* Create a basic block for initialization code. */
345 static basic_block
346 construct_init_block (void)
348 basic_block init_block, first_block;
349 edge e;
351 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
352 if (e->dest == ENTRY_BLOCK_PTR->next_bb)
353 break;
355 init_block = create_basic_block (NEXT_INSN (get_insns ()),
356 get_last_insn (),
357 ENTRY_BLOCK_PTR);
358 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
359 init_block->count = ENTRY_BLOCK_PTR->count;
360 if (e)
362 first_block = e->dest;
363 redirect_edge_succ (e, init_block);
364 e = make_edge (init_block, first_block, EDGE_FALLTHRU);
366 else
367 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
368 e->probability = REG_BR_PROB_BASE;
369 e->count = ENTRY_BLOCK_PTR->count;
371 update_bb_for_insn (init_block);
372 return init_block;
376 /* Create a block containing landing pads and similar stuff. */
378 static void
379 construct_exit_block (void)
381 rtx head = get_last_insn ();
382 rtx end;
383 basic_block exit_block;
384 edge e, e2, next;
386 /* Make sure the locus is set to the end of the function, so that
387 epilogue line numbers and warnings are set properly. */
388 #ifdef USE_MAPPED_LOCATION
389 if (cfun->function_end_locus != UNKNOWN_LOCATION)
390 #else
391 if (cfun->function_end_locus.file)
392 #endif
393 input_location = cfun->function_end_locus;
395 /* The following insns belong to the top scope. */
396 record_block_change (DECL_INITIAL (current_function_decl));
398 /* Generate rtl for function exit. */
399 expand_function_end ();
401 end = get_last_insn ();
402 if (head == end)
403 return;
404 while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
405 head = NEXT_INSN (head);
406 exit_block = create_basic_block (NEXT_INSN (head), end,
407 EXIT_BLOCK_PTR->prev_bb);
408 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
409 exit_block->count = EXIT_BLOCK_PTR->count;
410 for (e = EXIT_BLOCK_PTR->pred; e; e = next)
412 next = e->pred_next;
413 if (!(e->flags & EDGE_ABNORMAL))
414 redirect_edge_succ (e, exit_block);
416 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
417 e->probability = REG_BR_PROB_BASE;
418 e->count = EXIT_BLOCK_PTR->count;
419 for (e2 = EXIT_BLOCK_PTR->pred; e2; e2 = e2->pred_next)
420 if (e2 != e)
422 e->count -= e2->count;
423 exit_block->count -= e2->count;
424 exit_block->frequency -= EDGE_FREQUENCY (e2);
426 if (e->count < 0)
427 e->count = 0;
428 if (exit_block->count < 0)
429 exit_block->count = 0;
430 if (exit_block->frequency < 0)
431 exit_block->frequency = 0;
432 update_bb_for_insn (exit_block);
435 /* Translate the intermediate representation contained in the CFG
436 from GIMPLE trees to RTL.
438 We do conversion per basic block and preserve/update the tree CFG.
439 This implies we have to do some magic as the CFG can simultaneously
440 consist of basic blocks containing RTL and GIMPLE trees. This can
441 confuse the CFG hooks, so be careful to not manipulate CFG during
442 the expansion. */
444 static void
445 tree_expand_cfg (void)
447 basic_block bb, init_block;
448 sbitmap blocks;
450 if (dump_file)
452 fprintf (dump_file, "\n;; Function %s",
453 (*lang_hooks.decl_printable_name) (current_function_decl, 2));
454 fprintf (dump_file, " (%s)\n",
455 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (current_function_decl)));
458 profile_status = PROFILE_ABSENT;
460 /* Some backends want to know that we are expanding to RTL. */
461 currently_expanding_to_rtl = 1;
463 /* Prepare the rtl middle end to start recording block changes. */
464 reset_block_changes ();
466 /* Expand the variables recorded during gimple lowering. */
467 expand_used_vars ();
469 /* Set up parameters and prepare for return, for the function. */
470 expand_function_start (current_function_decl);
472 /* If this function is `main', emit a call to `__main'
473 to run global initializers, etc. */
474 if (DECL_NAME (current_function_decl)
475 && MAIN_NAME_P (DECL_NAME (current_function_decl))
476 && DECL_FILE_SCOPE_P (current_function_decl))
477 expand_main_function ();
479 /* Register rtl specific functions for cfg. */
480 rtl_register_cfg_hooks ();
482 init_block = construct_init_block ();
484 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
485 bb = expand_gimple_basic_block (bb, dump_file);
487 construct_exit_block ();
489 /* We're done expanding trees to RTL. */
490 currently_expanding_to_rtl = 0;
492 /* Convert from NOTE_INSN_EH_REGION style notes, and do other
493 sorts of eh initialization. Delay this until after the
494 initial rtl dump so that we can see the original nesting. */
495 convert_from_eh_region_ranges ();
497 rebuild_jump_labels (get_insns ());
498 find_exception_handler_labels ();
500 blocks = sbitmap_alloc (last_basic_block);
501 sbitmap_ones (blocks);
502 find_many_sub_basic_blocks (blocks);
503 purge_all_dead_edges (0);
504 sbitmap_free (blocks);
506 compact_blocks ();
507 #ifdef ENABLE_CHECKING
508 verify_flow_info();
509 #endif
512 struct tree_opt_pass pass_expand =
514 "expand", /* name */
515 NULL, /* gate */
516 tree_expand_cfg, /* execute */
517 NULL, /* sub */
518 NULL, /* next */
519 0, /* static_pass_number */
520 TV_EXPAND, /* tv_id */
521 /* ??? If TER is enabled, we actually receive GENERIC. */
522 PROP_gimple_leh | PROP_cfg, /* properties_required */
523 PROP_rtl, /* properties_provided */
524 PROP_gimple_leh, /* properties_destroyed */
525 0, /* todo_flags_start */
526 0 /* todo_flags_finish */