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 \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               default:
 259                 break;
 260               }
 261
 262             for (i = 0; i < num_args; i++)
 263               list = collect_iterators (TREE_OPERAND (exp, i), list);
 264             return list;
 265           }
 266         default:
 267           return list;
 268         }
 269     }
 270 }
 271 \f
 272 /* Emit rtl for the start of a loop for iterator IDECL.
 273
 274    If necessary, create loop counter rtx and store it as DECL_RTL of IDECL.
 275
 276    The prologue normally starts and ends with notes, which are returned
 277    by this function in *START_NOTE and *END_NODE.
 278    If START_NOTE and END_NODE are 0, we don't make those notes.  */
 279
 280 static void
 281 iterator_loop_prologue (idecl, start_note, end_note)
 282      tree idecl;
 283      rtx *start_note, *end_note;
 284 {
 285   tree expr;
 286
 287   /* Force the save_expr in DECL_INITIAL to be calculated
 288      if it hasn't been calculated yet.  */
 289   expand_expr (DECL_INITIAL (idecl), const0_rtx, VOIDmode, 0);
 290
 291   if (DECL_RTL (idecl) == 0)
 292     expand_decl (idecl);
 293
 294   if (start_note)
 295     *start_note = emit_note (0, NOTE_INSN_DELETED);
 296
 297   /* Initialize counter.  */
 298   expr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, integer_zero_node);
 299   TREE_SIDE_EFFECTS (expr) = 1;
 300   expand_expr (expr, const0_rtx, VOIDmode, 0);
 301
 302   expand_start_loop_continue_elsewhere (1);
 303
 304   ITERATOR_BOUND_P (idecl) = 1;
 305
 306   if (end_note)
 307     *end_note = emit_note (0, NOTE_INSN_DELETED);
 308 }
 309
 310 /* Similar to the previous function, but for the end of the loop.
 311
 312    DECL_RTL is zeroed unless we are inside "({...})". The reason for that is
 313    described below.
 314
 315    When we create two (or more) loops based on the same IDECL, and
 316    both inside the same "({...})"  construct, we must be prepared to
 317    delete both of the loops and create a single one on the level
 318    above, i.e.  enclosing the "({...})". The new loop has to use the
 319    same counter rtl because the references to the iterator decl
 320    (IDECL) have already been expanded as references to the counter
 321    rtl.
 322
 323    It is incorrect to use the same counter reg in different functions,
 324    and it is desirable to use different counters in disjoint loops
 325    when we know there's no need to combine them (because then they can
 326    get allocated separately).  */
 327
 328 static void
 329 iterator_loop_epilogue (idecl, start_note, end_note)
 330      tree idecl;
 331      rtx *start_note, *end_note;
 332 {
 333   tree test, incr;
 334
 335   if (start_note)
 336     *start_note = emit_note (0, NOTE_INSN_DELETED);
 337   expand_loop_continue_here ();
 338   incr = build_binary_op (PLUS_EXPR, idecl, integer_one_node, 0);
 339   incr = build (MODIFY_EXPR, TREE_TYPE (idecl), idecl, incr);
 340   TREE_SIDE_EFFECTS (incr) = 1;
 341   expand_expr (incr, const0_rtx, VOIDmode, 0);
 342   test = build_binary_op (LT_EXPR, idecl, DECL_INITIAL (idecl), 0);
 343   expand_exit_loop_if_false (0, test);
 344   expand_end_loop ();
 345
 346   ITERATOR_BOUND_P (idecl) = 0;
 347   /* we can reset rtl since there is not chance that this expansion */
 348   /* would be superseded by a higher level one */
 349   /* but don't do this if the decl is static, since we need to share */
 350   /* the same decl in that case.  */
 351   if (top_level_ixpansion_p () && ! TREE_STATIC (idecl))
 352     DECL_RTL (idecl) = 0;
 353   if (end_note)
 354     *end_note = emit_note (0, NOTE_INSN_DELETED);
 355 }
 356 \f
 357 /* Return true if we are not currently inside a "({...})" construct.  */
 358
 359 static int
 360 top_level_ixpansion_p ()
 361 {
 362   return iter_stack == 0;
 363 }
 364
 365 /* Given two chains of iter_stack_nodes,
 366    append the nodes in X into Y.  */
 367
 368 static void
 369 isn_append (x, y)
 370      struct iter_stack_node *x, *y;
 371 {
 372   if (x->first == 0)
 373     return;
 374
 375   if (y->first == 0)
 376     {
 377       y->first = x->first;
 378       y->last  = x->last;
 379     }
 380   else
 381     {
 382       y->last->next = x->first;
 383       y->last = x->last;
 384     }
 385 }
 386
 387 /** Make X empty **/
 388
 389 #define ISN_ZERO(X) (X).first=(X).last=0
 390 \f
 391 /* Move the ixpansions in sublevel_ixpansions into the current
 392    node on the iter_stack, or discard them if the iter_stack is empty.
 393    We do this at the end of a statement.  */
 394
 395 static void
 396 istack_sublevel_to_current ()
 397 {
 398   /* At the top level we can throw away sublevel's expansions  **/
 399   /* because there is nobody above us to ask for a cleanup **/
 400   if (iter_stack != 0)
 401     /** Merging with empty sublevel list is a no-op **/
 402     if (sublevel_ixpansions.last)
 403       isn_append (&sublevel_ixpansions, iter_stack);
 404
 405   if (iter_stack == 0)
 406     obstack_free (&ixp_obstack, ixp_firstobj);
 407
 408   ISN_ZERO (sublevel_ixpansions);
 409 }
 410
 411 /* Push a new node on the iter_stack, when we enter a ({...}).  */
 412
 413 void
 414 push_iterator_stack ()
 415 {
 416   struct iter_stack_node *new_top
 417     = (struct iter_stack_node *)
 418       obstack_alloc (&ixp_obstack, sizeof (struct iter_stack_node));
 419
 420   new_top->first = 0;
 421   new_top->last = 0;
 422   new_top->next = iter_stack;
 423   iter_stack = new_top;
 424 }
 425
 426 /* Pop iter_stack, moving the ixpansions in the node being popped
 427    into sublevel_ixpansions.  */
 428
 429 void
 430 pop_iterator_stack ()
 431 {
 432   if (iter_stack == 0)
 433     abort ();
 434
 435   isn_append (iter_stack, &sublevel_ixpansions);
 436   /** Pop current level node: */
 437   iter_stack = iter_stack->next;
 438 }
 439 \f
 440
 441 /* Record an iterator expansion ("ixpansion") for IDECL.
 442    The remaining parameters are the notes in the loop entry
 443    and exit rtl.  */
 444
 445 static void
 446 add_ixpansion (idecl, pro_start, pro_end, epi_start, epi_end)
 447      tree idecl;
 448      rtx pro_start, pro_end, epi_start, epi_end;
 449 {
 450   struct ixpansion *newix;
 451
 452   /* Do nothing if we are not inside "({...})",
 453      as in that case this expansion can't need subsequent RTL modification.  */
 454   if (iter_stack == 0)
 455     return;
 456
 457   newix = (struct ixpansion *) obstack_alloc (&ixp_obstack,
 458                                               sizeof (struct ixpansion));
 459   newix->ixdecl = idecl;
 460   newix->ixprologue_start = pro_start;
 461   newix->ixprologue_end   = pro_end;
 462   newix->ixepilogue_start = epi_start;
 463   newix->ixepilogue_end   = epi_end;
 464
 465   newix->next = iter_stack->first;
 466   iter_stack->first = newix;
 467   if (iter_stack->last == 0)
 468     iter_stack->last = newix;
 469 }
 470
 471 /* Delete the RTL for all ixpansions for iterator IDECL
 472    in our sublevels.  We do this when we make a larger
 473    containing expansion for IDECL.  */
 474
 475 static void
 476 delete_ixpansion (idecl)
 477      tree idecl;
 478 {
 479   struct ixpansion *previx = 0, *ix;
 480
 481   for (ix = sublevel_ixpansions.first; ix; ix = ix->next)
 482     if (ix->ixdecl == idecl)
 483       {
 484         /** zero means that this is a mark for FOR -- **/
 485         /** we do not delete anything, just issue an error. **/
 486
 487         if (ix->ixprologue_start == 0)
 488           error_with_decl (idecl,
 489                            "`for (%s)' appears within implicit iteration");
 490         else
 491           {
 492             rtx insn;
 493             /* We delete all insns, including notes because leaving loop */
 494             /* notes and barriers produced by iterator expansion would */
 495             /* be misleading to other phases */
 496
 497             for (insn = NEXT_INSN (ix->ixprologue_start);
 498                  insn != ix->ixprologue_end;
 499                  insn = NEXT_INSN (insn))
 500               delete_insn (insn);
 501             for (insn = NEXT_INSN (ix->ixepilogue_start);
 502                  insn != ix->ixepilogue_end;
 503                  insn = NEXT_INSN (insn))
 504               delete_insn (insn);
 505           }
 506
 507         /* Delete this ixpansion from sublevel_ixpansions.  */
 508         if (previx)
 509           previx->next = ix->next;
 510         else
 511           sublevel_ixpansions.first = ix->next;
 512         if (sublevel_ixpansions.last == ix)
 513           sublevel_ixpansions.last = previx;
 514       }
 515     else
 516       previx = ix;
 517 }
 518 \f
 519 #ifdef DEBUG_ITERATORS
 520
 521 /* The functions below are for use from source level debugger.
 522    They print short forms of iterator lists and the iterator stack.  */
 523
 524 /* Print the name of the iterator D.  */
 525
 526 void
 527 prdecl (d)
 528      tree d;
 529 {
 530   if (d)
 531     {
 532       if (TREE_CODE (d) == VAR_DECL)
 533         {
 534           tree tname = DECL_NAME (d);
 535           char *dname = IDENTIFIER_POINTER (tname);
 536           fprintf (stderr, dname);
 537         }
 538       else
 539         fprintf (stderr, "<<Not a Decl!!!>>");
 540     }
 541   else
 542     fprintf (stderr, "<<NULL!!>>");
 543 }
 544
 545 /* Print Iterator List -- names only */
 546
 547 tree
 548 pil (head)
 549      tree head;
 550 {
 551   tree current, next;
 552   for (current = head; current; current = next)
 553     {
 554       tree node = TREE_VALUE (current);
 555       prdecl (node);
 556       next = TREE_CHAIN (current);
 557       if (next) fprintf (stderr, ",");
 558     }
 559   fprintf (stderr, "\n");
 560 }
 561
 562 /* Print IXpansion List */
 563
 564 struct ixpansion *
 565 pixl (head)
 566      struct ixpansion *head;
 567 {
 568   struct ixpansion *current, *next;
 569   fprintf (stderr, "> ");
 570   if (head == 0)
 571     fprintf (stderr, "(empty)");
 572
 573   for (current=head; current; current = next)
 574     {
 575       tree node = current->ixdecl;
 576       prdecl (node);
 577       next = current->next;
 578       if (next)
 579         fprintf (stderr, ",");
 580     }
 581   fprintf (stderr, "\n");
 582   return head;
 583 }
 584
 585 /* Print Iterator Stack.  */
 586
 587 void
 588 pis ()
 589 {
 590   struct iter_stack_node *stack_node;
 591
 592   fprintf (stderr, "--SubLevel: ");
 593   pixl (sublevel_ixpansions.first);
 594   fprintf (stderr, "--Stack:--\n");
 595   for (stack_node = iter_stack;
 596        stack_node;
 597        stack_node = stack_node->next)
 598     pixl (stack_node->first);
 599 }
 600
 601 #endif /* DEBUG_ITERATORS */