1 /* A pass for lowering trees to RTL.
2 Copyright (C) 2004, 2005 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)
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, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
23 #include "coretypes.h"
28 #include "basic-block.h"
31 #include "langhooks.h"
32 #include "tree-flow.h"
34 #include "tree-dump.h"
35 #include "tree-pass.h"
38 #include "diagnostic.h"
41 /* Verify that there is exactly single jump instruction since last and attach
42 REG_BR_PROB note specifying probability.
43 ??? We really ought to pass the probability down to RTL expanders and let it
44 re-distribute it when the conditional expands into multiple conditionals.
45 This is however difficult to do. */
47 add_reg_br_prob_note (FILE *dump_file, rtx last, int probability)
49 if (profile_status == PROFILE_ABSENT)
51 for (last = NEXT_INSN (last); last && NEXT_INSN (last); last = NEXT_INSN (last))
54 /* It is common to emit condjump-around-jump sequence when we don't know
55 how to reverse the conditional. Special case this. */
56 if (!any_condjump_p (last)
57 || !JUMP_P (NEXT_INSN (last))
58 || !simplejump_p (NEXT_INSN (last))
59 || !BARRIER_P (NEXT_INSN (NEXT_INSN (last)))
60 || !LABEL_P (NEXT_INSN (NEXT_INSN (NEXT_INSN (last))))
61 || NEXT_INSN (NEXT_INSN (NEXT_INSN (NEXT_INSN (last)))))
63 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
65 = gen_rtx_EXPR_LIST (REG_BR_PROB,
66 GEN_INT (REG_BR_PROB_BASE - probability),
70 if (!last || !JUMP_P (last) || !any_condjump_p (last))
72 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
74 = gen_rtx_EXPR_LIST (REG_BR_PROB,
75 GEN_INT (probability), REG_NOTES (last));
79 fprintf (dump_file, "Failed to add probability note\n");
83 #ifndef LOCAL_ALIGNMENT
84 #define LOCAL_ALIGNMENT(TYPE, ALIGNMENT) ALIGNMENT
87 #ifndef STACK_ALIGNMENT_NEEDED
88 #define STACK_ALIGNMENT_NEEDED 1
92 /* This structure holds data relevant to one variable that will be
93 placed in a stack slot. */
99 /* The offset of the variable. During partitioning, this is the
100 offset relative to the partition. After partitioning, this
101 is relative to the stack frame. */
102 HOST_WIDE_INT offset;
104 /* Initially, the size of the variable. Later, the size of the partition,
105 if this variable becomes it's partition's representative. */
108 /* The *byte* alignment required for this variable. Or as, with the
109 size, the alignment for this partition. */
112 /* The partition representative. */
113 size_t representative;
115 /* The next stack variable in the partition, or EOC. */
119 #define EOC ((size_t)-1)
121 /* We have an array of such objects while deciding allocation. */
122 static struct stack_var *stack_vars;
123 static size_t stack_vars_alloc;
124 static size_t stack_vars_num;
126 /* An array of indicies such that stack_vars[stack_vars_sorted[i]].size
127 is non-decreasing. */
128 static size_t *stack_vars_sorted;
130 /* We have an interference graph between such objects. This graph
131 is lower triangular. */
132 static bool *stack_vars_conflict;
133 static size_t stack_vars_conflict_alloc;
135 /* The phase of the stack frame. This is the known misalignment of
136 virtual_stack_vars_rtx from PREFERRED_STACK_BOUNDARY. That is,
137 (frame_offset+frame_phase) % PREFERRED_STACK_BOUNDARY == 0. */
138 static int frame_phase;
141 /* Discover the byte alignment to use for DECL. Ignore alignment
142 we can't do with expected alignment of the stack boundary. */
145 get_decl_align_unit (tree decl)
149 align = DECL_ALIGN (decl);
150 align = LOCAL_ALIGNMENT (TREE_TYPE (decl), align);
151 if (align > PREFERRED_STACK_BOUNDARY)
152 align = PREFERRED_STACK_BOUNDARY;
153 if (cfun->stack_alignment_needed < align)
154 cfun->stack_alignment_needed = align;
156 return align / BITS_PER_UNIT;
159 /* Allocate SIZE bytes at byte alignment ALIGN from the stack frame.
160 Return the frame offset. */
163 alloc_stack_frame_space (HOST_WIDE_INT size, HOST_WIDE_INT align)
165 HOST_WIDE_INT offset, new_frame_offset;
167 new_frame_offset = frame_offset;
168 if (FRAME_GROWS_DOWNWARD)
170 new_frame_offset -= size + frame_phase;
171 new_frame_offset &= -align;
172 new_frame_offset += frame_phase;
173 offset = new_frame_offset;
177 new_frame_offset -= frame_phase;
178 new_frame_offset += align - 1;
179 new_frame_offset &= -align;
180 new_frame_offset += frame_phase;
181 offset = new_frame_offset;
182 new_frame_offset += size;
184 frame_offset = new_frame_offset;
189 /* Accumulate DECL into STACK_VARS. */
192 add_stack_var (tree decl)
194 if (stack_vars_num >= stack_vars_alloc)
196 if (stack_vars_alloc)
197 stack_vars_alloc = stack_vars_alloc * 3 / 2;
199 stack_vars_alloc = 32;
201 = XRESIZEVEC (struct stack_var, stack_vars, stack_vars_alloc);
203 stack_vars[stack_vars_num].decl = decl;
204 stack_vars[stack_vars_num].offset = 0;
205 stack_vars[stack_vars_num].size = tree_low_cst (DECL_SIZE_UNIT (decl), 1);
206 stack_vars[stack_vars_num].alignb = get_decl_align_unit (decl);
208 /* All variables are initially in their own partition. */
209 stack_vars[stack_vars_num].representative = stack_vars_num;
210 stack_vars[stack_vars_num].next = EOC;
212 /* Ensure that this decl doesn't get put onto the list twice. */
213 SET_DECL_RTL (decl, pc_rtx);
218 /* Compute the linear index of a lower-triangular coordinate (I, J). */
221 triangular_index (size_t i, size_t j)
228 return (i * (i + 1)) / 2 + j;
231 /* Ensure that STACK_VARS_CONFLICT is large enough for N objects. */
234 resize_stack_vars_conflict (size_t n)
236 size_t size = triangular_index (n-1, n-1) + 1;
238 if (size <= stack_vars_conflict_alloc)
241 stack_vars_conflict = XRESIZEVEC (bool, stack_vars_conflict, size);
242 memset (stack_vars_conflict + stack_vars_conflict_alloc, 0,
243 (size - stack_vars_conflict_alloc) * sizeof (bool));
244 stack_vars_conflict_alloc = size;
247 /* Make the decls associated with luid's X and Y conflict. */
250 add_stack_var_conflict (size_t x, size_t y)
252 size_t index = triangular_index (x, y);
253 gcc_assert (index < stack_vars_conflict_alloc);
254 stack_vars_conflict[index] = true;
257 /* Check whether the decls associated with luid's X and Y conflict. */
260 stack_var_conflict_p (size_t x, size_t y)
262 size_t index = triangular_index (x, y);
263 gcc_assert (index < stack_vars_conflict_alloc);
264 return stack_vars_conflict[index];
267 /* A subroutine of expand_used_vars. If two variables X and Y have alias
268 sets that do not conflict, then do add a conflict for these variables
269 in the interference graph. We also have to mind MEM_IN_STRUCT_P and
273 add_alias_set_conflicts (void)
275 size_t i, j, n = stack_vars_num;
277 for (i = 0; i < n; ++i)
279 bool aggr_i = AGGREGATE_TYPE_P (TREE_TYPE (stack_vars[i].decl));
280 HOST_WIDE_INT set_i = get_alias_set (stack_vars[i].decl);
282 for (j = 0; j < i; ++j)
284 bool aggr_j = AGGREGATE_TYPE_P (TREE_TYPE (stack_vars[j].decl));
285 HOST_WIDE_INT set_j = get_alias_set (stack_vars[j].decl);
286 if (aggr_i != aggr_j || !alias_sets_conflict_p (set_i, set_j))
287 add_stack_var_conflict (i, j);
292 /* A subroutine of partition_stack_vars. A comparison function for qsort,
293 sorting an array of indicies by the size of the object. */
296 stack_var_size_cmp (const void *a, const void *b)
298 HOST_WIDE_INT sa = stack_vars[*(const size_t *)a].size;
299 HOST_WIDE_INT sb = stack_vars[*(const size_t *)b].size;
308 /* A subroutine of partition_stack_vars. The UNION portion of a UNION/FIND
309 partitioning algorithm. Partitions A and B are known to be non-conflicting.
310 Merge them into a single partition A.
312 At the same time, add OFFSET to all variables in partition B. At the end
313 of the partitioning process we've have a nice block easy to lay out within
317 union_stack_vars (size_t a, size_t b, HOST_WIDE_INT offset)
321 /* Update each element of partition B with the given offset,
322 and merge them into partition A. */
323 for (last = i = b; i != EOC; last = i, i = stack_vars[i].next)
325 stack_vars[i].offset += offset;
326 stack_vars[i].representative = a;
328 stack_vars[last].next = stack_vars[a].next;
329 stack_vars[a].next = b;
331 /* Update the required alignment of partition A to account for B. */
332 if (stack_vars[a].alignb < stack_vars[b].alignb)
333 stack_vars[a].alignb = stack_vars[b].alignb;
335 /* Update the interference graph and merge the conflicts. */
336 for (last = stack_vars_num, i = 0; i < last; ++i)
337 if (stack_var_conflict_p (b, i))
338 add_stack_var_conflict (a, i);
341 /* A subroutine of expand_used_vars. Binpack the variables into
342 partitions constrained by the interference graph. The overall
343 algorithm used is as follows:
345 Sort the objects by size.
350 Look for the largest non-conflicting object B with size <= S.
360 partition_stack_vars (void)
362 size_t si, sj, n = stack_vars_num;
364 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
365 for (si = 0; si < n; ++si)
366 stack_vars_sorted[si] = si;
371 qsort (stack_vars_sorted, n, sizeof (size_t), stack_var_size_cmp);
373 /* Special case: detect when all variables conflict, and thus we can't
374 do anything during the partitioning loop. It isn't uncommon (with
375 C code at least) to declare all variables at the top of the function,
376 and if we're not inlining, then all variables will be in the same scope.
377 Take advantage of very fast libc routines for this scan. */
378 gcc_assert (sizeof(bool) == sizeof(char));
379 if (memchr (stack_vars_conflict, false, stack_vars_conflict_alloc) == NULL)
382 for (si = 0; si < n; ++si)
384 size_t i = stack_vars_sorted[si];
385 HOST_WIDE_INT isize = stack_vars[i].size;
386 HOST_WIDE_INT offset = 0;
388 for (sj = si; sj-- > 0; )
390 size_t j = stack_vars_sorted[sj];
391 HOST_WIDE_INT jsize = stack_vars[j].size;
392 unsigned int jalign = stack_vars[j].alignb;
394 /* Ignore objects that aren't partition representatives. */
395 if (stack_vars[j].representative != j)
398 /* Ignore objects too large for the remaining space. */
402 /* Ignore conflicting objects. */
403 if (stack_var_conflict_p (i, j))
406 /* Refine the remaining space check to include alignment. */
407 if (offset & (jalign - 1))
409 HOST_WIDE_INT toff = offset;
411 toff &= -(HOST_WIDE_INT)jalign;
412 if (isize - (toff - offset) < jsize)
415 isize -= toff - offset;
419 /* UNION the objects, placing J at OFFSET. */
420 union_stack_vars (i, j, offset);
429 /* A debugging aid for expand_used_vars. Dump the generated partitions. */
432 dump_stack_var_partition (void)
434 size_t si, i, j, n = stack_vars_num;
436 for (si = 0; si < n; ++si)
438 i = stack_vars_sorted[si];
440 /* Skip variables that aren't partition representatives, for now. */
441 if (stack_vars[i].representative != i)
444 fprintf (dump_file, "Partition %lu: size " HOST_WIDE_INT_PRINT_DEC
445 " align %u\n", (unsigned long) i, stack_vars[i].size,
446 stack_vars[i].alignb);
448 for (j = i; j != EOC; j = stack_vars[j].next)
450 fputc ('\t', dump_file);
451 print_generic_expr (dump_file, stack_vars[j].decl, dump_flags);
452 fprintf (dump_file, ", offset " HOST_WIDE_INT_PRINT_DEC "\n",
453 stack_vars[i].offset);
458 /* Assign rtl to DECL at frame offset OFFSET. */
461 expand_one_stack_var_at (tree decl, HOST_WIDE_INT offset)
466 /* If this fails, we've overflowed the stack frame. Error nicely? */
467 gcc_assert (offset == trunc_int_for_mode (offset, Pmode));
469 x = plus_constant (virtual_stack_vars_rtx, offset);
470 x = gen_rtx_MEM (DECL_MODE (decl), x);
472 /* Set alignment we actually gave this decl. */
473 offset -= frame_phase;
474 align = offset & -offset;
475 align *= BITS_PER_UNIT;
476 if (align > STACK_BOUNDARY || align == 0)
477 align = STACK_BOUNDARY;
478 DECL_ALIGN (decl) = align;
479 DECL_USER_ALIGN (decl) = 0;
481 set_mem_attributes (x, decl, true);
482 SET_DECL_RTL (decl, x);
485 /* A subroutine of expand_used_vars. Give each partition representative
486 a unique location within the stack frame. Update each partition member
487 with that location. */
490 expand_stack_vars (void)
492 size_t si, i, j, n = stack_vars_num;
494 for (si = 0; si < n; ++si)
496 HOST_WIDE_INT offset;
498 i = stack_vars_sorted[si];
500 /* Skip variables that aren't partition representatives, for now. */
501 if (stack_vars[i].representative != i)
504 offset = alloc_stack_frame_space (stack_vars[i].size,
505 stack_vars[i].alignb);
507 /* Create rtl for each variable based on their location within the
509 for (j = i; j != EOC; j = stack_vars[j].next)
510 expand_one_stack_var_at (stack_vars[j].decl,
511 stack_vars[j].offset + offset);
515 /* A subroutine of expand_one_var. Called to immediately assign rtl
516 to a variable to be allocated in the stack frame. */
519 expand_one_stack_var (tree var)
521 HOST_WIDE_INT size, offset, align;
523 size = tree_low_cst (DECL_SIZE_UNIT (var), 1);
524 align = get_decl_align_unit (var);
525 offset = alloc_stack_frame_space (size, align);
527 expand_one_stack_var_at (var, offset);
530 /* A subroutine of expand_one_var. Called to assign rtl
531 to a TREE_STATIC VAR_DECL. */
534 expand_one_static_var (tree var)
536 /* If this is an inlined copy of a static local variable,
537 look up the original. */
538 var = DECL_ORIGIN (var);
540 /* If we've already processed this variable because of that, do nothing. */
541 if (TREE_ASM_WRITTEN (var))
544 /* Give the front end a chance to do whatever. In practice, this is
545 resolving duplicate names for IMA in C. */
546 if (lang_hooks.expand_decl (var))
549 /* Otherwise, just emit the variable. */
550 rest_of_decl_compilation (var, 0, 0);
553 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
554 that will reside in a hard register. */
557 expand_one_hard_reg_var (tree var)
559 rest_of_decl_compilation (var, 0, 0);
562 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
563 that will reside in a pseudo register. */
566 expand_one_register_var (tree var)
568 tree type = TREE_TYPE (var);
569 int unsignedp = TYPE_UNSIGNED (type);
570 enum machine_mode reg_mode
571 = promote_mode (type, DECL_MODE (var), &unsignedp, 0);
572 rtx x = gen_reg_rtx (reg_mode);
574 SET_DECL_RTL (var, x);
576 /* Note if the object is a user variable. */
577 if (!DECL_ARTIFICIAL (var))
581 /* Trust user variables which have a pointer type to really
582 be pointers. Do not trust compiler generated temporaries
583 as our type system is totally busted as it relates to
584 pointer arithmetic which translates into lots of compiler
585 generated objects with pointer types, but which are not really
587 if (POINTER_TYPE_P (type))
588 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
592 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL that
593 has some associated error, e.g. its type is error-mark. We just need
594 to pick something that won't crash the rest of the compiler. */
597 expand_one_error_var (tree var)
599 enum machine_mode mode = DECL_MODE (var);
603 x = gen_rtx_MEM (BLKmode, const0_rtx);
604 else if (mode == VOIDmode)
607 x = gen_reg_rtx (mode);
609 SET_DECL_RTL (var, x);
612 /* A subroutine of expand_one_var. VAR is a variable that will be
613 allocated to the local stack frame. Return true if we wish to
614 add VAR to STACK_VARS so that it will be coalesced with other
615 variables. Return false to allocate VAR immediately.
617 This function is used to reduce the number of variables considered
618 for coalescing, which reduces the size of the quadratic problem. */
621 defer_stack_allocation (tree var, bool toplevel)
623 /* Variables in the outermost scope automatically conflict with
624 every other variable. The only reason to want to defer them
625 at all is that, after sorting, we can more efficiently pack
626 small variables in the stack frame. Continue to defer at -O2. */
627 if (toplevel && optimize < 2)
630 /* Without optimization, *most* variables are allocated from the
631 stack, which makes the quadratic problem large exactly when we
632 want compilation to proceed as quickly as possible. On the
633 other hand, we don't want the function's stack frame size to
634 get completely out of hand. So we avoid adding scalars and
635 "small" aggregates to the list at all. */
636 if (optimize == 0 && tree_low_cst (DECL_SIZE_UNIT (var), 1) < 32)
642 /* A subroutine of expand_used_vars. Expand one variable according to
643 its flavor. Variables to be placed on the stack are not actually
644 expanded yet, merely recorded. */
647 expand_one_var (tree var, bool toplevel)
649 if (TREE_CODE (var) != VAR_DECL)
650 lang_hooks.expand_decl (var);
651 else if (DECL_EXTERNAL (var))
653 else if (DECL_HAS_VALUE_EXPR_P (var))
655 else if (TREE_STATIC (var))
656 expand_one_static_var (var);
657 else if (DECL_RTL_SET_P (var))
659 else if (TREE_TYPE (var) == error_mark_node)
660 expand_one_error_var (var);
661 else if (DECL_HARD_REGISTER (var))
662 expand_one_hard_reg_var (var);
663 else if (use_register_for_decl (var))
664 expand_one_register_var (var);
665 else if (defer_stack_allocation (var, toplevel))
668 expand_one_stack_var (var);
671 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
672 expanding variables. Those variables that can be put into registers
673 are allocated pseudos; those that can't are put on the stack.
675 TOPLEVEL is true if this is the outermost BLOCK. */
678 expand_used_vars_for_block (tree block, bool toplevel)
680 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
683 old_sv_num = toplevel ? 0 : stack_vars_num;
685 /* Expand all variables at this level. */
686 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
688 expand_one_var (t, toplevel);
690 this_sv_num = stack_vars_num;
692 /* Expand all variables at containing levels. */
693 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
694 expand_used_vars_for_block (t, false);
696 /* Since we do not track exact variable lifetimes (which is not even
697 possible for varibles whose address escapes), we mirror the block
698 tree in the interference graph. Here we cause all variables at this
699 level, and all sublevels, to conflict. Do make certain that a
700 variable conflicts with itself. */
701 if (old_sv_num < this_sv_num)
703 new_sv_num = stack_vars_num;
704 resize_stack_vars_conflict (new_sv_num);
706 for (i = old_sv_num; i < new_sv_num; ++i)
707 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
708 add_stack_var_conflict (i, j);
712 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
713 and clear TREE_USED on all local variables. */
716 clear_tree_used (tree block)
720 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
721 /* if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) */
724 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
728 /* Expand all variables used in the function. */
731 expand_used_vars (void)
733 tree t, outer_block = DECL_INITIAL (current_function_decl);
735 /* Compute the phase of the stack frame for this function. */
737 int align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
738 int off = STARTING_FRAME_OFFSET % align;
739 frame_phase = off ? align - off : 0;
742 /* Set TREE_USED on all variables in the unexpanded_var_list. */
743 for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
744 TREE_USED (TREE_VALUE (t)) = 1;
746 /* Clear TREE_USED on all variables associated with a block scope. */
747 clear_tree_used (outer_block);
749 /* At this point all variables on the unexpanded_var_list with TREE_USED
750 set are not associated with any block scope. Lay them out. */
751 for (t = cfun->unexpanded_var_list; t; t = TREE_CHAIN (t))
753 tree var = TREE_VALUE (t);
754 bool expand_now = false;
756 /* We didn't set a block for static or extern because it's hard
757 to tell the difference between a global variable (re)declared
758 in a local scope, and one that's really declared there to
759 begin with. And it doesn't really matter much, since we're
760 not giving them stack space. Expand them now. */
761 if (TREE_STATIC (var) || DECL_EXTERNAL (var))
764 /* Any variable that could have been hoisted into an SSA_NAME
765 will have been propagated anywhere the optimizers chose,
766 i.e. not confined to their original block. Allocate them
767 as if they were defined in the outermost scope. */
768 else if (is_gimple_reg (var))
771 /* If the variable is not associated with any block, then it
772 was created by the optimizers, and could be live anywhere
774 else if (TREE_USED (var))
777 /* Finally, mark all variables on the list as used. We'll use
778 this in a moment when we expand those associated with scopes. */
782 expand_one_var (var, true);
784 cfun->unexpanded_var_list = NULL_TREE;
786 /* At this point, all variables within the block tree with TREE_USED
787 set are actually used by the optimized function. Lay them out. */
788 expand_used_vars_for_block (outer_block, true);
790 if (stack_vars_num > 0)
792 /* Due to the way alias sets work, no variables with non-conflicting
793 alias sets may be assigned the same address. Add conflicts to
795 add_alias_set_conflicts ();
797 /* Now that we have collected all stack variables, and have computed a
798 minimal interference graph, attempt to save some stack space. */
799 partition_stack_vars ();
801 dump_stack_var_partition ();
803 /* Assign rtl to each variable based on these partitions. */
804 expand_stack_vars ();
806 /* Free up stack variable graph data. */
807 XDELETEVEC (stack_vars);
808 XDELETEVEC (stack_vars_sorted);
809 XDELETEVEC (stack_vars_conflict);
811 stack_vars_alloc = stack_vars_num = 0;
812 stack_vars_conflict = NULL;
813 stack_vars_conflict_alloc = 0;
816 /* If the target requires that FRAME_OFFSET be aligned, do it. */
817 if (STACK_ALIGNMENT_NEEDED)
819 HOST_WIDE_INT align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
820 if (!FRAME_GROWS_DOWNWARD)
821 frame_offset += align - 1;
822 frame_offset &= -align;
827 /* If we need to produce a detailed dump, print the tree representation
828 for STMT to the dump file. SINCE is the last RTX after which the RTL
829 generated for STMT should have been appended. */
832 maybe_dump_rtl_for_tree_stmt (tree stmt, rtx since)
834 if (dump_file && (dump_flags & TDF_DETAILS))
836 fprintf (dump_file, "\n;; ");
837 print_generic_expr (dump_file, stmt, TDF_SLIM);
838 fprintf (dump_file, "\n");
840 print_rtl (dump_file, since ? NEXT_INSN (since) : since);
844 /* A subroutine of expand_gimple_basic_block. Expand one COND_EXPR.
845 Returns a new basic block if we've terminated the current basic
846 block and created a new one. */
849 expand_gimple_cond_expr (basic_block bb, tree stmt)
851 basic_block new_bb, dest;
855 tree pred = COND_EXPR_COND (stmt);
856 tree then_exp = COND_EXPR_THEN (stmt);
857 tree else_exp = COND_EXPR_ELSE (stmt);
860 last2 = last = get_last_insn ();
862 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
863 if (EXPR_LOCUS (stmt))
865 emit_line_note (*(EXPR_LOCUS (stmt)));
866 record_block_change (TREE_BLOCK (stmt));
869 /* These flags have no purpose in RTL land. */
870 true_edge->flags &= ~EDGE_TRUE_VALUE;
871 false_edge->flags &= ~EDGE_FALSE_VALUE;
873 /* We can either have a pure conditional jump with one fallthru edge or
874 two-way jump that needs to be decomposed into two basic blocks. */
875 if (TREE_CODE (then_exp) == GOTO_EXPR && IS_EMPTY_STMT (else_exp))
877 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
878 add_reg_br_prob_note (dump_file, last, true_edge->probability);
879 maybe_dump_rtl_for_tree_stmt (stmt, last);
880 if (EXPR_LOCUS (then_exp))
881 emit_line_note (*(EXPR_LOCUS (then_exp)));
884 if (TREE_CODE (else_exp) == GOTO_EXPR && IS_EMPTY_STMT (then_exp))
886 jumpifnot (pred, label_rtx (GOTO_DESTINATION (else_exp)));
887 add_reg_br_prob_note (dump_file, last, false_edge->probability);
888 maybe_dump_rtl_for_tree_stmt (stmt, last);
889 if (EXPR_LOCUS (else_exp))
890 emit_line_note (*(EXPR_LOCUS (else_exp)));
893 gcc_assert (TREE_CODE (then_exp) == GOTO_EXPR
894 && TREE_CODE (else_exp) == GOTO_EXPR);
896 jumpif (pred, label_rtx (GOTO_DESTINATION (then_exp)));
897 add_reg_br_prob_note (dump_file, last, true_edge->probability);
898 last = get_last_insn ();
899 expand_expr (else_exp, const0_rtx, VOIDmode, 0);
902 if (BARRIER_P (BB_END (bb)))
903 BB_END (bb) = PREV_INSN (BB_END (bb));
904 update_bb_for_insn (bb);
906 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
907 dest = false_edge->dest;
908 redirect_edge_succ (false_edge, new_bb);
909 false_edge->flags |= EDGE_FALLTHRU;
910 new_bb->count = false_edge->count;
911 new_bb->frequency = EDGE_FREQUENCY (false_edge);
912 new_edge = make_edge (new_bb, dest, 0);
913 new_edge->probability = REG_BR_PROB_BASE;
914 new_edge->count = new_bb->count;
915 if (BARRIER_P (BB_END (new_bb)))
916 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
917 update_bb_for_insn (new_bb);
919 maybe_dump_rtl_for_tree_stmt (stmt, last2);
921 if (EXPR_LOCUS (else_exp))
922 emit_line_note (*(EXPR_LOCUS (else_exp)));
927 /* A subroutine of expand_gimple_basic_block. Expand one CALL_EXPR
928 that has CALL_EXPR_TAILCALL set. Returns non-null if we actually
929 generated a tail call (something that might be denied by the ABI
930 rules governing the call; see calls.c).
932 Sets CAN_FALLTHRU if we generated a *conditional* tail call, and
933 can still reach the rest of BB. The case here is __builtin_sqrt,
934 where the NaN result goes through the external function (with a
935 tailcall) and the normal result happens via a sqrt instruction. */
938 expand_gimple_tailcall (basic_block bb, tree stmt, bool *can_fallthru)
946 last2 = last = get_last_insn ();
948 expand_expr_stmt (stmt);
950 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
951 if (CALL_P (last) && SIBLING_CALL_P (last))
954 maybe_dump_rtl_for_tree_stmt (stmt, last2);
956 *can_fallthru = true;
960 /* ??? Wouldn't it be better to just reset any pending stack adjust?
961 Any instructions emitted here are about to be deleted. */
962 do_pending_stack_adjust ();
964 /* Remove any non-eh, non-abnormal edges that don't go to exit. */
965 /* ??? I.e. the fallthrough edge. HOWEVER! If there were to be
966 EH or abnormal edges, we shouldn't have created a tail call in
967 the first place. So it seems to me we should just be removing
968 all edges here, or redirecting the existing fallthru edge to
974 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
976 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
978 if (e->dest != EXIT_BLOCK_PTR)
980 e->dest->count -= e->count;
981 e->dest->frequency -= EDGE_FREQUENCY (e);
982 if (e->dest->count < 0)
984 if (e->dest->frequency < 0)
985 e->dest->frequency = 0;
988 probability += e->probability;
995 /* This is somewhat ugly: the call_expr expander often emits instructions
996 after the sibcall (to perform the function return). These confuse the
997 find_many_sub_basic_blocks code, so we need to get rid of these. */
998 last = NEXT_INSN (last);
999 gcc_assert (BARRIER_P (last));
1001 *can_fallthru = false;
1002 while (NEXT_INSN (last))
1004 /* For instance an sqrt builtin expander expands if with
1005 sibcall in the then and label for `else`. */
1006 if (LABEL_P (NEXT_INSN (last)))
1008 *can_fallthru = true;
1011 delete_insn (NEXT_INSN (last));
1014 e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
1015 e->probability += probability;
1018 update_bb_for_insn (bb);
1020 if (NEXT_INSN (last))
1022 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
1025 if (BARRIER_P (last))
1026 BB_END (bb) = PREV_INSN (last);
1029 maybe_dump_rtl_for_tree_stmt (stmt, last2);
1034 /* Expand basic block BB from GIMPLE trees to RTL. */
1037 expand_gimple_basic_block (basic_block bb, FILE * dump_file)
1039 block_stmt_iterator bsi = bsi_start (bb);
1048 "\n;; Generating RTL for tree basic block %d\n",
1052 init_rtl_bb_info (bb);
1053 bb->flags |= BB_RTL;
1055 if (!bsi_end_p (bsi))
1056 stmt = bsi_stmt (bsi);
1058 if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
1060 last = get_last_insn ();
1062 expand_expr_stmt (stmt);
1064 /* Java emits line number notes in the top of labels.
1065 ??? Make this go away once line number notes are obsoleted. */
1066 BB_HEAD (bb) = NEXT_INSN (last);
1067 if (NOTE_P (BB_HEAD (bb)))
1068 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
1070 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
1072 maybe_dump_rtl_for_tree_stmt (stmt, last);
1075 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
1077 NOTE_BASIC_BLOCK (note) = bb;
1079 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1081 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
1082 e->flags &= ~EDGE_EXECUTABLE;
1084 /* At the moment not all abnormal edges match the RTL representation.
1085 It is safe to remove them here as find_many_sub_basic_blocks will
1086 rediscover them. In the future we should get this fixed properly. */
1087 if (e->flags & EDGE_ABNORMAL)
1093 for (; !bsi_end_p (bsi); bsi_next (&bsi))
1095 tree stmt = bsi_stmt (bsi);
1101 /* Expand this statement, then evaluate the resulting RTL and
1102 fixup the CFG accordingly. */
1103 if (TREE_CODE (stmt) == COND_EXPR)
1105 new_bb = expand_gimple_cond_expr (bb, stmt);
1111 tree call = get_call_expr_in (stmt);
1112 if (call && CALL_EXPR_TAILCALL (call))
1115 new_bb = expand_gimple_tailcall (bb, stmt, &can_fallthru);
1126 last = get_last_insn ();
1127 expand_expr_stmt (stmt);
1128 maybe_dump_rtl_for_tree_stmt (stmt, last);
1133 do_pending_stack_adjust ();
1135 /* Find the block tail. The last insn in the block is the insn
1136 before a barrier and/or table jump insn. */
1137 last = get_last_insn ();
1138 if (BARRIER_P (last))
1139 last = PREV_INSN (last);
1140 if (JUMP_TABLE_DATA_P (last))
1141 last = PREV_INSN (PREV_INSN (last));
1144 update_bb_for_insn (bb);
1150 /* Create a basic block for initialization code. */
1153 construct_init_block (void)
1155 basic_block init_block, first_block;
1159 /* Multiple entry points not supported yet. */
1160 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR->succs) == 1);
1161 init_rtl_bb_info (ENTRY_BLOCK_PTR);
1162 init_rtl_bb_info (EXIT_BLOCK_PTR);
1163 ENTRY_BLOCK_PTR->flags |= BB_RTL;
1164 EXIT_BLOCK_PTR->flags |= BB_RTL;
1166 e = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
1168 /* When entry edge points to first basic block, we don't need jump,
1169 otherwise we have to jump into proper target. */
1170 if (e && e->dest != ENTRY_BLOCK_PTR->next_bb)
1172 tree label = tree_block_label (e->dest);
1174 emit_jump (label_rtx (label));
1178 flags = EDGE_FALLTHRU;
1180 init_block = create_basic_block (NEXT_INSN (get_insns ()),
1183 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
1184 init_block->count = ENTRY_BLOCK_PTR->count;
1187 first_block = e->dest;
1188 redirect_edge_succ (e, init_block);
1189 e = make_edge (init_block, first_block, flags);
1192 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1193 e->probability = REG_BR_PROB_BASE;
1194 e->count = ENTRY_BLOCK_PTR->count;
1196 update_bb_for_insn (init_block);
1201 /* Create a block containing landing pads and similar stuff. */
1204 construct_exit_block (void)
1206 rtx head = get_last_insn ();
1208 basic_block exit_block;
1213 /* Make sure the locus is set to the end of the function, so that
1214 epilogue line numbers and warnings are set properly. */
1215 #ifdef USE_MAPPED_LOCATION
1216 if (cfun->function_end_locus != UNKNOWN_LOCATION)
1218 if (cfun->function_end_locus.file)
1220 input_location = cfun->function_end_locus;
1222 /* The following insns belong to the top scope. */
1223 record_block_change (DECL_INITIAL (current_function_decl));
1225 /* Generate rtl for function exit. */
1226 expand_function_end ();
1228 end = get_last_insn ();
1231 while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
1232 head = NEXT_INSN (head);
1233 exit_block = create_basic_block (NEXT_INSN (head), end,
1234 EXIT_BLOCK_PTR->prev_bb);
1235 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
1236 exit_block->count = EXIT_BLOCK_PTR->count;
1239 while (ix < EDGE_COUNT (EXIT_BLOCK_PTR->preds))
1241 e = EDGE_PRED (EXIT_BLOCK_PTR, ix);
1242 if (!(e->flags & EDGE_ABNORMAL))
1243 redirect_edge_succ (e, exit_block);
1248 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1249 e->probability = REG_BR_PROB_BASE;
1250 e->count = EXIT_BLOCK_PTR->count;
1251 FOR_EACH_EDGE (e2, ei, EXIT_BLOCK_PTR->preds)
1254 e->count -= e2->count;
1255 exit_block->count -= e2->count;
1256 exit_block->frequency -= EDGE_FREQUENCY (e2);
1260 if (exit_block->count < 0)
1261 exit_block->count = 0;
1262 if (exit_block->frequency < 0)
1263 exit_block->frequency = 0;
1264 update_bb_for_insn (exit_block);
1267 /* Translate the intermediate representation contained in the CFG
1268 from GIMPLE trees to RTL.
1270 We do conversion per basic block and preserve/update the tree CFG.
1271 This implies we have to do some magic as the CFG can simultaneously
1272 consist of basic blocks containing RTL and GIMPLE trees. This can
1273 confuse the CFG hooks, so be careful to not manipulate CFG during
1277 tree_expand_cfg (void)
1279 basic_block bb, init_block;
1282 /* Some backends want to know that we are expanding to RTL. */
1283 currently_expanding_to_rtl = 1;
1285 /* Prepare the rtl middle end to start recording block changes. */
1286 reset_block_changes ();
1288 /* Expand the variables recorded during gimple lowering. */
1289 expand_used_vars ();
1291 /* Set up parameters and prepare for return, for the function. */
1292 expand_function_start (current_function_decl);
1294 /* If this function is `main', emit a call to `__main'
1295 to run global initializers, etc. */
1296 if (DECL_NAME (current_function_decl)
1297 && MAIN_NAME_P (DECL_NAME (current_function_decl))
1298 && DECL_FILE_SCOPE_P (current_function_decl))
1299 expand_main_function ();
1301 /* Register rtl specific functions for cfg. */
1302 rtl_register_cfg_hooks ();
1304 init_block = construct_init_block ();
1306 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
1307 bb = expand_gimple_basic_block (bb, dump_file);
1309 construct_exit_block ();
1311 /* We're done expanding trees to RTL. */
1312 currently_expanding_to_rtl = 0;
1314 /* Convert tree EH labels to RTL EH labels, and clean out any unreachable
1316 convert_from_eh_region_ranges ();
1318 rebuild_jump_labels (get_insns ());
1319 find_exception_handler_labels ();
1321 blocks = sbitmap_alloc (last_basic_block);
1322 sbitmap_ones (blocks);
1323 find_many_sub_basic_blocks (blocks);
1324 purge_all_dead_edges ();
1325 sbitmap_free (blocks);
1328 #ifdef ENABLE_CHECKING
1332 /* There's no need to defer outputting this function any more; we
1333 know we want to output it. */
1334 DECL_DEFER_OUTPUT (current_function_decl) = 0;
1336 /* Now that we're done expanding trees to RTL, we shouldn't have any
1337 more CONCATs anywhere. */
1338 generating_concat_p = 0;
1340 finalize_block_changes ();
1345 "\n\n;;\n;; Full RTL generated for this function:\n;;\n");
1346 /* And the pass manager will dump RTL for us. */
1350 struct tree_opt_pass pass_expand =
1352 "expand", /* name */
1354 tree_expand_cfg, /* execute */
1357 0, /* static_pass_number */
1358 TV_EXPAND, /* tv_id */
1359 /* ??? If TER is enabled, we actually receive GENERIC. */
1360 PROP_gimple_leh | PROP_cfg, /* properties_required */
1361 PROP_rtl, /* properties_provided */
1362 PROP_gimple_leh, /* properties_destroyed */
1363 0, /* todo_flags_start */
1364 0, /* todo_flags_finish */