1 /* A pass for lowering trees to RTL.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "basic-block.h"
30 #include "langhooks.h"
31 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
37 #include "diagnostic.h"
41 #include "tree-inline.h"
42 #include "value-prof.h"
46 /* Return an expression tree corresponding to the RHS of GIMPLE
50 gimple_assign_rhs_to_tree (gimple stmt)
53 enum gimple_rhs_class class;
55 class = get_gimple_rhs_class (gimple_expr_code (stmt));
57 if (class == GIMPLE_BINARY_RHS)
58 t = build2 (gimple_assign_rhs_code (stmt),
59 TREE_TYPE (gimple_assign_lhs (stmt)),
60 gimple_assign_rhs1 (stmt),
61 gimple_assign_rhs2 (stmt));
62 else if (class == GIMPLE_UNARY_RHS)
63 t = build1 (gimple_assign_rhs_code (stmt),
64 TREE_TYPE (gimple_assign_lhs (stmt)),
65 gimple_assign_rhs1 (stmt));
66 else if (class == GIMPLE_SINGLE_RHS)
67 t = gimple_assign_rhs1 (stmt);
74 /* Return an expression tree corresponding to the PREDICATE of GIMPLE_COND
78 gimple_cond_pred_to_tree (gimple stmt)
80 return build2 (gimple_cond_code (stmt), boolean_type_node,
81 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
84 /* Helper for gimple_to_tree. Set EXPR_LOCATION for every expression
85 inside *TP. DATA is the location to set. */
88 set_expr_location_r (tree *tp, int *ws ATTRIBUTE_UNUSED, void *data)
90 location_t *loc = (location_t *) data;
92 SET_EXPR_LOCATION (*tp, *loc);
98 /* RTL expansion has traditionally been done on trees, so the
99 transition to doing it on GIMPLE tuples is very invasive to the RTL
100 expander. To facilitate the transition, this function takes a
101 GIMPLE tuple STMT and returns the same statement in the form of a
105 gimple_to_tree (gimple stmt)
109 tree_ann_common_t ann;
112 switch (gimple_code (stmt))
116 tree lhs = gimple_assign_lhs (stmt);
118 t = gimple_assign_rhs_to_tree (stmt);
119 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
120 if (gimple_assign_nontemporal_move_p (stmt))
121 MOVE_NONTEMPORAL (t) = true;
126 t = gimple_cond_pred_to_tree (stmt);
127 t = build3 (COND_EXPR, void_type_node, t, NULL_TREE, NULL_TREE);
131 t = build1 (GOTO_EXPR, void_type_node, gimple_goto_dest (stmt));
135 t = build1 (LABEL_EXPR, void_type_node, gimple_label_label (stmt));
140 tree retval = gimple_return_retval (stmt);
142 if (retval && retval != error_mark_node)
144 tree result = DECL_RESULT (current_function_decl);
146 /* If we are not returning the current function's RESULT_DECL,
147 build an assignment to it. */
148 if (retval != result)
150 /* I believe that a function's RESULT_DECL is unique. */
151 gcc_assert (TREE_CODE (retval) != RESULT_DECL);
153 retval = build2 (MODIFY_EXPR, TREE_TYPE (result),
157 t = build1 (RETURN_EXPR, void_type_node, retval);
168 n = gimple_asm_noutputs (stmt);
171 t = out = gimple_asm_output_op (stmt, 0);
172 for (i = 1; i < n; i++)
174 TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
175 t = gimple_asm_output_op (stmt, i);
180 n = gimple_asm_ninputs (stmt);
183 t = in = gimple_asm_input_op (stmt, 0);
184 for (i = 1; i < n; i++)
186 TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
187 t = gimple_asm_input_op (stmt, i);
192 n = gimple_asm_nclobbers (stmt);
195 t = cl = gimple_asm_clobber_op (stmt, 0);
196 for (i = 1; i < n; i++)
198 TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
199 t = gimple_asm_clobber_op (stmt, i);
203 s = gimple_asm_string (stmt);
204 t = build4 (ASM_EXPR, void_type_node, build_string (strlen (s), s),
206 ASM_VOLATILE_P (t) = gimple_asm_volatile_p (stmt);
207 ASM_INPUT_P (t) = gimple_asm_input_p (stmt);
215 tree_ann_common_t ann;
217 t = build_vl_exp (CALL_EXPR, gimple_call_num_args (stmt) + 3);
219 fn = gimple_call_fn (stmt);
220 if (TREE_CODE (fn) == FUNCTION_DECL)
221 CALL_EXPR_FN (t) = build1 (ADDR_EXPR,
222 build_pointer_type (TREE_TYPE (fn)),
225 CALL_EXPR_FN (t) = fn;
227 TREE_TYPE (t) = gimple_call_return_type (stmt);
229 CALL_EXPR_STATIC_CHAIN (t) = gimple_call_chain (stmt);
231 for (i = 0; i < gimple_call_num_args (stmt); i++)
232 CALL_EXPR_ARG (t, i) = gimple_call_arg (stmt, i);
234 if (!(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
235 TREE_SIDE_EFFECTS (t) = 1;
237 if (gimple_call_flags (stmt) & ECF_NOTHROW)
238 TREE_NOTHROW (t) = 1;
240 CALL_EXPR_TAILCALL (t) = gimple_call_tail_p (stmt);
241 CALL_EXPR_RETURN_SLOT_OPT (t) = gimple_call_return_slot_opt_p (stmt);
242 CALL_FROM_THUNK_P (t) = gimple_call_from_thunk_p (stmt);
243 CALL_CANNOT_INLINE_P (t) = gimple_call_cannot_inline_p (stmt);
244 CALL_EXPR_VA_ARG_PACK (t) = gimple_call_va_arg_pack_p (stmt);
246 /* If the call has a LHS then create a MODIFY_EXPR to hold it. */
248 tree lhs = gimple_call_lhs (stmt);
251 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
254 /* Record the original call statement, as it may be used
255 to retrieve profile information during expansion. */
256 if (TREE_CODE (fn) == FUNCTION_DECL && DECL_BUILT_IN (fn))
258 ann = get_tree_common_ann (t);
268 tree elt = gimple_switch_label (stmt, 0);
270 label_vec = make_tree_vec (gimple_switch_num_labels (stmt));
272 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
274 for (i = 1; i < gimple_switch_num_labels (stmt); i++)
275 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, i);
277 /* The default case in a SWITCH_EXPR must be at the end of
279 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, 0);
283 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
284 TREE_VEC_ELT (label_vec, i) = gimple_switch_label (stmt, i);
287 t = build3 (SWITCH_EXPR, void_type_node, gimple_switch_index (stmt),
294 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
298 t = build_resx (gimple_resx_region (stmt));
304 error ("Unrecognized GIMPLE statement during RTL expansion");
305 print_gimple_stmt (stderr, stmt, 4, 0);
310 /* Ignore any bad gimple codes if we're going to die anyhow,
311 so we can at least set TREE_ASM_WRITTEN and have the rest
312 of compilation advance without sudden ICE death. */
313 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
318 /* If STMT is inside an exception region, record it in the generated
320 rn = lookup_stmt_eh_region (stmt);
323 tree call = get_call_expr_in (t);
325 ann = get_tree_common_ann (t);
328 /* For a CALL_EXPR on the RHS of an assignment, calls.c looks up
329 the CALL_EXPR not the assignment statment for EH region number. */
330 if (call && call != t)
332 ann = get_tree_common_ann (call);
337 /* Set EXPR_LOCATION in all the embedded expressions. */
338 loc = gimple_location (stmt);
339 walk_tree (&t, set_expr_location_r, (void *) &loc, NULL);
341 TREE_BLOCK (t) = gimple_block (stmt);
347 /* Release back to GC memory allocated by gimple_to_tree. */
350 release_stmt_tree (gimple stmt, tree stmt_tree)
352 tree_ann_common_t ann;
354 switch (gimple_code (stmt))
357 if (get_gimple_rhs_class (gimple_expr_code (stmt)) != GIMPLE_SINGLE_RHS)
358 ggc_free (TREE_OPERAND (stmt_tree, 1));
361 ggc_free (COND_EXPR_COND (stmt_tree));
364 if (TREE_OPERAND (stmt_tree, 0)
365 && TREE_CODE (TREE_OPERAND (stmt_tree, 0)) == MODIFY_EXPR)
366 ggc_free (TREE_OPERAND (stmt_tree, 0));
369 if (gimple_call_lhs (stmt))
371 if (TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL)
372 ggc_free (CALL_EXPR_FN (TREE_OPERAND (stmt_tree, 1)));
373 ann = tree_common_ann (TREE_OPERAND (stmt_tree, 1));
376 ggc_free (TREE_OPERAND (stmt_tree, 1));
378 else if (TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL)
379 ggc_free (CALL_EXPR_FN (stmt_tree));
384 ann = tree_common_ann (stmt_tree);
387 ggc_free (stmt_tree);
391 /* Verify that there is exactly single jump instruction since last and attach
392 REG_BR_PROB note specifying probability.
393 ??? We really ought to pass the probability down to RTL expanders and let it
394 re-distribute it when the conditional expands into multiple conditionals.
395 This is however difficult to do. */
397 add_reg_br_prob_note (rtx last, int probability)
399 if (profile_status == PROFILE_ABSENT)
401 for (last = NEXT_INSN (last); last && NEXT_INSN (last); last = NEXT_INSN (last))
404 /* It is common to emit condjump-around-jump sequence when we don't know
405 how to reverse the conditional. Special case this. */
406 if (!any_condjump_p (last)
407 || !JUMP_P (NEXT_INSN (last))
408 || !simplejump_p (NEXT_INSN (last))
409 || !NEXT_INSN (NEXT_INSN (last))
410 || !BARRIER_P (NEXT_INSN (NEXT_INSN (last)))
411 || !NEXT_INSN (NEXT_INSN (NEXT_INSN (last)))
412 || !LABEL_P (NEXT_INSN (NEXT_INSN (NEXT_INSN (last))))
413 || NEXT_INSN (NEXT_INSN (NEXT_INSN (NEXT_INSN (last)))))
415 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
416 add_reg_note (last, REG_BR_PROB,
417 GEN_INT (REG_BR_PROB_BASE - probability));
420 if (!last || !JUMP_P (last) || !any_condjump_p (last))
422 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
423 add_reg_note (last, REG_BR_PROB, GEN_INT (probability));
427 fprintf (dump_file, "Failed to add probability note\n");
431 #ifndef STACK_ALIGNMENT_NEEDED
432 #define STACK_ALIGNMENT_NEEDED 1
436 /* This structure holds data relevant to one variable that will be
437 placed in a stack slot. */
443 /* The offset of the variable. During partitioning, this is the
444 offset relative to the partition. After partitioning, this
445 is relative to the stack frame. */
446 HOST_WIDE_INT offset;
448 /* Initially, the size of the variable. Later, the size of the partition,
449 if this variable becomes it's partition's representative. */
452 /* The *byte* alignment required for this variable. Or as, with the
453 size, the alignment for this partition. */
456 /* The partition representative. */
457 size_t representative;
459 /* The next stack variable in the partition, or EOC. */
463 #define EOC ((size_t)-1)
465 /* We have an array of such objects while deciding allocation. */
466 static struct stack_var *stack_vars;
467 static size_t stack_vars_alloc;
468 static size_t stack_vars_num;
470 /* An array of indices such that stack_vars[stack_vars_sorted[i]].size
471 is non-decreasing. */
472 static size_t *stack_vars_sorted;
474 /* We have an interference graph between such objects. This graph
475 is lower triangular. */
476 static bool *stack_vars_conflict;
477 static size_t stack_vars_conflict_alloc;
479 /* The phase of the stack frame. This is the known misalignment of
480 virtual_stack_vars_rtx from PREFERRED_STACK_BOUNDARY. That is,
481 (frame_offset+frame_phase) % PREFERRED_STACK_BOUNDARY == 0. */
482 static int frame_phase;
484 /* Used during expand_used_vars to remember if we saw any decls for
485 which we'd like to enable stack smashing protection. */
486 static bool has_protected_decls;
488 /* Used during expand_used_vars. Remember if we say a character buffer
489 smaller than our cutoff threshold. Used for -Wstack-protector. */
490 static bool has_short_buffer;
492 /* Discover the byte alignment to use for DECL. Ignore alignment
493 we can't do with expected alignment of the stack boundary. */
496 get_decl_align_unit (tree decl)
500 align = DECL_ALIGN (decl);
501 align = LOCAL_ALIGNMENT (TREE_TYPE (decl), align);
502 if (align > PREFERRED_STACK_BOUNDARY)
503 align = PREFERRED_STACK_BOUNDARY;
504 if (crtl->stack_alignment_needed < align)
505 crtl->stack_alignment_needed = align;
507 return align / BITS_PER_UNIT;
510 /* Allocate SIZE bytes at byte alignment ALIGN from the stack frame.
511 Return the frame offset. */
514 alloc_stack_frame_space (HOST_WIDE_INT size, HOST_WIDE_INT align)
516 HOST_WIDE_INT offset, new_frame_offset;
518 new_frame_offset = frame_offset;
519 if (FRAME_GROWS_DOWNWARD)
521 new_frame_offset -= size + frame_phase;
522 new_frame_offset &= -align;
523 new_frame_offset += frame_phase;
524 offset = new_frame_offset;
528 new_frame_offset -= frame_phase;
529 new_frame_offset += align - 1;
530 new_frame_offset &= -align;
531 new_frame_offset += frame_phase;
532 offset = new_frame_offset;
533 new_frame_offset += size;
535 frame_offset = new_frame_offset;
537 if (frame_offset_overflow (frame_offset, cfun->decl))
538 frame_offset = offset = 0;
543 /* Accumulate DECL into STACK_VARS. */
546 add_stack_var (tree decl)
548 if (stack_vars_num >= stack_vars_alloc)
550 if (stack_vars_alloc)
551 stack_vars_alloc = stack_vars_alloc * 3 / 2;
553 stack_vars_alloc = 32;
555 = XRESIZEVEC (struct stack_var, stack_vars, stack_vars_alloc);
557 stack_vars[stack_vars_num].decl = decl;
558 stack_vars[stack_vars_num].offset = 0;
559 stack_vars[stack_vars_num].size = tree_low_cst (DECL_SIZE_UNIT (decl), 1);
560 stack_vars[stack_vars_num].alignb = get_decl_align_unit (decl);
562 /* All variables are initially in their own partition. */
563 stack_vars[stack_vars_num].representative = stack_vars_num;
564 stack_vars[stack_vars_num].next = EOC;
566 /* Ensure that this decl doesn't get put onto the list twice. */
567 SET_DECL_RTL (decl, pc_rtx);
572 /* Compute the linear index of a lower-triangular coordinate (I, J). */
575 triangular_index (size_t i, size_t j)
582 return (i * (i + 1)) / 2 + j;
585 /* Ensure that STACK_VARS_CONFLICT is large enough for N objects. */
588 resize_stack_vars_conflict (size_t n)
590 size_t size = triangular_index (n-1, n-1) + 1;
592 if (size <= stack_vars_conflict_alloc)
595 stack_vars_conflict = XRESIZEVEC (bool, stack_vars_conflict, size);
596 memset (stack_vars_conflict + stack_vars_conflict_alloc, 0,
597 (size - stack_vars_conflict_alloc) * sizeof (bool));
598 stack_vars_conflict_alloc = size;
601 /* Make the decls associated with luid's X and Y conflict. */
604 add_stack_var_conflict (size_t x, size_t y)
606 size_t index = triangular_index (x, y);
607 gcc_assert (index < stack_vars_conflict_alloc);
608 stack_vars_conflict[index] = true;
611 /* Check whether the decls associated with luid's X and Y conflict. */
614 stack_var_conflict_p (size_t x, size_t y)
616 size_t index = triangular_index (x, y);
617 gcc_assert (index < stack_vars_conflict_alloc);
618 return stack_vars_conflict[index];
621 /* Returns true if TYPE is or contains a union type. */
624 aggregate_contains_union_type (tree type)
628 if (TREE_CODE (type) == UNION_TYPE
629 || TREE_CODE (type) == QUAL_UNION_TYPE)
631 if (TREE_CODE (type) == ARRAY_TYPE)
632 return aggregate_contains_union_type (TREE_TYPE (type));
633 if (TREE_CODE (type) != RECORD_TYPE)
636 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
637 if (TREE_CODE (field) == FIELD_DECL)
638 if (aggregate_contains_union_type (TREE_TYPE (field)))
644 /* A subroutine of expand_used_vars. If two variables X and Y have alias
645 sets that do not conflict, then do add a conflict for these variables
646 in the interference graph. We also need to make sure to add conflicts
647 for union containing structures. Else RTL alias analysis comes along
648 and due to type based aliasing rules decides that for two overlapping
649 union temporaries { short s; int i; } accesses to the same mem through
650 different types may not alias and happily reorders stores across
651 life-time boundaries of the temporaries (See PR25654).
652 We also have to mind MEM_IN_STRUCT_P and MEM_SCALAR_P. */
655 add_alias_set_conflicts (void)
657 size_t i, j, n = stack_vars_num;
659 for (i = 0; i < n; ++i)
661 tree type_i = TREE_TYPE (stack_vars[i].decl);
662 bool aggr_i = AGGREGATE_TYPE_P (type_i);
665 contains_union = aggregate_contains_union_type (type_i);
666 for (j = 0; j < i; ++j)
668 tree type_j = TREE_TYPE (stack_vars[j].decl);
669 bool aggr_j = AGGREGATE_TYPE_P (type_j);
671 /* Either the objects conflict by means of type based
672 aliasing rules, or we need to add a conflict. */
673 || !objects_must_conflict_p (type_i, type_j)
674 /* In case the types do not conflict ensure that access
675 to elements will conflict. In case of unions we have
676 to be careful as type based aliasing rules may say
677 access to the same memory does not conflict. So play
678 safe and add a conflict in this case. */
680 add_stack_var_conflict (i, j);
685 /* A subroutine of partition_stack_vars. A comparison function for qsort,
686 sorting an array of indices by the size of the object. */
689 stack_var_size_cmp (const void *a, const void *b)
691 HOST_WIDE_INT sa = stack_vars[*(const size_t *)a].size;
692 HOST_WIDE_INT sb = stack_vars[*(const size_t *)b].size;
693 unsigned int uida = DECL_UID (stack_vars[*(const size_t *)a].decl);
694 unsigned int uidb = DECL_UID (stack_vars[*(const size_t *)b].decl);
700 /* For stack variables of the same size use the uid of the decl
701 to make the sort stable. */
709 /* A subroutine of partition_stack_vars. The UNION portion of a UNION/FIND
710 partitioning algorithm. Partitions A and B are known to be non-conflicting.
711 Merge them into a single partition A.
713 At the same time, add OFFSET to all variables in partition B. At the end
714 of the partitioning process we've have a nice block easy to lay out within
718 union_stack_vars (size_t a, size_t b, HOST_WIDE_INT offset)
722 /* Update each element of partition B with the given offset,
723 and merge them into partition A. */
724 for (last = i = b; i != EOC; last = i, i = stack_vars[i].next)
726 stack_vars[i].offset += offset;
727 stack_vars[i].representative = a;
729 stack_vars[last].next = stack_vars[a].next;
730 stack_vars[a].next = b;
732 /* Update the required alignment of partition A to account for B. */
733 if (stack_vars[a].alignb < stack_vars[b].alignb)
734 stack_vars[a].alignb = stack_vars[b].alignb;
736 /* Update the interference graph and merge the conflicts. */
737 for (last = stack_vars_num, i = 0; i < last; ++i)
738 if (stack_var_conflict_p (b, i))
739 add_stack_var_conflict (a, i);
742 /* A subroutine of expand_used_vars. Binpack the variables into
743 partitions constrained by the interference graph. The overall
744 algorithm used is as follows:
746 Sort the objects by size.
751 Look for the largest non-conflicting object B with size <= S.
761 partition_stack_vars (void)
763 size_t si, sj, n = stack_vars_num;
765 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
766 for (si = 0; si < n; ++si)
767 stack_vars_sorted[si] = si;
772 qsort (stack_vars_sorted, n, sizeof (size_t), stack_var_size_cmp);
774 /* Special case: detect when all variables conflict, and thus we can't
775 do anything during the partitioning loop. It isn't uncommon (with
776 C code at least) to declare all variables at the top of the function,
777 and if we're not inlining, then all variables will be in the same scope.
778 Take advantage of very fast libc routines for this scan. */
779 gcc_assert (sizeof(bool) == sizeof(char));
780 if (memchr (stack_vars_conflict, false, stack_vars_conflict_alloc) == NULL)
783 for (si = 0; si < n; ++si)
785 size_t i = stack_vars_sorted[si];
786 HOST_WIDE_INT isize = stack_vars[i].size;
787 HOST_WIDE_INT offset = 0;
789 for (sj = si; sj-- > 0; )
791 size_t j = stack_vars_sorted[sj];
792 HOST_WIDE_INT jsize = stack_vars[j].size;
793 unsigned int jalign = stack_vars[j].alignb;
795 /* Ignore objects that aren't partition representatives. */
796 if (stack_vars[j].representative != j)
799 /* Ignore objects too large for the remaining space. */
803 /* Ignore conflicting objects. */
804 if (stack_var_conflict_p (i, j))
807 /* Refine the remaining space check to include alignment. */
808 if (offset & (jalign - 1))
810 HOST_WIDE_INT toff = offset;
812 toff &= -(HOST_WIDE_INT)jalign;
813 if (isize - (toff - offset) < jsize)
816 isize -= toff - offset;
820 /* UNION the objects, placing J at OFFSET. */
821 union_stack_vars (i, j, offset);
830 /* A debugging aid for expand_used_vars. Dump the generated partitions. */
833 dump_stack_var_partition (void)
835 size_t si, i, j, n = stack_vars_num;
837 for (si = 0; si < n; ++si)
839 i = stack_vars_sorted[si];
841 /* Skip variables that aren't partition representatives, for now. */
842 if (stack_vars[i].representative != i)
845 fprintf (dump_file, "Partition %lu: size " HOST_WIDE_INT_PRINT_DEC
846 " align %u\n", (unsigned long) i, stack_vars[i].size,
847 stack_vars[i].alignb);
849 for (j = i; j != EOC; j = stack_vars[j].next)
851 fputc ('\t', dump_file);
852 print_generic_expr (dump_file, stack_vars[j].decl, dump_flags);
853 fprintf (dump_file, ", offset " HOST_WIDE_INT_PRINT_DEC "\n",
854 stack_vars[j].offset);
859 /* Assign rtl to DECL at frame offset OFFSET. */
862 expand_one_stack_var_at (tree decl, HOST_WIDE_INT offset)
867 /* If this fails, we've overflowed the stack frame. Error nicely? */
868 gcc_assert (offset == trunc_int_for_mode (offset, Pmode));
870 x = plus_constant (virtual_stack_vars_rtx, offset);
871 x = gen_rtx_MEM (DECL_MODE (decl), x);
873 /* Set alignment we actually gave this decl. */
874 offset -= frame_phase;
875 align = offset & -offset;
876 align *= BITS_PER_UNIT;
877 if (align > STACK_BOUNDARY || align == 0)
878 align = STACK_BOUNDARY;
879 DECL_ALIGN (decl) = align;
880 DECL_USER_ALIGN (decl) = 0;
882 set_mem_attributes (x, decl, true);
883 SET_DECL_RTL (decl, x);
886 /* A subroutine of expand_used_vars. Give each partition representative
887 a unique location within the stack frame. Update each partition member
888 with that location. */
891 expand_stack_vars (bool (*pred) (tree))
893 size_t si, i, j, n = stack_vars_num;
895 for (si = 0; si < n; ++si)
897 HOST_WIDE_INT offset;
899 i = stack_vars_sorted[si];
901 /* Skip variables that aren't partition representatives, for now. */
902 if (stack_vars[i].representative != i)
905 /* Skip variables that have already had rtl assigned. See also
906 add_stack_var where we perpetrate this pc_rtx hack. */
907 if (DECL_RTL (stack_vars[i].decl) != pc_rtx)
910 /* Check the predicate to see whether this variable should be
911 allocated in this pass. */
912 if (pred && !pred (stack_vars[i].decl))
915 offset = alloc_stack_frame_space (stack_vars[i].size,
916 stack_vars[i].alignb);
918 /* Create rtl for each variable based on their location within the
920 for (j = i; j != EOC; j = stack_vars[j].next)
922 gcc_assert (stack_vars[j].offset <= stack_vars[i].size);
923 expand_one_stack_var_at (stack_vars[j].decl,
924 stack_vars[j].offset + offset);
929 /* Take into account all sizes of partitions and reset DECL_RTLs. */
931 account_stack_vars (void)
933 size_t si, j, i, n = stack_vars_num;
934 HOST_WIDE_INT size = 0;
936 for (si = 0; si < n; ++si)
938 i = stack_vars_sorted[si];
940 /* Skip variables that aren't partition representatives, for now. */
941 if (stack_vars[i].representative != i)
944 size += stack_vars[i].size;
945 for (j = i; j != EOC; j = stack_vars[j].next)
946 SET_DECL_RTL (stack_vars[j].decl, NULL);
951 /* A subroutine of expand_one_var. Called to immediately assign rtl
952 to a variable to be allocated in the stack frame. */
955 expand_one_stack_var (tree var)
957 HOST_WIDE_INT size, offset, align;
959 size = tree_low_cst (DECL_SIZE_UNIT (var), 1);
960 align = get_decl_align_unit (var);
961 offset = alloc_stack_frame_space (size, align);
963 expand_one_stack_var_at (var, offset);
966 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
967 that will reside in a hard register. */
970 expand_one_hard_reg_var (tree var)
972 rest_of_decl_compilation (var, 0, 0);
975 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
976 that will reside in a pseudo register. */
979 expand_one_register_var (tree var)
981 tree type = TREE_TYPE (var);
982 int unsignedp = TYPE_UNSIGNED (type);
983 enum machine_mode reg_mode
984 = promote_mode (type, DECL_MODE (var), &unsignedp, 0);
985 rtx x = gen_reg_rtx (reg_mode);
987 SET_DECL_RTL (var, x);
989 /* Note if the object is a user variable. */
990 if (!DECL_ARTIFICIAL (var))
993 if (POINTER_TYPE_P (type))
994 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
997 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL that
998 has some associated error, e.g. its type is error-mark. We just need
999 to pick something that won't crash the rest of the compiler. */
1002 expand_one_error_var (tree var)
1004 enum machine_mode mode = DECL_MODE (var);
1007 if (mode == BLKmode)
1008 x = gen_rtx_MEM (BLKmode, const0_rtx);
1009 else if (mode == VOIDmode)
1012 x = gen_reg_rtx (mode);
1014 SET_DECL_RTL (var, x);
1017 /* A subroutine of expand_one_var. VAR is a variable that will be
1018 allocated to the local stack frame. Return true if we wish to
1019 add VAR to STACK_VARS so that it will be coalesced with other
1020 variables. Return false to allocate VAR immediately.
1022 This function is used to reduce the number of variables considered
1023 for coalescing, which reduces the size of the quadratic problem. */
1026 defer_stack_allocation (tree var, bool toplevel)
1028 /* If stack protection is enabled, *all* stack variables must be deferred,
1029 so that we can re-order the strings to the top of the frame. */
1030 if (flag_stack_protect)
1033 /* Variables in the outermost scope automatically conflict with
1034 every other variable. The only reason to want to defer them
1035 at all is that, after sorting, we can more efficiently pack
1036 small variables in the stack frame. Continue to defer at -O2. */
1037 if (toplevel && optimize < 2)
1040 /* Without optimization, *most* variables are allocated from the
1041 stack, which makes the quadratic problem large exactly when we
1042 want compilation to proceed as quickly as possible. On the
1043 other hand, we don't want the function's stack frame size to
1044 get completely out of hand. So we avoid adding scalars and
1045 "small" aggregates to the list at all. */
1046 if (optimize == 0 && tree_low_cst (DECL_SIZE_UNIT (var), 1) < 32)
1052 /* A subroutine of expand_used_vars. Expand one variable according to
1053 its flavor. Variables to be placed on the stack are not actually
1054 expanded yet, merely recorded.
1055 When REALLY_EXPAND is false, only add stack values to be allocated.
1056 Return stack usage this variable is supposed to take.
1059 static HOST_WIDE_INT
1060 expand_one_var (tree var, bool toplevel, bool really_expand)
1062 if (TREE_CODE (var) != VAR_DECL)
1064 else if (DECL_EXTERNAL (var))
1066 else if (DECL_HAS_VALUE_EXPR_P (var))
1068 else if (TREE_STATIC (var))
1070 else if (DECL_RTL_SET_P (var))
1072 else if (TREE_TYPE (var) == error_mark_node)
1075 expand_one_error_var (var);
1077 else if (DECL_HARD_REGISTER (var))
1080 expand_one_hard_reg_var (var);
1082 else if (use_register_for_decl (var))
1085 expand_one_register_var (var);
1087 else if (defer_stack_allocation (var, toplevel))
1088 add_stack_var (var);
1092 expand_one_stack_var (var);
1093 return tree_low_cst (DECL_SIZE_UNIT (var), 1);
1098 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1099 expanding variables. Those variables that can be put into registers
1100 are allocated pseudos; those that can't are put on the stack.
1102 TOPLEVEL is true if this is the outermost BLOCK. */
1105 expand_used_vars_for_block (tree block, bool toplevel)
1107 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1110 old_sv_num = toplevel ? 0 : stack_vars_num;
1112 /* Expand all variables at this level. */
1113 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1115 expand_one_var (t, toplevel, true);
1117 this_sv_num = stack_vars_num;
1119 /* Expand all variables at containing levels. */
1120 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1121 expand_used_vars_for_block (t, false);
1123 /* Since we do not track exact variable lifetimes (which is not even
1124 possible for variables whose address escapes), we mirror the block
1125 tree in the interference graph. Here we cause all variables at this
1126 level, and all sublevels, to conflict. Do make certain that a
1127 variable conflicts with itself. */
1128 if (old_sv_num < this_sv_num)
1130 new_sv_num = stack_vars_num;
1131 resize_stack_vars_conflict (new_sv_num);
1133 for (i = old_sv_num; i < new_sv_num; ++i)
1134 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1135 add_stack_var_conflict (i, j);
1139 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1140 and clear TREE_USED on all local variables. */
1143 clear_tree_used (tree block)
1147 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1148 /* if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) */
1151 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1152 clear_tree_used (t);
1155 /* Examine TYPE and determine a bit mask of the following features. */
1157 #define SPCT_HAS_LARGE_CHAR_ARRAY 1
1158 #define SPCT_HAS_SMALL_CHAR_ARRAY 2
1159 #define SPCT_HAS_ARRAY 4
1160 #define SPCT_HAS_AGGREGATE 8
1163 stack_protect_classify_type (tree type)
1165 unsigned int ret = 0;
1168 switch (TREE_CODE (type))
1171 t = TYPE_MAIN_VARIANT (TREE_TYPE (type));
1172 if (t == char_type_node
1173 || t == signed_char_type_node
1174 || t == unsigned_char_type_node)
1176 unsigned HOST_WIDE_INT max = PARAM_VALUE (PARAM_SSP_BUFFER_SIZE);
1177 unsigned HOST_WIDE_INT len;
1179 if (!TYPE_SIZE_UNIT (type)
1180 || !host_integerp (TYPE_SIZE_UNIT (type), 1))
1183 len = tree_low_cst (TYPE_SIZE_UNIT (type), 1);
1186 ret = SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_ARRAY;
1188 ret = SPCT_HAS_LARGE_CHAR_ARRAY | SPCT_HAS_ARRAY;
1191 ret = SPCT_HAS_ARRAY;
1195 case QUAL_UNION_TYPE:
1197 ret = SPCT_HAS_AGGREGATE;
1198 for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
1199 if (TREE_CODE (t) == FIELD_DECL)
1200 ret |= stack_protect_classify_type (TREE_TYPE (t));
1210 /* Return nonzero if DECL should be segregated into the "vulnerable" upper
1211 part of the local stack frame. Remember if we ever return nonzero for
1212 any variable in this function. The return value is the phase number in
1213 which the variable should be allocated. */
1216 stack_protect_decl_phase (tree decl)
1218 unsigned int bits = stack_protect_classify_type (TREE_TYPE (decl));
1221 if (bits & SPCT_HAS_SMALL_CHAR_ARRAY)
1222 has_short_buffer = true;
1224 if (flag_stack_protect == 2)
1226 if ((bits & (SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_LARGE_CHAR_ARRAY))
1227 && !(bits & SPCT_HAS_AGGREGATE))
1229 else if (bits & SPCT_HAS_ARRAY)
1233 ret = (bits & SPCT_HAS_LARGE_CHAR_ARRAY) != 0;
1236 has_protected_decls = true;
1241 /* Two helper routines that check for phase 1 and phase 2. These are used
1242 as callbacks for expand_stack_vars. */
1245 stack_protect_decl_phase_1 (tree decl)
1247 return stack_protect_decl_phase (decl) == 1;
1251 stack_protect_decl_phase_2 (tree decl)
1253 return stack_protect_decl_phase (decl) == 2;
1256 /* Ensure that variables in different stack protection phases conflict
1257 so that they are not merged and share the same stack slot. */
1260 add_stack_protection_conflicts (void)
1262 size_t i, j, n = stack_vars_num;
1263 unsigned char *phase;
1265 phase = XNEWVEC (unsigned char, n);
1266 for (i = 0; i < n; ++i)
1267 phase[i] = stack_protect_decl_phase (stack_vars[i].decl);
1269 for (i = 0; i < n; ++i)
1271 unsigned char ph_i = phase[i];
1272 for (j = 0; j < i; ++j)
1273 if (ph_i != phase[j])
1274 add_stack_var_conflict (i, j);
1280 /* Create a decl for the guard at the top of the stack frame. */
1283 create_stack_guard (void)
1285 tree guard = build_decl (VAR_DECL, NULL, ptr_type_node);
1286 TREE_THIS_VOLATILE (guard) = 1;
1287 TREE_USED (guard) = 1;
1288 expand_one_stack_var (guard);
1289 crtl->stack_protect_guard = guard;
1292 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1293 expanding variables. Those variables that can be put into registers
1294 are allocated pseudos; those that can't are put on the stack.
1296 TOPLEVEL is true if this is the outermost BLOCK. */
1298 static HOST_WIDE_INT
1299 account_used_vars_for_block (tree block, bool toplevel)
1301 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1303 HOST_WIDE_INT size = 0;
1305 old_sv_num = toplevel ? 0 : stack_vars_num;
1307 /* Expand all variables at this level. */
1308 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1310 size += expand_one_var (t, toplevel, false);
1312 this_sv_num = stack_vars_num;
1314 /* Expand all variables at containing levels. */
1315 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1316 size += account_used_vars_for_block (t, false);
1318 /* Since we do not track exact variable lifetimes (which is not even
1319 possible for variables whose address escapes), we mirror the block
1320 tree in the interference graph. Here we cause all variables at this
1321 level, and all sublevels, to conflict. Do make certain that a
1322 variable conflicts with itself. */
1323 if (old_sv_num < this_sv_num)
1325 new_sv_num = stack_vars_num;
1326 resize_stack_vars_conflict (new_sv_num);
1328 for (i = old_sv_num; i < new_sv_num; ++i)
1329 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1330 add_stack_var_conflict (i, j);
1335 /* Prepare for expanding variables. */
1337 init_vars_expansion (void)
1340 /* Set TREE_USED on all variables in the local_decls. */
1341 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1342 TREE_USED (TREE_VALUE (t)) = 1;
1344 /* Clear TREE_USED on all variables associated with a block scope. */
1345 clear_tree_used (DECL_INITIAL (current_function_decl));
1347 /* Initialize local stack smashing state. */
1348 has_protected_decls = false;
1349 has_short_buffer = false;
1352 /* Free up stack variable graph data. */
1354 fini_vars_expansion (void)
1356 XDELETEVEC (stack_vars);
1357 XDELETEVEC (stack_vars_sorted);
1358 XDELETEVEC (stack_vars_conflict);
1360 stack_vars_alloc = stack_vars_num = 0;
1361 stack_vars_conflict = NULL;
1362 stack_vars_conflict_alloc = 0;
1366 estimated_stack_frame_size (void)
1368 HOST_WIDE_INT size = 0;
1369 tree t, outer_block = DECL_INITIAL (current_function_decl);
1371 init_vars_expansion ();
1373 /* At this point all variables on the local_decls with TREE_USED
1374 set are not associated with any block scope. Lay them out. */
1375 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1377 tree var = TREE_VALUE (t);
1379 if (TREE_USED (var))
1380 size += expand_one_var (var, true, false);
1381 TREE_USED (var) = 1;
1383 size += account_used_vars_for_block (outer_block, true);
1384 if (stack_vars_num > 0)
1386 /* Due to the way alias sets work, no variables with non-conflicting
1387 alias sets may be assigned the same address. Add conflicts to
1389 add_alias_set_conflicts ();
1391 /* If stack protection is enabled, we don't share space between
1392 vulnerable data and non-vulnerable data. */
1393 if (flag_stack_protect)
1394 add_stack_protection_conflicts ();
1396 /* Now that we have collected all stack variables, and have computed a
1397 minimal interference graph, attempt to save some stack space. */
1398 partition_stack_vars ();
1400 dump_stack_var_partition ();
1402 size += account_stack_vars ();
1403 fini_vars_expansion ();
1408 /* Expand all variables used in the function. */
1411 expand_used_vars (void)
1413 tree t, outer_block = DECL_INITIAL (current_function_decl);
1415 /* Compute the phase of the stack frame for this function. */
1417 int align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1418 int off = STARTING_FRAME_OFFSET % align;
1419 frame_phase = off ? align - off : 0;
1422 init_vars_expansion ();
1424 /* At this point all variables on the local_decls with TREE_USED
1425 set are not associated with any block scope. Lay them out. */
1426 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1428 tree var = TREE_VALUE (t);
1429 bool expand_now = false;
1431 /* We didn't set a block for static or extern because it's hard
1432 to tell the difference between a global variable (re)declared
1433 in a local scope, and one that's really declared there to
1434 begin with. And it doesn't really matter much, since we're
1435 not giving them stack space. Expand them now. */
1436 if (TREE_STATIC (var) || DECL_EXTERNAL (var))
1439 /* Any variable that could have been hoisted into an SSA_NAME
1440 will have been propagated anywhere the optimizers chose,
1441 i.e. not confined to their original block. Allocate them
1442 as if they were defined in the outermost scope. */
1443 else if (is_gimple_reg (var))
1446 /* If the variable is not associated with any block, then it
1447 was created by the optimizers, and could be live anywhere
1449 else if (TREE_USED (var))
1452 /* Finally, mark all variables on the list as used. We'll use
1453 this in a moment when we expand those associated with scopes. */
1454 TREE_USED (var) = 1;
1457 expand_one_var (var, true, true);
1459 cfun->local_decls = NULL_TREE;
1461 /* At this point, all variables within the block tree with TREE_USED
1462 set are actually used by the optimized function. Lay them out. */
1463 expand_used_vars_for_block (outer_block, true);
1465 if (stack_vars_num > 0)
1467 /* Due to the way alias sets work, no variables with non-conflicting
1468 alias sets may be assigned the same address. Add conflicts to
1470 add_alias_set_conflicts ();
1472 /* If stack protection is enabled, we don't share space between
1473 vulnerable data and non-vulnerable data. */
1474 if (flag_stack_protect)
1475 add_stack_protection_conflicts ();
1477 /* Now that we have collected all stack variables, and have computed a
1478 minimal interference graph, attempt to save some stack space. */
1479 partition_stack_vars ();
1481 dump_stack_var_partition ();
1484 /* There are several conditions under which we should create a
1485 stack guard: protect-all, alloca used, protected decls present. */
1486 if (flag_stack_protect == 2
1487 || (flag_stack_protect
1488 && (cfun->calls_alloca || has_protected_decls)))
1489 create_stack_guard ();
1491 /* Assign rtl to each variable based on these partitions. */
1492 if (stack_vars_num > 0)
1494 /* Reorder decls to be protected by iterating over the variables
1495 array multiple times, and allocating out of each phase in turn. */
1496 /* ??? We could probably integrate this into the qsort we did
1497 earlier, such that we naturally see these variables first,
1498 and thus naturally allocate things in the right order. */
1499 if (has_protected_decls)
1501 /* Phase 1 contains only character arrays. */
1502 expand_stack_vars (stack_protect_decl_phase_1);
1504 /* Phase 2 contains other kinds of arrays. */
1505 if (flag_stack_protect == 2)
1506 expand_stack_vars (stack_protect_decl_phase_2);
1509 expand_stack_vars (NULL);
1511 fini_vars_expansion ();
1514 /* If the target requires that FRAME_OFFSET be aligned, do it. */
1515 if (STACK_ALIGNMENT_NEEDED)
1517 HOST_WIDE_INT align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1518 if (!FRAME_GROWS_DOWNWARD)
1519 frame_offset += align - 1;
1520 frame_offset &= -align;
1525 /* If we need to produce a detailed dump, print the tree representation
1526 for STMT to the dump file. SINCE is the last RTX after which the RTL
1527 generated for STMT should have been appended. */
1530 maybe_dump_rtl_for_gimple_stmt (gimple stmt, rtx since)
1532 if (dump_file && (dump_flags & TDF_DETAILS))
1534 fprintf (dump_file, "\n;; ");
1535 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1536 fprintf (dump_file, "\n");
1538 print_rtl (dump_file, since ? NEXT_INSN (since) : since);
1542 /* Maps the blocks that do not contain tree labels to rtx labels. */
1544 static struct pointer_map_t *lab_rtx_for_bb;
1546 /* Returns the label_rtx expression for a label starting basic block BB. */
1549 label_rtx_for_bb (basic_block bb ATTRIBUTE_UNUSED)
1551 gimple_stmt_iterator gsi;
1556 if (bb->flags & BB_RTL)
1557 return block_label (bb);
1559 elt = pointer_map_contains (lab_rtx_for_bb, bb);
1563 /* Find the tree label if it is present. */
1565 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1567 lab_stmt = gsi_stmt (gsi);
1568 if (gimple_code (lab_stmt) != GIMPLE_LABEL)
1571 lab = gimple_label_label (lab_stmt);
1572 if (DECL_NONLOCAL (lab))
1575 return label_rtx (lab);
1578 elt = pointer_map_insert (lab_rtx_for_bb, bb);
1579 *elt = gen_label_rtx ();
1584 /* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_COND.
1585 Returns a new basic block if we've terminated the current basic
1586 block and created a new one. */
1589 expand_gimple_cond (basic_block bb, gimple stmt)
1591 basic_block new_bb, dest;
1595 tree pred = gimple_cond_pred_to_tree (stmt);
1598 last2 = last = get_last_insn ();
1600 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1601 if (gimple_has_location (stmt))
1603 set_curr_insn_source_location (gimple_location (stmt));
1604 set_curr_insn_block (gimple_block (stmt));
1607 /* These flags have no purpose in RTL land. */
1608 true_edge->flags &= ~EDGE_TRUE_VALUE;
1609 false_edge->flags &= ~EDGE_FALSE_VALUE;
1611 /* We can either have a pure conditional jump with one fallthru edge or
1612 two-way jump that needs to be decomposed into two basic blocks. */
1613 if (false_edge->dest == bb->next_bb)
1615 jumpif (pred, label_rtx_for_bb (true_edge->dest));
1616 add_reg_br_prob_note (last, true_edge->probability);
1617 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1618 if (true_edge->goto_locus)
1619 set_curr_insn_source_location (true_edge->goto_locus);
1620 false_edge->flags |= EDGE_FALLTHRU;
1624 if (true_edge->dest == bb->next_bb)
1626 jumpifnot (pred, label_rtx_for_bb (false_edge->dest));
1627 add_reg_br_prob_note (last, false_edge->probability);
1628 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1629 if (false_edge->goto_locus)
1630 set_curr_insn_source_location (false_edge->goto_locus);
1631 true_edge->flags |= EDGE_FALLTHRU;
1636 jumpif (pred, label_rtx_for_bb (true_edge->dest));
1637 add_reg_br_prob_note (last, true_edge->probability);
1638 last = get_last_insn ();
1639 emit_jump (label_rtx_for_bb (false_edge->dest));
1642 if (BARRIER_P (BB_END (bb)))
1643 BB_END (bb) = PREV_INSN (BB_END (bb));
1644 update_bb_for_insn (bb);
1646 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
1647 dest = false_edge->dest;
1648 redirect_edge_succ (false_edge, new_bb);
1649 false_edge->flags |= EDGE_FALLTHRU;
1650 new_bb->count = false_edge->count;
1651 new_bb->frequency = EDGE_FREQUENCY (false_edge);
1652 new_edge = make_edge (new_bb, dest, 0);
1653 new_edge->probability = REG_BR_PROB_BASE;
1654 new_edge->count = new_bb->count;
1655 if (BARRIER_P (BB_END (new_bb)))
1656 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
1657 update_bb_for_insn (new_bb);
1659 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1661 if (false_edge->goto_locus)
1662 set_curr_insn_source_location (false_edge->goto_locus);
1668 /* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_CALL
1669 that has CALL_EXPR_TAILCALL set. Returns non-null if we actually
1670 generated a tail call (something that might be denied by the ABI
1671 rules governing the call; see calls.c).
1673 Sets CAN_FALLTHRU if we generated a *conditional* tail call, and
1674 can still reach the rest of BB. The case here is __builtin_sqrt,
1675 where the NaN result goes through the external function (with a
1676 tailcall) and the normal result happens via a sqrt instruction. */
1679 expand_gimple_tailcall (basic_block bb, gimple stmt, bool *can_fallthru)
1686 tree stmt_tree = gimple_to_tree (stmt);
1688 last2 = last = get_last_insn ();
1690 expand_expr_stmt (stmt_tree);
1692 release_stmt_tree (stmt, stmt_tree);
1694 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
1695 if (CALL_P (last) && SIBLING_CALL_P (last))
1698 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1700 *can_fallthru = true;
1704 /* ??? Wouldn't it be better to just reset any pending stack adjust?
1705 Any instructions emitted here are about to be deleted. */
1706 do_pending_stack_adjust ();
1708 /* Remove any non-eh, non-abnormal edges that don't go to exit. */
1709 /* ??? I.e. the fallthrough edge. HOWEVER! If there were to be
1710 EH or abnormal edges, we shouldn't have created a tail call in
1711 the first place. So it seems to me we should just be removing
1712 all edges here, or redirecting the existing fallthru edge to
1718 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1720 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
1722 if (e->dest != EXIT_BLOCK_PTR)
1724 e->dest->count -= e->count;
1725 e->dest->frequency -= EDGE_FREQUENCY (e);
1726 if (e->dest->count < 0)
1728 if (e->dest->frequency < 0)
1729 e->dest->frequency = 0;
1732 probability += e->probability;
1739 /* This is somewhat ugly: the call_expr expander often emits instructions
1740 after the sibcall (to perform the function return). These confuse the
1741 find_many_sub_basic_blocks code, so we need to get rid of these. */
1742 last = NEXT_INSN (last);
1743 gcc_assert (BARRIER_P (last));
1745 *can_fallthru = false;
1746 while (NEXT_INSN (last))
1748 /* For instance an sqrt builtin expander expands if with
1749 sibcall in the then and label for `else`. */
1750 if (LABEL_P (NEXT_INSN (last)))
1752 *can_fallthru = true;
1755 delete_insn (NEXT_INSN (last));
1758 e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
1759 e->probability += probability;
1762 update_bb_for_insn (bb);
1764 if (NEXT_INSN (last))
1766 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
1769 if (BARRIER_P (last))
1770 BB_END (bb) = PREV_INSN (last);
1773 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1778 /* Expand basic block BB from GIMPLE trees to RTL. */
1781 expand_gimple_basic_block (basic_block bb)
1783 gimple_stmt_iterator gsi;
1792 fprintf (dump_file, "\n;; Generating RTL for gimple basic block %d\n",
1795 /* Note that since we are now transitioning from GIMPLE to RTL, we
1796 cannot use the gsi_*_bb() routines because they expect the basic
1797 block to be in GIMPLE, instead of RTL. Therefore, we need to
1798 access the BB sequence directly. */
1799 stmts = bb_seq (bb);
1800 bb->il.gimple = NULL;
1801 init_rtl_bb_info (bb);
1802 bb->flags |= BB_RTL;
1804 /* Remove the RETURN_EXPR if we may fall though to the exit
1806 gsi = gsi_last (stmts);
1807 if (!gsi_end_p (gsi)
1808 && gimple_code (gsi_stmt (gsi)) == GIMPLE_RETURN)
1810 gimple ret_stmt = gsi_stmt (gsi);
1812 gcc_assert (single_succ_p (bb));
1813 gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
1815 if (bb->next_bb == EXIT_BLOCK_PTR
1816 && !gimple_return_retval (ret_stmt))
1818 gsi_remove (&gsi, false);
1819 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
1823 gsi = gsi_start (stmts);
1824 if (!gsi_end_p (gsi))
1826 stmt = gsi_stmt (gsi);
1827 if (gimple_code (stmt) != GIMPLE_LABEL)
1831 elt = pointer_map_contains (lab_rtx_for_bb, bb);
1835 last = get_last_insn ();
1839 tree stmt_tree = gimple_to_tree (stmt);
1840 expand_expr_stmt (stmt_tree);
1841 release_stmt_tree (stmt, stmt_tree);
1846 emit_label ((rtx) *elt);
1848 /* Java emits line number notes in the top of labels.
1849 ??? Make this go away once line number notes are obsoleted. */
1850 BB_HEAD (bb) = NEXT_INSN (last);
1851 if (NOTE_P (BB_HEAD (bb)))
1852 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
1853 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
1855 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1858 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
1860 NOTE_BASIC_BLOCK (note) = bb;
1862 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1864 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
1865 e->flags &= ~EDGE_EXECUTABLE;
1867 /* At the moment not all abnormal edges match the RTL representation.
1868 It is safe to remove them here as find_many_sub_basic_blocks will
1869 rediscover them. In the future we should get this fixed properly. */
1870 if (e->flags & EDGE_ABNORMAL)
1876 for (; !gsi_end_p (gsi); gsi_next (&gsi))
1878 gimple stmt = gsi_stmt (gsi);
1881 /* Expand this statement, then evaluate the resulting RTL and
1882 fixup the CFG accordingly. */
1883 if (gimple_code (stmt) == GIMPLE_COND)
1885 new_bb = expand_gimple_cond (bb, stmt);
1891 if (is_gimple_call (stmt) && gimple_call_tail_p (stmt))
1894 new_bb = expand_gimple_tailcall (bb, stmt, &can_fallthru);
1905 tree stmt_tree = gimple_to_tree (stmt);
1906 last = get_last_insn ();
1907 expand_expr_stmt (stmt_tree);
1908 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1909 release_stmt_tree (stmt, stmt_tree);
1914 /* Expand implicit goto. */
1915 FOR_EACH_EDGE (e, ei, bb->succs)
1917 if (e->flags & EDGE_FALLTHRU)
1921 if (e && e->dest != bb->next_bb)
1923 emit_jump (label_rtx_for_bb (e->dest));
1925 set_curr_insn_source_location (e->goto_locus);
1926 e->flags &= ~EDGE_FALLTHRU;
1929 do_pending_stack_adjust ();
1931 /* Find the block tail. The last insn in the block is the insn
1932 before a barrier and/or table jump insn. */
1933 last = get_last_insn ();
1934 if (BARRIER_P (last))
1935 last = PREV_INSN (last);
1936 if (JUMP_TABLE_DATA_P (last))
1937 last = PREV_INSN (PREV_INSN (last));
1940 update_bb_for_insn (bb);
1946 /* Create a basic block for initialization code. */
1949 construct_init_block (void)
1951 basic_block init_block, first_block;
1955 /* Multiple entry points not supported yet. */
1956 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR->succs) == 1);
1957 init_rtl_bb_info (ENTRY_BLOCK_PTR);
1958 init_rtl_bb_info (EXIT_BLOCK_PTR);
1959 ENTRY_BLOCK_PTR->flags |= BB_RTL;
1960 EXIT_BLOCK_PTR->flags |= BB_RTL;
1962 e = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
1964 /* When entry edge points to first basic block, we don't need jump,
1965 otherwise we have to jump into proper target. */
1966 if (e && e->dest != ENTRY_BLOCK_PTR->next_bb)
1968 tree label = gimple_block_label (e->dest);
1970 emit_jump (label_rtx (label));
1974 flags = EDGE_FALLTHRU;
1976 init_block = create_basic_block (NEXT_INSN (get_insns ()),
1979 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
1980 init_block->count = ENTRY_BLOCK_PTR->count;
1983 first_block = e->dest;
1984 redirect_edge_succ (e, init_block);
1985 e = make_edge (init_block, first_block, flags);
1988 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
1989 e->probability = REG_BR_PROB_BASE;
1990 e->count = ENTRY_BLOCK_PTR->count;
1992 update_bb_for_insn (init_block);
1996 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
1997 found in the block tree. */
2000 set_block_levels (tree block, int level)
2004 BLOCK_NUMBER (block) = level;
2005 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
2006 block = BLOCK_CHAIN (block);
2010 /* Create a block containing landing pads and similar stuff. */
2013 construct_exit_block (void)
2015 rtx head = get_last_insn ();
2017 basic_block exit_block;
2021 rtx orig_end = BB_END (EXIT_BLOCK_PTR->prev_bb);
2023 /* Make sure the locus is set to the end of the function, so that
2024 epilogue line numbers and warnings are set properly. */
2025 if (cfun->function_end_locus != UNKNOWN_LOCATION)
2026 input_location = cfun->function_end_locus;
2028 /* The following insns belong to the top scope. */
2029 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2031 /* Generate rtl for function exit. */
2032 expand_function_end ();
2034 end = get_last_insn ();
2037 /* While emitting the function end we could move end of the last basic block.
2039 BB_END (EXIT_BLOCK_PTR->prev_bb) = orig_end;
2040 while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
2041 head = NEXT_INSN (head);
2042 exit_block = create_basic_block (NEXT_INSN (head), end,
2043 EXIT_BLOCK_PTR->prev_bb);
2044 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
2045 exit_block->count = EXIT_BLOCK_PTR->count;
2048 while (ix < EDGE_COUNT (EXIT_BLOCK_PTR->preds))
2050 e = EDGE_PRED (EXIT_BLOCK_PTR, ix);
2051 if (!(e->flags & EDGE_ABNORMAL))
2052 redirect_edge_succ (e, exit_block);
2057 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
2058 e->probability = REG_BR_PROB_BASE;
2059 e->count = EXIT_BLOCK_PTR->count;
2060 FOR_EACH_EDGE (e2, ei, EXIT_BLOCK_PTR->preds)
2063 e->count -= e2->count;
2064 exit_block->count -= e2->count;
2065 exit_block->frequency -= EDGE_FREQUENCY (e2);
2069 if (exit_block->count < 0)
2070 exit_block->count = 0;
2071 if (exit_block->frequency < 0)
2072 exit_block->frequency = 0;
2073 update_bb_for_insn (exit_block);
2076 /* Helper function for discover_nonconstant_array_refs.
2077 Look for ARRAY_REF nodes with non-constant indexes and mark them
2081 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
2082 void *data ATTRIBUTE_UNUSED)
2086 if (IS_TYPE_OR_DECL_P (t))
2088 else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2090 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2091 && is_gimple_min_invariant (TREE_OPERAND (t, 1))
2092 && (!TREE_OPERAND (t, 2)
2093 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2094 || (TREE_CODE (t) == COMPONENT_REF
2095 && (!TREE_OPERAND (t,2)
2096 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2097 || TREE_CODE (t) == BIT_FIELD_REF
2098 || TREE_CODE (t) == REALPART_EXPR
2099 || TREE_CODE (t) == IMAGPART_EXPR
2100 || TREE_CODE (t) == VIEW_CONVERT_EXPR
2101 || CONVERT_EXPR_P (t))
2102 t = TREE_OPERAND (t, 0);
2104 if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2106 t = get_base_address (t);
2107 if (t && DECL_P (t))
2108 TREE_ADDRESSABLE (t) = 1;
2117 /* RTL expansion is not able to compile array references with variable
2118 offsets for arrays stored in single register. Discover such
2119 expressions and mark variables as addressable to avoid this
2123 discover_nonconstant_array_refs (void)
2126 gimple_stmt_iterator gsi;
2129 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2131 gimple stmt = gsi_stmt (gsi);
2132 walk_gimple_op (stmt, discover_nonconstant_array_refs_r, NULL);
2136 /* Translate the intermediate representation contained in the CFG
2137 from GIMPLE trees to RTL.
2139 We do conversion per basic block and preserve/update the tree CFG.
2140 This implies we have to do some magic as the CFG can simultaneously
2141 consist of basic blocks containing RTL and GIMPLE trees. This can
2142 confuse the CFG hooks, so be careful to not manipulate CFG during
2146 gimple_expand_cfg (void)
2148 basic_block bb, init_block;
2153 /* Some backends want to know that we are expanding to RTL. */
2154 currently_expanding_to_rtl = 1;
2156 insn_locators_alloc ();
2157 if (!DECL_BUILT_IN (current_function_decl))
2158 set_curr_insn_source_location (DECL_SOURCE_LOCATION (current_function_decl));
2159 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2160 prologue_locator = curr_insn_locator ();
2162 /* Make sure first insn is a note even if we don't want linenums.
2163 This makes sure the first insn will never be deleted.
2164 Also, final expects a note to appear there. */
2165 emit_note (NOTE_INSN_DELETED);
2167 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2168 discover_nonconstant_array_refs ();
2170 targetm.expand_to_rtl_hook ();
2171 crtl->stack_alignment_needed = STACK_BOUNDARY;
2172 crtl->preferred_stack_boundary = STACK_BOUNDARY;
2173 cfun->cfg->max_jumptable_ents = 0;
2176 /* Expand the variables recorded during gimple lowering. */
2177 expand_used_vars ();
2179 /* Honor stack protection warnings. */
2180 if (warn_stack_protect)
2182 if (cfun->calls_alloca)
2183 warning (OPT_Wstack_protector,
2184 "not protecting local variables: variable length buffer");
2185 if (has_short_buffer && !crtl->stack_protect_guard)
2186 warning (OPT_Wstack_protector,
2187 "not protecting function: no buffer at least %d bytes long",
2188 (int) PARAM_VALUE (PARAM_SSP_BUFFER_SIZE));
2191 /* Set up parameters and prepare for return, for the function. */
2192 expand_function_start (current_function_decl);
2194 /* If this function is `main', emit a call to `__main'
2195 to run global initializers, etc. */
2196 if (DECL_NAME (current_function_decl)
2197 && MAIN_NAME_P (DECL_NAME (current_function_decl))
2198 && DECL_FILE_SCOPE_P (current_function_decl))
2199 expand_main_function ();
2201 /* Initialize the stack_protect_guard field. This must happen after the
2202 call to __main (if any) so that the external decl is initialized. */
2203 if (crtl->stack_protect_guard)
2204 stack_protect_prologue ();
2206 /* Register rtl specific functions for cfg. */
2207 rtl_register_cfg_hooks ();
2209 init_block = construct_init_block ();
2211 /* Clear EDGE_EXECUTABLE on the entry edge(s). It is cleaned from the
2212 remaining edges in expand_gimple_basic_block. */
2213 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2214 e->flags &= ~EDGE_EXECUTABLE;
2216 lab_rtx_for_bb = pointer_map_create ();
2217 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
2218 bb = expand_gimple_basic_block (bb);
2219 pointer_map_destroy (lab_rtx_for_bb);
2222 construct_exit_block ();
2223 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2224 insn_locators_finalize ();
2226 /* We're done expanding trees to RTL. */
2227 currently_expanding_to_rtl = 0;
2229 /* Convert tree EH labels to RTL EH labels and zap the tree EH table. */
2230 convert_from_eh_region_ranges ();
2231 set_eh_throw_stmt_table (cfun, NULL);
2233 rebuild_jump_labels (get_insns ());
2234 find_exception_handler_labels ();
2236 blocks = sbitmap_alloc (last_basic_block);
2237 sbitmap_ones (blocks);
2238 find_many_sub_basic_blocks (blocks);
2239 purge_all_dead_edges ();
2240 sbitmap_free (blocks);
2243 #ifdef ENABLE_CHECKING
2244 verify_flow_info ();
2247 /* There's no need to defer outputting this function any more; we
2248 know we want to output it. */
2249 DECL_DEFER_OUTPUT (current_function_decl) = 0;
2251 /* Now that we're done expanding trees to RTL, we shouldn't have any
2252 more CONCATs anywhere. */
2253 generating_concat_p = 0;
2258 "\n\n;;\n;; Full RTL generated for this function:\n;;\n");
2259 /* And the pass manager will dump RTL for us. */
2262 /* If we're emitting a nested function, make sure its parent gets
2263 emitted as well. Doing otherwise confuses debug info. */
2266 for (parent = DECL_CONTEXT (current_function_decl);
2267 parent != NULL_TREE;
2268 parent = get_containing_scope (parent))
2269 if (TREE_CODE (parent) == FUNCTION_DECL)
2270 TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (parent)) = 1;
2273 /* We are now committed to emitting code for this function. Do any
2274 preparation, such as emitting abstract debug info for the inline
2275 before it gets mangled by optimization. */
2276 if (cgraph_function_possibly_inlined_p (current_function_decl))
2277 (*debug_hooks->outlining_inline_function) (current_function_decl);
2279 TREE_ASM_WRITTEN (current_function_decl) = 1;
2281 /* After expanding, the return labels are no longer needed. */
2282 return_label = NULL;
2283 naked_return_label = NULL;
2284 /* Tag the blocks with a depth number so that change_scope can find
2285 the common parent easily. */
2286 set_block_levels (DECL_INITIAL (cfun->decl), 0);
2290 struct rtl_opt_pass pass_expand =
2294 "expand", /* name */
2296 gimple_expand_cfg, /* execute */
2299 0, /* static_pass_number */
2300 TV_EXPAND, /* tv_id */
2301 /* ??? If TER is enabled, we actually receive GENERIC. */
2302 PROP_gimple_leh | PROP_cfg, /* properties_required */
2303 PROP_rtl, /* properties_provided */
2304 PROP_trees, /* properties_destroyed */
2305 0, /* todo_flags_start */
2306 TODO_dump_func, /* todo_flags_finish */