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