gcc/c-iterate.c

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