Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / cfgexpand.c
1 /* A pass for lowering trees to RTL.
2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
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)
10 any later version.
11
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.
16
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/>.  */
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
50 tree
51 gimple_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
78 static tree
79 gimple_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
88 static tree
89 set_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
105 static tree
106 gimple_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
344 static void
345 release_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
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.  */
389 struct 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.  */
417 static struct stack_var *stack_vars;
418 static size_t stack_vars_alloc;
419 static size_t stack_vars_num;
420
421 /* An array of indices such that stack_vars[stack_vars_sorted[i]].size
422    is non-decreasing.  */
423 static size_t *stack_vars_sorted;
424
425 /* We have an interference graph between such objects.  This graph
426    is lower triangular.  */
427 static bool *stack_vars_conflict;
428 static 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.  */
433 static 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.  */
437 static 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.  */
441 static 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
446 static unsigned int
447 get_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
478 static HOST_WIDE_INT
479 alloc_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
510 static void
511 add_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
539 static size_t
540 triangular_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
552 static void
553 resize_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
568 static void
569 add_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
578 static bool
579 stack_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
588 static bool
589 aggregate_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
619 static void
620 add_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
653 static int
654 stack_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
682 static void
683 union_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
725 static void
726 partition_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
797 static void
798 dump_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
826 static void
827 expand_one_stack_var_at (tree decl, HOST_WIDE_INT offset)
828 {
829   HOST_WIDE_INT align, max_align;
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;
842   max_align = crtl->max_used_stack_slot_alignment;
843   if (align == 0 || align > max_align)
844     align = max_align;
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
856 static void
857 expand_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.  */
896 static HOST_WIDE_INT
897 account_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
920 static void
921 expand_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
935 static void
936 expand_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
944 static void
945 expand_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
967 static void
968 expand_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
991 static bool
992 defer_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
1025 static HOST_WIDE_INT
1026 expand_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     }
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     }
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
1105 static void
1106 expand_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
1143 static void
1144 clear_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
1163 static unsigned int
1164 stack_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
1216 static int
1217 stack_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
1245 static bool
1246 stack_protect_decl_phase_1 (tree decl)
1247 {
1248   return stack_protect_decl_phase (decl) == 1;
1249 }
1250
1251 static bool
1252 stack_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
1260 static void
1261 add_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
1283 static void
1284 create_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
1299 static HOST_WIDE_INT
1300 account_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.  */
1337 static void 
1338 init_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.  */
1354 static void
1355 fini_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
1374 HOST_WIDE_INT
1375 estimated_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
1408 static void
1409 expand_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
1547 static void
1548 maybe_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
1562 static struct pointer_map_t *lab_rtx_for_bb;
1563
1564 /* Returns the label_rtx expression for a label starting basic block BB.  */
1565
1566 static rtx
1567 label_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
1606 static basic_block
1607 expand_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     {
1633       jumpif (pred, label_rtx_for_bb (true_edge->dest),
1634               true_edge->probability);
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     {
1649       jumpifnot (pred, label_rtx_for_bb (false_edge->dest),
1650                  false_edge->probability);
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
1664   jumpif (pred, label_rtx_for_bb (true_edge->dest), true_edge->probability);
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
1717 static basic_block
1718 expand_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
1819 static basic_block
1820 expand_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
1990 static basic_block
1991 construct_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
2041 static void
2042 set_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
2054 static void
2055 construct_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
2124 static tree
2125 discover_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
2166 static void
2167 discover_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
2184 static void
2185 expand_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
2249 static unsigned int
2250 gimple_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
2429 struct 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 };