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