nloop.c

gcc-2.95.3 Linux下最常用的C编译器

/* Implement looping actions for CHILL.
   Copyright (C) 1992, 93, 1994 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include <stdio.h>
#include <limits.h>
#include "config.h"
#include "tree.h"
#include "ch-tree.h"
#include "lex.h"
#include "flags.h"
#include "actions.h"
#include "input.h"
#include "obstack.h"
#include "assert.h"
#include "rtl.h"

/* if the user codes '-flocal-loop-counter' on the command line,
   ch-actions.c (lang_decode_option) will set this flag. */
int flag_local_loop_counter = 0;

extern tree chill_truthvalue_conversion PROTO((tree));
extern rtx  emit_line_note              PROTO((char *, int)); 
extern void error                       PROTO((char *, ...));
extern rtx  expand_assignment           PROTO((tree, tree, int, int));
extern void save_expr_under_name        PROTO((tree, tree));
extern void stamp_nesting_label         PROTO((tree));
extern int  int_fits_type_p             PROTO((tree, tree));
extern void warning                     PROTO((char *, ...));

/* forward declarations */
static int  classify_loop            PROTO((void));
static int  declare_temps            PROTO((void));
static int  initialize_iter_var      PROTO((void));
static int  maybe_skip_loop          PROTO((void));
static int  top_loop_end_check       PROTO((void));
static int  bottom_loop_end_check    PROTO((void));
static int  increment_temps          PROTO((void));
static tree build_temporary_variable PROTO((char *, tree));
static tree maybe_make_for_temp      PROTO((tree, char *, tree));
static tree chill_unsigned_type      PROTO((tree));

/* In terms of the parameters passed to build_loop_iterator,
 *   there are several types of loops.  They are encoded by
 *   the ITER_TYPE enumeration.
 *
 *   1) DO FOR EVER; ... OD
 *      indicated by a NULL_TREE start_exp, step_exp and end_exp,
 *      condition == NULL, in_flag = 0, and ever_flag == 1 in the
 *      first ITERATOR.
 *
 *   2) DO WHILE cond; ... OD
 *      indicated by NULL_TREE start_exp, step_exp and end_exp, 
 *      in_flag = 0, and condition != NULL.
 *
 *   3) DO; ... OD
 *      indicated by NULL_TREEs in start_exp, step_exp and end_exp,
 *      condition != NULL, in_flag == 0 and ever_flag == 0.  This
 *      is not really a loop, but a compound statement.
 *
 *   4) DO FOR user_var := start_exp 
 *         [DOWN] TO end_exp BY step_exp; ... DO
 *      indicated by non-NULL_TREE start_exp, step_exp and end_exp.
 *
 *   5) DO FOR user_var [DOWN] IN discrete_mode; ... OD
 *      indicated by in_flag == 1.  start_exp is a non-NULL_TREE 
 *      discrete mode, with an optional down_flag.
 *
 *   6) DO FOR user_var [DOWN] IN powerset_expr; ... OD
 *      indicated by in_flag == 1.  start_exp is a non-NULL_TREE 
 *      powerset mode, with an optional down_flag.
 *
 *   7) DO FOR user_var [DOWN] IN location; ... OD
 *      indicated by in_flag == 1.  start_exp is a non-NULL_TREE 
 *      location mode, with an optional down_flag.
 */
typedef enum 
{
   DO_UNUSED,
   DO_FOREVER,
   DO_WHILE,
   DO_OD,
   DO_STEP,
   DO_RANGE,
   DO_POWERSET,
   DO_LOC,
   DO_LOC_VARYING 
} ITER_TYPE;


