![[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 [GCC 2.x] / gcc|
Return to c-iterate.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Build expressions with type checking for C compiler.
2: Copyright (C) 1987, 1988, 1989, 1992 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: {
213: tree tail;
214: for (tail = save_exprs; tail; tail = TREE_CHAIN (tail))
215: if (TREE_VALUE (tail) == exp)
216: return list;
217: }
218: save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
219: return collect_iterators (TREE_OPERAND (exp, 0), list);
220:
221: /* we do not automatically iterate blocks -- one must */
222: /* use the FOR construct to do that */
223:
224: case BLOCK:
225: return list;
226:
227: default:
228: switch (TREE_CODE_CLASS (TREE_CODE (exp)))
229: {
230: case '1':
231: return collect_iterators (TREE_OPERAND (exp, 0), list);
232:
233: case '2':
234: case '<':
235: return collect_iterators (TREE_OPERAND (exp, 0),
236: collect_iterators (TREE_OPERAND (exp, 1),
237: list));
238:
239: case 'e':
240: case 'r':
241: {
242: int num_args = tree_code_length[(int) TREE_CODE (exp)];
243: int i;
244:
245: /* Some tree codes have RTL, not trees, as operands. */
246: switch (TREE_CODE (exp))
247: {
248: case CALL_EXPR:
249: num_args = 2;
250: break;
251: case METHOD_CALL_EXPR:
252: num_args = 3;
253: break;
254: case WITH_CLEANUP_EXPR:
255: num_args = 1;
256: break;
257: case RTL_EXPR:
258: return list;
259: }
260:
261: for (i = 0; i < num_args; i++)
262: list = collect_iterators (TREE_OPERAND (exp, i), list);
263: return list;
264: }
265: default:
266: return list;
267: }
268: }
269: }
270:
271: /* Emit rtl for the start of a loop for iterator IDECL.
272:
273: If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
274:
275: The prologue normally starts and ends with notes, which are returned
276: by this function in *START_NOTE and *END_NODE.
277: If START_NOTE and END_NODE are 0, we don't make those notes. */
278:
279: static void
280: iterator_loop_prologue (idecl, start_note, end_note)
281: tree idecl;
282: rtx *start_note, *end_note;
283: {
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), 0, VOIDmode, 0);
287:
288: if (DECL_RTL (idecl) == 0)
289: expand_decl (idecl);
290:
291: if (start_note)
292: *start_note = emit_note (0, NOTE_INSN_DELETED);
293: /* Initialize counter. */
294: expand_expr (build (MODIFY_EXPR, TREE_TYPE (idecl),
295: idecl, integer_zero_node),
296: 0, 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: expand_expr (build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr),
336: 0, VOIDmode, 0);
337: test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
338: expand_exit_loop_if_false (0, test);
339: expand_end_loop ();
340:
341: ITERATOR_BOUND_P (idecl) = 0;
342: /* we can reset rtl since there is not chance that this expansion */
343: /* would be superceded by a higher level one */
344: if (top_level_ixpansion_p ())
345: DECL_RTL (idecl) = 0;
346: if (end_note)
347: *end_note = emit_note (0, NOTE_INSN_DELETED);
348: }
349:
350: /* Return true if we are not currently inside a "({...})" construct. */
351:
352: static int
353: top_level_ixpansion_p ()
354: {
355: return iter_stack == 0;
356: }
357:
358: /* Given two chains of iter_stack_nodes,
359: append the nodes in X into Y. */
360:
361: static void
362: isn_append (x, y)
363: struct iter_stack_node *x, *y;
364: {
365: if (x->first == 0)
366: return;
367:
368: if (y->first == 0)
369: {
370: y->first = x->first;
371: y->last = x->last;
372: }
373: else
374: {
375: y->last->next = x->first;
376: y->last = x->last;
377: }
378: }
379:
380: /** Make X empty **/
381:
382: #define ISN_ZERO(X) (X).first=(X).last=0
383:
384: /* Move the ixpansions in sublevel_ixpansions into the current
385: node on the iter_stack, or discard them if the iter_stack is empty.
386: We do this at the end of a statement. */
387:
388: static void
389: istack_sublevel_to_current ()
390: {
391: /* At the top level we can throw away sublevel's expansions **/
392: /* because there is nobody above us to ask for a cleanup **/
393: if (iter_stack != 0)
394: /** Merging with empty sublevel list is a no-op **/
395: if (sublevel_ixpansions.last)
396: isn_append (&sublevel_ixpansions, iter_stack);
397:
398: if (iter_stack == 0)
399: obstack_free (&ixp_obstack, ixp_firstobj);
400:
401: ISN_ZERO (sublevel_ixpansions);
402: }
403:
404: /* Push a new node on the iter_stack, when we enter a ({...}). */
405:
406: void
407: push_iterator_stack ()
408: {
409: struct iter_stack_node *new_top
410: = (struct iter_stack_node*)
411: obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
412:
413: new_top->first = 0;
414: new_top->last = 0;
415: new_top->next = iter_stack;
416: iter_stack = new_top;
417: }
418:
419: /* Pop iter_stack, moving the ixpansions in the node being popped
420: into sublevel_ixpansions. */
421:
422: void
423: pop_iterator_stack ()
424: {
425: if (iter_stack == 0)
426: abort ();
427:
428: isn_append (iter_stack, &sublevel_ixpansions);
429: /** Pop current level node: */
430: iter_stack = iter_stack->next;
431: }
432:
433:
434: /* Record an iterator expansion ("ixpansion") for IDECL.
435: The remaining paramters are the notes in the loop entry
436: and exit rtl. */
437:
438: static void
439: add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
440: tree idecl;
441: rtx pro_start, pro_end, epi_start, epi_end;
442: {
443: struct ixpansion* newix;
444:
445: /* Do nothing if we are not inside "({...})",
446: as in that case this expansion can't need subsequent RTL modification. */
447: if (iter_stack == 0)
448: return;
449:
450: newix = (struct ixpansion*) obstack_alloc (&ixp_obstack,
451: sizeof (struct ixpansion));
452: newix->ixdecl = idecl;
453: newix->ixprologue_start = pro_start;
454: newix->ixprologue_end = pro_end;
455: newix->ixepilogue_start = epi_start;
456: newix->ixepilogue_end = epi_end;
457:
458: newix->next = iter_stack->first;
459: iter_stack->first = newix;
460: if (iter_stack->last == 0)
461: iter_stack->last = newix;
462: }
463:
464: /* Delete the RTL for all ixpansions for iterator IDECL
465: in our sublevels. We do this when we make a larger
466: containing expansion for IDECL. */
467:
468: static void
469: delete_ixpansion (idecl)
470: tree idecl;
471: {
472: struct ixpansion* previx = 0, *ix;
473:
474: for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
475: if (ix->ixdecl == idecl)
476: {
477: /** zero means that this is a mark for FOR -- **/
478: /** we do not delete anything, just issue an error. **/
479:
480: if (ix->ixprologue_start == 0)
481: error_with_decl (idecl,
482: "`for (%s)' appears within implicit iteration");
483: else
484: {
485: rtx insn;
486: /* We delete all insns, including notes because leaving loop */
487: /* notes and barriers produced by iterator expansion would */
488: /* be misleading to other phases */
489:
490: for (insn = NEXT_INSN (ix->ixprologue_start);
491: insn != ix->ixprologue_end;
492: insn = NEXT_INSN (insn))
493: delete_insn (insn);
494: for (insn = NEXT_INSN (ix->ixepilogue_start);
495: insn != ix->ixepilogue_end;
496: insn = NEXT_INSN (insn))
497: delete_insn (insn);
498: }
499:
500: /* Delete this ixpansion from sublevel_ixpansions. */
501: if (previx)
502: previx->next = ix->next;
503: else
504: sublevel_ixpansions.first = ix->next;
505: if (sublevel_ixpansions.last == ix)
506: sublevel_ixpansions.last = previx;
507: }
508: else
509: previx = ix;
510: }
511:
512: #ifdef DEBUG_ITERATORS
513:
514: /* The functions below are for use from source level debugger.
515: They print short forms of iterator lists and the iterator stack. */
516:
517: /* Print the name of the iterator D. */
518:
519: void
520: prdecl (d)
521: tree d;
522: {
523: if (d)
524: {
525: if (TREE_CODE (d) == VAR_DECL)
526: {
527: tree tname = DECL_NAME (d);
528: char *dname = IDENTIFIER_POINTER (tname);
529: fprintf (stderr, dname);
530: }
531: else
532: fprintf (stderr, "<<Not a Decl!!!>>");
533: }
534: else
535: fprintf (stderr, "<<NULL!!>>");
536: }
537:
538: /* Print Iterator List -- names only */
539:
540: tree
541: pil (head)
542: tree head;
543: {
544: tree current, next;
545: for (current = head; current; current = next)
546: {
547: tree node = TREE_VALUE (current);
548: prdecl (node);
549: next = TREE_CHAIN (current);
550: if (next) fprintf (stderr, ",");
551: }
552: fprintf (stderr, "\n");
553: }
554:
555: /* Print IXpansion List */
556:
557: struct ixpansion *
558: pixl (head)
559: struct ixpansion *head;
560: {
561: struct ixpansion *current, *next;
562: fprintf (stderr, "> ");
563: if (head == 0)
564: fprintf (stderr, "(empty)");
565:
566: for (current=head; current; current = next)
567: {
568: tree node = current->ixdecl;
569: prdecl (node);
570: next = current->next;
571: if (next)
572: fprintf (stderr, ",");
573: }
574: fprintf (stderr, "\n");
575: return head;
576: }
577:
578: /* Print Iterator Stack*/
579:
580: void
581: pis ()
582: {
583: struct iter_stack_node *stack_node;
584:
585: fprintf (stderr, "--SubLevel: ");
586: pixl (sublevel_ixpansions.first);
587: fprintf (stderr, "--Stack:--\n");
588: for (stack_node = iter_stack;
589: stack_node;
590: stack_node = stack_node->next)
591: pixl (stack_node->first);
592: }
593:
594: #endif /* DEBUG_ITERATORS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.