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