1 /* Build expressions with type checking for C compiler.
2 Copyright (C) 1987, 88, 89, 92, 93, 96, 1997 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)
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. */
36 KEEPING TRACK OF EXPANSIONS
38 In order to clean out expansions corresponding to statements inside
39 "{(...)}" constructs we have to keep track of all expansions. The
40 cleanup is needed when an automatic, or implicit, expansion on
41 iterator, say X, happens to a statement which contains a {(...)}
42 form with a statement already expanded on X. In this case we have
43 to go back and cleanup the inner expansion. This can be further
44 complicated by the fact that {(...)} can be nested.
46 To make this cleanup possible, we keep lists of all expansions, and
47 to make it work for nested constructs, we keep a stack. The list at
48 the top of the stack (ITER_STACK.CURRENT_LEVEL) corresponds to the
49 currently parsed level. All expansions of the levels below the
50 current one are kept in one list whose head is pointed to by
51 ITER_STACK.SUBLEVEL_FIRST (SUBLEVEL_LAST is there for making merges
52 easy). The process works as follows:
54 -- On "({" a new node is added to the stack by PUSH_ITERATOR_STACK.
55 The sublevel list is not changed at this point.
57 -- On "})" the list for the current level is appended to the sublevel
60 -- On ";" sublevel lists are appended to the current level lists.
61 The reason is this: if they have not been superseded by the
62 expansion at the current level, they still might be
63 superseded later by the expansion on the higher level.
64 The levels do not have to distinguish levels below, so we
65 can merge the lists together. */
69 tree ixdecl; /* Iterator decl */
70 rtx ixprologue_start; /* First insn of epilogue. NULL means */
71 /* explicit (FOR) expansion*/
75 struct ixpansion *next; /* Next in the list */
78 struct iter_stack_node
80 struct ixpansion *first; /* Head of list of ixpansions */
81 struct ixpansion *last; /* Last node in list of ixpansions */
82 struct iter_stack_node *next; /* Next level iterator stack node */
85 struct iter_stack_node *iter_stack;
86 struct iter_stack_node sublevel_ixpansions;
88 /* A special obstack, and a pointer to the start of
89 all the data in it (so we can free everything easily). */
90 static struct obstack ixp_obstack;
91 static char *ixp_firstobj;
93 /* During collect_iterators, a list of SAVE_EXPRs already scanned. */
94 static tree save_exprs;
96 static void expand_stmt_with_iterators_1 PROTO((tree, tree));
97 static tree collect_iterators PROTO((tree, tree));
98 static void iterator_loop_prologue PROTO((tree, rtx *, rtx *));
99 static void iterator_loop_epilogue PROTO((tree, rtx *, rtx *));
100 static int top_level_ixpansion_p PROTO((void));
101 static void isn_append PROTO((struct iter_stack_node *,
102 struct iter_stack_node *));
103 static void istack_sublevel_to_current PROTO((void));
104 static void add_ixpansion PROTO((tree, rtx, rtx, rtx, rtx));
105 static void delete_ixpansion PROTO((tree));
107 /* Initialize our obstack once per compilation. */
112 gcc_obstack_init (&ixp_obstack);
113 ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0);
116 /* Handle the start of an explicit `for' loop for iterator IDECL. */
119 iterator_for_loop_start (idecl)
122 ITERATOR_BOUND_P (idecl) = 1;
123 add_ixpansion (idecl, 0, 0, 0, 0);
124 iterator_loop_prologue (idecl, 0, 0);
127 /* Handle the end of an explicit `for' loop for iterator IDECL. */
130 iterator_for_loop_end (idecl)
133 iterator_loop_epilogue (idecl, 0, 0);
134 ITERATOR_BOUND_P (idecl) = 0;
138 ITERATOR RTL EXPANSIONS
140 Expanding simple statements with iterators is straightforward:
141 collect the list of all free iterators in the statement, and
142 generate a loop for each of them.
144 An iterator is "free" if it has not been "bound" by a FOR
145 operator. The DECL_RTL of the iterator is the loop counter. */
147 /* Expand a statement STMT, possibly containing iterator usage, into RTL. */
150 iterator_expand (stmt)
154 save_exprs = NULL_TREE;
155 iter_list = collect_iterators (stmt, NULL_TREE);
156 expand_stmt_with_iterators_1 (stmt, iter_list);
157 istack_sublevel_to_current ();
162 expand_stmt_with_iterators_1 (stmt, iter_list)
163 tree stmt, iter_list;
166 expand_expr_stmt (stmt);
169 tree current_iterator = TREE_VALUE (iter_list);
170 tree iter_list_tail = TREE_CHAIN (iter_list);
171 rtx p_start, p_end, e_start, e_end;
173 iterator_loop_prologue (current_iterator, &p_start, &p_end);
174 expand_stmt_with_iterators_1 (stmt, iter_list_tail);
175 iterator_loop_epilogue (current_iterator, &e_start, &e_end);
177 /** Delete all inner expansions based on current_iterator **/
178 /** before adding the outer one. **/
180 delete_ixpansion (current_iterator);
181 add_ixpansion (current_iterator, p_start, p_end, e_start, e_end);
186 /* Return a list containing all the free (i.e. not bound by a
187 containing `for' statement) iterators mentioned in EXP, plus those
188 in LIST. Do not add duplicate entries to the list. */
191 collect_iterators (exp, list)
194 if (exp == 0) return list;
196 switch (TREE_CODE (exp))
199 if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp))
201 if (value_member (exp, list))
203 return tree_cons (NULL_TREE, exp, list);
208 for (tail = exp; tail; tail = TREE_CHAIN (tail))
209 list = collect_iterators (TREE_VALUE (tail), list);
214 /* In each scan, scan a given save_expr only once. */
215 if (value_member (exp, save_exprs))
218 save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
219 return collect_iterators (TREE_OPERAND (exp, 0), list);
221 /* we do not automatically iterate blocks -- one must */
222 /* use the FOR construct to do that */
228 switch (TREE_CODE_CLASS (TREE_CODE (exp)))
231 return collect_iterators (TREE_OPERAND (exp, 0), list);
235 return collect_iterators (TREE_OPERAND (exp, 0),
236 collect_iterators (TREE_OPERAND (exp, 1),
242 int num_args = tree_code_length[(int) TREE_CODE (exp)];
245 /* Some tree codes have RTL, not trees, as operands. */
246 switch (TREE_CODE (exp))
251 case METHOD_CALL_EXPR:
254 case WITH_CLEANUP_EXPR:
263 for (i = 0; i < num_args; i++)
264 list = collect_iterators (TREE_OPERAND (exp, i), list);
273 /* Emit rtl for the start of a loop for iterator IDECL.
275 If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
277 The prologue normally starts and ends with notes, which are returned
278 by this function in *START_NOTE and *END_NODE.
279 If START_NOTE and END_NODE are 0, we don't make those notes. */
282 iterator_loop_prologue (idecl, start_note, end_note)
284 rtx *start_note, *end_note;
288 /* Force the save_expr in DECL_INITIAL to be calculated
289 if it hasn't been calculated yet. */
290 expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
292 if (DECL_RTL (idecl) == 0)
296 *start_note = emit_note (0, NOTE_INSN_DELETED);
298 /* Initialize counter. */
299 expr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, integer_zero_node);
300 TREE_SIDE_EFFECTS (expr) = 1;
301 expand_expr (expr, const0_rtx, VOIDmode, 0);
303 expand_start_loop_continue_elsewhere (1);
305 ITERATOR_BOUND_P (idecl) = 1;
308 *end_note = emit_note (0, NOTE_INSN_DELETED);
311 /* Similar to the previous function, but for the end of the loop.
313 DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
316 When we create two (or more) loops based on the same IDECL, and
317 both inside the same "({...})" construct, we must be prepared to
318 delete both of the loops and create a single one on the level
319 above, i.e. enclosing the "({...})". The new loop has to use the
320 same counter rtl because the references to the iterator decl
321 (IDECL) have already been expanded as references to the counter
324 It is incorrect to use the same counter reg in different functions,
325 and it is desirable to use different counters in disjoint loops
326 when we know there's no need to combine them (because then they can
327 get allocated separately). */
330 iterator_loop_epilogue (idecl, start_note, end_note)
332 rtx *start_note, *end_note;
337 *start_note = emit_note (0, NOTE_INSN_DELETED);
338 expand_loop_continue_here ();
339 incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0);
340 incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
341 TREE_SIDE_EFFECTS (incr) = 1;
342 expand_expr (incr, const0_rtx, VOIDmode, 0);
343 test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
344 expand_exit_loop_if_false (0, test);
347 ITERATOR_BOUND_P (idecl) = 0;
348 /* we can reset rtl since there is not chance that this expansion */
349 /* would be superseded by a higher level one */
350 /* but don't do this if the decl is static, since we need to share */
351 /* the same decl in that case. */
352 if (top_level_ixpansion_p () && ! TREE_STATIC (idecl))
353 DECL_RTL (idecl) = 0;
355 *end_note = emit_note (0, NOTE_INSN_DELETED);
358 /* Return true if we are not currently inside a "({...})" construct. */
361 top_level_ixpansion_p ()
363 return iter_stack == 0;
366 /* Given two chains of iter_stack_nodes,
367 append the nodes in X into Y. */
371 struct iter_stack_node *x, *y;
383 y->last->next = x->first;
390 #define ISN_ZERO(X) (X).first=(X).last=0
392 /* Move the ixpansions in sublevel_ixpansions into the current
393 node on the iter_stack, or discard them if the iter_stack is empty.
394 We do this at the end of a statement. */
397 istack_sublevel_to_current ()
399 /* At the top level we can throw away sublevel's expansions **/
400 /* because there is nobody above us to ask for a cleanup **/
402 /** Merging with empty sublevel list is a no-op **/
403 if (sublevel_ixpansions.last)
404 isn_append (&sublevel_ixpansions, iter_stack);
407 obstack_free (&ixp_obstack, ixp_firstobj);
409 ISN_ZERO (sublevel_ixpansions);
412 /* Push a new node on the iter_stack, when we enter a ({...}). */
415 push_iterator_stack ()
417 struct iter_stack_node *new_top
418 = (struct iter_stack_node *)
419 obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
423 new_top->next = iter_stack;
424 iter_stack = new_top;
427 /* Pop iter_stack, moving the ixpansions in the node being popped
428 into sublevel_ixpansions. */
431 pop_iterator_stack ()
436 isn_append (iter_stack, &sublevel_ixpansions);
437 /** Pop current level node: */
438 iter_stack = iter_stack->next;
442 /* Record an iterator expansion ("ixpansion") for IDECL.
443 The remaining parameters are the notes in the loop entry
447 add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
449 rtx pro_start, pro_end, epi_start, epi_end;
451 struct ixpansion *newix;
453 /* Do nothing if we are not inside "({...})",
454 as in that case this expansion can't need subsequent RTL modification. */
458 newix = (struct ixpansion *) obstack_alloc (&ixp_obstack,
459 sizeof (struct ixpansion));
460 newix->ixdecl = idecl;
461 newix->ixprologue_start = pro_start;
462 newix->ixprologue_end = pro_end;
463 newix->ixepilogue_start = epi_start;
464 newix->ixepilogue_end = epi_end;
466 newix->next = iter_stack->first;
467 iter_stack->first = newix;
468 if (iter_stack->last == 0)
469 iter_stack->last = newix;
472 /* Delete the RTL for all ixpansions for iterator IDECL
473 in our sublevels. We do this when we make a larger
474 containing expansion for IDECL. */
477 delete_ixpansion (idecl)
480 struct ixpansion *previx = 0, *ix;
482 for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
483 if (ix->ixdecl == idecl)
485 /** zero means that this is a mark for FOR -- **/
486 /** we do not delete anything, just issue an error. **/
488 if (ix->ixprologue_start == 0)
489 error_with_decl (idecl,
490 "`for (%s)' appears within implicit iteration");
494 /* We delete all insns, including notes because leaving loop */
495 /* notes and barriers produced by iterator expansion would */
496 /* be misleading to other phases */
498 for (insn = NEXT_INSN (ix->ixprologue_start);
499 insn != ix->ixprologue_end;
500 insn = NEXT_INSN (insn))
502 for (insn = NEXT_INSN (ix->ixepilogue_start);
503 insn != ix->ixepilogue_end;
504 insn = NEXT_INSN (insn))
508 /* Delete this ixpansion from sublevel_ixpansions. */
510 previx->next = ix->next;
512 sublevel_ixpansions.first = ix->next;
513 if (sublevel_ixpansions.last == ix)
514 sublevel_ixpansions.last = previx;
520 #ifdef DEBUG_ITERATORS
522 /* The functions below are for use from source level debugger.
523 They print short forms of iterator lists and the iterator stack. */
525 /* Print the name of the iterator D. */
533 if (TREE_CODE (d) == VAR_DECL)
535 tree tname = DECL_NAME (d);
536 char *dname = IDENTIFIER_POINTER (tname);
537 fprintf (stderr, dname);
540 fprintf (stderr, "<<Not a Decl!!!>>");
543 fprintf (stderr, "<<NULL!!>>");
546 /* Print Iterator List -- names only */
553 for (current = head; current; current = next)
555 tree node = TREE_VALUE (current);
557 next = TREE_CHAIN (current);
558 if (next) fprintf (stderr, ",");
560 fprintf (stderr, "\n");
563 /* Print IXpansion List */
567 struct ixpansion *head;
569 struct ixpansion *current, *next;
570 fprintf (stderr, "> ");
572 fprintf (stderr, "(empty)");
574 for (current=head; current; current = next)
576 tree node = current->ixdecl;
578 next = current->next;
580 fprintf (stderr, ",");
582 fprintf (stderr, "\n");
586 /* Print Iterator Stack. */
591 struct iter_stack_node *stack_node;
593 fprintf (stderr, "--SubLevel: ");
594 pixl (sublevel_ixpansions.first);
595 fprintf (stderr, "--Stack:--\n");
596 for (stack_node = iter_stack;
598 stack_node = stack_node->next)
599 pixl (stack_node->first);
602 #endif /* DEBUG_ITERATORS */