typedef struct iterator 
{
/* These variables only have meaning in the first ITERATOR structure. */
  ITER_TYPE itype;                  /* type of this iterator */
  int  error_flag;                  /* TRUE if no loop was started due to 
				       user error */
  tree condition;                   /* WHILE condition expression */
  int  down_flag;                   /* TRUE if DOWN was coded */

/* These variables have meaning in every ITERATOR structure. */
  tree user_var;                    /* user's explicit iteration variable */
  tree start_exp;                   /* user's start expression
                                       or IN expression of a FOR .. IN*/
  tree step_exp;                    /* user's step expression */
  tree end_exp;                     /* user's end expression */
  tree start_temp;                  /* temp holding evaluated start_exp */
  tree end_temp;                    /* temp holding evaluated end_exp */
  tree step_temp;                   /* temp holding evaluated step_exp */
  tree powerset_temp;               /* temp holding user's initial powerset expression */
  tree loc_ptr_temp;                /* temp holding count for LOC enumeration ptr */
  tree iter_var;                    /* hidden variable for the loop */
  tree iter_type;                   /* hidden variable's type */
  tree base_type;                   /* LOC enumeration base type */
  struct iterator *next;            /* ptr to next iterator for this loop */
} ITERATOR;

/*
 * There's an entry like this for each nested DO loop.
 * The list is maintained by push_loop_block
 * and pop_loop_block.
 */
typedef struct loop {
  struct loop *nxt_level;   /* pointer to enclosing loop */
  ITERATOR    *iter_list;   /* iterators for the current loop */
} LOOP;

static LOOP *loop_stack = (LOOP *)0;

#if 0

Here is a CHILL DO FOR statement:

DO FOR user_var := start_exp BY step_exp [DOWN] TO end_exp 
   WHILE condition;

For this loop to be 'safe', like a Pascal FOR loop, the start,
end, and increment expressions are computed once, before the
assignment to the iteration variable and saved in temporaries,
before the first assignment of the iteration variable, so the
following works:

          FOR i := (i+1) TO (i+10) DO

To prevent changes to the start/end/step expressions from
effecting the loop''s termination, and to make the loop end-check
as simple as possible, we evaluate the step expression into
a temporary and compute a hidden iteration count before entering 
the loop''s body.  User code cannot effect the counter, and the
end-loop check simply decrements the counter and checks for zero.

The whole phrase FOR iter := ... TO end_exp can be repeated
multiple times, with different user-iteration variables.  This
is discussed later.

The loop counter calculations need careful design since a loop
from MININT TO MAXINT must work, in the precision of integers.

Here''s how it works, in C:

        0) The DO ... OD loop is simply a block with 
           its own scope.  

	1) The DO FOR EVER is simply implemented:

	   loop_top:
		.
		. body of loop
		.
		goto loop_top
	   end_loop:

	2) The DO WHILE is also simple:


	   loop_top:
		if (!condition) goto end_loop
		.
		. body of loop
		.
		goto loop_top
	   end_loop:


	3) The DO FOR [while condition] loop (no DOWN)

	push a new scope,
	decl iter_var

		step_temp = step_exp
                start_temp = start_exp
                end_temp = end_exp
		if (end_exp < start_exp) goto end_loop
                /* following line is all unsigned arithmetic */
		iter_var = (end_exp - start_exp + step_exp) / step_exp
                user_var = start_temp
	   loop_top:
		if (!condition) goto end_loop
		.
		. body of loop
		.
                iter_var--
		if (iter_var == 0) goto end_loop
                user_var += step_temp
		goto loop_top
	end_loop:
	pop scope

	4) The proposed CHILL for [while condition] loop (with DOWN)

	push a new scope,
        decl iter
		step_temp = step_exp
                start_temp = start_exp
                end_temp = end_exp
		if (end_exp > start_exp) goto end_loop
                /* following line is all unsigned arithmetic */
		iter_var = (start_exp - end_exp + step_exp) / step_exp
                user_var = start_temp
	   loop_top:
		if (!condition) goto end_loop
		.
		. body of loop
		.
                iter_var--
		if (iter_var == 0) goto end_loop
		user_var -= step_temp
		goto loop_top
	    end_loop:
	pop scope


        5) The range loop, which iterates over a mode''s possible
           values, works just like the above step loops, but with
           the start and end values taken from the mode''s lower
           and upper domain values.


	6) The FOR IN loop, where a location enumeration is
           specified (see spec on page 81 of Z.200, bottom
           of page 186):

	push a new scope,
        decl iter_var as an unsigned integer
             loc_ptr_temp as pointer to a composite base type
        
               if array is varying
                   iter_var = array''s length field
               else
                   iter_var = sizeof array / sizeof base_type
	       loc_ptr_temp = &of highest or lowest indexable entry
	   loop_top:
		if (!condition) goto end_loop
		.
		. body of loop
		.
                iter_var--
                if (iter_var == 0) goto end_loop               
		loc_ptr_temp +/-= sizeof array base_type
		goto loop_top
	   end_loop:
	pop scope

	7) The DO FOR (DOWN) IN powerset_exp

	push a new scope,
        decl powerset_temp
	decl iterator as basetype of powerset

	        powerset_temp := start_exp
	   loop_top:
	        /* if DOWN */
                if (__flsetclrpowerset () == 0) goto end_loop;
                /* not DOWN */
                if (__ffsetclrpowerset () == 0) goto end_loop;
		if (!condition) goto end_loop
		.
		. body of loop
		.
		goto loop_top
	   end_loop:
	pop scope


