]>
Commit | Line | Data |
---|---|---|
41424fdd RS |
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" | |
e26d4611 RS |
30 | #include "obstack.h" |
31 | #include "rtl.h" | |
41424fdd RS |
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 (); | |
e26d4611 RS |
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; | |
41424fdd | 46 | \f |
e26d4611 RS |
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 | |
41424fdd | 80 | { |
e26d4611 RS |
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 | \f | |
101 | /* Initialize our obstack once per compilation. */ | |
41424fdd RS |
102 | |
103 | void | |
e26d4611 | 104 | init_iterators () |
41424fdd | 105 | { |
e26d4611 RS |
106 | gcc_obstack_init (&ixp_obstack); |
107 | ixp_firstobj = (char *) obstack_alloc (&ixp_obstack, 0); | |
41424fdd RS |
108 | } |
109 | ||
e26d4611 RS |
110 | /* Handle the start of an explicit `for' loop for iterator IDECL. */ |
111 | ||
41424fdd | 112 | void |
e26d4611 | 113 | iterator_for_loop_start (idecl) |
41424fdd RS |
114 | tree idecl; |
115 | { | |
e26d4611 | 116 | ITERATOR_BOUND_P (idecl) = 1; |
41424fdd | 117 | add_ixpansion (idecl, 0, 0, 0, 0); |
e26d4611 | 118 | iterator_loop_prologue (idecl, 0, 0); |
41424fdd RS |
119 | } |
120 | ||
e26d4611 | 121 | /* Handle the end of an explicit `for' loop for iterator IDECL. */ |
41424fdd | 122 | |
e26d4611 RS |
123 | void |
124 | iterator_for_loop_end (idecl) | |
125 | tree idecl; | |
126 | { | |
127 | iterator_loop_epilogue (idecl, 0, 0); | |
128 | ITERATOR_BOUND_P (idecl) = 0; | |
129 | } | |
130 | \f | |
41424fdd RS |
131 | /* |
132 | ITERATOR DECLS | |
133 | ||
134 | Iterators are implemented as integer decls with a special flag set | |
135 | (rms's idea). This makes eliminates the need for special type | |
136 | checking. The flag is accesed using the ITERATOR_P macro. Each | |
137 | iterator's limit is saved as a decl with a special name. The decl is | |
138 | initialized with the limit value -- this way we get all the necessary | |
139 | semantical processing for free by calling finish decl. We might still | |
140 | eliminate that decl later -- it takes up time and space and, more | |
141 | importantly, produces strange error messages when something is wrong | |
142 | with the initializing expresison. */ | |
143 | ||
144 | tree | |
145 | build_iterator_decl (id, limit) | |
146 | tree id, limit; | |
147 | { | |
148 | tree type = integer_type_node, lim_decl; | |
149 | tree t1, t2, t3; | |
150 | tree start_node, limit_node, step_node; | |
151 | tree decl; | |
152 | ||
153 | if (limit) | |
154 | { | |
155 | limit_node = save_expr (limit); | |
156 | SAVE_EXPR_CONTEXT (limit_node) = current_function_decl; | |
157 | } | |
158 | else | |
159 | abort (); | |
160 | lim_decl = build_limit_decl (id, limit_node); | |
161 | push_obstacks_nochange (); | |
162 | decl = build_decl (VAR_DECL, id, type); | |
163 | ITERATOR_P (decl) = 1; | |
164 | ITERATOR_LIMIT (decl) = lim_decl; | |
165 | finish_decl (pushdecl (decl), 0, 0); | |
166 | return decl; | |
167 | } | |
168 | \f | |
169 | /* | |
170 | ITERATOR RTL EXPANSIONS | |
171 | ||
e26d4611 RS |
172 | Expanding simple statements with iterators is straightforward: |
173 | collect the list of all free iterators in the statement, and | |
174 | generate a loop for each of them. | |
175 | ||
176 | An iterator is "free" if it has not been "bound" by a FOR | |
177 | operator. The DECL_RTL of the iterator is the loop counter. */ | |
178 | ||
179 | /* Expand a statement STMT, possibly containing iterator usage, into RTL. */ | |
41424fdd RS |
180 | |
181 | void | |
182 | iterator_expand (stmt) | |
183 | tree stmt; | |
184 | { | |
185 | tree iter_list = collect_iterators (stmt, NULL_TREE); | |
186 | expand_stmt_with_iterators_1 (stmt, iter_list); | |
187 | istack_sublevel_to_current (); | |
188 | } | |
189 | ||
190 | ||
191 | static void | |
192 | expand_stmt_with_iterators_1 (stmt, iter_list) | |
193 | tree stmt, iter_list; | |
194 | { | |
195 | if (iter_list == 0) | |
196 | expand_expr_stmt (stmt); | |
197 | else | |
198 | { | |
199 | tree current_iterator = TREE_VALUE (iter_list); | |
200 | tree iter_list_tail = TREE_CHAIN (iter_list); | |
201 | rtx p_start, p_end, e_start, e_end; | |
202 | ||
203 | iterator_loop_prologue (current_iterator, &p_start, &p_end); | |
204 | expand_stmt_with_iterators_1 (stmt, iter_list_tail); | |
205 | iterator_loop_epilogue (current_iterator, &e_start, &e_end); | |
206 | ||
207 | /** Delete all inner expansions based on current_iterator **/ | |
208 | /** before adding the outer one. **/ | |
209 | ||
210 | delete_ixpansion (current_iterator); | |
211 | add_ixpansion (current_iterator, p_start, p_end, e_start, e_end); | |
212 | } | |
213 | } | |
214 | ||
215 | ||
e26d4611 RS |
216 | /* Return a list containing all the free (i.e. not bound by a |
217 | containing `for' statement) iterators mentioned in EXP, plus those | |
218 | in LIST. Do not add duplicate entries to the list. */ | |
41424fdd RS |
219 | |
220 | static tree | |
221 | collect_iterators (exp, list) | |
222 | tree exp, list; | |
223 | { | |
224 | if (exp == 0) return list; | |
225 | ||
226 | switch (TREE_CODE (exp)) | |
227 | { | |
228 | case VAR_DECL: | |
229 | if (! ITERATOR_P (exp) || ITERATOR_BOUND_P (exp)) | |
230 | return list; | |
231 | if (value_member (exp, list)) | |
232 | return list; | |
233 | return tree_cons (NULL_TREE, exp, list); | |
234 | ||
235 | case TREE_LIST: | |
236 | { | |
237 | tree tail; | |
238 | for (tail = exp; tail; tail = TREE_CHAIN (tail)) | |
239 | list = collect_iterators (TREE_VALUE (tail), list); | |
240 | return list; | |
241 | } | |
242 | ||
243 | /* we do not automatically iterate blocks -- one must */ | |
244 | /* use the FOR construct to do that */ | |
245 | ||
246 | case BLOCK: | |
247 | return list; | |
248 | ||
249 | default: | |
250 | switch (TREE_CODE_CLASS (code)) | |
251 | { | |
252 | case '1': | |
253 | case '2': | |
254 | case '<': | |
255 | case 'e': | |
256 | case 'r': | |
257 | { | |
258 | int num_args = tree_code_length[code]; | |
259 | int i; | |
260 | the_list = (tree) 0; | |
261 | for (i = 0; i < num_args; i++) | |
262 | list = collect_iterators (TREE_OPERAND (exp, i), list); | |
263 | return list; | |
264 | } | |
265 | } | |
266 | } | |
267 | } | |
268 | \f | |
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 | { | |
282 | /* Force the save_expr in DECL_INITIAL to be calculated | |
283 | if it hasn't been calculated yet. */ | |
284 | expand_expr (DECL_INITIAL (idecl), 0, VOIDmode, 0); | |
285 | ||
286 | if (DECL_RTL (idecl) == 0) | |
287 | expand_decl (idecl); | |
288 | ||
289 | if (start_note) | |
290 | *start_note = emit_note (0, NOTE_INSN_DELETED); | |
291 | /* Initialize counter. */ | |
292 | expand_expr (build_modify_expr (idecl, NOP_EXPR, integer_zero_node), | |
293 | 0, VOIDmode, 0); | |
294 | ||
295 | expand_start_loop_continue_elsewhere (1); | |
296 | ||
297 | ITERATOR_BOUND_P (idecl) = 1; | |
298 | ||
299 | if (end_note) | |
300 | *end_note = emit_note (0, NOTE_INSN_DELETED); | |
301 | } | |
302 | ||
303 | /* Similar to the previous function, but for the end of the loop. | |
304 | ||
305 | DECL_RTL is zeroed unless we are inside "({...})". The reason for that is | |
306 | described below. | |
307 | ||
e26d4611 RS |
308 | When we create two (or more) loops based on the same IDECL, and |
309 | both inside the same "({...})" construct, we must be prepared to | |
310 | delete both of the loops and create a single one on the level | |
311 | above, i.e. enclosing the "({...})". The new loop has to use the | |
312 | same counter rtl because the references to the iterator decl | |
313 | (IDECL) have already been expanded as references to the counter | |
314 | rtl. | |
41424fdd RS |
315 | |
316 | It is incorrect to use the same counter reg in different functions, | |
317 | and it is desirable to use different counters in disjoint loops | |
e26d4611 RS |
318 | when we know there's no need to combine them (because then they can |
319 | get allocated separately). */ | |
41424fdd RS |
320 | |
321 | static void | |
322 | iterator_loop_epilogue (idecl, start_note, end_note) | |
323 | tree idecl; | |
324 | rtx *start_note, *end_note; | |
325 | { | |
326 | tree test, incr; | |
327 | ||
328 | if (start_note) | |
329 | *start_note = emit_note (0, NOTE_INSN_DELETED); | |
330 | expand_loop_continue_here (); | |
331 | incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0); | |
332 | expand_expr (build_modify_expr (idecl, NOP_EXPR, incr)); | |
333 | test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0); | |
334 | expand_exit_loop_if_false (0, test); | |
335 | expand_end_loop (); | |
336 | ||
337 | ITERATOR_BOUND_P (idecl) = 0; | |
338 | /* we can reset rtl since there is not chance that this expansion */ | |
339 | /* would be superceded by a higher level one */ | |
340 | if (top_level_ixpansion_p ()) | |
341 | DECL_RTL (idecl) = 0; | |
342 | if (end_note) | |
343 | *end_note = emit_note (0, NOTE_INSN_DELETED); | |
344 | } | |
345 | \f | |
e26d4611 | 346 | /* Return true if we are not currently inside a "({...})" construct. */ |
41424fdd RS |
347 | |
348 | static int | |
349 | top_level_ixpansion_p () | |
350 | { | |
351 | return iter_stack == 0; | |
352 | } | |
353 | ||
354 | /* Given two chains of iter_stack_nodes, | |
355 | append the nodes in X into Y. */ | |
356 | ||
357 | static void | |
358 | isn_append (x, y) | |
359 | struct iter_stack_node *x, *y; | |
360 | { | |
361 | if (x->first == 0) | |
362 | return; | |
363 | ||
364 | if (y->first == 0) | |
365 | { | |
366 | y->first = x->first; | |
367 | y->last = x->last; | |
368 | } | |
369 | else | |
370 | { | |
371 | y->last->next = x->first; | |
372 | y->last = x->last; | |
373 | } | |
374 | } | |
375 | ||
376 | /** Make X empty **/ | |
377 | ||
378 | #define ISN_ZERO(X) (X).first=(X).last=0 | |
379 | \f | |
380 | /* Move the ixpansions in sublevel_ixpansions into the current | |
381 | node on the iter_stack, or discard them if the iter_stack is empty. | |
382 | We do this at the end of a statement. */ | |
383 | ||
384 | static void | |
385 | istack_sublevel_to_current () | |
386 | { | |
387 | /* At the top level we can throw away sublevel's expansions **/ | |
388 | /* because there is nobody above us to ask for a cleanup **/ | |
389 | if (iter_stack != 0) | |
390 | /** Merging with empty sublevel list is a no-op **/ | |
391 | if (sublevel_ixpansions.last) | |
392 | isn_append (&sublevel_ixpansions, iter_stack); | |
393 | ||
394 | if (iter_stack == 0) | |
395 | obstack_free (&ixp_obstack, ixp_firstobj); | |
396 | ||
397 | ISN_ZERO (sublevel_ixpansions); | |
398 | } | |
399 | ||
400 | /* Push a new node on the iter_stack, when we enter a ({...}). */ | |
401 | ||
402 | void | |
403 | push_iterator_stack () | |
404 | { | |
405 | struct iter_stack_node *new_top | |
406 | = (struct iter_stack_node*) | |
407 | obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node)); | |
408 | ||
409 | new_top->first = 0; | |
410 | new_top->last = 0; | |
411 | new_top->next = iter_stack; | |
412 | iter_stack = new_top; | |
413 | } | |
414 | ||
415 | /* Pop iter_stack, moving the ixpansions in the node being popped | |
416 | into sublevel_ixpansions. */ | |
417 | ||
418 | void | |
419 | pop_iterator_stack () | |
420 | { | |
421 | if (iter_stack == 0) | |
422 | abort (); | |
423 | ||
424 | isn_append (iter_stack, &sublevel_ixpansions); | |
425 | /** Pop current level node: */ | |
426 | iter_stack = iter_stack->next; | |
427 | } | |
428 | \f | |
429 | ||
430 | /* Record an iterator expansion ("ixpansion") for IDECL. | |
431 | The remaining paramters are the notes in the loop entry | |
432 | and exit rtl. */ | |
433 | ||
434 | static void | |
435 | add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end) | |
436 | tree idecl; | |
437 | rtx pro_start, pro_end, epi_start, epi_end; | |
438 | { | |
439 | struct ixpansion* newix; | |
440 | ||
441 | /* Do nothing if we are not inside "({...})", | |
442 | as in that case this expansion can't need subsequent RTL modification. */ | |
443 | if (iter_stack == 0) | |
444 | return; | |
445 | ||
446 | newix = (struct ixpansion*) obstack_alloc (&ixp_obstack, | |
447 | sizeof (struct ixpansion)); | |
448 | newix->ixdecl = idecl; | |
449 | newix->ixprologue_start = pro_start; | |
450 | newix->ixprologue_end = pro_end; | |
451 | newix->ixepilogue_start = epi_start; | |
452 | newix->ixepilogue_end = epi_end; | |
453 | ||
454 | newix->next = iter_stack->first; | |
455 | iter_stack->first = newix; | |
456 | if (iter_stack->last == 0) | |
457 | iter_stack->last = newix; | |
458 | } | |
459 | ||
460 | /* Delete the RTL for all ixpansions for iterator IDECL | |
461 | in our sublevels. We do this when we make a larger | |
462 | containing expansion for IDECL. */ | |
463 | ||
464 | static void | |
465 | delete_ixpansion (idecl) | |
466 | tree idecl; | |
467 | { | |
468 | struct ixpansion* previx = 0, *ix; | |
469 | ||
470 | for (ix = sublevel_ixpansions.first; ix; ix = ix->next) | |
471 | if (ix->ixdecl == idecl) | |
472 | { | |
473 | /** zero means that this is a mark for FOR -- **/ | |
474 | /** we do not delete anything, just issue an error. **/ | |
475 | ||
476 | if (ix->ixprologue_start == 0) | |
477 | error_with_decl (idecl, | |
478 | "`for (%s)' appears within implicit iteration") | |
479 | else | |
480 | { | |
481 | rtx insn; | |
482 | /* We delete all insns, including notes because leaving loop */ | |
483 | /* notes and barriers produced by iterator expansion would */ | |
484 | /* be misleading to other phases */ | |
485 | ||
486 | for (insn = NEXT_INSN (ix->ixprologue_start); | |
487 | insn != ix->ixprologue_end; | |
488 | insn = NEXT_INSN (insn)) | |
489 | delete_insn (insn); | |
490 | for (insn = NEXT_INSN (ix->ixepilogue_start); | |
491 | insn != ix->ixepilogue_end; | |
492 | insn = NEXT_INSN (insn)) | |
493 | delete_insn (insn); | |
494 | } | |
495 | ||
496 | /* Delete this ixpansion from sublevel_ixpansions. */ | |
497 | if (previx) | |
498 | previx->next = ix->next; | |
499 | else | |
500 | sublevel_ixpansions.first = ix->next; | |
501 | if (sublevel_ixpansions.last == ix) | |
502 | sublevel_ixpansions.last = previx; | |
503 | } | |
504 | else | |
505 | previx = ix; | |
506 | } | |
507 | \f | |
41424fdd RS |
508 | #ifdef DEBUG_ITERATORS |
509 | ||
e26d4611 RS |
510 | /* The functions below are for use from source level debugger. |
511 | They print short forms of iterator lists and the iterator stack. */ | |
512 | ||
513 | /* Print the name of the iterator D. */ | |
41424fdd | 514 | |
41424fdd | 515 | void |
e26d4611 RS |
516 | prdecl (d) |
517 | tree d; | |
41424fdd | 518 | { |
e26d4611 | 519 | if (d) |
41424fdd | 520 | { |
e26d4611 | 521 | if (TREE_CODE (d) == VAR_DECL) |
41424fdd | 522 | { |
e26d4611 | 523 | tree tname = DECL_NAME (d); |
41424fdd RS |
524 | char *dname = IDENTIFIER_POINTER (tname); |
525 | fprintf (stderr, dname); | |
526 | } | |
527 | else | |
528 | fprintf (stderr, "<<Not a Decl!!!>>"); | |
529 | } | |
530 | else | |
531 | fprintf (stderr, "<<NULL!!>>"); | |
532 | } | |
533 | ||
534 | /* Print Iterator List -- names only */ | |
535 | ||
536 | tree | |
537 | pil (head) | |
538 | tree head; | |
539 | { | |
540 | tree current, next; | |
e26d4611 | 541 | for (current = head; current; current = next) |
41424fdd RS |
542 | { |
543 | tree node = TREE_VALUE (current); | |
e26d4611 | 544 | prdecl (node); |
41424fdd RS |
545 | next = TREE_CHAIN (current); |
546 | if (next) fprintf (stderr, ","); | |
547 | } | |
548 | fprintf (stderr, "\n"); | |
549 | } | |
550 | ||
551 | /* Print IXpansion List */ | |
552 | ||
553 | struct ixpansion * | |
554 | pixl (head) | |
555 | struct ixpansion *head; | |
556 | { | |
557 | struct ixpansion *current, *next; | |
558 | fprintf (stderr, "> "); | |
559 | if (head == 0) | |
560 | fprintf (stderr, "(empty)"); | |
561 | ||
562 | for (current=head; current; current = next) | |
563 | { | |
564 | tree node = current->ixdecl; | |
e26d4611 | 565 | prdecl (node); |
41424fdd RS |
566 | next = current->next; |
567 | if (next) | |
568 | fprintf (stderr, ","); | |
569 | } | |
570 | fprintf (stderr, "\n"); | |
571 | return head; | |
572 | } | |
573 | ||
574 | /* Print Iterator Stack*/ | |
575 | ||
576 | void | |
577 | pis () | |
578 | { | |
579 | struct iter_stack_node *stack_node; | |
580 | ||
581 | fprintf (stderr, "--SubLevel: "); | |
582 | pixl (sublevel_ixpansions.first); | |
583 | fprintf (stderr, "--Stack:--\n"); | |
584 | for (stack_node = iter_stack; | |
585 | stack_node; | |
586 | stack_node = stack_node->next) | |
587 | pixl (stack_node->first); | |
588 | } | |
e26d4611 RS |
589 | |
590 | #endif /* DEBUG_ITERATORS */ |