Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / cfgexpand.c
CommitLineData
c251ad9e 1/* A pass for lowering trees to RTL.
4b1e227d 2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
c251ad9e
SS
3 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "basic-block.h"
29#include "function.h"
30#include "expr.h"
31#include "langhooks.h"
32#include "tree-flow.h"
33#include "timevar.h"
34#include "tree-dump.h"
35#include "tree-pass.h"
36#include "except.h"
37#include "flags.h"
38#include "diagnostic.h"
39#include "toplev.h"
40#include "debug.h"
41#include "params.h"
42#include "tree-inline.h"
43#include "value-prof.h"
44#include "target.h"
45
46
47/* Return an expression tree corresponding to the RHS of GIMPLE
48 statement STMT. */
49
50tree
51gimple_assign_rhs_to_tree (gimple stmt)
52{
53 tree t;
54 enum gimple_rhs_class grhs_class;
55
56 grhs_class = get_gimple_rhs_class (gimple_expr_code (stmt));
57
58 if (grhs_class == GIMPLE_BINARY_RHS)
59 t = build2 (gimple_assign_rhs_code (stmt),
60 TREE_TYPE (gimple_assign_lhs (stmt)),
61 gimple_assign_rhs1 (stmt),
62 gimple_assign_rhs2 (stmt));
63 else if (grhs_class == GIMPLE_UNARY_RHS)
64 t = build1 (gimple_assign_rhs_code (stmt),
65 TREE_TYPE (gimple_assign_lhs (stmt)),
66 gimple_assign_rhs1 (stmt));
67 else if (grhs_class == GIMPLE_SINGLE_RHS)
68 t = gimple_assign_rhs1 (stmt);
69 else
70 gcc_unreachable ();
71
72 return t;
73}
74
75/* Return an expression tree corresponding to the PREDICATE of GIMPLE_COND
76 statement STMT. */
77
78static tree
79gimple_cond_pred_to_tree (gimple stmt)
80{
81 return build2 (gimple_cond_code (stmt), boolean_type_node,
82 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
83}
84
85/* Helper for gimple_to_tree. Set EXPR_LOCATION for every expression
86 inside *TP. DATA is the location to set. */
87
88static tree
89set_expr_location_r (tree *tp, int *ws ATTRIBUTE_UNUSED, void *data)
90{
91 location_t *loc = (location_t *) data;
92 if (EXPR_P (*tp))
93 SET_EXPR_LOCATION (*tp, *loc);
94
95 return NULL_TREE;
96}
97
98
99/* RTL expansion has traditionally been done on trees, so the
100 transition to doing it on GIMPLE tuples is very invasive to the RTL
101 expander. To facilitate the transition, this function takes a
102 GIMPLE tuple STMT and returns the same statement in the form of a
103 tree. */
104
105static tree
106gimple_to_tree (gimple stmt)
107{
108 tree t;
109 int rn;
110 tree_ann_common_t ann;
111 location_t loc;
112
113 switch (gimple_code (stmt))
114 {
115 case GIMPLE_ASSIGN:
116 {
117 tree lhs = gimple_assign_lhs (stmt);
118
119 t = gimple_assign_rhs_to_tree (stmt);
120 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
121 if (gimple_assign_nontemporal_move_p (stmt))
122 MOVE_NONTEMPORAL (t) = true;
123 }
124 break;
125
126 case GIMPLE_COND:
127 t = gimple_cond_pred_to_tree (stmt);
128 t = build3 (COND_EXPR, void_type_node, t, NULL_TREE, NULL_TREE);
129 break;
130
131 case GIMPLE_GOTO:
132 t = build1 (GOTO_EXPR, void_type_node, gimple_goto_dest (stmt));
133 break;
134
135 case GIMPLE_LABEL:
136 t = build1 (LABEL_EXPR, void_type_node, gimple_label_label (stmt));
137 break;
138
139 case GIMPLE_RETURN:
140 {
141 tree retval = gimple_return_retval (stmt);
142
143 if (retval && retval != error_mark_node)
144 {
145 tree result = DECL_RESULT (current_function_decl);
146
147 /* If we are not returning the current function's RESULT_DECL,
148 build an assignment to it. */
149 if (retval != result)
150 {
151 /* I believe that a function's RESULT_DECL is unique. */
152 gcc_assert (TREE_CODE (retval) != RESULT_DECL);
153
154 retval = build2 (MODIFY_EXPR, TREE_TYPE (result),
155 result, retval);
156 }
157 }
158 t = build1 (RETURN_EXPR, void_type_node, retval);
159 }
160 break;
161
162 case GIMPLE_ASM:
163 {
164 size_t i, n;
165 tree out, in, cl;
166 const char *s;
167
168 out = NULL_TREE;
169 n = gimple_asm_noutputs (stmt);
170 if (n > 0)
171 {
172 t = out = gimple_asm_output_op (stmt, 0);
173 for (i = 1; i < n; i++)
174 {
175 TREE_CHAIN (t) = gimple_asm_output_op (stmt, i);
176 t = gimple_asm_output_op (stmt, i);
177 }
178 }
179
180 in = NULL_TREE;
181 n = gimple_asm_ninputs (stmt);
182 if (n > 0)
183 {
184 t = in = gimple_asm_input_op (stmt, 0);
185 for (i = 1; i < n; i++)
186 {
187 TREE_CHAIN (t) = gimple_asm_input_op (stmt, i);
188 t = gimple_asm_input_op (stmt, i);
189 }
190 }
191
192 cl = NULL_TREE;
193 n = gimple_asm_nclobbers (stmt);
194 if (n > 0)
195 {
196 t = cl = gimple_asm_clobber_op (stmt, 0);
197 for (i = 1; i < n; i++)
198 {
199 TREE_CHAIN (t) = gimple_asm_clobber_op (stmt, i);
200 t = gimple_asm_clobber_op (stmt, i);
201 }
202 }
203
204 s = gimple_asm_string (stmt);
205 t = build4 (ASM_EXPR, void_type_node, build_string (strlen (s), s),
206 out, in, cl);
207 ASM_VOLATILE_P (t) = gimple_asm_volatile_p (stmt);
208 ASM_INPUT_P (t) = gimple_asm_input_p (stmt);
209 }
210 break;
211
212 case GIMPLE_CALL:
213 {
214 size_t i;
215 tree fn;
216 tree_ann_common_t ann;
217
218 t = build_vl_exp (CALL_EXPR, gimple_call_num_args (stmt) + 3);
219
220 CALL_EXPR_FN (t) = gimple_call_fn (stmt);
221 TREE_TYPE (t) = gimple_call_return_type (stmt);
222 CALL_EXPR_STATIC_CHAIN (t) = gimple_call_chain (stmt);
223
224 for (i = 0; i < gimple_call_num_args (stmt); i++)
225 CALL_EXPR_ARG (t, i) = gimple_call_arg (stmt, i);
226
227 if (!(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
228 TREE_SIDE_EFFECTS (t) = 1;
229
230 if (gimple_call_flags (stmt) & ECF_NOTHROW)
231 TREE_NOTHROW (t) = 1;
232
233 CALL_EXPR_TAILCALL (t) = gimple_call_tail_p (stmt);
234 CALL_EXPR_RETURN_SLOT_OPT (t) = gimple_call_return_slot_opt_p (stmt);
235 CALL_FROM_THUNK_P (t) = gimple_call_from_thunk_p (stmt);
236 CALL_CANNOT_INLINE_P (t) = gimple_call_cannot_inline_p (stmt);
237 CALL_EXPR_VA_ARG_PACK (t) = gimple_call_va_arg_pack_p (stmt);
238
239 /* If the call has a LHS then create a MODIFY_EXPR to hold it. */
240 {
241 tree lhs = gimple_call_lhs (stmt);
242
243 if (lhs)
244 t = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, t);
245 }
246
247 /* Record the original call statement, as it may be used
248 to retrieve profile information during expansion. */
249
250 if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
251 && DECL_BUILT_IN (fn))
252 {
253 ann = get_tree_common_ann (t);
254 ann->stmt = stmt;
255 }
256 }
257 break;
258
259 case GIMPLE_SWITCH:
260 {
261 tree label_vec;
262 size_t i;
263 tree elt = gimple_switch_label (stmt, 0);
264
265 label_vec = make_tree_vec (gimple_switch_num_labels (stmt));
266
267 if (!CASE_LOW (elt) && !CASE_HIGH (elt))
268 {
269 for (i = 1; i < gimple_switch_num_labels (stmt); i++)
270 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, i);
271
272 /* The default case in a SWITCH_EXPR must be at the end of
273 the label vector. */
274 TREE_VEC_ELT (label_vec, i - 1) = gimple_switch_label (stmt, 0);
275 }
276 else
277 {
278 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
279 TREE_VEC_ELT (label_vec, i) = gimple_switch_label (stmt, i);
280 }
281
282 t = build3 (SWITCH_EXPR, void_type_node, gimple_switch_index (stmt),
283 NULL, label_vec);
284 }
285 break;
286
287 case GIMPLE_NOP:
288 case GIMPLE_PREDICT:
289 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
290 break;
291
292 case GIMPLE_RESX:
293 t = build_resx (gimple_resx_region (stmt));
294 break;
295
296 default:
297 if (errorcount == 0)
298 {
299 error ("Unrecognized GIMPLE statement during RTL expansion");
300 print_gimple_stmt (stderr, stmt, 4, 0);
301 gcc_unreachable ();
302 }
303 else
304 {
305 /* Ignore any bad gimple codes if we're going to die anyhow,
306 so we can at least set TREE_ASM_WRITTEN and have the rest
307 of compilation advance without sudden ICE death. */
308 t = build1 (NOP_EXPR, void_type_node, size_zero_node);
309 break;
310 }
311 }
312
313 /* If STMT is inside an exception region, record it in the generated
314 expression. */
315 rn = lookup_stmt_eh_region (stmt);
316 if (rn >= 0)
317 {
318 tree call = get_call_expr_in (t);
319
320 ann = get_tree_common_ann (t);
321 ann->rn = rn;
322
323 /* For a CALL_EXPR on the RHS of an assignment, calls.c looks up
324 the CALL_EXPR not the assignment statment for EH region number. */
325 if (call && call != t)
326 {
327 ann = get_tree_common_ann (call);
328 ann->rn = rn;
329 }
330 }
331
332 /* Set EXPR_LOCATION in all the embedded expressions. */
333 loc = gimple_location (stmt);
334 walk_tree (&t, set_expr_location_r, (void *) &loc, NULL);
335
336 TREE_BLOCK (t) = gimple_block (stmt);
337
338 return t;
339}
340
341
342/* Release back to GC memory allocated by gimple_to_tree. */
343
344static void
345release_stmt_tree (gimple stmt, tree stmt_tree)
346{
347 tree_ann_common_t ann;
348
349 switch (gimple_code (stmt))
350 {
351 case GIMPLE_ASSIGN:
352 if (get_gimple_rhs_class (gimple_expr_code (stmt)) != GIMPLE_SINGLE_RHS)
353 ggc_free (TREE_OPERAND (stmt_tree, 1));
354 break;
355 case GIMPLE_COND:
356 ggc_free (COND_EXPR_COND (stmt_tree));
357 break;
358 case GIMPLE_RETURN:
359 if (TREE_OPERAND (stmt_tree, 0)
360 && TREE_CODE (TREE_OPERAND (stmt_tree, 0)) == MODIFY_EXPR)
361 ggc_free (TREE_OPERAND (stmt_tree, 0));
362 break;
363 case GIMPLE_CALL:
364 if (gimple_call_lhs (stmt))
365 {
366 ann = tree_common_ann (TREE_OPERAND (stmt_tree, 1));
367 if (ann)
368 ggc_free (ann);
369 ggc_free (TREE_OPERAND (stmt_tree, 1));
370 }
371 break;
372 default:
373 break;
374 }
375 ann = tree_common_ann (stmt_tree);
376 if (ann)
377 ggc_free (ann);
378 ggc_free (stmt_tree);
379}
380
381
c251ad9e
SS
382#ifndef STACK_ALIGNMENT_NEEDED
383#define STACK_ALIGNMENT_NEEDED 1
384#endif
385
386
387/* This structure holds data relevant to one variable that will be
388 placed in a stack slot. */
389struct stack_var
390{
391 /* The Variable. */
392 tree decl;
393
394 /* The offset of the variable. During partitioning, this is the
395 offset relative to the partition. After partitioning, this
396 is relative to the stack frame. */
397 HOST_WIDE_INT offset;
398
399 /* Initially, the size of the variable. Later, the size of the partition,
400 if this variable becomes it's partition's representative. */
401 HOST_WIDE_INT size;
402
403 /* The *byte* alignment required for this variable. Or as, with the
404 size, the alignment for this partition. */
405 unsigned int alignb;
406
407 /* The partition representative. */
408 size_t representative;
409
410 /* The next stack variable in the partition, or EOC. */
411 size_t next;
412};
413
414#define EOC ((size_t)-1)
415
416/* We have an array of such objects while deciding allocation. */
417static struct stack_var *stack_vars;
418static size_t stack_vars_alloc;
419static size_t stack_vars_num;
420
421/* An array of indices such that stack_vars[stack_vars_sorted[i]].size
422 is non-decreasing. */
423static size_t *stack_vars_sorted;
424
425/* We have an interference graph between such objects. This graph
426 is lower triangular. */
427static bool *stack_vars_conflict;
428static size_t stack_vars_conflict_alloc;
429
430/* The phase of the stack frame. This is the known misalignment of
431 virtual_stack_vars_rtx from PREFERRED_STACK_BOUNDARY. That is,
432 (frame_offset+frame_phase) % PREFERRED_STACK_BOUNDARY == 0. */
433static int frame_phase;
434
435/* Used during expand_used_vars to remember if we saw any decls for
436 which we'd like to enable stack smashing protection. */
437static bool has_protected_decls;
438
439/* Used during expand_used_vars. Remember if we say a character buffer
440 smaller than our cutoff threshold. Used for -Wstack-protector. */
441static bool has_short_buffer;
442
443/* Discover the byte alignment to use for DECL. Ignore alignment
444 we can't do with expected alignment of the stack boundary. */
445
446static unsigned int
447get_decl_align_unit (tree decl)
448{
449 unsigned int align;
450
451 align = LOCAL_DECL_ALIGNMENT (decl);
452
453 if (align > MAX_SUPPORTED_STACK_ALIGNMENT)
454 align = MAX_SUPPORTED_STACK_ALIGNMENT;
455
456 if (SUPPORTS_STACK_ALIGNMENT)
457 {
458 if (crtl->stack_alignment_estimated < align)
459 {
460 gcc_assert(!crtl->stack_realign_processed);
461 crtl->stack_alignment_estimated = align;
462 }
463 }
464
465 /* stack_alignment_needed > PREFERRED_STACK_BOUNDARY is permitted.
466 So here we only make sure stack_alignment_needed >= align. */
467 if (crtl->stack_alignment_needed < align)
468 crtl->stack_alignment_needed = align;
469 if (crtl->max_used_stack_slot_alignment < crtl->stack_alignment_needed)
470 crtl->max_used_stack_slot_alignment = crtl->stack_alignment_needed;
471
472 return align / BITS_PER_UNIT;
473}
474
475/* Allocate SIZE bytes at byte alignment ALIGN from the stack frame.
476 Return the frame offset. */
477
478static HOST_WIDE_INT
479alloc_stack_frame_space (HOST_WIDE_INT size, HOST_WIDE_INT align)
480{
481 HOST_WIDE_INT offset, new_frame_offset;
482
483 new_frame_offset = frame_offset;
484 if (FRAME_GROWS_DOWNWARD)
485 {
486 new_frame_offset -= size + frame_phase;
487 new_frame_offset &= -align;
488 new_frame_offset += frame_phase;
489 offset = new_frame_offset;
490 }
491 else
492 {
493 new_frame_offset -= frame_phase;
494 new_frame_offset += align - 1;
495 new_frame_offset &= -align;
496 new_frame_offset += frame_phase;
497 offset = new_frame_offset;
498 new_frame_offset += size;
499 }
500 frame_offset = new_frame_offset;
501
502 if (frame_offset_overflow (frame_offset, cfun->decl))
503 frame_offset = offset = 0;
504
505 return offset;
506}
507
508/* Accumulate DECL into STACK_VARS. */
509
510static void
511add_stack_var (tree decl)
512{
513 if (stack_vars_num >= stack_vars_alloc)
514 {
515 if (stack_vars_alloc)
516 stack_vars_alloc = stack_vars_alloc * 3 / 2;
517 else
518 stack_vars_alloc = 32;
519 stack_vars
520 = XRESIZEVEC (struct stack_var, stack_vars, stack_vars_alloc);
521 }
522 stack_vars[stack_vars_num].decl = decl;
523 stack_vars[stack_vars_num].offset = 0;
524 stack_vars[stack_vars_num].size = tree_low_cst (DECL_SIZE_UNIT (decl), 1);
525 stack_vars[stack_vars_num].alignb = get_decl_align_unit (decl);
526
527 /* All variables are initially in their own partition. */
528 stack_vars[stack_vars_num].representative = stack_vars_num;
529 stack_vars[stack_vars_num].next = EOC;
530
531 /* Ensure that this decl doesn't get put onto the list twice. */
532 SET_DECL_RTL (decl, pc_rtx);
533
534 stack_vars_num++;
535}
536
537/* Compute the linear index of a lower-triangular coordinate (I, J). */
538
539static size_t
540triangular_index (size_t i, size_t j)
541{
542 if (i < j)
543 {
544 size_t t;
545 t = i, i = j, j = t;
546 }
547 return (i * (i + 1)) / 2 + j;
548}
549
550/* Ensure that STACK_VARS_CONFLICT is large enough for N objects. */
551
552static void
553resize_stack_vars_conflict (size_t n)
554{
555 size_t size = triangular_index (n-1, n-1) + 1;
556
557 if (size <= stack_vars_conflict_alloc)
558 return;
559
560 stack_vars_conflict = XRESIZEVEC (bool, stack_vars_conflict, size);
561 memset (stack_vars_conflict + stack_vars_conflict_alloc, 0,
562 (size - stack_vars_conflict_alloc) * sizeof (bool));
563 stack_vars_conflict_alloc = size;
564}
565
566/* Make the decls associated with luid's X and Y conflict. */
567
568static void
569add_stack_var_conflict (size_t x, size_t y)
570{
571 size_t index = triangular_index (x, y);
572 gcc_assert (index < stack_vars_conflict_alloc);
573 stack_vars_conflict[index] = true;
574}
575
576/* Check whether the decls associated with luid's X and Y conflict. */
577
578static bool
579stack_var_conflict_p (size_t x, size_t y)
580{
581 size_t index = triangular_index (x, y);
582 gcc_assert (index < stack_vars_conflict_alloc);
583 return stack_vars_conflict[index];
584}
585
586/* Returns true if TYPE is or contains a union type. */
587
588static bool
589aggregate_contains_union_type (tree type)
590{
591 tree field;
592
593 if (TREE_CODE (type) == UNION_TYPE
594 || TREE_CODE (type) == QUAL_UNION_TYPE)
595 return true;
596 if (TREE_CODE (type) == ARRAY_TYPE)
597 return aggregate_contains_union_type (TREE_TYPE (type));
598 if (TREE_CODE (type) != RECORD_TYPE)
599 return false;
600
601 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
602 if (TREE_CODE (field) == FIELD_DECL)
603 if (aggregate_contains_union_type (TREE_TYPE (field)))
604 return true;
605
606 return false;
607}
608
609/* A subroutine of expand_used_vars. If two variables X and Y have alias
610 sets that do not conflict, then do add a conflict for these variables
611 in the interference graph. We also need to make sure to add conflicts
612 for union containing structures. Else RTL alias analysis comes along
613 and due to type based aliasing rules decides that for two overlapping
614 union temporaries { short s; int i; } accesses to the same mem through
615 different types may not alias and happily reorders stores across
616 life-time boundaries of the temporaries (See PR25654).
617 We also have to mind MEM_IN_STRUCT_P and MEM_SCALAR_P. */
618
619static void
620add_alias_set_conflicts (void)
621{
622 size_t i, j, n = stack_vars_num;
623
624 for (i = 0; i < n; ++i)
625 {
626 tree type_i = TREE_TYPE (stack_vars[i].decl);
627 bool aggr_i = AGGREGATE_TYPE_P (type_i);
628 bool contains_union;
629
630 contains_union = aggregate_contains_union_type (type_i);
631 for (j = 0; j < i; ++j)
632 {
633 tree type_j = TREE_TYPE (stack_vars[j].decl);
634 bool aggr_j = AGGREGATE_TYPE_P (type_j);
635 if (aggr_i != aggr_j
636 /* Either the objects conflict by means of type based
637 aliasing rules, or we need to add a conflict. */
638 || !objects_must_conflict_p (type_i, type_j)
639 /* In case the types do not conflict ensure that access
640 to elements will conflict. In case of unions we have
641 to be careful as type based aliasing rules may say
642 access to the same memory does not conflict. So play
643 safe and add a conflict in this case. */
644 || contains_union)
645 add_stack_var_conflict (i, j);
646 }
647 }
648}
649
650/* A subroutine of partition_stack_vars. A comparison function for qsort,
651 sorting an array of indices by the size of the object. */
652
653static int
654stack_var_size_cmp (const void *a, const void *b)
655{
656 HOST_WIDE_INT sa = stack_vars[*(const size_t *)a].size;
657 HOST_WIDE_INT sb = stack_vars[*(const size_t *)b].size;
658 unsigned int uida = DECL_UID (stack_vars[*(const size_t *)a].decl);
659 unsigned int uidb = DECL_UID (stack_vars[*(const size_t *)b].decl);
660
661 if (sa < sb)
662 return -1;
663 if (sa > sb)
664 return 1;
665 /* For stack variables of the same size use the uid of the decl
666 to make the sort stable. */
667 if (uida < uidb)
668 return -1;
669 if (uida > uidb)
670 return 1;
671 return 0;
672}
673
674/* A subroutine of partition_stack_vars. The UNION portion of a UNION/FIND
675 partitioning algorithm. Partitions A and B are known to be non-conflicting.
676 Merge them into a single partition A.
677
678 At the same time, add OFFSET to all variables in partition B. At the end
679 of the partitioning process we've have a nice block easy to lay out within
680 the stack frame. */
681
682static void
683union_stack_vars (size_t a, size_t b, HOST_WIDE_INT offset)
684{
685 size_t i, last;
686
687 /* Update each element of partition B with the given offset,
688 and merge them into partition A. */
689 for (last = i = b; i != EOC; last = i, i = stack_vars[i].next)
690 {
691 stack_vars[i].offset += offset;
692 stack_vars[i].representative = a;
693 }
694 stack_vars[last].next = stack_vars[a].next;
695 stack_vars[a].next = b;
696
697 /* Update the required alignment of partition A to account for B. */
698 if (stack_vars[a].alignb < stack_vars[b].alignb)
699 stack_vars[a].alignb = stack_vars[b].alignb;
700
701 /* Update the interference graph and merge the conflicts. */
702 for (last = stack_vars_num, i = 0; i < last; ++i)
703 if (stack_var_conflict_p (b, i))
704 add_stack_var_conflict (a, i);
705}
706
707/* A subroutine of expand_used_vars. Binpack the variables into
708 partitions constrained by the interference graph. The overall
709 algorithm used is as follows:
710
711 Sort the objects by size.
712 For each object A {
713 S = size(A)
714 O = 0
715 loop {
716 Look for the largest non-conflicting object B with size <= S.
717 UNION (A, B)
718 offset(B) = O
719 O += size(B)
720 S -= size(B)
721 }
722 }
723*/
724
725static void
726partition_stack_vars (void)
727{
728 size_t si, sj, n = stack_vars_num;
729
730 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
731 for (si = 0; si < n; ++si)
732 stack_vars_sorted[si] = si;
733
734 if (n == 1)
735 return;
736
737 qsort (stack_vars_sorted, n, sizeof (size_t), stack_var_size_cmp);
738
739 /* Special case: detect when all variables conflict, and thus we can't
740 do anything during the partitioning loop. It isn't uncommon (with
741 C code at least) to declare all variables at the top of the function,
742 and if we're not inlining, then all variables will be in the same scope.
743 Take advantage of very fast libc routines for this scan. */
744 gcc_assert (sizeof(bool) == sizeof(char));
745 if (memchr (stack_vars_conflict, false, stack_vars_conflict_alloc) == NULL)
746 return;
747
748 for (si = 0; si < n; ++si)
749 {
750 size_t i = stack_vars_sorted[si];
751 HOST_WIDE_INT isize = stack_vars[i].size;
752 HOST_WIDE_INT offset = 0;
753
754 for (sj = si; sj-- > 0; )
755 {
756 size_t j = stack_vars_sorted[sj];
757 HOST_WIDE_INT jsize = stack_vars[j].size;
758 unsigned int jalign = stack_vars[j].alignb;
759
760 /* Ignore objects that aren't partition representatives. */
761 if (stack_vars[j].representative != j)
762 continue;
763
764 /* Ignore objects too large for the remaining space. */
765 if (isize < jsize)
766 continue;
767
768 /* Ignore conflicting objects. */
769 if (stack_var_conflict_p (i, j))
770 continue;
771
772 /* Refine the remaining space check to include alignment. */
773 if (offset & (jalign - 1))
774 {
775 HOST_WIDE_INT toff = offset;
776 toff += jalign - 1;
777 toff &= -(HOST_WIDE_INT)jalign;
778 if (isize - (toff - offset) < jsize)
779 continue;
780
781 isize -= toff - offset;
782 offset = toff;
783 }
784
785 /* UNION the objects, placing J at OFFSET. */
786 union_stack_vars (i, j, offset);
787
788 isize -= jsize;
789 if (isize == 0)
790 break;
791 }
792 }
793}
794
795/* A debugging aid for expand_used_vars. Dump the generated partitions. */
796
797static void
798dump_stack_var_partition (void)
799{
800 size_t si, i, j, n = stack_vars_num;
801
802 for (si = 0; si < n; ++si)
803 {
804 i = stack_vars_sorted[si];
805
806 /* Skip variables that aren't partition representatives, for now. */
807 if (stack_vars[i].representative != i)
808 continue;
809
810 fprintf (dump_file, "Partition %lu: size " HOST_WIDE_INT_PRINT_DEC
811 " align %u\n", (unsigned long) i, stack_vars[i].size,
812 stack_vars[i].alignb);
813
814 for (j = i; j != EOC; j = stack_vars[j].next)
815 {
816 fputc ('\t', dump_file);
817 print_generic_expr (dump_file, stack_vars[j].decl, dump_flags);
818 fprintf (dump_file, ", offset " HOST_WIDE_INT_PRINT_DEC "\n",
819 stack_vars[j].offset);
820 }
821 }
822}
823
824/* Assign rtl to DECL at frame offset OFFSET. */
825
826static void
827expand_one_stack_var_at (tree decl, HOST_WIDE_INT offset)
828{
4b1e227d 829 HOST_WIDE_INT align, max_align;
c251ad9e
SS
830 rtx x;
831
832 /* If this fails, we've overflowed the stack frame. Error nicely? */
833 gcc_assert (offset == trunc_int_for_mode (offset, Pmode));
834
835 x = plus_constant (virtual_stack_vars_rtx, offset);
836 x = gen_rtx_MEM (DECL_MODE (decl), x);
837
838 /* Set alignment we actually gave this decl. */
839 offset -= frame_phase;
840 align = offset & -offset;
841 align *= BITS_PER_UNIT;
4b1e227d
SW
842 max_align = crtl->max_used_stack_slot_alignment;
843 if (align == 0 || align > max_align)
844 align = max_align;
c251ad9e
SS
845 DECL_ALIGN (decl) = align;
846 DECL_USER_ALIGN (decl) = 0;
847
848 set_mem_attributes (x, decl, true);
849 SET_DECL_RTL (decl, x);
850}
851
852/* A subroutine of expand_used_vars. Give each partition representative
853 a unique location within the stack frame. Update each partition member
854 with that location. */
855
856static void
857expand_stack_vars (bool (*pred) (tree))
858{
859 size_t si, i, j, n = stack_vars_num;
860
861 for (si = 0; si < n; ++si)
862 {
863 HOST_WIDE_INT offset;
864
865 i = stack_vars_sorted[si];
866
867 /* Skip variables that aren't partition representatives, for now. */
868 if (stack_vars[i].representative != i)
869 continue;
870
871 /* Skip variables that have already had rtl assigned. See also
872 add_stack_var where we perpetrate this pc_rtx hack. */
873 if (DECL_RTL (stack_vars[i].decl) != pc_rtx)
874 continue;
875
876 /* Check the predicate to see whether this variable should be
877 allocated in this pass. */
878 if (pred && !pred (stack_vars[i].decl))
879 continue;
880
881 offset = alloc_stack_frame_space (stack_vars[i].size,
882 stack_vars[i].alignb);
883
884 /* Create rtl for each variable based on their location within the
885 partition. */
886 for (j = i; j != EOC; j = stack_vars[j].next)
887 {
888 gcc_assert (stack_vars[j].offset <= stack_vars[i].size);
889 expand_one_stack_var_at (stack_vars[j].decl,
890 stack_vars[j].offset + offset);
891 }
892 }
893}
894
895/* Take into account all sizes of partitions and reset DECL_RTLs. */
896static HOST_WIDE_INT
897account_stack_vars (void)
898{
899 size_t si, j, i, n = stack_vars_num;
900 HOST_WIDE_INT size = 0;
901
902 for (si = 0; si < n; ++si)
903 {
904 i = stack_vars_sorted[si];
905
906 /* Skip variables that aren't partition representatives, for now. */
907 if (stack_vars[i].representative != i)
908 continue;
909
910 size += stack_vars[i].size;
911 for (j = i; j != EOC; j = stack_vars[j].next)
912 SET_DECL_RTL (stack_vars[j].decl, NULL);
913 }
914 return size;
915}
916
917/* A subroutine of expand_one_var. Called to immediately assign rtl
918 to a variable to be allocated in the stack frame. */
919
920static void
921expand_one_stack_var (tree var)
922{
923 HOST_WIDE_INT size, offset, align;
924
925 size = tree_low_cst (DECL_SIZE_UNIT (var), 1);
926 align = get_decl_align_unit (var);
927 offset = alloc_stack_frame_space (size, align);
928
929 expand_one_stack_var_at (var, offset);
930}
931
932/* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
933 that will reside in a hard register. */
934
935static void
936expand_one_hard_reg_var (tree var)
937{
938 rest_of_decl_compilation (var, 0, 0);
939}
940
941/* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL
942 that will reside in a pseudo register. */
943
944static void
945expand_one_register_var (tree var)
946{
947 tree type = TREE_TYPE (var);
948 int unsignedp = TYPE_UNSIGNED (type);
949 enum machine_mode reg_mode
950 = promote_mode (type, DECL_MODE (var), &unsignedp, 0);
951 rtx x = gen_reg_rtx (reg_mode);
952
953 SET_DECL_RTL (var, x);
954
955 /* Note if the object is a user variable. */
956 if (!DECL_ARTIFICIAL (var))
957 mark_user_reg (x);
958
959 if (POINTER_TYPE_P (type))
960 mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
961}
962
963/* A subroutine of expand_one_var. Called to assign rtl to a VAR_DECL that
964 has some associated error, e.g. its type is error-mark. We just need
965 to pick something that won't crash the rest of the compiler. */
966
967static void
968expand_one_error_var (tree var)
969{
970 enum machine_mode mode = DECL_MODE (var);
971 rtx x;
972
973 if (mode == BLKmode)
974 x = gen_rtx_MEM (BLKmode, const0_rtx);
975 else if (mode == VOIDmode)
976 x = const0_rtx;
977 else
978 x = gen_reg_rtx (mode);
979
980 SET_DECL_RTL (var, x);
981}
982
983/* A subroutine of expand_one_var. VAR is a variable that will be
984 allocated to the local stack frame. Return true if we wish to
985 add VAR to STACK_VARS so that it will be coalesced with other
986 variables. Return false to allocate VAR immediately.
987
988 This function is used to reduce the number of variables considered
989 for coalescing, which reduces the size of the quadratic problem. */
990
991static bool
992defer_stack_allocation (tree var, bool toplevel)
993{
994 /* If stack protection is enabled, *all* stack variables must be deferred,
995 so that we can re-order the strings to the top of the frame. */
996 if (flag_stack_protect)
997 return true;
998
999 /* Variables in the outermost scope automatically conflict with
1000 every other variable. The only reason to want to defer them
1001 at all is that, after sorting, we can more efficiently pack
1002 small variables in the stack frame. Continue to defer at -O2. */
1003 if (toplevel && optimize < 2)
1004 return false;
1005
1006 /* Without optimization, *most* variables are allocated from the
1007 stack, which makes the quadratic problem large exactly when we
1008 want compilation to proceed as quickly as possible. On the
1009 other hand, we don't want the function's stack frame size to
1010 get completely out of hand. So we avoid adding scalars and
1011 "small" aggregates to the list at all. */
1012 if (optimize == 0 && tree_low_cst (DECL_SIZE_UNIT (var), 1) < 32)
1013 return false;
1014
1015 return true;
1016}
1017
1018/* A subroutine of expand_used_vars. Expand one variable according to
1019 its flavor. Variables to be placed on the stack are not actually
1020 expanded yet, merely recorded.
1021 When REALLY_EXPAND is false, only add stack values to be allocated.
1022 Return stack usage this variable is supposed to take.
1023*/
1024
1025static HOST_WIDE_INT
1026expand_one_var (tree var, bool toplevel, bool really_expand)
1027{
1028 if (SUPPORTS_STACK_ALIGNMENT
1029 && TREE_TYPE (var) != error_mark_node
1030 && TREE_CODE (var) == VAR_DECL)
1031 {
1032 unsigned int align;
1033
1034 /* Because we don't know if VAR will be in register or on stack,
1035 we conservatively assume it will be on stack even if VAR is
1036 eventually put into register after RA pass. For non-automatic
1037 variables, which won't be on stack, we collect alignment of
1038 type and ignore user specified alignment. */
1039 if (TREE_STATIC (var) || DECL_EXTERNAL (var))
1040 align = MINIMUM_ALIGNMENT (TREE_TYPE (var),
1041 TYPE_MODE (TREE_TYPE (var)),
1042 TYPE_ALIGN (TREE_TYPE (var)));
1043 else
1044 align = MINIMUM_ALIGNMENT (var, DECL_MODE (var), DECL_ALIGN (var));
1045
1046 if (crtl->stack_alignment_estimated < align)
1047 {
1048 /* stack_alignment_estimated shouldn't change after stack
1049 realign decision made */
1050 gcc_assert(!crtl->stack_realign_processed);
1051 crtl->stack_alignment_estimated = align;
1052 }
1053 }
1054
1055 if (TREE_CODE (var) != VAR_DECL)
1056 ;
1057 else if (DECL_EXTERNAL (var))
1058 ;
1059 else if (DECL_HAS_VALUE_EXPR_P (var))
1060 ;
1061 else if (TREE_STATIC (var))
1062 ;
1063 else if (DECL_RTL_SET_P (var))
1064 ;
1065 else if (TREE_TYPE (var) == error_mark_node)
1066 {
1067 if (really_expand)
1068 expand_one_error_var (var);
1069 }
1070 else if (DECL_HARD_REGISTER (var))
1071 {
1072 if (really_expand)
1073 expand_one_hard_reg_var (var);
1074 }
1075 else if (use_register_for_decl (var))
1076 {
1077 if (really_expand)
1078 expand_one_register_var (var);
1079 }
4b1e227d
SW
1080 else if (!host_integerp (DECL_SIZE_UNIT (var), 1))
1081 {
1082 if (really_expand)
1083 {
1084 error ("size of variable %q+D is too large", var);
1085 expand_one_error_var (var);
1086 }
1087 }
c251ad9e
SS
1088 else if (defer_stack_allocation (var, toplevel))
1089 add_stack_var (var);
1090 else
1091 {
1092 if (really_expand)
1093 expand_one_stack_var (var);
1094 return tree_low_cst (DECL_SIZE_UNIT (var), 1);
1095 }
1096 return 0;
1097}
1098
1099/* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1100 expanding variables. Those variables that can be put into registers
1101 are allocated pseudos; those that can't are put on the stack.
1102
1103 TOPLEVEL is true if this is the outermost BLOCK. */
1104
1105static void
1106expand_used_vars_for_block (tree block, bool toplevel)
1107{
1108 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1109 tree t;
1110
1111 old_sv_num = toplevel ? 0 : stack_vars_num;
1112
1113 /* Expand all variables at this level. */
1114 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1115 if (TREE_USED (t))
1116 expand_one_var (t, toplevel, true);
1117
1118 this_sv_num = stack_vars_num;
1119
1120 /* Expand all variables at containing levels. */
1121 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1122 expand_used_vars_for_block (t, false);
1123
1124 /* Since we do not track exact variable lifetimes (which is not even
1125 possible for variables whose address escapes), we mirror the block
1126 tree in the interference graph. Here we cause all variables at this
1127 level, and all sublevels, to conflict. Do make certain that a
1128 variable conflicts with itself. */
1129 if (old_sv_num < this_sv_num)
1130 {
1131 new_sv_num = stack_vars_num;
1132 resize_stack_vars_conflict (new_sv_num);
1133
1134 for (i = old_sv_num; i < new_sv_num; ++i)
1135 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1136 add_stack_var_conflict (i, j);
1137 }
1138}
1139
1140/* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1141 and clear TREE_USED on all local variables. */
1142
1143static void
1144clear_tree_used (tree block)
1145{
1146 tree t;
1147
1148 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1149 /* if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) */
1150 TREE_USED (t) = 0;
1151
1152 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1153 clear_tree_used (t);
1154}
1155
1156/* Examine TYPE and determine a bit mask of the following features. */
1157
1158#define SPCT_HAS_LARGE_CHAR_ARRAY 1
1159#define SPCT_HAS_SMALL_CHAR_ARRAY 2
1160#define SPCT_HAS_ARRAY 4
1161#define SPCT_HAS_AGGREGATE 8
1162
1163static unsigned int
1164stack_protect_classify_type (tree type)
1165{
1166 unsigned int ret = 0;
1167 tree t;
1168
1169 switch (TREE_CODE (type))
1170 {
1171 case ARRAY_TYPE:
1172 t = TYPE_MAIN_VARIANT (TREE_TYPE (type));
1173 if (t == char_type_node
1174 || t == signed_char_type_node
1175 || t == unsigned_char_type_node)
1176 {
1177 unsigned HOST_WIDE_INT max = PARAM_VALUE (PARAM_SSP_BUFFER_SIZE);
1178 unsigned HOST_WIDE_INT len;
1179
1180 if (!TYPE_SIZE_UNIT (type)
1181 || !host_integerp (TYPE_SIZE_UNIT (type), 1))
1182 len = max;
1183 else
1184 len = tree_low_cst (TYPE_SIZE_UNIT (type), 1);
1185
1186 if (len < max)
1187 ret = SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_ARRAY;
1188 else
1189 ret = SPCT_HAS_LARGE_CHAR_ARRAY | SPCT_HAS_ARRAY;
1190 }
1191 else
1192 ret = SPCT_HAS_ARRAY;
1193 break;
1194
1195 case UNION_TYPE:
1196 case QUAL_UNION_TYPE:
1197 case RECORD_TYPE:
1198 ret = SPCT_HAS_AGGREGATE;
1199 for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t))
1200 if (TREE_CODE (t) == FIELD_DECL)
1201 ret |= stack_protect_classify_type (TREE_TYPE (t));
1202 break;
1203
1204 default:
1205 break;
1206 }
1207
1208 return ret;
1209}
1210
1211/* Return nonzero if DECL should be segregated into the "vulnerable" upper
1212 part of the local stack frame. Remember if we ever return nonzero for
1213 any variable in this function. The return value is the phase number in
1214 which the variable should be allocated. */
1215
1216static int
1217stack_protect_decl_phase (tree decl)
1218{
1219 unsigned int bits = stack_protect_classify_type (TREE_TYPE (decl));
1220 int ret = 0;
1221
1222 if (bits & SPCT_HAS_SMALL_CHAR_ARRAY)
1223 has_short_buffer = true;
1224
1225 if (flag_stack_protect == 2)
1226 {
1227 if ((bits & (SPCT_HAS_SMALL_CHAR_ARRAY | SPCT_HAS_LARGE_CHAR_ARRAY))
1228 && !(bits & SPCT_HAS_AGGREGATE))
1229 ret = 1;
1230 else if (bits & SPCT_HAS_ARRAY)
1231 ret = 2;
1232 }
1233 else
1234 ret = (bits & SPCT_HAS_LARGE_CHAR_ARRAY) != 0;
1235
1236 if (ret)
1237 has_protected_decls = true;
1238
1239 return ret;
1240}
1241
1242/* Two helper routines that check for phase 1 and phase 2. These are used
1243 as callbacks for expand_stack_vars. */
1244
1245static bool
1246stack_protect_decl_phase_1 (tree decl)
1247{
1248 return stack_protect_decl_phase (decl) == 1;
1249}
1250
1251static bool
1252stack_protect_decl_phase_2 (tree decl)
1253{
1254 return stack_protect_decl_phase (decl) == 2;
1255}
1256
1257/* Ensure that variables in different stack protection phases conflict
1258 so that they are not merged and share the same stack slot. */
1259
1260static void
1261add_stack_protection_conflicts (void)
1262{
1263 size_t i, j, n = stack_vars_num;
1264 unsigned char *phase;
1265
1266 phase = XNEWVEC (unsigned char, n);
1267 for (i = 0; i < n; ++i)
1268 phase[i] = stack_protect_decl_phase (stack_vars[i].decl);
1269
1270 for (i = 0; i < n; ++i)
1271 {
1272 unsigned char ph_i = phase[i];
1273 for (j = 0; j < i; ++j)
1274 if (ph_i != phase[j])
1275 add_stack_var_conflict (i, j);
1276 }
1277
1278 XDELETEVEC (phase);
1279}
1280
1281/* Create a decl for the guard at the top of the stack frame. */
1282
1283static void
1284create_stack_guard (void)
1285{
1286 tree guard = build_decl (VAR_DECL, NULL, ptr_type_node);
1287 TREE_THIS_VOLATILE (guard) = 1;
1288 TREE_USED (guard) = 1;
1289 expand_one_stack_var (guard);
1290 crtl->stack_protect_guard = guard;
1291}
1292
1293/* A subroutine of expand_used_vars. Walk down through the BLOCK tree
1294 expanding variables. Those variables that can be put into registers
1295 are allocated pseudos; those that can't are put on the stack.
1296
1297 TOPLEVEL is true if this is the outermost BLOCK. */
1298
1299static HOST_WIDE_INT
1300account_used_vars_for_block (tree block, bool toplevel)
1301{
1302 size_t i, j, old_sv_num, this_sv_num, new_sv_num;
1303 tree t;
1304 HOST_WIDE_INT size = 0;
1305
1306 old_sv_num = toplevel ? 0 : stack_vars_num;
1307
1308 /* Expand all variables at this level. */
1309 for (t = BLOCK_VARS (block); t ; t = TREE_CHAIN (t))
1310 if (TREE_USED (t))
1311 size += expand_one_var (t, toplevel, false);
1312
1313 this_sv_num = stack_vars_num;
1314
1315 /* Expand all variables at containing levels. */
1316 for (t = BLOCK_SUBBLOCKS (block); t ; t = BLOCK_CHAIN (t))
1317 size += account_used_vars_for_block (t, false);
1318
1319 /* Since we do not track exact variable lifetimes (which is not even
1320 possible for variables whose address escapes), we mirror the block
1321 tree in the interference graph. Here we cause all variables at this
1322 level, and all sublevels, to conflict. Do make certain that a
1323 variable conflicts with itself. */
1324 if (old_sv_num < this_sv_num)
1325 {
1326 new_sv_num = stack_vars_num;
1327 resize_stack_vars_conflict (new_sv_num);
1328
1329 for (i = old_sv_num; i < new_sv_num; ++i)
1330 for (j = i < this_sv_num ? i+1 : this_sv_num; j-- > old_sv_num ;)
1331 add_stack_var_conflict (i, j);
1332 }
1333 return size;
1334}
1335
1336/* Prepare for expanding variables. */
1337static void
1338init_vars_expansion (void)
1339{
1340 tree t;
1341 /* Set TREE_USED on all variables in the local_decls. */
1342 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1343 TREE_USED (TREE_VALUE (t)) = 1;
1344
1345 /* Clear TREE_USED on all variables associated with a block scope. */
1346 clear_tree_used (DECL_INITIAL (current_function_decl));
1347
1348 /* Initialize local stack smashing state. */
1349 has_protected_decls = false;
1350 has_short_buffer = false;
1351}
1352
1353/* Free up stack variable graph data. */
1354static void
1355fini_vars_expansion (void)
1356{
1357 XDELETEVEC (stack_vars);
1358 XDELETEVEC (stack_vars_sorted);
1359 XDELETEVEC (stack_vars_conflict);
1360 stack_vars = NULL;
1361 stack_vars_alloc = stack_vars_num = 0;
1362 stack_vars_conflict = NULL;
1363 stack_vars_conflict_alloc = 0;
1364}
1365
1366/* Make a fair guess for the size of the stack frame of the current
1367 function. This doesn't have to be exact, the result is only used
1368 in the inline heuristics. So we don't want to run the full stack
1369 var packing algorithm (which is quadratic in the number of stack
1370 vars). Instead, we calculate the total size of all stack vars.
1371 This turns out to be a pretty fair estimate -- packing of stack
1372 vars doesn't happen very often. */
1373
1374HOST_WIDE_INT
1375estimated_stack_frame_size (void)
1376{
1377 HOST_WIDE_INT size = 0;
1378 size_t i;
1379 tree t, outer_block = DECL_INITIAL (current_function_decl);
1380
1381 init_vars_expansion ();
1382
1383 for (t = cfun->local_decls; t; t = TREE_CHAIN (t))
1384 {
1385 tree var = TREE_VALUE (t);
1386
1387 if (TREE_USED (var))
1388 size += expand_one_var (var, true, false);
1389 TREE_USED (var) = 1;
1390 }
1391 size += account_used_vars_for_block (outer_block, true);
1392
1393 if (stack_vars_num > 0)
1394 {
1395 /* Fake sorting the stack vars for account_stack_vars (). */
1396 stack_vars_sorted = XNEWVEC (size_t, stack_vars_num);
1397 for (i = 0; i < stack_vars_num; ++i)
1398 stack_vars_sorted[i] = i;
1399 size += account_stack_vars ();
1400 fini_vars_expansion ();
1401 }
1402
1403 return size;
1404}
1405
1406/* Expand all variables used in the function. */
1407
1408static void
1409expand_used_vars (void)
1410{
1411 tree t, next, outer_block = DECL_INITIAL (current_function_decl);
1412
1413 /* Compute the phase of the stack frame for this function. */
1414 {
1415 int align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1416 int off = STARTING_FRAME_OFFSET % align;
1417 frame_phase = off ? align - off : 0;
1418 }
1419
1420 init_vars_expansion ();
1421
1422 /* At this point all variables on the local_decls with TREE_USED
1423 set are not associated with any block scope. Lay them out. */
1424 t = cfun->local_decls;
1425 cfun->local_decls = NULL_TREE;
1426 for (; t; t = next)
1427 {
1428 tree var = TREE_VALUE (t);
1429 bool expand_now = false;
1430
1431 next = TREE_CHAIN (t);
1432
1433 /* We didn't set a block for static or extern because it's hard
1434 to tell the difference between a global variable (re)declared
1435 in a local scope, and one that's really declared there to
1436 begin with. And it doesn't really matter much, since we're
1437 not giving them stack space. Expand them now. */
1438 if (TREE_STATIC (var) || DECL_EXTERNAL (var))
1439 expand_now = true;
1440
1441 /* Any variable that could have been hoisted into an SSA_NAME
1442 will have been propagated anywhere the optimizers chose,
1443 i.e. not confined to their original block. Allocate them
1444 as if they were defined in the outermost scope. */
1445 else if (is_gimple_reg (var))
1446 expand_now = true;
1447
1448 /* If the variable is not associated with any block, then it
1449 was created by the optimizers, and could be live anywhere
1450 in the function. */
1451 else if (TREE_USED (var))
1452 expand_now = true;
1453
1454 /* Finally, mark all variables on the list as used. We'll use
1455 this in a moment when we expand those associated with scopes. */
1456 TREE_USED (var) = 1;
1457
1458 if (expand_now)
1459 {
1460 expand_one_var (var, true, true);
1461 if (DECL_ARTIFICIAL (var) && !DECL_IGNORED_P (var))
1462 {
1463 rtx rtl = DECL_RTL_IF_SET (var);
1464
1465 /* Keep artificial non-ignored vars in cfun->local_decls
1466 chain until instantiate_decls. */
1467 if (rtl && (MEM_P (rtl) || GET_CODE (rtl) == CONCAT))
1468 {
1469 TREE_CHAIN (t) = cfun->local_decls;
1470 cfun->local_decls = t;
1471 continue;
1472 }
1473 }
1474 }
1475
1476 ggc_free (t);
1477 }
1478
1479 /* At this point, all variables within the block tree with TREE_USED
1480 set are actually used by the optimized function. Lay them out. */
1481 expand_used_vars_for_block (outer_block, true);
1482
1483 if (stack_vars_num > 0)
1484 {
1485 /* Due to the way alias sets work, no variables with non-conflicting
1486 alias sets may be assigned the same address. Add conflicts to
1487 reflect this. */
1488 add_alias_set_conflicts ();
1489
1490 /* If stack protection is enabled, we don't share space between
1491 vulnerable data and non-vulnerable data. */
1492 if (flag_stack_protect)
1493 add_stack_protection_conflicts ();
1494
1495 /* Now that we have collected all stack variables, and have computed a
1496 minimal interference graph, attempt to save some stack space. */
1497 partition_stack_vars ();
1498 if (dump_file)
1499 dump_stack_var_partition ();
1500 }
1501
1502 /* There are several conditions under which we should create a
1503 stack guard: protect-all, alloca used, protected decls present. */
1504 if (flag_stack_protect == 2
1505 || (flag_stack_protect
1506 && (cfun->calls_alloca || has_protected_decls)))
1507 create_stack_guard ();
1508
1509 /* Assign rtl to each variable based on these partitions. */
1510 if (stack_vars_num > 0)
1511 {
1512 /* Reorder decls to be protected by iterating over the variables
1513 array multiple times, and allocating out of each phase in turn. */
1514 /* ??? We could probably integrate this into the qsort we did
1515 earlier, such that we naturally see these variables first,
1516 and thus naturally allocate things in the right order. */
1517 if (has_protected_decls)
1518 {
1519 /* Phase 1 contains only character arrays. */
1520 expand_stack_vars (stack_protect_decl_phase_1);
1521
1522 /* Phase 2 contains other kinds of arrays. */
1523 if (flag_stack_protect == 2)
1524 expand_stack_vars (stack_protect_decl_phase_2);
1525 }
1526
1527 expand_stack_vars (NULL);
1528
1529 fini_vars_expansion ();
1530 }
1531
1532 /* If the target requires that FRAME_OFFSET be aligned, do it. */
1533 if (STACK_ALIGNMENT_NEEDED)
1534 {
1535 HOST_WIDE_INT align = PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT;
1536 if (!FRAME_GROWS_DOWNWARD)
1537 frame_offset += align - 1;
1538 frame_offset &= -align;
1539 }
1540}
1541
1542
1543/* If we need to produce a detailed dump, print the tree representation
1544 for STMT to the dump file. SINCE is the last RTX after which the RTL
1545 generated for STMT should have been appended. */
1546
1547static void
1548maybe_dump_rtl_for_gimple_stmt (gimple stmt, rtx since)
1549{
1550 if (dump_file && (dump_flags & TDF_DETAILS))
1551 {
1552 fprintf (dump_file, "\n;; ");
1553 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1554 fprintf (dump_file, "\n");
1555
1556 print_rtl (dump_file, since ? NEXT_INSN (since) : since);
1557 }
1558}
1559
1560/* Maps the blocks that do not contain tree labels to rtx labels. */
1561
1562static struct pointer_map_t *lab_rtx_for_bb;
1563
1564/* Returns the label_rtx expression for a label starting basic block BB. */
1565
1566static rtx
1567label_rtx_for_bb (basic_block bb ATTRIBUTE_UNUSED)
1568{
1569 gimple_stmt_iterator gsi;
1570 tree lab;
1571 gimple lab_stmt;
1572 void **elt;
1573
1574 if (bb->flags & BB_RTL)
1575 return block_label (bb);
1576
1577 elt = pointer_map_contains (lab_rtx_for_bb, bb);
1578 if (elt)
1579 return (rtx) *elt;
1580
1581 /* Find the tree label if it is present. */
1582
1583 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1584 {
1585 lab_stmt = gsi_stmt (gsi);
1586 if (gimple_code (lab_stmt) != GIMPLE_LABEL)
1587 break;
1588
1589 lab = gimple_label_label (lab_stmt);
1590 if (DECL_NONLOCAL (lab))
1591 break;
1592
1593 return label_rtx (lab);
1594 }
1595
1596 elt = pointer_map_insert (lab_rtx_for_bb, bb);
1597 *elt = gen_label_rtx ();
1598 return (rtx) *elt;
1599}
1600
1601
1602/* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_COND.
1603 Returns a new basic block if we've terminated the current basic
1604 block and created a new one. */
1605
1606static basic_block
1607expand_gimple_cond (basic_block bb, gimple stmt)
1608{
1609 basic_block new_bb, dest;
1610 edge new_edge;
1611 edge true_edge;
1612 edge false_edge;
1613 tree pred = gimple_cond_pred_to_tree (stmt);
1614 rtx last2, last;
1615
1616 last2 = last = get_last_insn ();
1617
1618 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1619 if (gimple_has_location (stmt))
1620 {
1621 set_curr_insn_source_location (gimple_location (stmt));
1622 set_curr_insn_block (gimple_block (stmt));
1623 }
1624
1625 /* These flags have no purpose in RTL land. */
1626 true_edge->flags &= ~EDGE_TRUE_VALUE;
1627 false_edge->flags &= ~EDGE_FALSE_VALUE;
1628
1629 /* We can either have a pure conditional jump with one fallthru edge or
1630 two-way jump that needs to be decomposed into two basic blocks. */
1631 if (false_edge->dest == bb->next_bb)
1632 {
4b1e227d
SW
1633 jumpif (pred, label_rtx_for_bb (true_edge->dest),
1634 true_edge->probability);
c251ad9e
SS
1635 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1636 if (true_edge->goto_locus)
1637 {
1638 set_curr_insn_source_location (true_edge->goto_locus);
1639 set_curr_insn_block (true_edge->goto_block);
1640 true_edge->goto_locus = curr_insn_locator ();
1641 }
1642 true_edge->goto_block = NULL;
1643 false_edge->flags |= EDGE_FALLTHRU;
1644 ggc_free (pred);
1645 return NULL;
1646 }
1647 if (true_edge->dest == bb->next_bb)
1648 {
4b1e227d
SW
1649 jumpifnot (pred, label_rtx_for_bb (false_edge->dest),
1650 false_edge->probability);
c251ad9e
SS
1651 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1652 if (false_edge->goto_locus)
1653 {
1654 set_curr_insn_source_location (false_edge->goto_locus);
1655 set_curr_insn_block (false_edge->goto_block);
1656 false_edge->goto_locus = curr_insn_locator ();
1657 }
1658 false_edge->goto_block = NULL;
1659 true_edge->flags |= EDGE_FALLTHRU;
1660 ggc_free (pred);
1661 return NULL;
1662 }
1663
4b1e227d 1664 jumpif (pred, label_rtx_for_bb (true_edge->dest), true_edge->probability);
c251ad9e
SS
1665 last = get_last_insn ();
1666 if (false_edge->goto_locus)
1667 {
1668 set_curr_insn_source_location (false_edge->goto_locus);
1669 set_curr_insn_block (false_edge->goto_block);
1670 false_edge->goto_locus = curr_insn_locator ();
1671 }
1672 false_edge->goto_block = NULL;
1673 emit_jump (label_rtx_for_bb (false_edge->dest));
1674
1675 BB_END (bb) = last;
1676 if (BARRIER_P (BB_END (bb)))
1677 BB_END (bb) = PREV_INSN (BB_END (bb));
1678 update_bb_for_insn (bb);
1679
1680 new_bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
1681 dest = false_edge->dest;
1682 redirect_edge_succ (false_edge, new_bb);
1683 false_edge->flags |= EDGE_FALLTHRU;
1684 new_bb->count = false_edge->count;
1685 new_bb->frequency = EDGE_FREQUENCY (false_edge);
1686 new_edge = make_edge (new_bb, dest, 0);
1687 new_edge->probability = REG_BR_PROB_BASE;
1688 new_edge->count = new_bb->count;
1689 if (BARRIER_P (BB_END (new_bb)))
1690 BB_END (new_bb) = PREV_INSN (BB_END (new_bb));
1691 update_bb_for_insn (new_bb);
1692
1693 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1694
1695 if (true_edge->goto_locus)
1696 {
1697 set_curr_insn_source_location (true_edge->goto_locus);
1698 set_curr_insn_block (true_edge->goto_block);
1699 true_edge->goto_locus = curr_insn_locator ();
1700 }
1701 true_edge->goto_block = NULL;
1702
1703 ggc_free (pred);
1704 return new_bb;
1705}
1706
1707/* A subroutine of expand_gimple_basic_block. Expand one GIMPLE_CALL
1708 that has CALL_EXPR_TAILCALL set. Returns non-null if we actually
1709 generated a tail call (something that might be denied by the ABI
1710 rules governing the call; see calls.c).
1711
1712 Sets CAN_FALLTHRU if we generated a *conditional* tail call, and
1713 can still reach the rest of BB. The case here is __builtin_sqrt,
1714 where the NaN result goes through the external function (with a
1715 tailcall) and the normal result happens via a sqrt instruction. */
1716
1717static basic_block
1718expand_gimple_tailcall (basic_block bb, gimple stmt, bool *can_fallthru)
1719{
1720 rtx last2, last;
1721 edge e;
1722 edge_iterator ei;
1723 int probability;
1724 gcov_type count;
1725 tree stmt_tree = gimple_to_tree (stmt);
1726
1727 last2 = last = get_last_insn ();
1728
1729 expand_expr_stmt (stmt_tree);
1730
1731 release_stmt_tree (stmt, stmt_tree);
1732
1733 for (last = NEXT_INSN (last); last; last = NEXT_INSN (last))
1734 if (CALL_P (last) && SIBLING_CALL_P (last))
1735 goto found;
1736
1737 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1738
1739 *can_fallthru = true;
1740 return NULL;
1741
1742 found:
1743 /* ??? Wouldn't it be better to just reset any pending stack adjust?
1744 Any instructions emitted here are about to be deleted. */
1745 do_pending_stack_adjust ();
1746
1747 /* Remove any non-eh, non-abnormal edges that don't go to exit. */
1748 /* ??? I.e. the fallthrough edge. HOWEVER! If there were to be
1749 EH or abnormal edges, we shouldn't have created a tail call in
1750 the first place. So it seems to me we should just be removing
1751 all edges here, or redirecting the existing fallthru edge to
1752 the exit block. */
1753
1754 probability = 0;
1755 count = 0;
1756
1757 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1758 {
1759 if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
1760 {
1761 if (e->dest != EXIT_BLOCK_PTR)
1762 {
1763 e->dest->count -= e->count;
1764 e->dest->frequency -= EDGE_FREQUENCY (e);
1765 if (e->dest->count < 0)
1766 e->dest->count = 0;
1767 if (e->dest->frequency < 0)
1768 e->dest->frequency = 0;
1769 }
1770 count += e->count;
1771 probability += e->probability;
1772 remove_edge (e);
1773 }
1774 else
1775 ei_next (&ei);
1776 }
1777
1778 /* This is somewhat ugly: the call_expr expander often emits instructions
1779 after the sibcall (to perform the function return). These confuse the
1780 find_many_sub_basic_blocks code, so we need to get rid of these. */
1781 last = NEXT_INSN (last);
1782 gcc_assert (BARRIER_P (last));
1783
1784 *can_fallthru = false;
1785 while (NEXT_INSN (last))
1786 {
1787 /* For instance an sqrt builtin expander expands if with
1788 sibcall in the then and label for `else`. */
1789 if (LABEL_P (NEXT_INSN (last)))
1790 {
1791 *can_fallthru = true;
1792 break;
1793 }
1794 delete_insn (NEXT_INSN (last));
1795 }
1796
1797 e = make_edge (bb, EXIT_BLOCK_PTR, EDGE_ABNORMAL | EDGE_SIBCALL);
1798 e->probability += probability;
1799 e->count += count;
1800 BB_END (bb) = last;
1801 update_bb_for_insn (bb);
1802
1803 if (NEXT_INSN (last))
1804 {
1805 bb = create_basic_block (NEXT_INSN (last), get_last_insn (), bb);
1806
1807 last = BB_END (bb);
1808 if (BARRIER_P (last))
1809 BB_END (bb) = PREV_INSN (last);
1810 }
1811
1812 maybe_dump_rtl_for_gimple_stmt (stmt, last2);
1813
1814 return bb;
1815}
1816
1817/* Expand basic block BB from GIMPLE trees to RTL. */
1818
1819static basic_block
1820expand_gimple_basic_block (basic_block bb)
1821{
1822 gimple_stmt_iterator gsi;
1823 gimple_seq stmts;
1824 gimple stmt = NULL;
1825 rtx note, last;
1826 edge e;
1827 edge_iterator ei;
1828 void **elt;
1829
1830 if (dump_file)
1831 fprintf (dump_file, "\n;; Generating RTL for gimple basic block %d\n",
1832 bb->index);
1833
1834 /* Note that since we are now transitioning from GIMPLE to RTL, we
1835 cannot use the gsi_*_bb() routines because they expect the basic
1836 block to be in GIMPLE, instead of RTL. Therefore, we need to
1837 access the BB sequence directly. */
1838 stmts = bb_seq (bb);
1839 bb->il.gimple = NULL;
1840 rtl_profile_for_bb (bb);
1841 init_rtl_bb_info (bb);
1842 bb->flags |= BB_RTL;
1843
1844 /* Remove the RETURN_EXPR if we may fall though to the exit
1845 instead. */
1846 gsi = gsi_last (stmts);
1847 if (!gsi_end_p (gsi)
1848 && gimple_code (gsi_stmt (gsi)) == GIMPLE_RETURN)
1849 {
1850 gimple ret_stmt = gsi_stmt (gsi);
1851
1852 gcc_assert (single_succ_p (bb));
1853 gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
1854
1855 if (bb->next_bb == EXIT_BLOCK_PTR
1856 && !gimple_return_retval (ret_stmt))
1857 {
1858 gsi_remove (&gsi, false);
1859 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
1860 }
1861 }
1862
1863 gsi = gsi_start (stmts);
1864 if (!gsi_end_p (gsi))
1865 {
1866 stmt = gsi_stmt (gsi);
1867 if (gimple_code (stmt) != GIMPLE_LABEL)
1868 stmt = NULL;
1869 }
1870
1871 elt = pointer_map_contains (lab_rtx_for_bb, bb);
1872
1873 if (stmt || elt)
1874 {
1875 last = get_last_insn ();
1876
1877 if (stmt)
1878 {
1879 tree stmt_tree = gimple_to_tree (stmt);
1880 expand_expr_stmt (stmt_tree);
1881 release_stmt_tree (stmt, stmt_tree);
1882 gsi_next (&gsi);
1883 }
1884
1885 if (elt)
1886 emit_label ((rtx) *elt);
1887
1888 /* Java emits line number notes in the top of labels.
1889 ??? Make this go away once line number notes are obsoleted. */
1890 BB_HEAD (bb) = NEXT_INSN (last);
1891 if (NOTE_P (BB_HEAD (bb)))
1892 BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
1893 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
1894
1895 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1896 }
1897 else
1898 note = BB_HEAD (bb) = emit_note (NOTE_INSN_BASIC_BLOCK);
1899
1900 NOTE_BASIC_BLOCK (note) = bb;
1901
1902 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
1903 {
1904 /* Clear EDGE_EXECUTABLE. This flag is never used in the backend. */
1905 e->flags &= ~EDGE_EXECUTABLE;
1906
1907 /* At the moment not all abnormal edges match the RTL representation.
1908 It is safe to remove them here as find_many_sub_basic_blocks will
1909 rediscover them. In the future we should get this fixed properly. */
1910 if (e->flags & EDGE_ABNORMAL)
1911 remove_edge (e);
1912 else
1913 ei_next (&ei);
1914 }
1915
1916 for (; !gsi_end_p (gsi); gsi_next (&gsi))
1917 {
1918 gimple stmt = gsi_stmt (gsi);
1919 basic_block new_bb;
1920
1921 /* Expand this statement, then evaluate the resulting RTL and
1922 fixup the CFG accordingly. */
1923 if (gimple_code (stmt) == GIMPLE_COND)
1924 {
1925 new_bb = expand_gimple_cond (bb, stmt);
1926 if (new_bb)
1927 return new_bb;
1928 }
1929 else
1930 {
1931 if (is_gimple_call (stmt) && gimple_call_tail_p (stmt))
1932 {
1933 bool can_fallthru;
1934 new_bb = expand_gimple_tailcall (bb, stmt, &can_fallthru);
1935 if (new_bb)
1936 {
1937 if (can_fallthru)
1938 bb = new_bb;
1939 else
1940 return new_bb;
1941 }
1942 }
1943 else if (gimple_code (stmt) != GIMPLE_CHANGE_DYNAMIC_TYPE)
1944 {
1945 tree stmt_tree = gimple_to_tree (stmt);
1946 last = get_last_insn ();
1947 expand_expr_stmt (stmt_tree);
1948 maybe_dump_rtl_for_gimple_stmt (stmt, last);
1949 release_stmt_tree (stmt, stmt_tree);
1950 }
1951 }
1952 }
1953
1954 /* Expand implicit goto and convert goto_locus. */
1955 FOR_EACH_EDGE (e, ei, bb->succs)
1956 {
1957 if (e->goto_locus && e->goto_block)
1958 {
1959 set_curr_insn_source_location (e->goto_locus);
1960 set_curr_insn_block (e->goto_block);
1961 e->goto_locus = curr_insn_locator ();
1962 }
1963 e->goto_block = NULL;
1964 if ((e->flags & EDGE_FALLTHRU) && e->dest != bb->next_bb)
1965 {
1966 emit_jump (label_rtx_for_bb (e->dest));
1967 e->flags &= ~EDGE_FALLTHRU;
1968 }
1969 }
1970
1971 do_pending_stack_adjust ();
1972
1973 /* Find the block tail. The last insn in the block is the insn
1974 before a barrier and/or table jump insn. */
1975 last = get_last_insn ();
1976 if (BARRIER_P (last))
1977 last = PREV_INSN (last);
1978 if (JUMP_TABLE_DATA_P (last))
1979 last = PREV_INSN (PREV_INSN (last));
1980 BB_END (bb) = last;
1981
1982 update_bb_for_insn (bb);
1983
1984 return bb;
1985}
1986
1987
1988/* Create a basic block for initialization code. */
1989
1990static basic_block
1991construct_init_block (void)
1992{
1993 basic_block init_block, first_block;
1994 edge e = NULL;
1995 int flags;
1996
1997 /* Multiple entry points not supported yet. */
1998 gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR->succs) == 1);
1999 init_rtl_bb_info (ENTRY_BLOCK_PTR);
2000 init_rtl_bb_info (EXIT_BLOCK_PTR);
2001 ENTRY_BLOCK_PTR->flags |= BB_RTL;
2002 EXIT_BLOCK_PTR->flags |= BB_RTL;
2003
2004 e = EDGE_SUCC (ENTRY_BLOCK_PTR, 0);
2005
2006 /* When entry edge points to first basic block, we don't need jump,
2007 otherwise we have to jump into proper target. */
2008 if (e && e->dest != ENTRY_BLOCK_PTR->next_bb)
2009 {
2010 tree label = gimple_block_label (e->dest);
2011
2012 emit_jump (label_rtx (label));
2013 flags = 0;
2014 }
2015 else
2016 flags = EDGE_FALLTHRU;
2017
2018 init_block = create_basic_block (NEXT_INSN (get_insns ()),
2019 get_last_insn (),
2020 ENTRY_BLOCK_PTR);
2021 init_block->frequency = ENTRY_BLOCK_PTR->frequency;
2022 init_block->count = ENTRY_BLOCK_PTR->count;
2023 if (e)
2024 {
2025 first_block = e->dest;
2026 redirect_edge_succ (e, init_block);
2027 e = make_edge (init_block, first_block, flags);
2028 }
2029 else
2030 e = make_edge (init_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
2031 e->probability = REG_BR_PROB_BASE;
2032 e->count = ENTRY_BLOCK_PTR->count;
2033
2034 update_bb_for_insn (init_block);
2035 return init_block;
2036}
2037
2038/* For each lexical block, set BLOCK_NUMBER to the depth at which it is
2039 found in the block tree. */
2040
2041static void
2042set_block_levels (tree block, int level)
2043{
2044 while (block)
2045 {
2046 BLOCK_NUMBER (block) = level;
2047 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
2048 block = BLOCK_CHAIN (block);
2049 }
2050}
2051
2052/* Create a block containing landing pads and similar stuff. */
2053
2054static void
2055construct_exit_block (void)
2056{
2057 rtx head = get_last_insn ();
2058 rtx end;
2059 basic_block exit_block;
2060 edge e, e2;
2061 unsigned ix;
2062 edge_iterator ei;
2063 rtx orig_end = BB_END (EXIT_BLOCK_PTR->prev_bb);
2064
2065 rtl_profile_for_bb (EXIT_BLOCK_PTR);
2066
2067 /* Make sure the locus is set to the end of the function, so that
2068 epilogue line numbers and warnings are set properly. */
2069 if (cfun->function_end_locus != UNKNOWN_LOCATION)
2070 input_location = cfun->function_end_locus;
2071
2072 /* The following insns belong to the top scope. */
2073 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2074
2075 /* Generate rtl for function exit. */
2076 expand_function_end ();
2077
2078 end = get_last_insn ();
2079 if (head == end)
2080 return;
2081 /* While emitting the function end we could move end of the last basic block.
2082 */
2083 BB_END (EXIT_BLOCK_PTR->prev_bb) = orig_end;
2084 while (NEXT_INSN (head) && NOTE_P (NEXT_INSN (head)))
2085 head = NEXT_INSN (head);
2086 exit_block = create_basic_block (NEXT_INSN (head), end,
2087 EXIT_BLOCK_PTR->prev_bb);
2088 exit_block->frequency = EXIT_BLOCK_PTR->frequency;
2089 exit_block->count = EXIT_BLOCK_PTR->count;
2090
2091 ix = 0;
2092 while (ix < EDGE_COUNT (EXIT_BLOCK_PTR->preds))
2093 {
2094 e = EDGE_PRED (EXIT_BLOCK_PTR, ix);
2095 if (!(e->flags & EDGE_ABNORMAL))
2096 redirect_edge_succ (e, exit_block);
2097 else
2098 ix++;
2099 }
2100
2101 e = make_edge (exit_block, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
2102 e->probability = REG_BR_PROB_BASE;
2103 e->count = EXIT_BLOCK_PTR->count;
2104 FOR_EACH_EDGE (e2, ei, EXIT_BLOCK_PTR->preds)
2105 if (e2 != e)
2106 {
2107 e->count -= e2->count;
2108 exit_block->count -= e2->count;
2109 exit_block->frequency -= EDGE_FREQUENCY (e2);
2110 }
2111 if (e->count < 0)
2112 e->count = 0;
2113 if (exit_block->count < 0)
2114 exit_block->count = 0;
2115 if (exit_block->frequency < 0)
2116 exit_block->frequency = 0;
2117 update_bb_for_insn (exit_block);
2118}
2119
2120/* Helper function for discover_nonconstant_array_refs.
2121 Look for ARRAY_REF nodes with non-constant indexes and mark them
2122 addressable. */
2123
2124static tree
2125discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
2126 void *data ATTRIBUTE_UNUSED)
2127{
2128 tree t = *tp;
2129
2130 if (IS_TYPE_OR_DECL_P (t))
2131 *walk_subtrees = 0;
2132 else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2133 {
2134 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2135 && is_gimple_min_invariant (TREE_OPERAND (t, 1))
2136 && (!TREE_OPERAND (t, 2)
2137 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2138 || (TREE_CODE (t) == COMPONENT_REF
2139 && (!TREE_OPERAND (t,2)
2140 || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
2141 || TREE_CODE (t) == BIT_FIELD_REF
2142 || TREE_CODE (t) == REALPART_EXPR
2143 || TREE_CODE (t) == IMAGPART_EXPR
2144 || TREE_CODE (t) == VIEW_CONVERT_EXPR
2145 || CONVERT_EXPR_P (t))
2146 t = TREE_OPERAND (t, 0);
2147
2148 if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
2149 {
2150 t = get_base_address (t);
2151 if (t && DECL_P (t))
2152 TREE_ADDRESSABLE (t) = 1;
2153 }
2154
2155 *walk_subtrees = 0;
2156 }
2157
2158 return NULL_TREE;
2159}
2160
2161/* RTL expansion is not able to compile array references with variable
2162 offsets for arrays stored in single register. Discover such
2163 expressions and mark variables as addressable to avoid this
2164 scenario. */
2165
2166static void
2167discover_nonconstant_array_refs (void)
2168{
2169 basic_block bb;
2170 gimple_stmt_iterator gsi;
2171
2172 FOR_EACH_BB (bb)
2173 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2174 {
2175 gimple stmt = gsi_stmt (gsi);
2176 walk_gimple_op (stmt, discover_nonconstant_array_refs_r, NULL);
2177 }
2178}
2179
2180/* This function sets crtl->args.internal_arg_pointer to a virtual
2181 register if DRAP is needed. Local register allocator will replace
2182 virtual_incoming_args_rtx with the virtual register. */
2183
2184static void
2185expand_stack_alignment (void)
2186{
2187 rtx drap_rtx;
2188 unsigned int preferred_stack_boundary;
2189
2190 if (! SUPPORTS_STACK_ALIGNMENT)
2191 return;
2192
2193 if (cfun->calls_alloca
2194 || cfun->has_nonlocal_label
2195 || crtl->has_nonlocal_goto)
2196 crtl->need_drap = true;
2197
2198 gcc_assert (crtl->stack_alignment_needed
2199 <= crtl->stack_alignment_estimated);
2200
2201 /* Update crtl->stack_alignment_estimated and use it later to align
2202 stack. We check PREFERRED_STACK_BOUNDARY if there may be non-call
2203 exceptions since callgraph doesn't collect incoming stack alignment
2204 in this case. */
2205 if (flag_non_call_exceptions
2206 && PREFERRED_STACK_BOUNDARY > crtl->preferred_stack_boundary)
2207 preferred_stack_boundary = PREFERRED_STACK_BOUNDARY;
2208 else
2209 preferred_stack_boundary = crtl->preferred_stack_boundary;
2210 if (preferred_stack_boundary > crtl->stack_alignment_estimated)
2211 crtl->stack_alignment_estimated = preferred_stack_boundary;
2212 if (preferred_stack_boundary > crtl->stack_alignment_needed)
2213 crtl->stack_alignment_needed = preferred_stack_boundary;
2214
2215 crtl->stack_realign_needed
2216 = INCOMING_STACK_BOUNDARY < crtl->stack_alignment_estimated;
2217 crtl->stack_realign_tried = crtl->stack_realign_needed;
2218
2219 crtl->stack_realign_processed = true;
2220
2221 /* Target has to redefine TARGET_GET_DRAP_RTX to support stack
2222 alignment. */
2223 gcc_assert (targetm.calls.get_drap_rtx != NULL);
2224 drap_rtx = targetm.calls.get_drap_rtx ();
2225
2226 /* stack_realign_drap and drap_rtx must match. */
2227 gcc_assert ((stack_realign_drap != 0) == (drap_rtx != NULL));
2228
2229 /* Do nothing if NULL is returned, which means DRAP is not needed. */
2230 if (NULL != drap_rtx)
2231 {
2232 crtl->args.internal_arg_pointer = drap_rtx;
2233
2234 /* Call fixup_tail_calls to clean up REG_EQUIV note if DRAP is
2235 needed. */
2236 fixup_tail_calls ();
2237 }
2238}
2239
2240/* Translate the intermediate representation contained in the CFG
2241 from GIMPLE trees to RTL.
2242
2243 We do conversion per basic block and preserve/update the tree CFG.
2244 This implies we have to do some magic as the CFG can simultaneously
2245 consist of basic blocks containing RTL and GIMPLE trees. This can
2246 confuse the CFG hooks, so be careful to not manipulate CFG during
2247 the expansion. */
2248
2249static unsigned int
2250gimple_expand_cfg (void)
2251{
2252 basic_block bb, init_block;
2253 sbitmap blocks;
2254 edge_iterator ei;
2255 edge e;
2256
2257 /* Some backends want to know that we are expanding to RTL. */
2258 currently_expanding_to_rtl = 1;
2259
2260 rtl_profile_for_bb (ENTRY_BLOCK_PTR);
2261
2262 insn_locators_alloc ();
2263 if (!DECL_BUILT_IN (current_function_decl))
2264 {
2265 /* Eventually, all FEs should explicitly set function_start_locus. */
2266 if (cfun->function_start_locus == UNKNOWN_LOCATION)
2267 set_curr_insn_source_location
2268 (DECL_SOURCE_LOCATION (current_function_decl));
2269 else
2270 set_curr_insn_source_location (cfun->function_start_locus);
2271 }
2272 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2273 prologue_locator = curr_insn_locator ();
2274
2275 /* Make sure first insn is a note even if we don't want linenums.
2276 This makes sure the first insn will never be deleted.
2277 Also, final expects a note to appear there. */
2278 emit_note (NOTE_INSN_DELETED);
2279
2280 /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE. */
2281 discover_nonconstant_array_refs ();
2282
2283 targetm.expand_to_rtl_hook ();
2284 crtl->stack_alignment_needed = STACK_BOUNDARY;
2285 crtl->max_used_stack_slot_alignment = STACK_BOUNDARY;
2286 crtl->stack_alignment_estimated = STACK_BOUNDARY;
2287 crtl->preferred_stack_boundary = STACK_BOUNDARY;
2288 cfun->cfg->max_jumptable_ents = 0;
2289
2290
2291 /* Expand the variables recorded during gimple lowering. */
2292 expand_used_vars ();
2293
2294 /* Honor stack protection warnings. */
2295 if (warn_stack_protect)
2296 {
2297 if (cfun->calls_alloca)
2298 warning (OPT_Wstack_protector,
2299 "not protecting local variables: variable length buffer");
2300 if (has_short_buffer && !crtl->stack_protect_guard)
2301 warning (OPT_Wstack_protector,
2302 "not protecting function: no buffer at least %d bytes long",
2303 (int) PARAM_VALUE (PARAM_SSP_BUFFER_SIZE));
2304 }
2305
2306 /* Set up parameters and prepare for return, for the function. */
2307 expand_function_start (current_function_decl);
2308
2309 /* If this function is `main', emit a call to `__main'
2310 to run global initializers, etc. */
2311 if (DECL_NAME (current_function_decl)
2312 && MAIN_NAME_P (DECL_NAME (current_function_decl))
2313 && DECL_FILE_SCOPE_P (current_function_decl))
2314 expand_main_function ();
2315
2316 /* Initialize the stack_protect_guard field. This must happen after the
2317 call to __main (if any) so that the external decl is initialized. */
2318 if (crtl->stack_protect_guard)
2319 stack_protect_prologue ();
2320
2321 /* Update stack boundary if needed. */
2322 if (SUPPORTS_STACK_ALIGNMENT)
2323 {
2324 /* Call update_stack_boundary here to update incoming stack
2325 boundary before TARGET_FUNCTION_OK_FOR_SIBCALL is called.
2326 TARGET_FUNCTION_OK_FOR_SIBCALL needs to know the accurate
2327 incoming stack alignment to check if it is OK to perform
2328 sibcall optimization since sibcall optimization will only
2329 align the outgoing stack to incoming stack boundary. */
2330 if (targetm.calls.update_stack_boundary)
2331 targetm.calls.update_stack_boundary ();
2332
2333 /* The incoming stack frame has to be aligned at least at
2334 parm_stack_boundary. */
2335 gcc_assert (crtl->parm_stack_boundary <= INCOMING_STACK_BOUNDARY);
2336 }
2337
2338 /* Register rtl specific functions for cfg. */
2339 rtl_register_cfg_hooks ();
2340
2341 init_block = construct_init_block ();
2342
2343 /* Clear EDGE_EXECUTABLE on the entry edge(s). It is cleaned from the
2344 remaining edges in expand_gimple_basic_block. */
2345 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2346 e->flags &= ~EDGE_EXECUTABLE;
2347
2348 lab_rtx_for_bb = pointer_map_create ();
2349 FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
2350 bb = expand_gimple_basic_block (bb);
2351
2352 /* Expansion is used by optimization passes too, set maybe_hot_insn_p
2353 conservatively to true until they are all profile aware. */
2354 pointer_map_destroy (lab_rtx_for_bb);
2355 free_histograms ();
2356
2357 construct_exit_block ();
2358 set_curr_insn_block (DECL_INITIAL (current_function_decl));
2359 insn_locators_finalize ();
2360
2361 /* We're done expanding trees to RTL. */
2362 currently_expanding_to_rtl = 0;
2363
2364 /* Convert tree EH labels to RTL EH labels and zap the tree EH table. */
2365 convert_from_eh_region_ranges ();
2366 set_eh_throw_stmt_table (cfun, NULL);
2367
2368 rebuild_jump_labels (get_insns ());
2369 find_exception_handler_labels ();
2370
2371 blocks = sbitmap_alloc (last_basic_block);
2372 sbitmap_ones (blocks);
2373 find_many_sub_basic_blocks (blocks);
2374 purge_all_dead_edges ();
2375 sbitmap_free (blocks);
2376
2377 compact_blocks ();
2378
2379 expand_stack_alignment ();
2380
2381#ifdef ENABLE_CHECKING
2382 verify_flow_info ();
2383#endif
2384
2385 /* There's no need to defer outputting this function any more; we
2386 know we want to output it. */
2387 DECL_DEFER_OUTPUT (current_function_decl) = 0;
2388
2389 /* Now that we're done expanding trees to RTL, we shouldn't have any
2390 more CONCATs anywhere. */
2391 generating_concat_p = 0;
2392
2393 if (dump_file)
2394 {
2395 fprintf (dump_file,
2396 "\n\n;;\n;; Full RTL generated for this function:\n;;\n");
2397 /* And the pass manager will dump RTL for us. */
2398 }
2399
2400 /* If we're emitting a nested function, make sure its parent gets
2401 emitted as well. Doing otherwise confuses debug info. */
2402 {
2403 tree parent;
2404 for (parent = DECL_CONTEXT (current_function_decl);
2405 parent != NULL_TREE;
2406 parent = get_containing_scope (parent))
2407 if (TREE_CODE (parent) == FUNCTION_DECL)
2408 TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (parent)) = 1;
2409 }
2410
2411 /* We are now committed to emitting code for this function. Do any
2412 preparation, such as emitting abstract debug info for the inline
2413 before it gets mangled by optimization. */
2414 if (cgraph_function_possibly_inlined_p (current_function_decl))
2415 (*debug_hooks->outlining_inline_function) (current_function_decl);
2416
2417 TREE_ASM_WRITTEN (current_function_decl) = 1;
2418
2419 /* After expanding, the return labels are no longer needed. */
2420 return_label = NULL;
2421 naked_return_label = NULL;
2422 /* Tag the blocks with a depth number so that change_scope can find
2423 the common parent easily. */
2424 set_block_levels (DECL_INITIAL (cfun->decl), 0);
2425 default_rtl_profile ();
2426 return 0;
2427}
2428
2429struct rtl_opt_pass pass_expand =
2430{
2431 {
2432 RTL_PASS,
2433 "expand", /* name */
2434 NULL, /* gate */
2435 gimple_expand_cfg, /* execute */
2436 NULL, /* sub */
2437 NULL, /* next */
2438 0, /* static_pass_number */
2439 TV_EXPAND, /* tv_id */
2440 /* ??? If TER is enabled, we actually receive GENERIC. */
2441 PROP_gimple_leh | PROP_cfg, /* properties_required */
2442 PROP_rtl, /* properties_provided */
2443 PROP_trees, /* properties_destroyed */
2444 0, /* todo_flags_start */
2445 TODO_dump_func, /* todo_flags_finish */
2446 }
2447};