![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to c-iterate.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / cc|
Return to c-iterate.c CVS log | Up to [Apple XNU] / GNUtools / cc |
1.1 root 1: /* Build expressions with type checking for C compiler.
2: Copyright (C) 1987, 1988, 1989, 1992, 1993 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
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.
10:
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.
15:
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, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* This file is part of the C front end.
22: It is responsible for implementing iterators,
23: both their declarations and the expansion of statements using them. */
24:
25: #include "config.h"
26: #include <stdio.h>
27: #include "tree.h"
28: #include "c-tree.h"
29: #include "flags.h"
30: #include "obstack.h"
31: #include "rtl.h"
32:
33: static void expand_stmt_with_iterators_1 ();
34: static tree collect_iterators ();
35: static void iterator_loop_prologue ();
36: static void iterator_loop_epilogue ();
37: static void add_ixpansion ();
38: static void delete_ixpansion();
39: static int top_level_ixpansion_p ();
40: static void istack_sublevel_to_current ();
41:
42: /* A special obstack, and a pointer to the start of
43: all the data in it (so we can free everything easily). */
44: static struct obstack ixp_obstack;
45: static char *ixp_firstobj;
46:
47: /*
48: KEEPING TRACK OF EXPANSIONS
49:
50: In order to clean out expansions corresponding to statements inside
51: "{(...)}" constructs we have to keep track of all expansions. The
52: cleanup is needed when an automatic, or implicit, expansion on
53: iterator, say X, happens to a statement which contains a {(...)}
54: form with a statement already expanded on X. In this case we have
55: to go back and cleanup the inner expansion. This can be further
56: complicated by the fact that {(...)} can be nested.
57:
58: To make this cleanup possible, we keep lists of all expansions, and
59: to make it work for nested constructs, we keep a stack. The list at
60: the top of the stack (ITER_STACK.CURRENT_LEVEL) corresponds to the
61: currently parsed level. All expansions of the levels below the
62: current one are kept in one list whose head is pointed to by
63: ITER_STACK.SUBLEVEL_FIRST (SUBLEVEL_LAST is there for making merges
64: easy). The process works as follows:
65:
66: -- On "({" a new node is added to the stack by PUSH_ITERATOR_STACK.
67: The sublevel list is not changed at this point.
68:
69: -- On "})" the list for the current level is appended to the sublevel
70: list.
71:
72: -- On ";" sublevel lists are appended to the current level lists.
73: The reason is this: if they have not been superseded by the
74: expansion at the current level, they still might be
75: superseded later by the expansion on the higher level.
76: The levels do not have to distinguish levels below, so we
77: can merge the lists together. */
78:
79: struct ixpansion
80: {
81: tree ixdecl; /* Iterator decl */
82: rtx ixprologue_start; /* First insn of epilogue. NULL means */
83: /* explicit (FOR) expansion*/
84: rtx ixprologue_end;
85: rtx ixepilogue_start;
86: rtx ixepilogue_end;
87: struct ixpansion *next; /* Next in the list */
88: };
89:
90: struct iter_stack_node
91: {
92: struct ixpansion *first; /* Head of list of ixpansions */
93: struct ixpansion *last; /* Last node in list of ixpansions */
94: struct iter_stack_node *next; /* Next level iterator stack node */
95: };
96:
97: struct iter_stack_node *iter_stack;
98:
99: struct iter_stack_node sublevel_ixpansions;
100:
101: /* During collect_iterators, a list of SAVE_EXPRs already scanned. */
102: static tree save_exprs;
103:
104: /* Initialize our obstack once per compilation. */
105:
106: void
107: init_iterators ()
108: {
109: gcc_obstack_init (&ixp_obstack);
110: ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0);
111: }
112:
113: /* Handle the start of an explicit `for' loop for iterator IDECL. */
114:
115: void
116: iterator_for_loop_start (idecl)
117: tree idecl;
118: {
119: ITERATOR_BOUND_P (idecl) = 1;
120: add_ixpansion (idecl, 0, 0, 0, 0);
121: iterator_loop_prologue (idecl, 0, 0);
122: }
123:
124: /* Handle the end of an explicit `for' loop for iterator IDECL. */
125:
126: void
127: iterator_for_loop_end (idecl)
128: tree idecl;
129: {
130: iterator_loop_epilogue (idecl, 0, 0);
131: ITERATOR_BOUND_P (idecl) = 0;
132: }
133:
134: /*
135: ITERATOR RTL EXPANSIONS
136:
137: Expanding simple statements with iterators is straightforward:
138: collect the list of all free iterators in the statement, and
139: generate a loop for each of them.
140:
141: An iterator is "free" if it has not been "bound" by a FOR
142: operator. The DECL_RTL of the iterator is the loop counter. */
143:
144: /* Expand a statement STMT, possibly containing iterator usage, into RTL. */
145:
146: void
147: iterator_expand (stmt)
148: tree stmt;
149: {
150: tree iter_list;
151: save_exprs = NULL_TREE;
152: iter_list = collect_iterators (stmt, NULL_TREE);
153: expand_stmt_with_iterators_1 (stmt, iter_list);
154: istack_sublevel_to_current ();
155: }
156:
157:
158: static void
159: expand_stmt_with_iterators_1 (stmt, iter_list)
160: tree stmt, iter_list;
161: {
162: if (iter_list == 0)
163: expand_expr_stmt (stmt);
164: else
165: {
166: tree current_iterator = TREE_VALUE (iter_list);
167: tree iter_list_tail = TREE_CHAIN (iter_list);
168: rtx p_start, p_end, e_start, e_end;
169:
170: iterator_loop_prologue (current_iterator, &p_start, &p_end);
171: expand_stmt_with_iterators_1 (stmt, iter_list_tail);
172: iterator_loop_epilogue (current_iterator, &e_start, &e_end);
173:
174: /** Delete all inner expansions based on current_iterator **/
175: /** before adding the outer one. **/
176:
177: delete_ixpansion (current_iterator);
178: add_ixpansion (current_iterator, p_start, p_end, e_start, e_end);
179: }
180: }
181:
182:
183: /* Return a list containing all the free (i.e. not bound by a
184: containing `for' statement) iterators mentioned in EXP, plus those
185: in LIST. Do not add duplicate entries to the list. */
186:
187: static tree
188: collect_iterators (exp, list)
189: tree exp, list;
190: {
191: if (exp == 0) return list;
192:
193: switch (TREE_CODE (exp))
194: {
195: case VAR_DECL:
196: if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp))
197: return list;
198: if (value_member (exp, list))
199: return list;
200: return tree_cons (NULL_TREE, exp, list);
201:
202: case TREE_LIST:
203: {
204: tree tail;
205: for (tail = exp; tail; tail = TREE_CHAIN (tail))
206: list = collect_iterators (TREE_VALUE (tail), list);
207: return list;
208: }
209:
210: case SAVE_EXPR:
211: /* In each scan, scan a given save_expr only once. */
212: if (value_member (exp, save_exprs))
213: return list;
214:
215: save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
216: return collect_iterators (TREE_OPERAND (exp, 0), list);
217:
218: /* we do not automatically iterate blocks -- one must */
219: /* use the FOR construct to do that */
220:
221: case BLOCK:
222: return list;
223:
224: default:
225: switch (TREE_CODE_CLASS (TREE_CODE (exp)))
226: {
227: case '1':
228: return collect_iterators (TREE_OPERAND (exp, 0), list);
229:
230: case '2':
231: case '<':
232: return collect_iterators (TREE_OPERAND (exp, 0),
233: collect_iterators (TREE_OPERAND (exp, 1),
234: list));
235:
236: case 'e':
237: case 'r':
238: {
239: int num_args = tree_code_length[(int) TREE_CODE (exp)];
240: int i;
241:
242: /* Some tree codes have RTL, not trees, as operands. */
243: switch (TREE_CODE (exp))
244: {
245: case CALL_EXPR:
246: num_args = 2;
247: break;
248: case METHOD_CALL_EXPR:
249: num_args = 3;
250: break;
251: case WITH_CLEANUP_EXPR:
252: num_args = 1;
253: break;
254: case RTL_EXPR:
255: return list;
256: }
257:
258: for (i = 0; i < num_args; i++)
259: list = collect_iterators (TREE_OPERAND (exp, i), list);
260: return list;
261: }
262: default:
263: return list;
264: }
265: }
266: }
267:
268: /* Emit rtl for the start of a loop for iterator IDECL.
269:
270: If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
271:
272: The prologue normally starts and ends with notes, which are returned
273: by this function in *START_NOTE and *END_NODE.
274: If START_NOTE and END_NODE are 0, we don't make those notes. */
275:
276: static void
277: iterator_loop_prologue (idecl, start_note, end_note)
278: tree idecl;
279: rtx *start_note, *end_note;
280: {
281: tree expr;
282:
283: /* Force the save_expr in DECL_INITIAL to be calculated
284: if it hasn't been calculated yet. */
285: expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
286:
287: if (DECL_RTL (idecl) == 0)
288: expand_decl (idecl);
289:
290: if (start_note)
291: *start_note = emit_note (0, NOTE_INSN_DELETED);
292:
293: /* Initialize counter. */
294: expr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, integer_zero_node);
295: TREE_SIDE_EFFECTS (expr) = 1;
296: expand_expr (expr, const0_rtx, VOIDmode, 0);
297:
298: expand_start_loop_continue_elsewhere (1);
299:
300: ITERATOR_BOUND_P (idecl) = 1;
301:
302: if (end_note)
303: *end_note = emit_note (0, NOTE_INSN_DELETED);
304: }
305:
306: /* Similar to the previous function, but for the end of the loop.
307:
308: DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
309: described below.
310:
311: When we create two (or more) loops based on the same IDECL, and
312: both inside the same "({...})" construct, we must be prepared to
313: delete both of the loops and create a single one on the level
314: above, i.e. enclosing the "({...})". The new loop has to use the
315: same counter rtl because the references to the iterator decl
316: (IDECL) have already been expanded as references to the counter
317: rtl.
318:
319: It is incorrect to use the same counter reg in different functions,
320: and it is desirable to use different counters in disjoint loops
321: when we know there's no need to combine them (because then they can
322: get allocated separately). */
323:
324: static void
325: iterator_loop_epilogue (idecl, start_note, end_note)
326: tree idecl;
327: rtx *start_note, *end_note;
328: {
329: tree test, incr;
330:
331: if (start_note)
332: *start_note = emit_note (0, NOTE_INSN_DELETED);
333: expand_loop_continue_here ();
334: incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0);
335: incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
336: TREE_SIDE_EFFECTS (incr) = 1;
337: expand_expr (incr, const0_rtx, VOIDmode, 0);
338: test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
339: expand_exit_loop_if_false (0, test);
340: expand_end_loop ();
341:
342: ITERATOR_BOUND_P (idecl) = 0;
343: /* we can reset rtl since there is not chance that this expansion */
344: /* would be superceded by a higher level one */
345: if (top_level_ixpansion_p ())
346: DECL_RTL (idecl) = 0;
347: if (end_note)
348: *end_note = emit_note (0, NOTE_INSN_DELETED);
349: }
350:
351: /* Return true if we are not currently inside a "({...})" construct. */
352:
353: static int
354: top_level_ixpansion_p ()
355: {
356: return iter_stack == 0;
357: }
358:
359: /* Given two chains of iter_stack_nodes,
360: append the nodes in X into Y. */
361:
362: static void
363: isn_append (x, y)
364: struct iter_stack_node *x, *y;
365: {
366: if (x->first == 0)
367: return;
368:
369: if (y->first == 0)
370: {
371: y->first = x->first;
372: y->last = x->last;
373: }
374: else
375: {
376: y->last->next = x->first;
377: y->last = x->last;
378: }
379: }
380:
381: /** Make X empty **/
382:
383: #define ISN_ZERO(X) (X).first=(X).last=0
384:
385: /* Move the ixpansions in sublevel_ixpansions into the current
386: node on the iter_stack, or discard them if the iter_stack is empty.
387: We do this at the end of a statement. */
388:
389: static void
390: istack_sublevel_to_current ()
391: {
392: /* At the top level we can throw away sublevel's expansions **/
393: /* because there is nobody above us to ask for a cleanup **/
394: if (iter_stack != 0)
395: /** Merging with empty sublevel list is a no-op **/
396: if (sublevel_ixpansions.last)
397: isn_append (&sublevel_ixpansions, iter_stack);
398:
399: if (iter_stack == 0)
400: obstack_free (&ixp_obstack, ixp_firstobj);
401:
402: ISN_ZERO (sublevel_ixpansions);
403: }
404:
405: /* Push a new node on the iter_stack, when we enter a ({...}). */
406:
407: void
408: push_iterator_stack ()
409: {
410: struct iter_stack_node *new_top
411: = (struct iter_stack_node*)
412: obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
413:
414: new_top->first = 0;
415: new_top->last = 0;
416: new_top->next = iter_stack;
417: iter_stack = new_top;
418: }
419:
420: /* Pop iter_stack, moving the ixpansions in the node being popped
421: into sublevel_ixpansions. */
422:
423: void
424: pop_iterator_stack ()
425: {
426: if (iter_stack == 0)
427: abort ();
428:
429: isn_append (iter_stack, &sublevel_ixpansions);
430: /** Pop current level node: */
431: iter_stack = iter_stack->next;
432: }
433:
434:
435: /* Record an iterator expansion ("ixpansion") for IDECL.
436: The remaining paramters are the notes in the loop entry
437: and exit rtl. */
438:
439: static void
440: add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
441: tree idecl;
442: rtx pro_start, pro_end, epi_start, epi_end;
443: {
444: struct ixpansion* newix;
445:
446: /* Do nothing if we are not inside "({...})",
447: as in that case this expansion can't need subsequent RTL modification. */
448: if (iter_stack == 0)
449: return;
450:
451: newix = (struct ixpansion*) obstack_alloc (&ixp_obstack,
452: sizeof (struct ixpansion));
453: newix->ixdecl = idecl;
454: newix->ixprologue_start = pro_start;
455: newix->ixprologue_end = pro_end;
456: newix->ixepilogue_start = epi_start;
457: newix->ixepilogue_end = epi_end;
458:
459: newix->next = iter_stack->first;
460: iter_stack->first = newix;
461: if (iter_stack->last == 0)
462: iter_stack->last = newix;
463: }
464:
465: /* Delete the RTL for all ixpansions for iterator IDECL
466: in our sublevels. We do this when we make a larger
467: containing expansion for IDECL. */
468:
469: static void
470: delete_ixpansion (idecl)
471: tree idecl;
472: {
473: struct ixpansion* previx = 0, *ix;
474:
475: for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
476: if (ix->ixdecl == idecl)
477: {
478: /** zero means that this is a mark for FOR -- **/
479: /** we do not delete anything, just issue an error. **/
480:
481: if (ix->ixprologue_start == 0)
482: error_with_decl (idecl,
483: "`for (%s)' appears within implicit iteration");
484: else
485: {
486: rtx insn;
487: /* We delete all insns, including notes because leaving loop */
488: /* notes and barriers produced by iterator expansion would */
489: /* be misleading to other phases */
490:
491: for (insn = NEXT_INSN (ix->ixprologue_start);
492: insn != ix->ixprologue_end;
493: insn = NEXT_INSN (insn))
494: delete_insn (insn);
495: for (insn = NEXT_INSN (ix->ixepilogue_start);
496: insn != ix->ixepilogue_end;
497: insn = NEXT_INSN (insn))
498: delete_insn (insn);
499: }
500:
501: /* Delete this ixpansion from sublevel_ixpansions. */
502: if (previx)
503: previx->next = ix->next;
504: else
505: sublevel_ixpansions.first = ix->next;
506: if (sublevel_ixpansions.last == ix)
507: sublevel_ixpansions.last = previx;
508: }
509: else
510: previx = ix;
511: }
512:
513: #ifdef DEBUG_ITERATORS
514:
515: /* The functions below are for use from source level debugger.
516: They print short forms of iterator lists and the iterator stack. */
517:
518: /* Print the name of the iterator D. */
519:
520: void
521: prdecl (d)
522: tree d;
523: {
524: if (d)
525: {
526: if (TREE_CODE (d) == VAR_DECL)
527: {
528: tree tname = DECL_NAME (d);
529: char *dname = IDENTIFIER_POINTER (tname);
530: fprintf (stderr, dname);
531: }
532: else
533: fprintf (stderr, "<<Not a Decl!!!>>");
534: }
535: else
536: fprintf (stderr, "<<NULL!!>>");
537: }
538:
539: /* Print Iterator List -- names only */
540:
541: tree
542: pil (head)
543: tree head;
544: {
545: tree current, next;
546: for (current = head; current; current = next)
547: {
548: tree node = TREE_VALUE (current);
549: prdecl (node);
550: next = TREE_CHAIN (current);
551: if (next) fprintf (stderr, ",");
552: }
553: fprintf (stderr, "\n");
554: }
555:
556: /* Print IXpansion List */
557:
558: struct ixpansion *
559: pixl (head)
560: struct ixpansion *head;
561: {
562: struct ixpansion *current, *next;
563: fprintf (stderr, "> ");
564: if (head == 0)
565: fprintf (stderr, "(empty)");
566:
567: for (current=head; current; current = next)
568: {
569: tree node = current->ixdecl;
570: prdecl (node);
571: next = current->next;
572: if (next)
573: fprintf (stderr, ",");
574: }
575: fprintf (stderr, "\n");
576: return head;
577: }
578:
579: /* Print Iterator Stack*/
580:
581: void
582: pis ()
583: {
584: struct iter_stack_node *stack_node;
585:
586: fprintf (stderr, "--SubLevel: ");
587: pixl (sublevel_ixpansions.first);
588: fprintf (stderr, "--Stack:--\n");
589: for (stack_node = iter_stack;
590: stack_node;
591: stack_node = stack_node->next)
592: pixl (stack_node->first);
593: }
594:
595: #endif /* DEBUG_ITERATORS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.