1 /* Build expressions with type checking for C compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993 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. */
34 static void expand_stmt_with_iterators_1 ();
35 static tree collect_iterators ();
36 static void iterator_loop_prologue ();
37 static void iterator_loop_epilogue ();
38 static void add_ixpansion ();
39 static void delete_ixpansion();
40 static int top_level_ixpansion_p ();
41 static void istack_sublevel_to_current ();
43 /* A special obstack, and a pointer to the start of
44 all the data in it (so we can free everything easily). */
45 static struct obstack ixp_obstack;
46 static char *ixp_firstobj;
49 KEEPING TRACK OF EXPANSIONS
51 In order to clean out expansions corresponding to statements inside
52 "{(...)}" constructs we have to keep track of all expansions. The
53 cleanup is needed when an automatic, or implicit, expansion on
54 iterator, say X, happens to a statement which contains a {(...)}
55 form with a statement already expanded on X. In this case we have
56 to go back and cleanup the inner expansion. This can be further
57 complicated by the fact that {(...)} can be nested.
59 To make this cleanup possible, we keep lists of all expansions, and
60 to make it work for nested constructs, we keep a stack. The list at
61 the top of the stack (ITER_STACK.CURRENT_LEVEL) corresponds to the
62 currently parsed level. All expansions of the levels below the
63 current one are kept in one list whose head is pointed to by
64 ITER_STACK.SUBLEVEL_FIRST (SUBLEVEL_LAST is there for making merges
65 easy). The process works as follows:
67 -- On "({" a new node is added to the stack by PUSH_ITERATOR_STACK.
68 The sublevel list is not changed at this point.
70 -- On "})" the list for the current level is appended to the sublevel
73 -- On ";" sublevel lists are appended to the current level lists.
74 The reason is this: if they have not been superseded by the
75 expansion at the current level, they still might be
76 superseded later by the expansion on the higher level.
77 The levels do not have to distinguish levels below, so we
78 can merge the lists together. */
82 tree ixdecl; /* Iterator decl */
83 rtx ixprologue_start; /* First insn of epilogue. NULL means */
84 /* explicit (FOR) expansion*/
88 struct ixpansion *next; /* Next in the list */
91 struct iter_stack_node
93 struct ixpansion *first; /* Head of list of ixpansions */
94 struct ixpansion *last; /* Last node in list of ixpansions */
95 struct iter_stack_node *next; /* Next level iterator stack node */
98 struct iter_stack_node *iter_stack;
100 struct iter_stack_node sublevel_ixpansions;
102 /* During collect_iterators, a list of SAVE_EXPRs already scanned. */
103 static tree save_exprs;
105 /* Initialize our obstack once per compilation. */
110 gcc_obstack_init (&ixp_obstack);
111 ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0);
114 /* Handle the start of an explicit `for' loop for iterator IDECL. */
117 iterator_for_loop_start (idecl)
120 ITERATOR_BOUND_P (idecl) = 1;
121 add_ixpansion (idecl, 0, 0, 0, 0);
122 iterator_loop_prologue (idecl, 0, 0);
125 /* Handle the end of an explicit `for' loop for iterator IDECL. */
128 iterator_for_loop_end (idecl)
131 iterator_loop_epilogue (idecl, 0, 0);
132 ITERATOR_BOUND_P (idecl) = 0;
136 ITERATOR RTL EXPANSIONS
138 Expanding simple statements with iterators is straightforward:
139 collect the list of all free iterators in the statement, and
140 generate a loop for each of them.
142 An iterator is "free" if it has not been "bound" by a FOR
143 operator. The DECL_RTL of the iterator is the loop counter. */
145 /* Expand a statement STMT, possibly containing iterator usage, into RTL. */
148 iterator_expand (stmt)
152 save_exprs = NULL_TREE;
153 iter_list = collect_iterators (stmt, NULL_TREE);
154 expand_stmt_with_iterators_1 (stmt, iter_list);
155 istack_sublevel_to_current ();
160 expand_stmt_with_iterators_1 (stmt, iter_list)
161 tree stmt, iter_list;
164 expand_expr_stmt (stmt);
167 tree current_iterator = TREE_VALUE (iter_list);
168 tree iter_list_tail = TREE_CHAIN (iter_list);
169 rtx p_start, p_end, e_start, e_end;
171 iterator_loop_prologue (current_iterator, &p_start, &p_end);
172 expand_stmt_with_iterators_1 (stmt, iter_list_tail);
173 iterator_loop_epilogue (current_iterator, &e_start, &e_end);
175 /** Delete all inner expansions based on current_iterator **/
176 /** before adding the outer one. **/
178 delete_ixpansion (current_iterator);
179 add_ixpansion (current_iterator, p_start, p_end, e_start, e_end);
184 /* Return a list containing all the free (i.e. not bound by a
185 containing `for' statement) iterators mentioned in EXP, plus those
186 in LIST. Do not add duplicate entries to the list. */
189 collect_iterators (exp, list)
192 if (exp == 0) return list;
194 switch (TREE_CODE (exp))
197 if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp))
199 if (value_member (exp, list))
201 return tree_cons (NULL_TREE, exp, list);
206 for (tail = exp; tail; tail = TREE_CHAIN (tail))
207 list = collect_iterators (TREE_VALUE (tail), list);
212 /* In each scan, scan a given save_expr only once. */
213 if (value_member (exp, save_exprs))
216 save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
217 return collect_iterators (TREE_OPERAND (exp, 0), list);
219 /* we do not automatically iterate blocks -- one must */
220 /* use the FOR construct to do that */
226 switch (TREE_CODE_CLASS (TREE_CODE (exp)))
229 return collect_iterators (TREE_OPERAND (exp, 0), list);
233 return collect_iterators (TREE_OPERAND (exp, 0),
234 collect_iterators (TREE_OPERAND (exp, 1),
240 int num_args = tree_code_length[(int) TREE_CODE (exp)];
243 /* Some tree codes have RTL, not trees, as operands. */
244 switch (TREE_CODE (exp))
249 case METHOD_CALL_EXPR:
252 case WITH_CLEANUP_EXPR:
259 for (i = 0; i < num_args; i++)
260 list = collect_iterators (TREE_OPERAND (exp, i), list);
269 /* Emit rtl for the start of a loop for iterator IDECL.
271 If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
273 The prologue normally starts and ends with notes, which are returned
274 by this function in *START_NOTE and *END_NODE.
275 If START_NOTE and END_NODE are 0, we don't make those notes. */
278 iterator_loop_prologue (idecl, start_note, end_note)
280 rtx *start_note, *end_note;
284 /* Force the save_expr in DECL_INITIAL to be calculated
285 if it hasn't been calculated yet. */
286 expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
288 if (DECL_RTL (idecl) == 0)
292 *start_note = emit_note (0, NOTE_INSN_DELETED);
294 /* Initialize counter. */
295 expr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, integer_zero_node);
296 TREE_SIDE_EFFECTS (expr) = 1;
297 expand_expr (expr, const0_rtx, VOIDmode, 0);
299 expand_start_loop_continue_elsewhere (1);
301 ITERATOR_BOUND_P (idecl) = 1;
304 *end_note = emit_note (0, NOTE_INSN_DELETED);
307 /* Similar to the previous function, but for the end of the loop.
309 DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
312 When we create two (or more) loops based on the same IDECL, and
313 both inside the same "({...})" construct, we must be prepared to
314 delete both of the loops and create a single one on the level
315 above, i.e. enclosing the "({...})". The new loop has to use the
316 same counter rtl because the references to the iterator decl
317 (IDECL) have already been expanded as references to the counter
320 It is incorrect to use the same counter reg in different functions,
321 and it is desirable to use different counters in disjoint loops
322 when we know there's no need to combine them (because then they can
323 get allocated separately). */
326 iterator_loop_epilogue (idecl, start_note, end_note)
328 rtx *start_note, *end_note;
333 *start_note = emit_note (0, NOTE_INSN_DELETED);
334 expand_loop_continue_here ();
335 incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0);
336 incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
337 TREE_SIDE_EFFECTS (incr) = 1;
338 expand_expr (incr, const0_rtx, VOIDmode, 0);
339 test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
340 expand_exit_loop_if_false (0, test);
343 ITERATOR_BOUND_P (idecl) = 0;
344 /* we can reset rtl since there is not chance that this expansion */
345 /* would be superseded by a higher level one */
346 if (top_level_ixpansion_p ())
347 DECL_RTL (idecl) = 0;
349 *end_note = emit_note (0, NOTE_INSN_DELETED);
352 /* Return true if we are not currently inside a "({...})" construct. */
355 top_level_ixpansion_p ()
357 return iter_stack == 0;
360 /* Given two chains of iter_stack_nodes,
361 append the nodes in X into Y. */
365 struct iter_stack_node *x, *y;
377 y->last->next = x->first;
384 #define ISN_ZERO(X) (X).first=(X).last=0
386 /* Move the ixpansions in sublevel_ixpansions into the current
387 node on the iter_stack, or discard them if the iter_stack is empty.
388 We do this at the end of a statement. */
391 istack_sublevel_to_current ()
393 /* At the top level we can throw away sublevel's expansions **/
394 /* because there is nobody above us to ask for a cleanup **/
396 /** Merging with empty sublevel list is a no-op **/
397 if (sublevel_ixpansions.last)
398 isn_append (&sublevel_ixpansions, iter_stack);
401 obstack_free (&ixp_obstack, ixp_firstobj);
403 ISN_ZERO (sublevel_ixpansions);
406 /* Push a new node on the iter_stack, when we enter a ({...}). */
409 push_iterator_stack ()
411 struct iter_stack_node *new_top
412 = (struct iter_stack_node*)
413 obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
417 new_top->next = iter_stack;
418 iter_stack = new_top;
421 /* Pop iter_stack, moving the ixpansions in the node being popped
422 into sublevel_ixpansions. */
425 pop_iterator_stack ()
430 isn_append (iter_stack, &sublevel_ixpansions);
431 /** Pop current level node: */
432 iter_stack = iter_stack->next;
436 /* Record an iterator expansion ("ixpansion") for IDECL.
437 The remaining parameters are the notes in the loop entry
441 add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
443 rtx pro_start, pro_end, epi_start, epi_end;
445 struct ixpansion* newix;
447 /* Do nothing if we are not inside "({...})",
448 as in that case this expansion can't need subsequent RTL modification. */
452 newix = (struct ixpansion*) obstack_alloc (&ixp_obstack,
453 sizeof (struct ixpansion));
454 newix->ixdecl = idecl;
455 newix->ixprologue_start = pro_start;
456 newix->ixprologue_end = pro_end;
457 newix->ixepilogue_start = epi_start;
458 newix->ixepilogue_end = epi_end;
460 newix->next = iter_stack->first;
461 iter_stack->first = newix;
462 if (iter_stack->last == 0)
463 iter_stack->last = newix;
466 /* Delete the RTL for all ixpansions for iterator IDECL
467 in our sublevels. We do this when we make a larger
468 containing expansion for IDECL. */
471 delete_ixpansion (idecl)
474 struct ixpansion* previx = 0, *ix;
476 for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
477 if (ix->ixdecl == idecl)
479 /** zero means that this is a mark for FOR -- **/
480 /** we do not delete anything, just issue an error. **/
482 if (ix->ixprologue_start == 0)
483 error_with_decl (idecl,
484 "`for (%s)' appears within implicit iteration");
488 /* We delete all insns, including notes because leaving loop */
489 /* notes and barriers produced by iterator expansion would */
490 /* be misleading to other phases */
492 for (insn = NEXT_INSN (ix->ixprologue_start);
493 insn != ix->ixprologue_end;
494 insn = NEXT_INSN (insn))
496 for (insn = NEXT_INSN (ix->ixepilogue_start);
497 insn != ix->ixepilogue_end;
498 insn = NEXT_INSN (insn))
502 /* Delete this ixpansion from sublevel_ixpansions. */
504 previx->next = ix->next;
506 sublevel_ixpansions.first = ix->next;
507 if (sublevel_ixpansions.last == ix)
508 sublevel_ixpansions.last = previx;
514 #ifdef DEBUG_ITERATORS
516 /* The functions below are for use from source level debugger.
517 They print short forms of iterator lists and the iterator stack. */
519 /* Print the name of the iterator D. */
527 if (TREE_CODE (d) == VAR_DECL)
529 tree tname = DECL_NAME (d);
530 char *dname = IDENTIFIER_POINTER (tname);
531 fprintf (stderr, dname);
534 fprintf (stderr, "<<Not a Decl!!!>>");
537 fprintf (stderr, "<<NULL!!>>");
540 /* Print Iterator List -- names only */
547 for (current = head; current; current = next)
549 tree node = TREE_VALUE (current);
551 next = TREE_CHAIN (current);
552 if (next) fprintf (stderr, ",");
554 fprintf (stderr, "\n");
557 /* Print IXpansion List */
561 struct ixpansion *head;
563 struct ixpansion *current, *next;
564 fprintf (stderr, "> ");
566 fprintf (stderr, "(empty)");
568 for (current=head; current; current = next)
570 tree node = current->ixdecl;
572 next = current->next;
574 fprintf (stderr, ",");
576 fprintf (stderr, "\n");
580 /* Print Iterator Stack*/
585 struct iter_stack_node *stack_node;
587 fprintf (stderr, "--SubLevel: ");
588 pixl (sublevel_ixpansions.first);
589 fprintf (stderr, "--Stack:--\n");
590 for (stack_node = iter_stack;
592 stack_node = stack_node->next)
593 pixl (stack_node->first);
596 #endif /* DEBUG_ITERATORS */