![[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.
1.1.1.2 root 2: Copyright (C) 1987, 1988, 1989, 1992, 1993 Free Software Foundation, Inc.
1.1 root 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
1.1.1.3 ! root 18: the Free Software Foundation, 59 Temple Place - Suite 330,
! 19: Boston, MA 02111-1307, USA. */
1.1 root 20:
21:
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. */
25:
26: #include "config.h"
27: #include <stdio.h>
28: #include "tree.h"
29: #include "c-tree.h"
30: #include "flags.h"
31: #include "obstack.h"
32: #include "rtl.h"
33:
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 ();
42:
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;
47:
48: /*
49: KEEPING TRACK OF EXPANSIONS
50:
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.
58:
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:
66:
67: -- On "({" a new node is added to the stack by PUSH_ITERATOR_STACK.
68: The sublevel list is not changed at this point.
69:
70: -- On "})" the list for the current level is appended to the sublevel
71: list.
72:
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. */
79:
80: struct ixpansion
81: {
82: tree ixdecl; /* Iterator decl */
83: rtx ixprologue_start; /* First insn of epilogue. NULL means */
84: /* explicit (FOR) expansion*/
85: rtx ixprologue_end;
86: rtx ixepilogue_start;
87: rtx ixepilogue_end;
88: struct ixpansion *next; /* Next in the list */
89: };
90:
91: struct iter_stack_node
92: {
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 */
96: };
97:
98: struct iter_stack_node *iter_stack;
99:
100: struct iter_stack_node sublevel_ixpansions;
101:
102: /* During collect_iterators, a list of SAVE_EXPRs already scanned. */
103: static tree save_exprs;
104:
105: /* Initialize our obstack once per compilation. */
106:
107: void
108: init_iterators ()
109: {
110: gcc_obstack_init (&ixp_obstack);
111: ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0);
112: }
113:
114: /* Handle the start of an explicit `for' loop for iterator IDECL. */
115:
116: void
117: iterator_for_loop_start (idecl)
118: tree idecl;
119: {
120: ITERATOR_BOUND_P (idecl) = 1;
121: add_ixpansion (idecl, 0, 0, 0, 0);
122: iterator_loop_prologue (idecl, 0, 0);
123: }
124:
125: /* Handle the end of an explicit `for' loop for iterator IDECL. */
126:
127: void
128: iterator_for_loop_end (idecl)
129: tree idecl;
130: {
131: iterator_loop_epilogue (idecl, 0, 0);
132: ITERATOR_BOUND_P (idecl) = 0;
133: }
134:
135: /*
136: ITERATOR RTL EXPANSIONS
137:
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.
141:
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. */
144:
145: /* Expand a statement STMT, possibly containing iterator usage, into RTL. */
146:
147: void
148: iterator_expand (stmt)
149: tree stmt;
150: {
151: tree iter_list;
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 ();
156: }
157:
158:
159: static void
160: expand_stmt_with_iterators_1 (stmt, iter_list)
161: tree stmt, iter_list;
162: {
163: if (iter_list == 0)
164: expand_expr_stmt (stmt);
165: else
166: {
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;
170:
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);
174:
175: /** Delete all inner expansions based on current_iterator **/
176: /** before adding the outer one. **/
177:
178: delete_ixpansion (current_iterator);
179: add_ixpansion (current_iterator, p_start, p_end, e_start, e_end);
180: }
181: }
182:
183:
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. */
187:
188: static tree
189: collect_iterators (exp, list)
190: tree exp, list;
191: {
192: if (exp == 0) return list;
193:
194: switch (TREE_CODE (exp))
195: {
196: case VAR_DECL:
197: if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp))
198: return list;
199: if (value_member (exp, list))
200: return list;
201: return tree_cons (NULL_TREE, exp, list);
202:
203: case TREE_LIST:
204: {
205: tree tail;
206: for (tail = exp; tail; tail = TREE_CHAIN (tail))
207: list = collect_iterators (TREE_VALUE (tail), list);
208: return list;
209: }
210:
211: case SAVE_EXPR:
212: /* In each scan, scan a given save_expr only once. */
1.1.1.2 root 213: if (value_member (exp, save_exprs))
214: return list;
215:
1.1 root 216: save_exprs = tree_cons (NULL_TREE, exp, save_exprs);
217: return collect_iterators (TREE_OPERAND (exp, 0), list);
218:
219: /* we do not automatically iterate blocks -- one must */
220: /* use the FOR construct to do that */
221:
222: case BLOCK:
223: return list;
224:
225: default:
226: switch (TREE_CODE_CLASS (TREE_CODE (exp)))
227: {
228: case '1':
229: return collect_iterators (TREE_OPERAND (exp, 0), list);
230:
231: case '2':
232: case '<':
233: return collect_iterators (TREE_OPERAND (exp, 0),
234: collect_iterators (TREE_OPERAND (exp, 1),
235: list));
236:
237: case 'e':
238: case 'r':
239: {
240: int num_args = tree_code_length[(int) TREE_CODE (exp)];
241: int i;
242:
243: /* Some tree codes have RTL, not trees, as operands. */
244: switch (TREE_CODE (exp))
245: {
246: case CALL_EXPR:
247: num_args = 2;
248: break;
249: case METHOD_CALL_EXPR:
250: num_args = 3;
251: break;
252: case WITH_CLEANUP_EXPR:
253: num_args = 1;
254: break;
255: case RTL_EXPR:
256: return list;
257: }
258:
259: for (i = 0; i < num_args; i++)
260: list = collect_iterators (TREE_OPERAND (exp, i), list);
261: return list;
262: }
263: default:
264: return list;
265: }
266: }
267: }
268:
269: /* Emit rtl for the start of a loop for iterator IDECL.
270:
271: If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
272:
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. */
276:
277: static void
278: iterator_loop_prologue (idecl, start_note, end_note)
279: tree idecl;
280: rtx *start_note, *end_note;
281: {
1.1.1.2 root 282: tree expr;
283:
1.1 root 284: /* Force the save_expr in DECL_INITIAL to be calculated
285: if it hasn't been calculated yet. */
1.1.1.2 root 286: expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
1.1 root 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);
1.1.1.2 root 293:
1.1 root 294: /* Initialize counter. */
1.1.1.2 root 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);
1.1 root 298:
299: expand_start_loop_continue_elsewhere (1);
300:
301: ITERATOR_BOUND_P (idecl) = 1;
302:
303: if (end_note)
304: *end_note = emit_note (0, NOTE_INSN_DELETED);
305: }
306:
307: /* Similar to the previous function, but for the end of the loop.
308:
309: DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
310: described below.
311:
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
318: rtl.
319:
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). */
324:
325: static void
326: iterator_loop_epilogue (idecl, start_note, end_note)
327: tree idecl;
328: rtx *start_note, *end_note;
329: {
330: tree test, incr;
331:
332: if (start_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);
1.1.1.2 root 336: incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
337: TREE_SIDE_EFFECTS (incr) = 1;
338: expand_expr (incr, const0_rtx, VOIDmode, 0);
1.1 root 339: test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
340: expand_exit_loop_if_false (0, test);
341: expand_end_loop ();
342:
343: ITERATOR_BOUND_P (idecl) = 0;
344: /* we can reset rtl since there is not chance that this expansion */
1.1.1.3 ! root 345: /* would be superseded by a higher level one */
1.1 root 346: if (top_level_ixpansion_p ())
347: DECL_RTL (idecl) = 0;
348: if (end_note)
349: *end_note = emit_note (0, NOTE_INSN_DELETED);
350: }
351:
352: /* Return true if we are not currently inside a "({...})" construct. */
353:
354: static int
355: top_level_ixpansion_p ()
356: {
357: return iter_stack == 0;
358: }
359:
360: /* Given two chains of iter_stack_nodes,
361: append the nodes in X into Y. */
362:
363: static void
364: isn_append (x, y)
365: struct iter_stack_node *x, *y;
366: {
367: if (x->first == 0)
368: return;
369:
370: if (y->first == 0)
371: {
372: y->first = x->first;
373: y->last = x->last;
374: }
375: else
376: {
377: y->last->next = x->first;
378: y->last = x->last;
379: }
380: }
381:
382: /** Make X empty **/
383:
384: #define ISN_ZERO(X) (X).first=(X).last=0
385:
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. */
389:
390: static void
391: istack_sublevel_to_current ()
392: {
393: /* At the top level we can throw away sublevel's expansions **/
394: /* because there is nobody above us to ask for a cleanup **/
395: if (iter_stack != 0)
396: /** Merging with empty sublevel list is a no-op **/
397: if (sublevel_ixpansions.last)
398: isn_append (&sublevel_ixpansions, iter_stack);
399:
400: if (iter_stack == 0)
401: obstack_free (&ixp_obstack, ixp_firstobj);
402:
403: ISN_ZERO (sublevel_ixpansions);
404: }
405:
406: /* Push a new node on the iter_stack, when we enter a ({...}). */
407:
408: void
409: push_iterator_stack ()
410: {
411: struct iter_stack_node *new_top
412: = (struct iter_stack_node*)
413: obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
414:
415: new_top->first = 0;
416: new_top->last = 0;
417: new_top->next = iter_stack;
418: iter_stack = new_top;
419: }
420:
421: /* Pop iter_stack, moving the ixpansions in the node being popped
422: into sublevel_ixpansions. */
423:
424: void
425: pop_iterator_stack ()
426: {
427: if (iter_stack == 0)
428: abort ();
429:
430: isn_append (iter_stack, &sublevel_ixpansions);
431: /** Pop current level node: */
432: iter_stack = iter_stack->next;
433: }
434:
435:
436: /* Record an iterator expansion ("ixpansion") for IDECL.
1.1.1.3 ! root 437: The remaining parameters are the notes in the loop entry
1.1 root 438: and exit rtl. */
439:
440: static void
441: add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
442: tree idecl;
443: rtx pro_start, pro_end, epi_start, epi_end;
444: {
445: struct ixpansion* newix;
446:
447: /* Do nothing if we are not inside "({...})",
448: as in that case this expansion can't need subsequent RTL modification. */
449: if (iter_stack == 0)
450: return;
451:
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;
459:
460: newix->next = iter_stack->first;
461: iter_stack->first = newix;
462: if (iter_stack->last == 0)
463: iter_stack->last = newix;
464: }
465:
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. */
469:
470: static void
471: delete_ixpansion (idecl)
472: tree idecl;
473: {
474: struct ixpansion* previx = 0, *ix;
475:
476: for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
477: if (ix->ixdecl == idecl)
478: {
479: /** zero means that this is a mark for FOR -- **/
480: /** we do not delete anything, just issue an error. **/
481:
482: if (ix->ixprologue_start == 0)
483: error_with_decl (idecl,
484: "`for (%s)' appears within implicit iteration");
485: else
486: {
487: rtx insn;
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 */
491:
492: for (insn = NEXT_INSN (ix->ixprologue_start);
493: insn != ix->ixprologue_end;
494: insn = NEXT_INSN (insn))
495: delete_insn (insn);
496: for (insn = NEXT_INSN (ix->ixepilogue_start);
497: insn != ix->ixepilogue_end;
498: insn = NEXT_INSN (insn))
499: delete_insn (insn);
500: }
501:
502: /* Delete this ixpansion from sublevel_ixpansions. */
503: if (previx)
504: previx->next = ix->next;
505: else
506: sublevel_ixpansions.first = ix->next;
507: if (sublevel_ixpansions.last == ix)
508: sublevel_ixpansions.last = previx;
509: }
510: else
511: previx = ix;
512: }
513:
514: #ifdef DEBUG_ITERATORS
515:
516: /* The functions below are for use from source level debugger.
517: They print short forms of iterator lists and the iterator stack. */
518:
519: /* Print the name of the iterator D. */
520:
521: void
522: prdecl (d)
523: tree d;
524: {
525: if (d)
526: {
527: if (TREE_CODE (d) == VAR_DECL)
528: {
529: tree tname = DECL_NAME (d);
530: char *dname = IDENTIFIER_POINTER (tname);
531: fprintf (stderr, dname);
532: }
533: else
534: fprintf (stderr, "<<Not a Decl!!!>>");
535: }
536: else
537: fprintf (stderr, "<<NULL!!>>");
538: }
539:
540: /* Print Iterator List -- names only */
541:
542: tree
543: pil (head)
544: tree head;
545: {
546: tree current, next;
547: for (current = head; current; current = next)
548: {
549: tree node = TREE_VALUE (current);
550: prdecl (node);
551: next = TREE_CHAIN (current);
552: if (next) fprintf (stderr, ",");
553: }
554: fprintf (stderr, "\n");
555: }
556:
557: /* Print IXpansion List */
558:
559: struct ixpansion *
560: pixl (head)
561: struct ixpansion *head;
562: {
563: struct ixpansion *current, *next;
564: fprintf (stderr, "> ");
565: if (head == 0)
566: fprintf (stderr, "(empty)");
567:
568: for (current=head; current; current = next)
569: {
570: tree node = current->ixdecl;
571: prdecl (node);
572: next = current->next;
573: if (next)
574: fprintf (stderr, ",");
575: }
576: fprintf (stderr, "\n");
577: return head;
578: }
579:
580: /* Print Iterator Stack*/
581:
582: void
583: pis ()
584: {
585: struct iter_stack_node *stack_node;
586:
587: fprintf (stderr, "--SubLevel: ");
588: pixl (sublevel_ixpansions.first);
589: fprintf (stderr, "--Stack:--\n");
590: for (stack_node = iter_stack;
591: stack_node;
592: stack_node = stack_node->next)
593: pixl (stack_node->first);
594: }
595:
596: #endif /* DEBUG_ITERATORS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.