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