Return to c-iterate.c CVS log

Up to [GCC 2.x] / gcc

Annotation of gcc/c-iterate.c, revision 1.1.1.2

1.1       root        1: /* Build expressions with type checking for C compiler.
1.1.1.2 ! root        2:    Copyright (C) 1987, 1988, 1989, 1992, 1993 Free Software Foundation, Inc.
1.1       root        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.  */
1.1.1.2 ! root      212:       if (value_member (exp, save_exprs))
        !           213:        return list;
        !           214: 
1.1       root      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: {
1.1.1.2 ! root      281:   tree expr;
        !           282: 
1.1       root      283:   /* Force the save_expr in DECL_INITIAL to be calculated
                    284:      if it hasn't been calculated yet.  */
1.1.1.2 ! root      285:   expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
1.1       root      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);
1.1.1.2 ! root      292: 
1.1       root      293:   /* Initialize counter.  */
1.1.1.2 ! root      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);
1.1       root      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);
1.1.1.2 ! root      335:   incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
        !           336:   TREE_SIDE_EFFECTS (incr) = 1;
        !           337:   expand_expr (incr, const0_rtx, VOIDmode, 0);
1.1       root      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.