* cp-tree.h (DECL_LOCAL_FUCNTION_P): New macro.
[official-gcc.git] / gcc / c-iterate.c
blobc8acc4b81e313f51a8041ffb009ba5e2a84a8889
1 /* Build expressions with type checking for C compiler.
2 Copyright (C) 1987, 88, 89, 92-97, 1998 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
22 /* This file is part of the C front end.
23 It is responsible for implementing iterators,
24 both their declarations and the expansion of statements using them. */
26 #include "config.h"
27 #include "system.h"
28 #include "tree.h"
29 #include "c-tree.h"
30 #include "flags.h"
31 #include "obstack.h"
32 #include "rtl.h"
33 #include "toplev.h"
34 #include "expr.h"
37 KEEPING TRACK OF EXPANSIONS
39 In order to clean out expansions corresponding to statements inside
40 "{(...)}" constructs we have to keep track of all expansions. The
41 cleanup is needed when an automatic, or implicit, expansion on
42 iterator, say X, happens to a statement which contains a {(...)}
43 form with a statement already expanded on X. In this case we have
44 to go back and cleanup the inner expansion. This can be further
45 complicated by the fact that {(...)} can be nested.
47 To make this cleanup possible, we keep lists of all expansions, and
48 to make it work for nested constructs, we keep a stack. The list at
49 the top of the stack (ITER_STACK.CURRENT_LEVEL) corresponds to the
50 currently parsed level. All expansions of the levels below the
51 current one are kept in one list whose head is pointed to by
52 ITER_STACK.SUBLEVEL_FIRST (SUBLEVEL_LAST is there for making merges
53 easy). The process works as follows:
55 -- On "({" a new node is added to the stack by PUSH_ITERATOR_STACK.
56 The sublevel list is not changed at this point.
58 -- On "})" the list for the current level is appended to the sublevel
59 list.
61 -- On ";" sublevel lists are appended to the current level lists.
62 The reason is this: if they have not been superseded by the
63 expansion at the current level, they still might be
64 superseded later by the expansion on the higher level.
65 The levels do not have to distinguish levels below, so we
66 can merge the lists together. */
68 struct ixpansion
70 tree ixdecl; /* Iterator decl */
71 rtx ixprologue_start; /* First insn of epilogue. NULL means */
72 /* explicit (FOR) expansion*/
73 rtx ixprologue_end;
74 rtx ixepilogue_start;
75 rtx ixepilogue_end;
76 struct ixpansion *next; /* Next in the list */
79 struct iter_stack_node
81 struct ixpansion *first; /* Head of list of ixpansions */
82 struct ixpansion *last; /* Last node in list of ixpansions */
83 struct iter_stack_node *next; /* Next level iterator stack node */
86 struct iter_stack_node *iter_stack;
87 struct iter_stack_node sublevel_ixpansions;
89 /* A special obstack, and a pointer to the start of
90 all the data in it (so we can free everything easily). */
91 static struct obstack ixp_obstack;
92 static char *ixp_firstobj;
94 /* During collect_iterators, a list of SAVE_EXPRs already scanned. */
95 static tree save_exprs;
97 static void expand_stmt_with_iterators_1 PROTO((tree, tree));
98 static tree collect_iterators PROTO((tree, tree));
99 static void iterator_loop_prologue PROTO((tree, rtx *, rtx *));
100 static void iterator_loop_epilogue PROTO((tree, rtx *, rtx *));
101 static int top_level_ixpansion_p PROTO((void));
102 static void isn_append PROTO((struct iter_stack_node *,
103 struct iter_stack_node *));
104 static void istack_sublevel_to_current PROTO((void));
105 static void add_ixpansion PROTO((tree, rtx, rtx, rtx, rtx));
106 static void delete_ixpansion PROTO((tree));
108 /* Initialize our obstack once per compilation. */
110 void
111 init_iterators ()
113 gcc_obstack_init (&ixp_obstack);
114 ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0);
117 /* Handle the start of an explicit `for' loop for iterator IDECL. */
119 void
120 iterator_for_loop_start (idecl)
121 tree idecl;
123 ITERATOR_BOUND_P (idecl) = 1;
124 add_ixpansion (idecl, 0, 0, 0, 0);
125 iterator_loop_prologue (idecl, 0, 0);
128 /* Handle the end of an explicit `for' loop for iterator IDECL. */
130 void
131 iterator_for_loop_end (idecl)
132 tree idecl;
134 iterator_loop_epilogue (idecl, 0, 0);
135 ITERATOR_BOUND_P (idecl) = 0;
139 ITERATOR RTL EXPANSIONS
141 Expanding simple statements with iterators is straightforward:
142 collect the list of all free iterators in the statement, and
143 generate a loop for each of them.
145 An iterator is "free" if it has not been "bound" by a FOR
146 operator. The DECL_RTL of the iterator is the loop counter. */
148 /* Expand a statement STMT, possibly containing iterator usage, into RTL. */
150 void
151 iterator_expand (stmt)
152 tree stmt;
154 tree iter_list;
155 save_exprs = NULL_TREE;
156 iter_list = collect_iterators (stmt, NULL_TREE);
157 expand_stmt_with_iterators_1 (stmt, iter_list);
158 istack_sublevel_to_current ();
162 static void
163 expand_stmt_with_iterators_1 (stmt, iter_list)
164 tree stmt, iter_list;
166 if (iter_list == 0)
167 expand_expr_stmt (stmt);
168 else
170 tree current_iterator = TREE_VALUE (iter_list);
171 tree iter_list_tail = TREE_CHAIN (iter_list);
172 rtx p_start, p_end, e_start, e_end;
174 iterator_loop_prologue (current_iterator, &p_start, &p_end);
175 expand_stmt_with_iterators_1 (stmt, iter_list_tail);
176 iterator_loop_epilogue (current_iterator, &e_start, &e_end);
178 /** Delete all inner expansions based on current_iterator **/
179 /** before adding the outer one. **/
181 delete_ixpansion (current_iterator);
182 add_ixpansion (current_iterator, p_start, p_end, e_start, e_end);
187 /* Return a list containing all the free (i.e. not bound by a
188 containing `for' statement) iterators mentioned in EXP, plus those
189 in LIST. Do not add duplicate entries to the list. */
191 static tree
192 collect_iterators (exp, list)
193 tree exp, list;
195 if (exp == 0) return list;
197 switch (TREE_CODE (exp))
199 case VAR_DECL:
200 if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp))
201 return list;
202 if (value_member (exp, list))
203 return list;
204 return tree_cons (NULL_TREE, exp, list);
206 case TREE_LIST:
208 tree tail;
209 for (tail = exp; tail; tail = TREE_CHAIN (tail))
210 list = collect_iterators (TREE_VALUE (tail), list);
211 return list;
214 case SAVE_EXPR:
215 /* In each scan, scan a given save_expr only once. */
216 if (value_member (exp, save_exprs))
217 return list;
219 save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
220 return collect_iterators (TREE_OPERAND (exp, 0), list);
222 /* we do not automatically iterate blocks -- one must */
223 /* use the FOR construct to do that */
225 case BLOCK:
226 return list;
228 default:
229 switch (TREE_CODE_CLASS (TREE_CODE (exp)))
231 case '1':
232 return collect_iterators (TREE_OPERAND (exp, 0), list);
234 case '2':
235 case '<':
236 return collect_iterators (TREE_OPERAND (exp, 0),
237 collect_iterators (TREE_OPERAND (exp, 1),
238 list));
240 case 'e':
241 case 'r':
243 int num_args = tree_code_length[(int) TREE_CODE (exp)];
244 int i;
246 /* Some tree codes have RTL, not trees, as operands. */
247 switch (TREE_CODE (exp))
249 case CALL_EXPR:
250 num_args = 2;
251 break;
252 case METHOD_CALL_EXPR:
253 num_args = 3;
254 break;
255 case WITH_CLEANUP_EXPR:
256 num_args = 1;
257 break;
258 case RTL_EXPR:
259 return list;
260 default:
261 break;
264 for (i = 0; i < num_args; i++)
265 list = collect_iterators (TREE_OPERAND (exp, i), list);
266 return list;
268 default:
269 return list;
274 /* Emit rtl for the start of a loop for iterator IDECL.
276 If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
278 The prologue normally starts and ends with notes, which are returned
279 by this function in *START_NOTE and *END_NODE.
280 If START_NOTE and END_NODE are 0, we don't make those notes. */
282 static void
283 iterator_loop_prologue (idecl, start_note, end_note)
284 tree idecl;
285 rtx *start_note, *end_note;
287 tree expr;
289 /* Force the save_expr in DECL_INITIAL to be calculated
290 if it hasn't been calculated yet. */
291 expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode,
292 EXPAND_NORMAL);
294 if (DECL_RTL (idecl) == 0)
295 expand_decl (idecl);
297 if (start_note)
298 *start_note = emit_note (0, NOTE_INSN_DELETED);
300 /* Initialize counter. */
301 expr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, integer_zero_node);
302 TREE_SIDE_EFFECTS (expr) = 1;
303 expand_expr (expr, const0_rtx, VOIDmode, EXPAND_NORMAL);
305 expand_start_loop_continue_elsewhere (1);
307 ITERATOR_BOUND_P (idecl) = 1;
309 if (end_note)
310 *end_note = emit_note (0, NOTE_INSN_DELETED);
313 /* Similar to the previous function, but for the end of the loop.
315 DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
316 described below.
318 When we create two (or more) loops based on the same IDECL, and
319 both inside the same "({...})" construct, we must be prepared to
320 delete both of the loops and create a single one on the level
321 above, i.e. enclosing the "({...})". The new loop has to use the
322 same counter rtl because the references to the iterator decl
323 (IDECL) have already been expanded as references to the counter
324 rtl.
326 It is incorrect to use the same counter reg in different functions,
327 and it is desirable to use different counters in disjoint loops
328 when we know there's no need to combine them (because then they can
329 get allocated separately). */
331 static void
332 iterator_loop_epilogue (idecl, start_note, end_note)
333 tree idecl;
334 rtx *start_note, *end_note;
336 tree test, incr;
338 if (start_note)
339 *start_note = emit_note (0, NOTE_INSN_DELETED);
340 expand_loop_continue_here ();
341 incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0);
342 incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
343 TREE_SIDE_EFFECTS (incr) = 1;
344 expand_expr (incr, const0_rtx, VOIDmode, EXPAND_NORMAL);
345 test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
346 expand_exit_loop_if_false (0, test);
347 expand_end_loop ();
349 ITERATOR_BOUND_P (idecl) = 0;
350 /* we can reset rtl since there is not chance that this expansion */
351 /* would be superseded by a higher level one */
352 /* but don't do this if the decl is static, since we need to share */
353 /* the same decl in that case. */
354 if (top_level_ixpansion_p () && ! TREE_STATIC (idecl))
355 DECL_RTL (idecl) = 0;
356 if (end_note)
357 *end_note = emit_note (0, NOTE_INSN_DELETED);
360 /* Return true if we are not currently inside a "({...})" construct. */
362 static int
363 top_level_ixpansion_p ()
365 return iter_stack == 0;
368 /* Given two chains of iter_stack_nodes,
369 append the nodes in X into Y. */
371 static void
372 isn_append (x, y)
373 struct iter_stack_node *x, *y;
375 if (x->first == 0)
376 return;
378 if (y->first == 0)
380 y->first = x->first;
381 y->last = x->last;
383 else
385 y->last->next = x->first;
386 y->last = x->last;
390 /** Make X empty **/
392 #define ISN_ZERO(X) (X).first=(X).last=0
394 /* Move the ixpansions in sublevel_ixpansions into the current
395 node on the iter_stack, or discard them if the iter_stack is empty.
396 We do this at the end of a statement. */
398 static void
399 istack_sublevel_to_current ()
401 /* At the top level we can throw away sublevel's expansions **/
402 /* because there is nobody above us to ask for a cleanup **/
403 if (iter_stack != 0)
404 /** Merging with empty sublevel list is a no-op **/
405 if (sublevel_ixpansions.last)
406 isn_append (&sublevel_ixpansions, iter_stack);
408 if (iter_stack == 0)
409 obstack_free (&ixp_obstack, ixp_firstobj);
411 ISN_ZERO (sublevel_ixpansions);
414 /* Push a new node on the iter_stack, when we enter a ({...}). */
416 void
417 push_iterator_stack ()
419 struct iter_stack_node *new_top
420 = (struct iter_stack_node *)
421 obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
423 new_top->first = 0;
424 new_top->last = 0;
425 new_top->next = iter_stack;
426 iter_stack = new_top;
429 /* Pop iter_stack, moving the ixpansions in the node being popped
430 into sublevel_ixpansions. */
432 void
433 pop_iterator_stack ()
435 if (iter_stack == 0)
436 abort ();
438 isn_append (iter_stack, &sublevel_ixpansions);
439 /** Pop current level node: */
440 iter_stack = iter_stack->next;
444 /* Record an iterator expansion ("ixpansion") for IDECL.
445 The remaining parameters are the notes in the loop entry
446 and exit rtl. */
448 static void
449 add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
450 tree idecl;
451 rtx pro_start, pro_end, epi_start, epi_end;
453 struct ixpansion *newix;
455 /* Do nothing if we are not inside "({...})",
456 as in that case this expansion can't need subsequent RTL modification. */
457 if (iter_stack == 0)
458 return;
460 newix = (struct ixpansion *) obstack_alloc (&ixp_obstack,
461 sizeof (struct ixpansion));
462 newix->ixdecl = idecl;
463 newix->ixprologue_start = pro_start;
464 newix->ixprologue_end = pro_end;
465 newix->ixepilogue_start = epi_start;
466 newix->ixepilogue_end = epi_end;
468 newix->next = iter_stack->first;
469 iter_stack->first = newix;
470 if (iter_stack->last == 0)
471 iter_stack->last = newix;
474 /* Delete the RTL for all ixpansions for iterator IDECL
475 in our sublevels. We do this when we make a larger
476 containing expansion for IDECL. */
478 static void
479 delete_ixpansion (idecl)
480 tree idecl;
482 struct ixpansion *previx = 0, *ix;
484 for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
485 if (ix->ixdecl == idecl)
487 /** zero means that this is a mark for FOR -- **/
488 /** we do not delete anything, just issue an error. **/
490 if (ix->ixprologue_start == 0)
491 error_with_decl (idecl,
492 "`for (%s)' appears within implicit iteration");
493 else
495 rtx insn;
496 /* We delete all insns, including notes because leaving loop */
497 /* notes and barriers produced by iterator expansion would */
498 /* be misleading to other phases */
500 for (insn = NEXT_INSN (ix->ixprologue_start);
501 insn != ix->ixprologue_end;
502 insn = NEXT_INSN (insn))
503 delete_insn (insn);
504 for (insn = NEXT_INSN (ix->ixepilogue_start);
505 insn != ix->ixepilogue_end;
506 insn = NEXT_INSN (insn))
507 delete_insn (insn);
510 /* Delete this ixpansion from sublevel_ixpansions. */
511 if (previx)
512 previx->next = ix->next;
513 else
514 sublevel_ixpansions.first = ix->next;
515 if (sublevel_ixpansions.last == ix)
516 sublevel_ixpansions.last = previx;
518 else
519 previx = ix;
522 #ifdef DEBUG_ITERATORS
524 /* The functions below are for use from source level debugger.
525 They print short forms of iterator lists and the iterator stack. */
527 /* Print the name of the iterator D. */
529 void
530 prdecl (d)
531 tree d;
533 if (d)
535 if (TREE_CODE (d) == VAR_DECL)
537 tree tname = DECL_NAME (d);
538 char *dname = IDENTIFIER_POINTER (tname);
539 fprintf (stderr, dname);
541 else
542 fprintf (stderr, "<<?>>");
544 else
545 fprintf (stderr, "<<0>>");
548 /* Print Iterator List -- names only */
550 tree
551 pil (head)
552 tree head;
554 tree current, next;
555 for (current = head; current; current = next)
557 tree node = TREE_VALUE (current);
558 prdecl (node);
559 next = TREE_CHAIN (current);
560 if (next) fprintf (stderr, ",");
562 fprintf (stderr, "\n");
565 /* Print IXpansion List */
567 struct ixpansion *
568 pixl (head)
569 struct ixpansion *head;
571 struct ixpansion *current, *next;
572 fprintf (stderr, "> ");
573 if (head == 0)
574 fprintf (stderr, "(empty)");
576 for (current=head; current; current = next)
578 tree node = current->ixdecl;
579 prdecl (node);
580 next = current->next;
581 if (next)
582 fprintf (stderr, ",");
584 fprintf (stderr, "\n");
585 return head;
588 /* Print Iterator Stack. */
590 void
591 pis ()
593 struct iter_stack_node *stack_node;
595 fprintf (stderr, "--SubLevel: ");
596 pixl (sublevel_ixpansions.first);
597 fprintf (stderr, "--Stack:--\n");
598 for (stack_node = iter_stack;
599 stack_node;
600 stack_node = stack_node->next)
601 pixl (stack_node->first);
604 #endif /* DEBUG_ITERATORS */