So, here''s the general DO FOR schema, as implemented here:

        classify_loop       -- what type of loop have we?
                            -- build_iterator does some of this, also
        expand_start_loop   -- start the loop''s control scope
        -- start scope for synthesized loop variables
        declare_temps       -- create, initialize temporary variables
        maybe_skip_loop     -- skip loop if end conditions unsatisfiable
        initialize_iter_var -- initialize the iteration counter
                            -- initialize user''s loop variable
        expand_start_loop   -- generate top-of-loop label
        top_loop_end_check  -- generate while code and/or
                               powerset find-a-bit function call
        .
        .
        .  user''s loop body code
        .
        .
        bottom_loop_end_check  -- exit if counter has become zero
        increment_temps     -- update temps for next iteration
        expand_end_loop     -- generate jump back to top of loop
        expand_end_cond     -- generate label for end of conditional
        -- end of scope for synthesized loop variables
        free_iterators      -- free up iterator space

When there are two or more iterator phrases, each of the
above loop steps must act upon all iterators.  For example,
the 'increment_temps' step must increment all temporaries
(associated with all iterators).

 NOTE: Z.200, section 10.1 says that a block is ...
       "the actions statement list in a do action, including any
       loop counter and while control".  This means that an exp-
       ression in a WHILE control can include references to the
       loop counters created for the loop''s exclusive use.  
       Example:

             DCL a (1:10) INT;
             DCL j INT;
             DO FOR j IN a WHILE j > 0;
             ...
             OD;
       The 'j' referenced in the while is the loc-identity 'j'
       created inside the loop''s scope, and NOT the 'j' declared
       before the loop.
#endif

/*
 * The following routines are called directly by the
 * CHILL parser.
 */
void
push_loop_block ()
{
  LOOP *temp = (LOOP *)xmalloc (sizeof (LOOP));

  /* push a new loop onto the stack */
  temp->nxt_level = loop_stack;
  temp->iter_list = (ITERATOR *)0;
  loop_stack = temp;
}

void
pop_loop_block ()
{
  LOOP *do_temp = loop_stack;
  ITERATOR  *ip;

  /* pop loop block off the list */
  loop_stack = do_temp->nxt_level;

  /* free the loop's iterator blocks */
  ip = do_temp->iter_list;
  while (ip != NULL)
    {
      ITERATOR *temp = ip->next;
      free (ip);
      ip = temp;
    }
  free (do_temp);
}

void
begin_loop_scope ()
{
  ITERATOR *firstp = loop_stack->iter_list;

  if (pass < 2)
    return;

  /*
   * We need to classify the loop and declare its temporaries
   * here, so as to define them before the WHILE condition
   * (if any) is parsed.  The WHILE expression may refer to
   * a temporary.
   */
  if (classify_loop ())
    return;

  if (firstp->itype != DO_OD)
    declare_temps ();
  
  clear_last_expr ();
  push_momentary ();
  expand_start_bindings (0);
}


void
end_loop_scope (opt_label)
     tree opt_label;
{
  if (opt_label)
    possibly_define_exit_label (opt_label);
  poplevel (0, 0, 0);

  if (pass < 2)