gcc/c-iterate.c

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