Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfgexpand.c @ 0:a06113de4d67

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