gcc/c-iterate.c

   1 /* Build expressions with type checking for C compiler.
   2    Copyright (C) 1987, 88, 89, 92-97, 1998 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 "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 \f
  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
  68 struct  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
  79 struct 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
  86 struct iter_stack_node *iter_stack;
  87 struct 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).  */
  91 static struct obstack ixp_obstack;
  92 static char *ixp_firstobj;
  93
  94 /* During collect_iterators, a list of SAVE_EXPRs already scanned.  */
  95 static tree save_exprs;
  96
  97 static void expand_stmt_with_iterators_1 PROTO((tree, tree));
  98 static tree collect_iterators           PROTO((tree, tree));
  99 static void iterator_loop_prologue      PROTO((tree, rtx *, rtx *));
 100 static void iterator_loop_epilogue      PROTO((tree, rtx *, rtx *));
 101 static int top_level_ixpansion_p        PROTO((void));
 102 static void isn_append                  PROTO((struct iter_stack_node *,
 103                                                struct iter_stack_node *));
 104 static void istack_sublevel_to_current  PROTO((void));
 105 static void add_ixpansion               PROTO((tree, rtx, rtx, rtx, rtx));
 106 static void delete_ixpansion            PROTO((tree));
 107 \f
 108 /* Initialize our obstack once per compilation.  */
 109
 110 void
 111 init_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
 119 void
 120 iterator_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
 130 void
 131 iterator_for_loop_end (idecl)
 132      tree idecl;
 133 {
 134   iterator_loop_epilogue (idecl, 0, 0);
 135   ITERATOR_BOUND_P (idecl) = 0;
 136 }
 137 \f
 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
 150 void
 151 iterator_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
 162 static void
 163 expand_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
 191 static tree
 192 collect_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 \f
 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
 282 static void
 283 iterator_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
 331 static void
 332 iterator_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 \f
 360 /* Return true if we are not currently inside a "({...})" construct.  */
 361
 362 static int
 363 top_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
 371 static void
 372 isn_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 \f
 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
 398 static void
 399 istack_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
 416 void
 417 push_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
 432 void
 433 pop_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 \f
 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
 448 static void
 449 add_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
 478 static void
 479 delete_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 \f
 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
 529 void
 530 prdecl (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
 550 tree
 551 pil (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
 567 struct ixpansion *
 568 pixl (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
 590 void
 591 pis ()
 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 */