1 /* A pass for lowering trees to RTL.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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"
42 #include "tree-inline.h"
43 #include "value-prof.h"
45 #include "ssaexpand.h"
48 /* This variable holds information helping the rewriting of SSA trees
52 /* Return an expression tree corresponding to the RHS of GIMPLE
56 gimple_assign_rhs_to_tree (gimple stmt)
59 enum gimple_rhs_class grhs_class;
61 grhs_class = get_gimple_rhs_class (gimple_expr_code (stmt));
63 if (grhs_class == GIMPLE_BINARY_RHS)
64 t = build2 (gimple_assign_rhs_code (stmt),
65 TREE_TYPE (gimple_assign_lhs (stmt)),
66 gimple_assign_rhs1 (stmt),
67 gimple_assign_rhs2 (stmt));
68 else if (grhs_class == GIMPLE_UNARY_RHS)
69 t = build1 (gimple_assign_rhs_code (stmt),
70 TREE_TYPE (gimple_assign_lhs (stmt)),
71 gimple_assign_rhs1 (stmt));
72 else if (grhs_class == GIMPLE_SINGLE_RHS)
73 t = gimple_assign_rhs1 (stmt);
80 /* Return an expression tree corresponding to the PREDICATE of GIMPLE_COND
84 gimple_cond_pred_to_tree (gimple stmt)
86 /* We're sometimes presented with such code:
90 This would expand to two comparisons which then later might
91 be cleaned up by combine. But some pattern matchers like if-conversion
92 work better when there's only one compare, so make up for this
93 here as special exception if TER would have made the same change. */
94 tree lhs = gimple_cond_lhs (stmt);
96 && TREE_CODE (lhs) == SSA_NAME
97 && bitmap_bit_p (SA.values, SSA_NAME_VERSION (lhs)))
98 lhs = gimple_assign_rhs_to_tree (SSA_NAME_DEF_STMT (lhs));
100 return build2 (gimple_cond_code (stmt), boolean_type_node,
101 lhs, gimple_cond_rhs (stmt));
104 /* Helper for gimple_to_tree. Set EXPR_LOCATION for every expression
105 inside *TP. DATA is the location to set. */
108 set_expr_location_r (tree *tp, int *ws ATTRIBUTE_UNUSED, void *data)
110 location_t *loc = (location_t *) data;
112 SET_EXPR_LOCATION (*tp, *loc);
118 /* RTL expansion has traditionally been done on trees, so the
119 transition to doing it on GIMPLE tuples is very invasive to the RTL
120 expander. To facilitate the transition, this function takes a
121 GIMPLE tuple STMT and returns the same statement in the form of a
125 gimple_to_tree (gimple stmt)
129 tree_ann_common_t ann;
132 switch (gimple_code (stmt))
136 tree lhs = gimple_assign_lhs (stmt);
138 t = gimple_assign_rhs_to_tree (stmt);
139 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
140 if (gimple_assign_nontemporal_move_p (stmt))
141 MOVE_NONTEMPORAL (t) = true;
146 t = gimple_cond_pred_to_tree (stmt);
147 t = build3 (COND_EXPR, void_type_node, t, NULL_TREE, NULL_TREE);
151 t = build1 (GOTO_EXPR, void_type_node, gimple_goto_dest (stmt));
155 t = build1 (LABEL_EXPR, void_type_node, gimple_label_label (stmt));
160 tree retval = gimple_return_retval (stmt);
162 if (retval && retval != error_mark_node)
164 tree result = DECL_RESULT (current_function_decl);
166 /* If we are not returning the current function's RESULT_DECL,
167 build an assignment to it. */
168 if (retval != result)
170 /* I believe that a function's RESULT_DECL is unique. */
171 gcc_assert (TREE_CODE (retval) != RESULT_DECL);
173 retval = build2 (MODIFY_EXPR, TREE_TYPE (result),
177 t = build1 (RETURN_EXPR, void_type_node, retval);
188 n = gimple_asm_noutputs (stmt);
191 t = out = gimple_asm_output_op (stmt, 0);
192 for (i = 1; i < n; i++)
194 TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
195 t = gimple_asm_output_op (stmt, i);
200 n = gimple_asm_ninputs (stmt);
203 t = in = gimple_asm_input_op (stmt, 0);
204 for (i = 1; i < n; i++)
206 TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
207 t = gimple_asm_input_op (stmt, i);
212 n = gimple_asm_nclobbers (stmt);
215 t = cl = gimple_asm_clobber_op (stmt, 0);
216 for (i = 1; i < n; i++)
218 TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
219 t = gimple_asm_clobber_op (stmt, i);
223 s = gimple_asm_string (stmt);
224 t = build4 (ASM_EXPR, void_type_node, build_string (strlen (s), s),
226 ASM_VOLATILE_P (t) = gimple_asm_volatile_p (stmt);
227 ASM_INPUT_P (t) = gimple_asm_input_p (stmt);
235 tree_ann_common_t ann;
237 t = build_vl_exp (CALL_EXPR, gimple_call_num_args (stmt) + 3);
239 CALL_EXPR_FN (t) = gimple_call_fn (stmt);
240 TREE_TYPE (t) = gimple_call_return_type (stmt);
241 CALL_EXPR_STATIC_CHAIN (t) = gimple_call_chain (stmt);
243 for (i = 0; i < gimple_call_num_args (stmt); i++)
244 CALL_EXPR_ARG (t, i) = gimple_call_arg (stmt, i);
246 if (!(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
247 TREE_SIDE_EFFECTS (t) = 1;
249 if (gimple_call_flags (stmt) & ECF_NOTHROW)
250 TREE_NOTHROW (t) = 1;
252 CALL_EXPR_TAILCALL (t) = gimple_call_tail_p (stmt);
253 CALL_EXPR_RETURN_SLOT_OPT (t) = gimple_call_return_slot_opt_p (stmt);
254 CALL_FROM_THUNK_P (t) = gimple_call_from_thunk_p (stmt);
255 CALL_CANNOT_INLINE_P (t) = gimple_call_cannot_inline_p (stmt);
256 CALL_EXPR_VA_ARG_PACK (t) = gimple_call_va_arg_pack_p (stmt);
258 /* If the call has a LHS then create a MODIFY_EXPR to hold it. */
260 tree lhs = gimple_call_lhs (stmt);
263 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
266 /* Record the original call statement, as it may be used
267 to retrieve profile information during expansion. */
269 if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
270 && DECL_BUILT_IN (fn))
272 ann = get_tree_common_ann (t);
282 tree elt = gimple_switch_label (stmt, 0);
284 label_vec = make_tree_vec (gimple_switch_num_labels (stmt));
286 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
288 for (i = 1; i < gimple_switch_num_labels (stmt); i++)
289 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, i);
291 /* The default case in a SWITCH_EXPR must be at the end of
293 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, 0);
297 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
298 TREE_VEC_ELT (label_vec, i) = gimple_switch_label (stmt, i);
301 t = build3 (SWITCH_EXPR, void_type_node, gimple_switch_index (stmt),
308 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
312 t = build_resx (gimple_resx_region (stmt));
318 error ("Unrecognized GIMPLE statement during RTL expansion");
319 print_gimple_stmt (stderr, stmt, 4, 0);
324 /* Ignore any bad gimple codes if we're going to die anyhow,
325 so we can at least set TREE_ASM_WRITTEN and have the rest
326 of compilation advance without sudden ICE death. */
327 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
332 /* If STMT is inside an exception region, record it in the generated
334 rn = lookup_stmt_eh_region (stmt);
337 tree call = get_call_expr_in (t);
339 ann = get_tree_common_ann (t);
342 /* For a CALL_EXPR on the RHS of an assignment, calls.c looks up
343 the CALL_EXPR not the assignment statment for EH region number. */
344 if (call && call != t)
346 ann = get_tree_common_ann (call);
351 /* Set EXPR_LOCATION in all the embedded expressions. */
352 loc = gimple_location (stmt);
353 walk_tree (&t, set_expr_location_r, (void *) &loc, NULL);
355 TREE_BLOCK (t) = gimple_block (stmt);
361 /* Release back to GC memory allocated by gimple_to_tree. */
364 release_stmt_tree (gimple stmt, tree stmt_tree)
366 tree_ann_common_t ann;
368 switch (gimple_code (stmt))
371 if (get_gimple_rhs_class (gimple_expr_code (stmt)) != GIMPLE_SINGLE_RHS)
372 ggc_free (TREE_OPERAND (stmt_tree, 1));
375 ggc_free (COND_EXPR_COND (stmt_tree));
378 if (TREE_OPERAND (stmt_tree, 0)
379 && TREE_CODE (TREE_OPERAND (stmt_tree, 0)) == MODIFY_EXPR)
380 ggc_free (TREE_OPERAND (stmt_tree, 0));
383 if (gimple_call_lhs (stmt))
385 ann = tree_common_ann (TREE_OPERAND (stmt_tree, 1));
388 ggc_free (TREE_OPERAND (stmt_tree, 1));
394 ann = tree_common_ann (stmt_tree);
397 ggc_free (stmt_tree);
401 /* Verify that there is exactly single jump instruction since last and attach
402 REG_BR_PROB note specifying probability.
403 ??? We really ought to pass the probability down to RTL expanders and let it
404 re-distribute it when the conditional expands into multiple conditionals.
405 This is however difficult to do. */
407 add_reg_br_prob_note (rtx last, int probability)
409 if (profile_status == PROFILE_ABSENT)
411 for (last = NEXT_INSN (last); last && NEXT_INSN (last); last = NEXT_INSN (last))
414 /* It is common to emit condjump-around-jump sequence when we don't know
415 how to reverse the conditional. Special case this. */
416 if (!any_condjump_p (last)
417 || !JUMP_P (NEXT_INSN (last))
418 || !simplejump_p (NEXT_INSN (last))
419 || !NEXT_INSN (NEXT_INSN (last))
420 || !BARRIER_P (NEXT_INSN (NEXT_INSN (last)))
421 || !NEXT_INSN (NEXT_INSN (NEXT_INSN (last)))
422 || !LABEL_P (NEXT_INSN (NEXT_INSN (NEXT_INSN (last))))
423 || NEXT_INSN (NEXT_INSN (NEXT_INSN (NEXT_INSN (last)))))
425 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
426 add_reg_note (last, REG_BR_PROB,
427 GEN_INT (REG_BR_PROB_BASE - probability));
430 if (!last || !JUMP_P (last) || !any_condjump_p (last))
432 gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
433 add_reg_note (last, REG_BR_PROB, GEN_INT (probability));
437 fprintf (dump_file, "Failed to add probability note\n");
441 #ifndef STACK_ALIGNMENT_NEEDED
442 #define STACK_ALIGNMENT_NEEDED 1
445 #define SSAVAR(x) (TREE_CODE (x) == SSA_NAME ? SSA_NAME_VAR (x) : x)
447 /* Associate declaration T with storage space X. If T is no
448 SSA name this is exactly SET_DECL_RTL, otherwise make the
449 partition of T associated with X. */
451 set_rtl (tree t, rtx x)
453 if (TREE_CODE (t) == SSA_NAME)
455 SA.partition_to_pseudo[var_to_partition (SA.map, t)] = x;
457 set_reg_attrs_for_decl_rtl (SSA_NAME_VAR (t), x);
458 /* For the benefit of debug information at -O0 (where vartracking
459 doesn't run) record the place also in the base DECL if it's
460 a normal variable (not a parameter). */
461 if (x && x != pc_rtx && TREE_CODE (SSA_NAME_VAR (t)) == VAR_DECL)
463 tree var = SSA_NAME_VAR (t);
464 /* If we don't yet have something recorded, just record it now. */
465 if (!DECL_RTL_SET_P (var))
466 SET_DECL_RTL (var, x);
467 /* If we have it set alrady to "multiple places" don't
469 else if (DECL_RTL (var) == pc_rtx)
471 /* If we have something recorded and it's not the same place
472 as we want to record now, we have multiple partitions for the
473 same base variable, with different places. We can't just
474 randomly chose one, hence we have to say that we don't know.
475 This only happens with optimization, and there var-tracking
476 will figure out the right thing. */
477 else if (DECL_RTL (var) != x)
478 SET_DECL_RTL (var, pc_rtx);
485 /* This structure holds data relevant to one variable that will be
486 placed in a stack slot. */
492 /* The offset of the variable. During partitioning, this is the
493 offset relative to the partition. After partitioning, this
494 is relative to the stack frame. */
495 HOST_WIDE_INT offset;
497 /* Initially, the size of the variable. Later, the size of the partition,
498 if this variable becomes it's partition's representative. */
501 /* The *byte* alignment required for this variable. Or as, with the
502 size, the alignment for this partition. */
505 /* The partition representative. */
506 size_t representative;
508 /* The next stack variable in the partition, or EOC. */
512 #define EOC ((size_t)-1)
514 /* We have an array of such objects while deciding allocation. */
515 static struct stack_var *stack_vars;
516 static size_t stack_vars_alloc;
517 static size_t stack_vars_num;
519 /* An array of indices such that stack_vars[stack_vars_sorted[i]].size
520 is non-decreasing. */
521 static size_t *stack_vars_sorted;
523 /* We have an interference graph between such objects. This graph
524 is lower triangular. */
525 static bool *stack_vars_conflict;
526 static size_t stack_vars_conflict_alloc;
528 /* The phase of the stack frame. This is the known misalignment of
529 virtual_stack_vars_rtx from PREFERRED_STACK_BOUNDARY. That is,
530 (frame_offset+frame_phase) % PREFERRED_STACK_BOUNDARY == 0. */
531 static int frame_phase;
533 /* Used during expand_used_vars to remember if we saw any decls for
534 which we'd like to enable stack smashing protection. */
535 static bool has_protected_decls;
537 /* Used during expand_used_vars. Remember if we say a character buffer
538 smaller than our cutoff threshold. Used for -Wstack-protector. */
539 static bool has_short_buffer;
541 /* Discover the byte alignment to use for DECL. Ignore alignment
542 we can't do with expected alignment of the stack boundary. */
545 get_decl_align_unit (tree decl)
549 align = LOCAL_DECL_ALIGNMENT (decl);
551 if (align > MAX_SUPPORTED_STACK_ALIGNMENT)
552 align = MAX_SUPPORTED_STACK_ALIGNMENT;
554 if (SUPPORTS_STACK_ALIGNMENT)
556 if (crtl->stack_alignment_estimated < align)
558 gcc_assert(!crtl->stack_realign_processed);
559 crtl->stack_alignment_estimated = align;
563 /* stack_alignment_needed > PREFERRED_STACK_BOUNDARY is permitted.
564 So here we only make sure stack_alignment_needed >= align. */
565 if (crtl->stack_alignment_needed < align)
566 crtl->stack_alignment_needed = align;
567 if (crtl->max_used_stack_slot_alignment < align)
568 crtl->max_used_stack_slot_alignment = align;
570 return align / BITS_PER_UNIT;
573 /* Allocate SIZE bytes at byte alignment ALIGN from the stack frame.
574 Return the frame offset. */
577 alloc_stack_frame_space (HOST_WIDE_INT size, HOST_WIDE_INT align)
579 HOST_WIDE_INT offset, new_frame_offset;
581 new_frame_offset = frame_offset;
582 if (FRAME_GROWS_DOWNWARD)
584 new_frame_offset -= size + frame_phase;
585 new_frame_offset &= -align;
586 new_frame_offset += frame_phase;
587 offset = new_frame_offset;
591 new_frame_offset -= frame_phase;
592 new_frame_offset += align - 1;
593 new_frame_offset &= -align;
594 new_frame_offset += frame_phase;
595 offset = new_frame_offset;
596 new_frame_offset += size;
598 frame_offset = new_frame_offset;
600 if (frame_offset_overflow (frame_offset, cfun->decl))
601 frame_offset = offset = 0;
606 /* Accumulate DECL into STACK_VARS. */
609 add_stack_var (tree decl)
611 if (stack_vars_num >= stack_vars_alloc)
613 if (stack_vars_alloc)
614 stack_vars_alloc = stack_vars_alloc * 3 / 2;
616 stack_vars_alloc = 32;
618 = XRESIZEVEC (struct stack_var, stack_vars, stack_vars_alloc);
620 stack_vars[stack_vars_num].decl = decl;
621 stack_vars[stack_vars_num].offset = 0;
622 stack_vars[stack_vars_num].size = tree_low_cst (DECL_SIZE_UNIT (SSAVAR (decl)), 1);
623 stack_vars[stack_vars_num].alignb = get_decl_align_unit (SSAVAR (decl));
625 /* All variables are initially in their own partition. */
626 stack_vars[stack_vars_num].representative = stack_vars_num;
627 stack_vars[stack_vars_num].next = EOC;
629 /* Ensure that this decl doesn't get put onto the list twice. */
630 set_rtl (decl, pc_rtx);
635 /* Compute the linear index of a lower-triangular coordinate (I, J). */
638 triangular_index (size_t i, size_t j)
645 return (i * (i + 1)) / 2 + j;
648 /* Ensure that STACK_VARS_CONFLICT is large enough for N objects. */
651 resize_stack_vars_conflict (size_t n)
653 size_t size = triangular_index (n-1, n-1) + 1;
655 if (size <= stack_vars_conflict_alloc)
658 stack_vars_conflict = XRESIZEVEC (bool, stack_vars_conflict, size);
659 memset (stack_vars_conflict + stack_vars_conflict_alloc, 0,
660 (size - stack_vars_conflict_alloc) * sizeof (bool));
661 stack_vars_conflict_alloc = size;
664 /* Make the decls associated with luid's X and Y conflict. */
667 add_stack_var_conflict (size_t x, size_t y)
669 size_t index = triangular_index (x, y);
670 gcc_assert (index < stack_vars_conflict_alloc);
671 stack_vars_conflict[index] = true;
674 /* Check whether the decls associated with luid's X and Y conflict. */
677 stack_var_conflict_p (size_t x, size_t y)
679 size_t index = triangular_index (x, y);
680 gcc_assert (index < stack_vars_conflict_alloc);
681 return stack_vars_conflict[index];
684 /* Returns true if TYPE is or contains a union type. */
687 aggregate_contains_union_type (tree type)
691 if (TREE_CODE (type) == UNION_TYPE
692 || TREE_CODE (type) == QUAL_UNION_TYPE)
694 if (TREE_CODE (type) == ARRAY_TYPE)
695 return aggregate_contains_union_type (TREE_TYPE (type));
696 if (TREE_CODE (type) != RECORD_TYPE)
699 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
700 if (TREE_CODE (field) == FIELD_DECL)
701 if (aggregate_contains_union_type (TREE_TYPE (field)))
707 /* A subroutine of expand_used_vars. If two variables X and Y have alias
708 sets that do not conflict, then do add a conflict for these variables
709 in the interference graph. We also need to make sure to add conflicts
710 for union containing structures. Else RTL alias analysis comes along
711 and due to type based aliasing rules decides that for two overlapping
712 union temporaries { short s; int i; } accesses to the same mem through
713 different types may not alias and happily reorders stores across
714 life-time boundaries of the temporaries (See PR25654).
715 We also have to mind MEM_IN_STRUCT_P and MEM_SCALAR_P. */
718 add_alias_set_conflicts (void)
720 size_t i, j, n = stack_vars_num;
722 for (i = 0; i < n; ++i)
724 tree type_i = TREE_TYPE (stack_vars[i].decl);
725 bool aggr_i = AGGREGATE_TYPE_P (type_i);
728 contains_union = aggregate_contains_union_type (type_i);
729 for (j = 0; j < i; ++j)
731 tree type_j = TREE_TYPE (stack_vars[j].decl);
732 bool aggr_j = AGGREGATE_TYPE_P (type_j);
734 /* Either the objects conflict by means of type based
735 aliasing rules, or we need to add a conflict. */
736 || !objects_must_conflict_p (type_i, type_j)
737 /* In case the types do not conflict ensure that access
738 to elements will conflict. In case of unions we have
739 to be careful as type based aliasing rules may say
740 access to the same memory does not conflict. So play
741 safe and add a conflict in this case. */
743 add_stack_var_conflict (i, j);
748 /* A subroutine of partition_stack_vars. A comparison function for qsort,
749 sorting an array of indices by the size and type of the object. */
752 stack_var_size_cmp (const void *a, const void *b)
754 HOST_WIDE_INT sa = stack_vars[*(const size_t *)a].size;
755 HOST_WIDE_INT sb = stack_vars[*(const size_t *)b].size;
757 unsigned int uida, uidb;
763 decla = stack_vars[*(const size_t *)a].decl;
764 declb = stack_vars[*(const size_t *)b].decl;
765 /* For stack variables of the same size use and id of the decls
766 to make the sort stable. Two SSA names are compared by their
767 version, SSA names come before non-SSA names, and two normal
768 decls are compared by their DECL_UID. */
769 if (TREE_CODE (decla) == SSA_NAME)
771 if (TREE_CODE (declb) == SSA_NAME)
772 uida = SSA_NAME_VERSION (decla), uidb = SSA_NAME_VERSION (declb);
776 else if (TREE_CODE (declb) == SSA_NAME)
779 uida = DECL_UID (decla), uidb = DECL_UID (declb);
788 /* If the points-to solution *PI points to variables that are in a partition
789 together with other variables add all partition members to the pointed-to
793 add_partitioned_vars_to_ptset (struct pt_solution *pt,
794 struct pointer_map_t *decls_to_partitions,
795 struct pointer_set_t *visited, bitmap temp)
803 /* The pointed-to vars bitmap is shared, it is enough to
805 || pointer_set_insert(visited, pt->vars))
810 /* By using a temporary bitmap to store all members of the partitions
811 we have to add we make sure to visit each of the partitions only
813 EXECUTE_IF_SET_IN_BITMAP (pt->vars, 0, i, bi)
815 || !bitmap_bit_p (temp, i))
816 && (part = (bitmap *) pointer_map_contains (decls_to_partitions,
817 (void *)(size_t) i)))
818 bitmap_ior_into (temp, *part);
819 if (!bitmap_empty_p (temp))
820 bitmap_ior_into (pt->vars, temp);
823 /* Update points-to sets based on partition info, so we can use them on RTL.
824 The bitmaps representing stack partitions will be saved until expand,
825 where partitioned decls used as bases in memory expressions will be
829 update_alias_info_with_stack_vars (void)
831 struct pointer_map_t *decls_to_partitions = NULL;
833 tree var = NULL_TREE;
835 for (i = 0; i < stack_vars_num; i++)
839 struct ptr_info_def *pi;
841 /* Not interested in partitions with single variable. */
842 if (stack_vars[i].representative != i
843 || stack_vars[i].next == EOC)
846 if (!decls_to_partitions)
848 decls_to_partitions = pointer_map_create ();
849 cfun->gimple_df->decls_to_pointers = pointer_map_create ();
852 /* Create an SSA_NAME that points to the partition for use
853 as base during alias-oracle queries on RTL for bases that
854 have been partitioned. */
855 if (var == NULL_TREE)
856 var = create_tmp_var (ptr_type_node, NULL);
857 name = make_ssa_name (var, NULL);
859 /* Create bitmaps representing partitions. They will be used for
860 points-to sets later, so use GGC alloc. */
861 part = BITMAP_GGC_ALLOC ();
862 for (j = i; j != EOC; j = stack_vars[j].next)
864 tree decl = stack_vars[j].decl;
865 unsigned int uid = DECL_UID (decl);
866 /* We should never end up partitioning SSA names (though they
867 may end up on the stack). Neither should we allocate stack
868 space to something that is unused and thus unreferenced. */
869 gcc_assert (DECL_P (decl)
870 && referenced_var_lookup (uid));
871 bitmap_set_bit (part, uid);
872 *((bitmap *) pointer_map_insert (decls_to_partitions,
873 (void *)(size_t) uid)) = part;
874 *((tree *) pointer_map_insert (cfun->gimple_df->decls_to_pointers,
878 /* Make the SSA name point to all partition members. */
879 pi = get_ptr_info (name);
880 pt_solution_set (&pi->pt, part);
883 /* Make all points-to sets that contain one member of a partition
884 contain all members of the partition. */
885 if (decls_to_partitions)
888 struct pointer_set_t *visited = pointer_set_create ();
889 bitmap temp = BITMAP_ALLOC (NULL);
891 for (i = 1; i < num_ssa_names; i++)
893 tree name = ssa_name (i);
894 struct ptr_info_def *pi;
897 && POINTER_TYPE_P (TREE_TYPE (name))
898 && ((pi = SSA_NAME_PTR_INFO (name)) != NULL))
899 add_partitioned_vars_to_ptset (&pi->pt, decls_to_partitions,
903 add_partitioned_vars_to_ptset (&cfun->gimple_df->escaped,
904 decls_to_partitions, visited, temp);
905 add_partitioned_vars_to_ptset (&cfun->gimple_df->callused,
906 decls_to_partitions, visited, temp);
908 pointer_set_destroy (visited);
909 pointer_map_destroy (decls_to_partitions);
914 /* A subroutine of partition_stack_vars. The UNION portion of a UNION/FIND
915 partitioning algorithm. Partitions A and B are known to be non-conflicting.
916 Merge them into a single partition A.
918 At the same time, add OFFSET to all variables in partition B. At the end
919 of the partitioning process we've have a nice block easy to lay out within
923 union_stack_vars (size_t a, size_t b, HOST_WIDE_INT offset)
927 /* Update each element of partition B with the given offset,
928 and merge them into partition A. */
929 for (last = i = b; i != EOC; last = i, i = stack_vars[i].next)
931 stack_vars[i].offset += offset;
932 stack_vars[i].representative = a;
934 stack_vars[last].next = stack_vars[a].next;
935 stack_vars[a].next = b;
937 /* Update the required alignment of partition A to account for B. */
938 if (stack_vars[a].alignb < stack_vars[b].alignb)
939 stack_vars[a].alignb = stack_vars[b].alignb;
941 /* Update the interference graph and merge the conflicts. */
942 for (last = stack_vars_num, i = 0; i < last; ++i)
943 if (stack_var_conflict_p (b, i))
944 add_stack_var_conflict (a, i);
947 /* A subroutine of expand_used_vars. Binpack the variables into
948 partitions constrained by the interference graph. The overall
949 algorithm used is as follows:
951 Sort the objects by size.
956 Look for the largest non-conflicting object B with size <= S.
966 partition_stack_vars (void)
968 size_t si, sj, n = stack_vars_num;
970 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
971 for (si = 0; si < n; ++si)
972 stack_vars_sorted[si] = si;
977 qsort (stack_vars_sorted, n, sizeof (size_t), stack_var_size_cmp);
979 /* Special case: detect when all variables conflict, and thus we can't
980 do anything during the partitioning loop. It isn't uncommon (with
981 C code at least) to declare all variables at the top of the function,
982 and if we're not inlining, then all variables will be in the same scope.
983 Take advantage of very fast libc routines for this scan. */
984 gcc_assert (sizeof(bool) == sizeof(char));
985 if (memchr (stack_vars_conflict, false, stack_vars_conflict_alloc) == NULL)
988 for (si = 0; si < n; ++si)
990 size_t i = stack_vars_sorted[si];
991 HOST_WIDE_INT isize = stack_vars[i].size;
992 HOST_WIDE_INT offset = 0;
994 for (sj = si; sj-- > 0; )
996 size_t j = stack_vars_sorted[sj];
997 HOST_WIDE_INT jsize = stack_vars[j].size;
998 unsigned int jalign = stack_vars[j].alignb;
1000 /* Ignore objects that aren't partition representatives. */
1001 if (stack_vars[j].representative != j)
1004 /* Ignore objects too large for the remaining space. */
1008 /* Ignore conflicting objects. */
1009 if (stack_var_conflict_p (i, j))
1012 /* Refine the remaining space check to include alignment. */
1013 if (offset & (jalign - 1))
1015 HOST_WIDE_INT toff = offset;
1017 toff &= -(HOST_WIDE_INT)jalign;
1018 if (isize - (toff - offset) < jsize)
1021 isize -= toff - offset;
1025 /* UNION the objects, placing J at OFFSET. */
1026 union_stack_vars (i, j, offset);
1035 update_alias_info_with_stack_vars ();
1038 /* A debugging aid for expand_used_vars. Dump the generated partitions. */
1041 dump_stack_var_partition (void)
1043 size_t si, i, j, n = stack_vars_num;
1045 for (si = 0; si < n; ++si)
1047 i = stack_vars_sorted[si];
1049 /* Skip variables that aren't partition representatives, for now. */
1050 if (stack_vars[i].representative != i)
1053 fprintf (dump_file, "Partition %lu: size " HOST_WIDE_INT_PRINT_DEC
1054 " align %u\n", (unsigned long) i, stack_vars[i].size,
1055 stack_vars[i].alignb);
1057 for (j = i; j != EOC; j = stack_vars[j].next)
1059 fputc ('\t', dump_file);
1060 print_generic_expr (dump_file, stack_vars[j].decl, dump_flags);
1061 fprintf (dump_file, ", offset " HOST_WIDE_INT_PRINT_DEC "\n",
1062 stack_vars[j].offset);
1067 /* Assign rtl to DECL at frame offset OFFSET. */
1070 expand_one_stack_var_at (tree decl, HOST_WIDE_INT offset)
1072 /* Alignment is unsigned. */
1073 unsigned HOST_WIDE_INT align;
1076 /* If this fails, we've overflowed the stack frame. Error nicely? */
1077 gcc_assert (offset == trunc_int_for_mode (offset, Pmode));
1079 x = plus_constant (virtual_stack_vars_rtx, offset);
1080 x = gen_rtx_MEM (DECL_MODE (SSAVAR (decl)), x);
1082 if (TREE_CODE (decl) != SSA_NAME)
1084 /* Set alignment we actually gave this decl if it isn't an SSA name.
1085 If it is we generate stack slots only accidentally so it isn't as
1086 important, we'll simply use the alignment that is already set. */
1087 offset -= frame_phase;
1088 align = offset & -offset;
1089 align *= BITS_PER_UNIT;
1091 align = STACK_BOUNDARY;
1092 else if (align > MAX_SUPPORTED_STACK_ALIGNMENT)
1093 align = MAX_SUPPORTED_STACK_ALIGNMENT;
1095 DECL_ALIGN (decl) = align;
1096 DECL_USER_ALIGN (decl) = 0;
1099 set_mem_attributes (x, SSAVAR (decl), true);
1103 /* A subroutine of expand_used_vars. Give each partition representative
1104 a unique location within the stack frame. Update each partition member
1105 with that location. */
1108 expand_stack_vars (bool (*pred) (tree))
1110 size_t si, i, j, n = stack_vars_num;
1112 for (si = 0; si < n; ++si)
1114 HOST_WIDE_INT offset;
1116 i = stack_vars_sorted[si];
1118 /* Skip variables that aren't partition representatives, for now. */
1119 if (stack_vars[i].representative != i)
1122 /* Skip variables that have already had rtl assigned. See also
1123 add_stack_var where we perpetrate this pc_rtx hack. */
1124 if ((TREE_CODE (stack_vars[i].decl) == SSA_NAME
1125 ? SA.partition_to_pseudo[var_to_partition (SA.map, stack_vars[i].decl)]
1126 : DECL_RTL (stack_vars[i].decl)) != pc_rtx)
1129 /* Check the predicate to see whether this variable should be
1130 allocated in this pass. */
1131 if (pred && !pred (stack_vars[i].decl))
1134 offset = alloc_stack_frame_space (stack_vars[i].size,
1135 stack_vars[i].alignb);
1137 /* Create rtl for each variable based on their location within the
1139 for (j = i; j != EOC; j = stack_vars[j].next)
1141 gcc_assert (stack_vars[j].offset <= stack_vars[i].size);
1142 expand_one_stack_var_at (stack_vars[j].decl,
1143 stack_vars[j].offset + offset);
1148 /* Take into account all sizes of partitions and reset DECL_RTLs. */
1149 static HOST_WIDE_INT
1150 account_stack_vars (void)
1152 size_t si, j, i, n = stack_vars_num;
1153 HOST_WIDE_INT size = 0;
1155 for (si = 0; si < n; ++si)
1157 i = stack_vars_sorted[si];
1159 /* Skip variables that aren't partition representatives, for now. */
1160 if (stack_vars[i].representative != i)
1163 size += stack_vars[i].size;
1164 for (j = i; j != EOC; j = stack_vars[j].next)
1165 set_rtl (stack_vars[j].decl, NULL);
1170 /* A subroutine of expand_one_var. Called to immediately assign rtl
1171 to a variable to be allocated in the stack frame. */
1174 expand_one_stack_var (tree var)
1176 HOST_WIDE_INT size, offset, align;
1178 size = tree_low_cst (DECL_SIZE_UNIT (SSAVAR (var)), 1);
1179 align = get_decl_align_unit (SSAVAR (var));
1180 offset = alloc_stack_frame_space (size, align);
1182 expand_one_stack_var_at (var, offset);
1185 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
1186 that will reside in a hard register. */
1189 expand_one_hard_reg_var (tree var)
1191 rest_of_decl_compilation (var, 0, 0);
1194 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
1195 that will reside in a pseudo register. */
1198 expand_one_register_var (tree var)
1200 tree decl = SSAVAR (var);
1201 tree type = TREE_TYPE (decl);
1202 int unsignedp = TYPE_UNSIGNED (type);
1203 enum machine_mode reg_mode
1204 = promote_mode (type, DECL_MODE (decl), &unsignedp, 0);
1205 rtx x = gen_reg_rtx (reg_mode);
1209 /* Note if the object is a user variable. */
1210 if (!DECL_ARTIFICIAL (decl))
1213 if (POINTER_TYPE_P (type))
1214 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type)));
1217 /* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL that
1218 has some associated error, e.g. its type is error-mark. We just need
1219 to pick something that won't crash the rest of the compiler. */
1222 expand_one_error_var (tree var)
1224 enum machine_mode mode = DECL_MODE (var);
1227 if (mode == BLKmode)
1228 x = gen_rtx_MEM (BLKmode, const0_rtx);
1229 else if (mode == VOIDmode)
1232 x = gen_reg_rtx (mode);
1234 SET_DECL_RTL (var, x);
1237 /* A subroutine of expand_one_var. VAR is a variable that will be
1238 allocated to the local stack frame. Return true if we wish to
1239 add VAR to STACK_VARS so that it will be coalesced with other
1240 variables. Return false to allocate VAR immediately.
1242 This function is used to reduce the number of variables considered
1243 for coalescing, which reduces the size of the quadratic problem. */
1246 defer_stack_allocation (tree var, bool toplevel)
1248 /* If stack protection is enabled, *all* stack variables must be deferred,
1249 so that we can re-order the strings to the top of the frame. */
1250 if (flag_stack_protect)
1253 /* Variables in the outermost scope automatically conflict with
1254 every other variable. The only reason to want to defer them
1255 at all is that, after sorting, we can more efficiently pack
1256 small variables in the stack frame. Continue to defer at -O2. */
1257 if (toplevel && optimize < 2)
1260 /* Without optimization, *most* variables are allocated from the
1261 stack, which makes the quadratic problem large exactly when we
1262 want compilation to proceed as quickly as possible. On the
1263 other hand, we don't want the function's stack frame size to
1264 get completely out of hand. So we avoid adding scalars and
1265 "small" aggregates to the list at all. */
1266 if (optimize == 0 && tree_low_cst (DECL_SIZE_UNIT (var), 1) < 32)
1272 /* A subroutine of expand_used_vars. Expand one variable according to
1273 its flavor. Variables to be placed on the stack are not actually
1274 expanded yet, merely recorded.
1275 When REALLY_EXPAND is false, only add stack values to be allocated.
1276 Return stack usage this variable is supposed to take.
1279 static HOST_WIDE_INT
1280 expand_one_var (tree var, bool toplevel, bool really_expand)
1285 if (SUPPORTS_STACK_ALIGNMENT
1286 && TREE_TYPE (var) != error_mark_node
1287 && TREE_CODE (var) == VAR_DECL)
1291 /* Because we don't know if VAR will be in register or on stack,
1292 we conservatively assume it will be on stack even if VAR is
1293 eventually put into register after RA pass. For non-automatic
1294 variables, which won't be on stack, we collect alignment of
1295 type and ignore user specified alignment. */
1296 if (TREE_STATIC (var) || DECL_EXTERNAL (var))
1297 align = MINIMUM_ALIGNMENT (TREE_TYPE (var),
1298 TYPE_MODE (TREE_TYPE (var)),
1299 TYPE_ALIGN (TREE_TYPE (var)));
1301 align = MINIMUM_ALIGNMENT (var, DECL_MODE (var), DECL_ALIGN (var));
1303 if (crtl->stack_alignment_estimated < align)
1305 /* stack_alignment_estimated shouldn't change after stack
1306 realign decision made */
1307 gcc_assert(!crtl->stack_realign_processed);
1308 crtl->stack_alignment_estimated = align;
1312 if (TREE_CODE (origvar) == SSA_NAME)
1314 gcc_assert (TREE_CODE (var) != VAR_DECL
1315 || (!DECL_EXTERNAL (var)
1316 && !DECL_HAS_VALUE_EXPR_P (var)
1317 && !TREE_STATIC (var)
1318 && TREE_TYPE (var) != error_mark_node
1319 && !DECL_HARD_REGISTER (var)
1322 if (TREE_CODE (var) != VAR_DECL && TREE_CODE (origvar) != SSA_NAME)
1324 else if (DECL_EXTERNAL (var))
1326 else if (DECL_HAS_VALUE_EXPR_P (var))
1328 else if (TREE_STATIC (var))
1330 else if (TREE_CODE (origvar) != SSA_NAME && DECL_RTL_SET_P (var))
1332 else if (TREE_TYPE (var) == error_mark_node)
1335 expand_one_error_var (var);
1337 else if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1340 expand_one_hard_reg_var (var);
1342 else if (use_register_for_decl (var))
1345 expand_one_register_var (origvar);
1347 else if (defer_stack_allocation (var, toplevel))
1348 add_stack_var (origvar);
1352 expand_one_stack_var (origvar);
1353 return tree_low_cst (DECL_SIZE_UNIT (var), 1);
1358 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1359 expanding variables. Those variables that can be put into registers
1360 are allocated pseudos; those that can't are put on the stack.
1362 TOPLEVEL is true if this is the outermost BLOCK. */
1365 expand_used_vars_for_block (tree block, bool toplevel)
1367 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1370 old_sv_num = toplevel ? 0 : stack_vars_num;
1372 /* Expand all variables at this level. */
1373 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1375 expand_one_var (t, toplevel, true);
1377 this_sv_num = stack_vars_num;
1379 /* Expand all variables at containing levels. */
1380 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1381 expand_used_vars_for_block (t, false);
1383 /* Since we do not track exact variable lifetimes (which is not even
1384 possible for variables whose address escapes), we mirror the block
1385 tree in the interference graph. Here we cause all variables at this
1386 level, and all sublevels, to conflict. Do make certain that a
1387 variable conflicts with itself. */
1388 if (old_sv_num < this_sv_num)
1390 new_sv_num = stack_vars_num;
1391 resize_stack_vars_conflict (new_sv_num);
1393 for (i = old_sv_num; i < new_sv_num; ++i)
1394 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1395 add_stack_var_conflict (i, j);
1399 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1400 and clear TREE_USED on all local variables. */
1403 clear_tree_used (tree block)
1407 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1408 /* if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) */
1411 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1412 clear_tree_used (t);
1415 /* Examine TYPE and determine a bit mask of the following features. */
1417 #define SPCT_HAS_LARGE_CHAR_ARRAY 1
1418 #define SPCT_HAS_SMALL_CHAR_ARRAY 2
1419 #define SPCT_HAS_ARRAY 4
1420 #define SPCT_HAS_AGGREGATE 8
1423 stack_protect_classify_type (tree type)
1425 unsigned int ret = 0;
1428 switch (TREE_CODE (type))
1431 t = TYPE_MAIN_VARIANT (TREE_TYPE (type));
1432 if (t == char_type_node
1433 || t == signed_char_type_node
1434 || t == unsigned_char_type_node)
1436 unsigned HOST_WIDE_INT max = PARAM_VALUE (PARAM_SSP_BUFFER_SIZE);
1437 unsigned HOST_WIDE_INT len;
1439 if (!TYPE_SIZE_UNIT (type)
1440 || !host_integerp (TYPE_SIZE_UNIT (type), 1))
1443 len = tree_low_cst (TYPE_SIZE_UNIT (type), 1);
1446 ret = SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_ARRAY;
1448 ret = SPCT_HAS_LARGE_CHAR_ARRAY | SPCT_HAS_ARRAY;
1451 ret = SPCT_HAS_ARRAY;
1455 case QUAL_UNION_TYPE:
1457 ret = SPCT_HAS_AGGREGATE;
1458 for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
1459 if (TREE_CODE (t) == FIELD_DECL)
1460 ret |= stack_protect_classify_type (TREE_TYPE (t));
1470 /* Return nonzero if DECL should be segregated into the "vulnerable" upper
1471 part of the local stack frame. Remember if we ever return nonzero for
1472 any variable in this function. The return value is the phase number in
1473 which the variable should be allocated. */
1476 stack_protect_decl_phase (tree decl)
1478 unsigned int bits = stack_protect_classify_type (TREE_TYPE (decl));
1481 if (bits & SPCT_HAS_SMALL_CHAR_ARRAY)
1482 has_short_buffer = true;
1484 if (flag_stack_protect == 2)
1486 if ((bits & (SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_LARGE_CHAR_ARRAY))
1487 && !(bits & SPCT_HAS_AGGREGATE))
1489 else if (bits & SPCT_HAS_ARRAY)
1493 ret = (bits & SPCT_HAS_LARGE_CHAR_ARRAY) != 0;
1496 has_protected_decls = true;
1501 /* Two helper routines that check for phase 1 and phase 2. These are used
1502 as callbacks for expand_stack_vars. */
1505 stack_protect_decl_phase_1 (tree decl)
1507 return stack_protect_decl_phase (decl) == 1;
1511 stack_protect_decl_phase_2 (tree decl)
1513 return stack_protect_decl_phase (decl) == 2;
1516 /* Ensure that variables in different stack protection phases conflict
1517 so that they are not merged and share the same stack slot. */
1520 add_stack_protection_conflicts (void)
1522 size_t i, j, n = stack_vars_num;
1523 unsigned char *phase;
1525 phase = XNEWVEC (unsigned char, n);
1526 for (i = 0; i < n; ++i)
1527 phase[i] = stack_protect_decl_phase (stack_vars[i].decl);
1529 for (i = 0; i < n; ++i)
1531 unsigned char ph_i = phase[i];
1532 for (j = 0; j < i; ++j)
1533 if (ph_i != phase[j])
1534 add_stack_var_conflict (i, j);
1540 /* Create a decl for the guard at the top of the stack frame. */
1543 create_stack_guard (void)
1545 tree guard = build_decl (DECL_SOURCE_LOCATION (current_function_decl),
1546 VAR_DECL, NULL, ptr_type_node);
1547 TREE_THIS_VOLATILE (guard) = 1;
1548 TREE_USED (guard) = 1;
1549 expand_one_stack_var (guard);
1550 crtl->stack_protect_guard = guard;
1553 /* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1554 expanding variables. Those variables that can be put into registers
1555 are allocated pseudos; those that can't are put on the stack.
1557 TOPLEVEL is true if this is the outermost BLOCK. */
1559 static HOST_WIDE_INT
1560 account_used_vars_for_block (tree block, bool toplevel)
1562 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1564 HOST_WIDE_INT size = 0;
1566 old_sv_num = toplevel ? 0 : stack_vars_num;
1568 /* Expand all variables at this level. */
1569 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1571 size += expand_one_var (t, toplevel, false);
1573 this_sv_num = stack_vars_num;
1575 /* Expand all variables at containing levels. */
1576 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1577 size += account_used_vars_for_block (t, false);
1579 /* Since we do not track exact variable lifetimes (which is not even
1580 possible for variables whose address escapes), we mirror the block
1581 tree in the interference graph. Here we cause all variables at this
1582 level, and all sublevels, to conflict. Do make certain that a
1583 variable conflicts with itself. */
1584 if (old_sv_num < this_sv_num)
1586 new_sv_num = stack_vars_num;
1587 resize_stack_vars_conflict (new_sv_num);
1589 for (i = old_sv_num; i < new_sv_num; ++i)
1590 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1591 add_stack_var_conflict (i, j);
1596 /* Prepare for expanding variables. */
1598 init_vars_expansion (void)
1601 /* Set TREE_USED on all variables in the local_decls. */
1602 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1603 TREE_USED (TREE_VALUE (t)) = 1;
1605 /* Clear TREE_USED on all variables associated with a block scope. */
1606 clear_tree_used (DECL_INITIAL (current_function_decl));
1608 /* Initialize local stack smashing state. */
1609 has_protected_decls = false;
1610 has_short_buffer = false;
1613 /* Free up stack variable graph data. */
1615 fini_vars_expansion (void)
1617 XDELETEVEC (stack_vars);
1618 XDELETEVEC (stack_vars_sorted);
1619 XDELETEVEC (stack_vars_conflict);
1621 stack_vars_alloc = stack_vars_num = 0;
1622 stack_vars_conflict = NULL;
1623 stack_vars_conflict_alloc = 0;
1626 /* Make a fair guess for the size of the stack frame of the current
1627 function. This doesn't have to be exact, the result is only used
1628 in the inline heuristics. So we don't want to run the full stack
1629 var packing algorithm (which is quadratic in the number of stack
1630 vars). Instead, we calculate the total size of all stack vars.
1631 This turns out to be a pretty fair estimate -- packing of stack
1632 vars doesn't happen very often. */
1635 estimated_stack_frame_size (void)
1637 HOST_WIDE_INT size = 0;
1639 tree t, outer_block = DECL_INITIAL (current_function_decl);
1641 init_vars_expansion ();
1643 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1645 tree var = TREE_VALUE (t);
1647 if (TREE_USED (var))
1648 size += expand_one_var (var, true, false);
1649 TREE_USED (var) = 1;
1651 size += account_used_vars_for_block (outer_block, true);
1653 if (stack_vars_num > 0)
1655 /* Fake sorting the stack vars for account_stack_vars (). */
1656 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
1657 for (i = 0; i < stack_vars_num; ++i)
1658 stack_vars_sorted[i] = i;
1659 size += account_stack_vars ();
1660 fini_vars_expansion ();
1666 /* Expand all variables used in the function. */
1669 expand_used_vars (void)
1671 tree t, next, outer_block = DECL_INITIAL (current_function_decl);
1674 /* Compute the phase of the stack frame for this function. */
1676 int align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1677 int off = STARTING_FRAME_OFFSET % align;
1678 frame_phase = off ? align - off : 0;
1681 init_vars_expansion ();
1683 for (i = 0; i < SA.map->num_partitions; i++)
1685 tree var = partition_to_var (SA.map, i);
1687 gcc_assert (is_gimple_reg (var));
1688 if (TREE_CODE (SSA_NAME_VAR (var)) == VAR_DECL)
1689 expand_one_var (var, true, true);
1692 /* This is a PARM_DECL or RESULT_DECL. For those partitions that
1693 contain the default def (representing the parm or result itself)
1694 we don't do anything here. But those which don't contain the
1695 default def (representing a temporary based on the parm/result)
1696 we need to allocate space just like for normal VAR_DECLs. */
1697 if (!bitmap_bit_p (SA.partition_has_default_def, i))
1699 expand_one_var (var, true, true);
1700 gcc_assert (SA.partition_to_pseudo[i]);
1705 /* At this point all variables on the local_decls with TREE_USED
1706 set are not associated with any block scope. Lay them out. */
1707 t = cfun->local_decls;
1708 cfun->local_decls = NULL_TREE;
1711 tree var = TREE_VALUE (t);
1712 bool expand_now = false;
1714 next = TREE_CHAIN (t);
1716 /* Expanded above already. */
1717 if (is_gimple_reg (var))
1719 TREE_USED (var) = 0;
1723 /* We didn't set a block for static or extern because it's hard
1724 to tell the difference between a global variable (re)declared
1725 in a local scope, and one that's really declared there to
1726 begin with. And it doesn't really matter much, since we're
1727 not giving them stack space. Expand them now. */
1728 else if (TREE_STATIC (var) || DECL_EXTERNAL (var))
1731 /* If the variable is not associated with any block, then it
1732 was created by the optimizers, and could be live anywhere
1734 else if (TREE_USED (var))
1737 /* Finally, mark all variables on the list as used. We'll use
1738 this in a moment when we expand those associated with scopes. */
1739 TREE_USED (var) = 1;
1743 expand_one_var (var, true, true);
1744 if (DECL_ARTIFICIAL (var) && !DECL_IGNORED_P (var))
1746 rtx rtl = DECL_RTL_IF_SET (var);
1748 /* Keep artificial non-ignored vars in cfun->local_decls
1749 chain until instantiate_decls. */
1750 if (rtl && (MEM_P (rtl) || GET_CODE (rtl) == CONCAT))
1752 TREE_CHAIN (t) = cfun->local_decls;
1753 cfun->local_decls = t;
1762 /* At this point, all variables within the block tree with TREE_USED
1763 set are actually used by the optimized function. Lay them out. */
1764 expand_used_vars_for_block (outer_block, true);
1766 if (stack_vars_num > 0)
1768 /* Due to the way alias sets work, no variables with non-conflicting
1769 alias sets may be assigned the same address. Add conflicts to
1771 add_alias_set_conflicts ();
1773 /* If stack protection is enabled, we don't share space between
1774 vulnerable data and non-vulnerable data. */
1775 if (flag_stack_protect)
1776 add_stack_protection_conflicts ();
1778 /* Now that we have collected all stack variables, and have computed a
1779 minimal interference graph, attempt to save some stack space. */
1780 partition_stack_vars ();
1782 dump_stack_var_partition ();
1785 /* There are several conditions under which we should create a
1786 stack guard: protect-all, alloca used, protected decls present. */
1787 if (flag_stack_protect == 2
1788 || (flag_stack_protect
1789 && (cfun->calls_alloca || has_protected_decls)))
1790 create_stack_guard ();
1792 /* Assign rtl to each variable based on these partitions. */
1793 if (stack_vars_num > 0)
1795 /* Reorder decls to be protected by iterating over the variables
1796 array multiple times, and allocating out of each phase in turn. */
1797 /* ??? We could probably integrate this into the qsort we did
1798 earlier, such that we naturally see these variables first,
1799 and thus naturally allocate things in the right order. */
1800 if (has_protected_decls)
1802 /* Phase 1 contains only character arrays. */
1803 expand_stack_vars (stack_protect_decl_phase_1);
1805 /* Phase 2 contains other kinds of arrays. */
1806 if (flag_stack_protect == 2)
1807 expand_stack_vars (stack_protect_decl_phase_2);
1810 expand_stack_vars (NULL);
1812 fini_vars_expansion ();
1815 /* If the target requires that FRAME_OFFSET be aligned, do it. */
1816 if (STACK_ALIGNMENT_NEEDED)
1818 HOST_WIDE_INT align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1819 if (!FRAME_GROWS_DOWNWARD)
1820 frame_offset += align - 1;
1821 frame_offset &= -align;
1826 /* If we need to produce a detailed dump, print the tree representation
1827 for STMT to the dump file. SINCE is the last RTX after which the RTL
1828 generated for STMT should have been appended. */
1831 maybe_dump_rtl_for_gimple_stmt (gimple stmt, rtx since)
1833 if (dump_file && (dump_flags & TDF_DETAILS))
1835 fprintf (dump_file, "\n;; ");
1836 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1837 fprintf (dump_file, "\n");
1839 print_rtl (dump_file, since ? NEXT_INSN (since) : since);
1843 /* Maps the blocks that do not contain tree labels to rtx labels. */
1845 static struct pointer_map_t *lab_rtx_for_bb;
1847 /* Returns the label_rtx expression for a label starting basic block BB. */
1850 label_rtx_for_bb (basic_block bb ATTRIBUTE_UNUSED)
1852 gimple_stmt_iterator gsi;
1857 if (bb->flags & BB_RTL)
1858 return block_label (bb);
1860 elt = pointer_map_contains (lab_rtx_for_bb, bb);
1864 /* Find the tree label if it is present. */
1866 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1868 lab_stmt = gsi_stmt (gsi);
1869 if (gimple_code (lab_stmt) != GIMPLE_LABEL)
1872 lab = gimple_label_label (lab_stmt);
1873 if (DECL_NONLOCAL (lab))
1876 return label_rtx (lab);
1879 elt = pointer_map_insert (lab_rtx_for_bb, bb);
1880 *elt = gen_label_rtx ();
1885 /* A subroutine of expand_gimple_cond. Given E, a fallthrough edge
1886 of a basic block where we just expanded the conditional at the end,
1887 possibly clean up the CFG and instruction sequence. */
1890 maybe_cleanup_end_of_block (edge e)
1892 /* Special case: when jumpif decides that the condition is
1893 trivial it emits an unconditional jump (and the necessary
1894 barrier). But we still have two edges, the fallthru one is
1895 wrong. purge_dead_edges would clean this up later. Unfortunately
1896 we have to insert insns (and split edges) before
1897 find_many_sub_basic_blocks and hence before purge_dead_edges.
1898 But splitting edges might create new blocks which depend on the
1899 fact that if there are two edges there's no barrier. So the
1900 barrier would get lost and verify_flow_info would ICE. Instead
1901 of auditing all edge splitters to care for the barrier (which
1902 normally isn't there in a cleaned CFG), fix it here. */
1903 if (BARRIER_P (get_last_insn ()))
1905 basic_block bb = e->src;
1908 /* Now, we have a single successor block, if we have insns to
1909 insert on the remaining edge we potentially will insert
1910 it at the end of this block (if the dest block isn't feasible)
1911 in order to avoid splitting the edge. This insertion will take
1912 place in front of the last jump. But we might have emitted
1913 multiple jumps (conditional and one unconditional) to the
1914 same destination. Inserting in front of the last one then
1915 is a problem. See PR 40021. We fix this by deleting all
1916 jumps except the last unconditional one. */
1917 insn = PREV_INSN (get_last_insn ());
1918 /* Make sure we have an unconditional jump. Otherwise we're
1920 gcc_assert (JUMP_P (insn) && !any_condjump_p (insn));
1921 for (insn = PREV_INSN (insn); insn != BB_HEAD (bb);)
1923 insn = PREV_INSN (insn);
1924 if (JUMP_P (NEXT_INSN (insn)))
1925 delete_insn (NEXT_INSN (insn));
1931 /* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_COND.
1932 Returns a new basic block if we've terminated the current basic
1933 block and created a new one. */
1936 expand_gimple_cond (basic_block bb, gimple stmt)
1938 basic_block new_bb, dest;
1942 tree pred = gimple_cond_pred_to_tree (stmt);
1945 last2 = last = get_last_insn ();
1947 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1948 if (gimple_has_location (stmt))
1950 set_curr_insn_source_location (gimple_location (stmt));
1951 set_curr_insn_block (gimple_block (stmt));
1954 /* These flags have no purpose in RTL land. */
1955 true_edge->flags &= ~EDGE_TRUE_VALUE;
1956 false_edge->flags &= ~EDGE_FALSE_VALUE;
1958 /* We can either have a pure conditional jump with one fallthru edge or
1959 two-way jump that needs to be decomposed into two basic blocks. */
1960 if (false_edge->dest == bb->next_bb)
1962 jumpif (pred, label_rtx_for_bb (true_edge->dest));
1963 add_reg_br_prob_note (last, true_edge->probability);
1964 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1965 if (true_edge->goto_locus)
1967 set_curr_insn_source_location (true_edge->goto_locus);
1968 set_curr_insn_block (true_edge->goto_block);
1969 true_edge->goto_locus = curr_insn_locator ();
1971 true_edge->goto_block = NULL;
1972 false_edge->flags |= EDGE_FALLTHRU;
1974 maybe_cleanup_end_of_block (false_edge);
1977 if (true_edge->dest == bb->next_bb)
1979 jumpifnot (pred, label_rtx_for_bb (false_edge->dest));
1980 add_reg_br_prob_note (last, false_edge->probability);
1981 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1982 if (false_edge->goto_locus)
1984 set_curr_insn_source_location (false_edge->goto_locus);
1985 set_curr_insn_block (false_edge->goto_block);
1986 false_edge->goto_locus = curr_insn_locator ();
1988 false_edge->goto_block = NULL;
1989 true_edge->flags |= EDGE_FALLTHRU;
1991 maybe_cleanup_end_of_block (true_edge);
1995 jumpif (pred, label_rtx_for_bb (true_edge->dest));
1996 add_reg_br_prob_note (last, true_edge->probability);
1997 last = get_last_insn ();
1998 if (false_edge->goto_locus)
2000 set_curr_insn_source_location (false_edge->goto_locus);
2001 set_curr_insn_block (false_edge->goto_block);
2002 false_edge->goto_locus = curr_insn_locator ();
2004 false_edge->goto_block = NULL;
2005 emit_jump (label_rtx_for_bb (false_edge->dest));
2008 if (BARRIER_P (BB_END (bb)))
2009 BB_END (bb) = PREV_INSN (BB_END (bb));
2010 update_bb_for_insn (bb);
2012 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
2013 dest = false_edge->dest;
2014 redirect_edge_succ (false_edge, new_bb);
2015 false_edge->flags |= EDGE_FALLTHRU;
2016 new_bb->count = false_edge->count;
2017 new_bb->frequency = EDGE_FREQUENCY (false_edge);
2018 new_edge = make_edge (new_bb, dest, 0);
2019 new_edge->probability = REG_BR_PROB_BASE;
2020 new_edge->count = new_bb->count;
2021 if (BARRIER_P (BB_END (new_bb)))
2022 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
2023 update_bb_for_insn (new_bb);
2025 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
2027 if (true_edge->goto_locus)
2029 set_curr_insn_source_location (true_edge->goto_locus);
2030 set_curr_insn_block (true_edge->goto_block);
2031 true_edge->goto_locus = curr_insn_locator ();
2033 true_edge->goto_block = NULL;
2039 /* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_CALL
2040 that has CALL_EXPR_TAILCALL set. Returns non-null if we actually
2041 generated a tail call (something that might be denied by the ABI
2042 rules governing the call; see calls.c).
2044 Sets CAN_FALLTHRU if we generated a *conditional* tail call, and
2045 can still reach the rest of BB. The case here is __builtin_sqrt,
2046 where the NaN result goes through the external function (with a
2047 tailcall) and the normal result happens via a sqrt instruction. */
2050 expand_gimple_tailcall (basic_block bb, gimple stmt, bool *can_fallthru)
2057 tree stmt_tree = gimple_to_tree (stmt);
2059 last2 = last = get_last_insn ();
2061 expand_expr_stmt (stmt_tree);
2063 release_stmt_tree (stmt, stmt_tree);
2065 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
2066 if (CALL_P (last) && SIBLING_CALL_P (last))
2069 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
2071 *can_fallthru = true;
2075 /* ??? Wouldn't it be better to just reset any pending stack adjust?
2076 Any instructions emitted here are about to be deleted. */
2077 do_pending_stack_adjust ();
2079 /* Remove any non-eh, non-abnormal edges that don't go to exit. */
2080 /* ??? I.e. the fallthrough edge. HOWEVER! If there were to be
2081 EH or abnormal edges, we shouldn't have created a tail call in
2082 the first place. So it seems to me we should just be removing
2083 all edges here, or redirecting the existing fallthru edge to
2089 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2091 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
2093 if (e->dest != EXIT_BLOCK_PTR)
2095 e->dest->count -= e->count;
2096 e->dest->frequency -= EDGE_FREQUENCY (e);
2097 if (e->dest->count < 0)
2099 if (e->dest->frequency < 0)
2100 e->dest->frequency = 0;
2103 probability += e->probability;
2110 /* This is somewhat ugly: the call_expr expander often emits instructions
2111 after the sibcall (to perform the function return). These confuse the
2112 find_many_sub_basic_blocks code, so we need to get rid of these. */
2113 last = NEXT_INSN (last);
2114 gcc_assert (BARRIER_P (last));
2116 *can_fallthru = false;
2117 while (NEXT_INSN (last))
2119 /* For instance an sqrt builtin expander expands if with
2120 sibcall in the then and label for `else`. */
2121 if (LABEL_P (NEXT_INSN (last)))
2123 *can_fallthru = true;
2126 delete_insn (NEXT_INSN (last));
2129 e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
2130 e->probability += probability;
2133 update_bb_for_insn (bb);
2135 if (NEXT_INSN (last))
2137 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
2140 if (BARRIER_P (last))
2141 BB_END (bb) = PREV_INSN (last);
2144 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
2149 /* Expand basic block BB from GIMPLE trees to RTL. */
2152 expand_gimple_basic_block (basic_block bb)
2154 gimple_stmt_iterator gsi;
2163 fprintf (dump_file, "\n;; Generating RTL for gimple basic block %d\n",
2166 /* Note that since we are now transitioning from GIMPLE to RTL, we
2167 cannot use the gsi_*_bb() routines because they expect the basic
2168 block to be in GIMPLE, instead of RTL. Therefore, we need to
2169 access the BB sequence directly. */
2170 stmts = bb_seq (bb);
2171 bb->il.gimple = NULL;
2172 rtl_profile_for_bb (bb);
2173 init_rtl_bb_info (bb);
2174 bb->flags |= BB_RTL;
2176 /* Remove the RETURN_EXPR if we may fall though to the exit
2178 gsi = gsi_last (stmts);
2179 if (!gsi_end_p (gsi)
2180 && gimple_code (gsi_stmt (gsi)) == GIMPLE_RETURN)
2182 gimple ret_stmt = gsi_stmt (gsi);
2184 gcc_assert (single_succ_p (bb));
2185 gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2187 if (bb->next_bb == EXIT_BLOCK_PTR
2188 && !gimple_return_retval (ret_stmt))
2190 gsi_remove (&gsi, false);
2191 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2195 gsi = gsi_start (stmts);
2196 if (!gsi_end_p (gsi))
2198 stmt = gsi_stmt (gsi);
2199 if (gimple_code (stmt) != GIMPLE_LABEL)
2203 elt = pointer_map_contains (lab_rtx_for_bb, bb);
2207 last = get_last_insn ();
2211 tree stmt_tree = gimple_to_tree (stmt);
2212 expand_expr_stmt (stmt_tree);
2213 release_stmt_tree (stmt, stmt_tree);
2218 emit_label ((rtx) *elt);
2220 /* Java emits line number notes in the top of labels.
2221 ??? Make this go away once line number notes are obsoleted. */
2222 BB_HEAD (bb) = NEXT_INSN (last);
2223 if (NOTE_P (BB_HEAD (bb)))
2224 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
2225 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
2227 maybe_dump_rtl_for_gimple_stmt (stmt, last);
2230 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
2232 NOTE_BASIC_BLOCK (note) = bb;
2234 for (; !gsi_end_p (gsi); gsi_next (&gsi))
2236 gimple stmt = gsi_stmt (gsi);
2239 /* Expand this statement, then evaluate the resulting RTL and
2240 fixup the CFG accordingly. */
2241 if (gimple_code (stmt) == GIMPLE_COND)
2243 new_bb = expand_gimple_cond (bb, stmt);
2249 if (is_gimple_call (stmt) && gimple_call_tail_p (stmt))
2252 new_bb = expand_gimple_tailcall (bb, stmt, &can_fallthru);
2263 def_operand_p def_p;
2265 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
2269 /* Ignore this stmt if it is in the list of
2270 replaceable expressions. */
2272 && bitmap_bit_p (SA.values,
2273 SSA_NAME_VERSION (DEF_FROM_PTR (def_p))))
2276 stmt_tree = gimple_to_tree (stmt);
2277 last = get_last_insn ();
2278 expand_expr_stmt (stmt_tree);
2279 maybe_dump_rtl_for_gimple_stmt (stmt, last);
2280 release_stmt_tree (stmt, stmt_tree);
2285 /* Expand implicit goto and convert goto_locus. */
2286 FOR_EACH_EDGE (e, ei, bb->succs)
2288 if (e->goto_locus && e->goto_block)
2290 set_curr_insn_source_location (e->goto_locus);
2291 set_curr_insn_block (e->goto_block);
2292 e->goto_locus = curr_insn_locator ();
2294 e->goto_block = NULL;
2295 if ((e->flags & EDGE_FALLTHRU) && e->dest != bb->next_bb)
2297 emit_jump (label_rtx_for_bb (e->dest));
2298 e->flags &= ~EDGE_FALLTHRU;
2302 do_pending_stack_adjust ();
2304 /* Find the block tail. The last insn in the block is the insn
2305 before a barrier and/or table jump insn. */
2306 last = get_last_insn ();
2307 if (BARRIER_P (last))
2308 last = PREV_INSN (last);
2309 if (JUMP_TABLE_DATA_P (last))
2310 last = PREV_INSN (PREV_INSN (last));
2313 update_bb_for_insn (bb);
2319 /* Create a basic block for initialization code. */
2322 construct_init_block (void)
2324 basic_block init_block, first_block;
2328 /* Multiple entry points not supported yet. */
2329 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR->succs) == 1);
2330 init_rtl_bb_info (ENTRY_BLOCK_PTR);
2331 init_rtl_bb_info (EXIT_BLOCK_PTR);
2332 ENTRY_BLOCK_PTR->flags |= BB_RTL;
2333 EXIT_BLOCK_PTR->flags |= BB_RTL;
2335 e = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
2337 /* When entry edge points to first basic block, we don't need jump,
2338 otherwise we have to jump into proper target. */
2339 if (e && e->dest != ENTRY_BLOCK_PTR->next_bb)
2341 tree label = gimple_block_label (e->dest);
2343 emit_jump (label_rtx (label));
2347 flags = EDGE_FALLTHRU;
2349 init_block = create_basic_block (NEXT_INSN (get_insns ()),
2352 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
2353 init_block->count = ENTRY_BLOCK_PTR->count;
2356 first_block = e->dest;
2357 redirect_edge_succ (e, init_block);
2358 e = make_edge (init_block, first_block, flags);
2361 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
2362 e->probability = REG_BR_PROB_BASE;
2363 e->count = ENTRY_BLOCK_PTR->count;
2365 update_bb_for_insn (init_block);
2369 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
2370 found in the block tree. */
2373 set_block_levels (tree block, int level)
2377 BLOCK_NUMBER (block) = level;
2378 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
2379 block = BLOCK_CHAIN (block);
2383 /* Create a block containing landing pads and similar stuff. */
2386 construct_exit_block (void)
2388 rtx head = get_last_insn ();
2390 basic_block exit_block;
2394 rtx orig_end = BB_END (EXIT_BLOCK_PTR->prev_bb);
2396 rtl_profile_for_bb (EXIT_BLOCK_PTR);
2398 /* Make sure the locus is set to the end of the function, so that
2399 epilogue line numbers and warnings are set properly. */
2400 if (cfun->function_end_locus != UNKNOWN_LOCATION)
2401 input_location = cfun->function_end_locus;
2403 /* The following insns belong to the top scope. */
2404 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2406 /* Generate rtl for function exit. */
2407 expand_function_end ();
2409 end = get_last_insn ();
2412 /* While emitting the function end we could move end of the last basic block.
2414 BB_END (EXIT_BLOCK_PTR->prev_bb) = orig_end;
2415 while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
2416 head = NEXT_INSN (head);
2417 exit_block = create_basic_block (NEXT_INSN (head), end,
2418 EXIT_BLOCK_PTR->prev_bb);
2419 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
2420 exit_block->count = EXIT_BLOCK_PTR->count;
2423 while (ix < EDGE_COUNT (EXIT_BLOCK_PTR->preds))
2425 e = EDGE_PRED (EXIT_BLOCK_PTR, ix);
2426 if (!(e->flags & EDGE_ABNORMAL))
2427 redirect_edge_succ (e, exit_block);
2432 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
2433 e->probability = REG_BR_PROB_BASE;
2434 e->count = EXIT_BLOCK_PTR->count;
2435 FOR_EACH_EDGE (e2, ei, EXIT_BLOCK_PTR->preds)
2438 e->count -= e2->count;
2439 exit_block->count -= e2->count;
2440 exit_block->frequency -= EDGE_FREQUENCY (e2);
2444 if (exit_block->count < 0)
2445 exit_block->count = 0;
2446 if (exit_block->frequency < 0)
2447 exit_block->frequency = 0;
2448 update_bb_for_insn (exit_block);
2451 /* Helper function for discover_nonconstant_array_refs.
2452 Look for ARRAY_REF nodes with non-constant indexes and mark them
2456 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
2457 void *data ATTRIBUTE_UNUSED)
2461 if (IS_TYPE_OR_DECL_P (t))
2463 else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2465 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2466 && is_gimple_min_invariant (TREE_OPERAND (t, 1))
2467 && (!TREE_OPERAND (t, 2)
2468 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2469 || (TREE_CODE (t) == COMPONENT_REF
2470 && (!TREE_OPERAND (t,2)
2471 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2472 || TREE_CODE (t) == BIT_FIELD_REF
2473 || TREE_CODE (t) == REALPART_EXPR
2474 || TREE_CODE (t) == IMAGPART_EXPR
2475 || TREE_CODE (t) == VIEW_CONVERT_EXPR
2476 || CONVERT_EXPR_P (t))
2477 t = TREE_OPERAND (t, 0);
2479 if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2481 t = get_base_address (t);
2483 && DECL_MODE (t) != BLKmode)
2484 TREE_ADDRESSABLE (t) = 1;
2493 /* RTL expansion is not able to compile array references with variable
2494 offsets for arrays stored in single register. Discover such
2495 expressions and mark variables as addressable to avoid this
2499 discover_nonconstant_array_refs (void)
2502 gimple_stmt_iterator gsi;
2505 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2507 gimple stmt = gsi_stmt (gsi);
2508 walk_gimple_op (stmt, discover_nonconstant_array_refs_r, NULL);
2512 /* This function sets crtl->args.internal_arg_pointer to a virtual
2513 register if DRAP is needed. Local register allocator will replace
2514 virtual_incoming_args_rtx with the virtual register. */
2517 expand_stack_alignment (void)
2520 unsigned int preferred_stack_boundary;
2522 if (! SUPPORTS_STACK_ALIGNMENT)
2525 if (cfun->calls_alloca
2526 || cfun->has_nonlocal_label
2527 || crtl->has_nonlocal_goto)
2528 crtl->need_drap = true;
2530 gcc_assert (crtl->stack_alignment_needed
2531 <= crtl->stack_alignment_estimated);
2533 /* Update crtl->stack_alignment_estimated and use it later to align
2534 stack. We check PREFERRED_STACK_BOUNDARY if there may be non-call
2535 exceptions since callgraph doesn't collect incoming stack alignment
2537 if (flag_non_call_exceptions
2538 && PREFERRED_STACK_BOUNDARY > crtl->preferred_stack_boundary)
2539 preferred_stack_boundary = PREFERRED_STACK_BOUNDARY;
2541 preferred_stack_boundary = crtl->preferred_stack_boundary;
2542 if (preferred_stack_boundary > crtl->stack_alignment_estimated)
2543 crtl->stack_alignment_estimated = preferred_stack_boundary;
2544 if (preferred_stack_boundary > crtl->stack_alignment_needed)
2545 crtl->stack_alignment_needed = preferred_stack_boundary;
2547 crtl->stack_realign_needed
2548 = INCOMING_STACK_BOUNDARY < crtl->stack_alignment_estimated;
2549 crtl->stack_realign_tried = crtl->stack_realign_needed;
2551 crtl->stack_realign_processed = true;
2553 /* Target has to redefine TARGET_GET_DRAP_RTX to support stack
2555 gcc_assert (targetm.calls.get_drap_rtx != NULL);
2556 drap_rtx = targetm.calls.get_drap_rtx ();
2558 /* stack_realign_drap and drap_rtx must match. */
2559 gcc_assert ((stack_realign_drap != 0) == (drap_rtx != NULL));
2561 /* Do nothing if NULL is returned, which means DRAP is not needed. */
2562 if (NULL != drap_rtx)
2564 crtl->args.internal_arg_pointer = drap_rtx;
2566 /* Call fixup_tail_calls to clean up REG_EQUIV note if DRAP is
2568 fixup_tail_calls ();
2572 /* Translate the intermediate representation contained in the CFG
2573 from GIMPLE trees to RTL.
2575 We do conversion per basic block and preserve/update the tree CFG.
2576 This implies we have to do some magic as the CFG can simultaneously
2577 consist of basic blocks containing RTL and GIMPLE trees. This can
2578 confuse the CFG hooks, so be careful to not manipulate CFG during
2582 gimple_expand_cfg (void)
2584 basic_block bb, init_block;
2590 rewrite_out_of_ssa (&SA);
2591 SA.partition_to_pseudo = (rtx *)xcalloc (SA.map->num_partitions,
2594 /* Some backends want to know that we are expanding to RTL. */
2595 currently_expanding_to_rtl = 1;
2597 rtl_profile_for_bb (ENTRY_BLOCK_PTR);
2599 insn_locators_alloc ();
2600 if (!DECL_IS_BUILTIN (current_function_decl))
2602 /* Eventually, all FEs should explicitly set function_start_locus. */
2603 if (cfun->function_start_locus == UNKNOWN_LOCATION)
2604 set_curr_insn_source_location
2605 (DECL_SOURCE_LOCATION (current_function_decl));
2607 set_curr_insn_source_location (cfun->function_start_locus);
2609 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2610 prologue_locator = curr_insn_locator ();
2612 /* Make sure first insn is a note even if we don't want linenums.
2613 This makes sure the first insn will never be deleted.
2614 Also, final expects a note to appear there. */
2615 emit_note (NOTE_INSN_DELETED);
2617 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2618 discover_nonconstant_array_refs ();
2620 targetm.expand_to_rtl_hook ();
2621 crtl->stack_alignment_needed = STACK_BOUNDARY;
2622 crtl->max_used_stack_slot_alignment = STACK_BOUNDARY;
2623 crtl->stack_alignment_estimated = STACK_BOUNDARY;
2624 crtl->preferred_stack_boundary = STACK_BOUNDARY;
2625 cfun->cfg->max_jumptable_ents = 0;
2628 /* Expand the variables recorded during gimple lowering. */
2629 expand_used_vars ();
2631 /* Honor stack protection warnings. */
2632 if (warn_stack_protect)
2634 if (cfun->calls_alloca)
2635 warning (OPT_Wstack_protector,
2636 "not protecting local variables: variable length buffer");
2637 if (has_short_buffer && !crtl->stack_protect_guard)
2638 warning (OPT_Wstack_protector,
2639 "not protecting function: no buffer at least %d bytes long",
2640 (int) PARAM_VALUE (PARAM_SSP_BUFFER_SIZE));
2643 /* Set up parameters and prepare for return, for the function. */
2644 expand_function_start (current_function_decl);
2646 /* Now that we also have the parameter RTXs, copy them over to our
2648 for (i = 0; i < SA.map->num_partitions; i++)
2650 tree var = SSA_NAME_VAR (partition_to_var (SA.map, i));
2652 if (TREE_CODE (var) != VAR_DECL
2653 && !SA.partition_to_pseudo[i])
2654 SA.partition_to_pseudo[i] = DECL_RTL_IF_SET (var);
2655 gcc_assert (SA.partition_to_pseudo[i]);
2657 /* If this decl was marked as living in multiple places, reset
2658 this now to NULL. */
2659 if (DECL_RTL_IF_SET (var) == pc_rtx)
2660 SET_DECL_RTL (var, NULL);
2662 /* Some RTL parts really want to look at DECL_RTL(x) when x
2663 was a decl marked in REG_ATTR or MEM_ATTR. We could use
2664 SET_DECL_RTL here making this available, but that would mean
2665 to select one of the potentially many RTLs for one DECL. Instead
2666 of doing that we simply reset the MEM_EXPR of the RTL in question,
2667 then nobody can get at it and hence nobody can call DECL_RTL on it. */
2668 if (!DECL_RTL_SET_P (var))
2670 if (MEM_P (SA.partition_to_pseudo[i]))
2671 set_mem_expr (SA.partition_to_pseudo[i], NULL);
2675 /* If this function is `main', emit a call to `__main'
2676 to run global initializers, etc. */
2677 if (DECL_NAME (current_function_decl)
2678 && MAIN_NAME_P (DECL_NAME (current_function_decl))
2679 && DECL_FILE_SCOPE_P (current_function_decl))
2680 expand_main_function ();
2682 /* Initialize the stack_protect_guard field. This must happen after the
2683 call to __main (if any) so that the external decl is initialized. */
2684 if (crtl->stack_protect_guard)
2685 stack_protect_prologue ();
2687 /* Update stack boundary if needed. */
2688 if (SUPPORTS_STACK_ALIGNMENT)
2690 /* Call update_stack_boundary here to update incoming stack
2691 boundary before TARGET_FUNCTION_OK_FOR_SIBCALL is called.
2692 TARGET_FUNCTION_OK_FOR_SIBCALL needs to know the accurate
2693 incoming stack alignment to check if it is OK to perform
2694 sibcall optimization since sibcall optimization will only
2695 align the outgoing stack to incoming stack boundary. */
2696 if (targetm.calls.update_stack_boundary)
2697 targetm.calls.update_stack_boundary ();
2699 /* The incoming stack frame has to be aligned at least at
2700 parm_stack_boundary. */
2701 gcc_assert (crtl->parm_stack_boundary <= INCOMING_STACK_BOUNDARY);
2704 expand_phi_nodes (&SA);
2706 /* Register rtl specific functions for cfg. */
2707 rtl_register_cfg_hooks ();
2709 init_block = construct_init_block ();
2711 /* Clear EDGE_EXECUTABLE on the entry edge(s). It is cleaned from the
2712 remaining edges later. */
2713 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2714 e->flags &= ~EDGE_EXECUTABLE;
2716 lab_rtx_for_bb = pointer_map_create ();
2717 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
2718 bb = expand_gimple_basic_block (bb);
2720 execute_free_datastructures ();
2721 finish_out_of_ssa (&SA);
2723 /* Expansion is used by optimization passes too, set maybe_hot_insn_p
2724 conservatively to true until they are all profile aware. */
2725 pointer_map_destroy (lab_rtx_for_bb);
2728 construct_exit_block ();
2729 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2730 insn_locators_finalize ();
2732 /* Convert tree EH labels to RTL EH labels and zap the tree EH table. */
2733 convert_from_eh_region_ranges ();
2734 set_eh_throw_stmt_table (cfun, NULL);
2736 rebuild_jump_labels (get_insns ());
2737 find_exception_handler_labels ();
2739 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
2743 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2746 commit_one_edge_insertion (e);
2752 /* We're done expanding trees to RTL. */
2753 currently_expanding_to_rtl = 0;
2755 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
2759 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2761 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
2762 e->flags &= ~EDGE_EXECUTABLE;
2764 /* At the moment not all abnormal edges match the RTL
2765 representation. It is safe to remove them here as
2766 find_many_sub_basic_blocks will rediscover them.
2767 In the future we should get this fixed properly. */
2768 if ((e->flags & EDGE_ABNORMAL)
2769 && !(e->flags & EDGE_SIBCALL))
2776 blocks = sbitmap_alloc (last_basic_block);
2777 sbitmap_ones (blocks);
2778 find_many_sub_basic_blocks (blocks);
2779 sbitmap_free (blocks);
2780 purge_all_dead_edges ();
2784 expand_stack_alignment ();
2786 #ifdef ENABLE_CHECKING
2787 verify_flow_info ();
2790 /* There's no need to defer outputting this function any more; we
2791 know we want to output it. */
2792 DECL_DEFER_OUTPUT (current_function_decl) = 0;
2794 /* Now that we're done expanding trees to RTL, we shouldn't have any
2795 more CONCATs anywhere. */
2796 generating_concat_p = 0;
2801 "\n\n;;\n;; Full RTL generated for this function:\n;;\n");
2802 /* And the pass manager will dump RTL for us. */
2805 /* If we're emitting a nested function, make sure its parent gets
2806 emitted as well. Doing otherwise confuses debug info. */
2809 for (parent = DECL_CONTEXT (current_function_decl);
2810 parent != NULL_TREE;
2811 parent = get_containing_scope (parent))
2812 if (TREE_CODE (parent) == FUNCTION_DECL)
2813 TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (parent)) = 1;
2816 /* We are now committed to emitting code for this function. Do any
2817 preparation, such as emitting abstract debug info for the inline
2818 before it gets mangled by optimization. */
2819 if (cgraph_function_possibly_inlined_p (current_function_decl))
2820 (*debug_hooks->outlining_inline_function) (current_function_decl);
2822 TREE_ASM_WRITTEN (current_function_decl) = 1;
2824 /* After expanding, the return labels are no longer needed. */
2825 return_label = NULL;
2826 naked_return_label = NULL;
2827 /* Tag the blocks with a depth number so that change_scope can find
2828 the common parent easily. */
2829 set_block_levels (DECL_INITIAL (cfun->decl), 0);
2830 default_rtl_profile ();
2834 struct rtl_opt_pass pass_expand =
2838 "expand", /* name */
2840 gimple_expand_cfg, /* execute */
2843 0, /* static_pass_number */
2844 TV_EXPAND, /* tv_id */
2845 PROP_ssa | PROP_gimple_leh | PROP_cfg,/* properties_required */
2846 PROP_rtl, /* properties_provided */
2847 PROP_ssa | PROP_trees, /* properties_destroyed */
2848 TODO_verify_ssa | TODO_verify_flow
2849 | TODO_verify_stmts, /* todo_flags_start */
2851 | TODO_ggc_collect /* todo_flags_finish */