Scalarizer documentation

[Paul Richard Thomas]

Dear Mikael,

This really is very good - thank you!

I will go through it and check that it corresponds to my somewhat
weaker knowledge of the subject and will try to find the time to
analyze in the same fashion chunks of scalarizer code that I have
written; elemental subroutines, copy-in and copy-out of arbitrary
objects and allocatable array components.  The latter, of course, is a
relatively trivial application because it handles complete, contiguous
arrays but it does demonstrate how loops are made and how the loop
code is inserted.

In the mean time, I suggest that you post it, as it is, on the wiki.

Cheers

Paul

On Fri, Oct 28, 2011 at 12:24 AM, Mikael Morin <mikael.morin@sfr.fr> wrote:
> Hello,
>
> I dump here some documentation I have started to write about the scalarizer as
> per popular request.
>
> Mikael.
>
>
>
> * Disclaimer.
>
> - This documentation was not written by the one who wrote the scalarizer in
>  the first place, so approximations or errors are possible.
> - The code that has been used as support for this is the code from
>  gfc_trans_assignment_1. As a result, this documentation may certainly miss
>  some aspects of the scalarizer which are not used there (TODO).
>
> * Introduction
>
> The aim of the scalarizer is to translate array assignments (resp. elemental
> procedure calls) into scalar assignments (resp. procedure calls) enclosed in
> one or more loop. Thus, the following fortran assignment:
>  a(:,:) = b(:,:) + somefunc()
>
> is translated into:
>  allocate(tmp)
>  tmp(:,:) = somefunc()
>  do s2 = 0,e2
>    do s1 = 0,e1
>      a(s1, s2) = b(s1,s2) + tmp(s1,s2)
>    end do
>  end do
>  deallocate(tmp)
>
>
> * General design.
>
> The first thing to notice in the snippet above is that code is generated at
> three different places:
>  - in the prologue, a temporary is generated, and the function somefunc is
>   called to fill the descriptor
>  - inside the loops, the actual assignment takes place.
>  - in the epilogue, the temporary variable is freed.
>
> The gfortran code generation relies heavily on gfc_create_var, which itself
> relies on pushdecl, which uses current_binding_level.
> As the loop code and the prologue/epilogue code are at different binding
> levels (or scopes), they can't be generated together on the fly; they have to
> be generated at different places (*). Thus, we have the following general
> outline:
>  - generate prologue/epilogue
>  - create loops and scopes
>  - generate loop body
>
> Now, to generate prologue and epilogue, we have to walk along the lhs and rhs
> expression and output the corresponding code (if needed) for each
> subexpression requiring it. As such a walk is necessary for other things (see
> below), and walking an expression being quite complicated in the general case,
> we walk the subexpressions only once to avoid code duplication, and record the
> "interesting" parts (arrays, function calls, scalars, ...) in a linked list.
> Then, subsequent walks will only require a linear walk of the linked list. The
> layout is then as follows:
>  - walk lhs and rhs
>  - add the lhs and rhs to the loop information
>  - generate prologue/epilogue
>  - create loops and scopes
>  - generate loop body
>
> * Preliminary implementation
>
> At this point, we can start outlining the core structs we are going to use.
>
> Let's consider the following example:
>  a(:) = b(:) + c(:)
>
> The linked lists as described above will be as follows:
> for lhs: a -> (nil)
> for rhs: b -> c -> (nil)
> And once added to the loop, they will be:
> a -> b -> c -> (nil)
> Thus, there will be two "next" pointers in the linked lists; one for the
> expression chain, one for the loop chain.
> Thus, the linked lists will have the following fields:
> struct gfc_ss {
>  gfc_ss *next;
>  gfc_ss *loop_chain;
> }
>
> The loop, as explained above, will have prologue code and epilogue code.
> They have also pointer to the above linked list.
> Thus, the loop struct is as follows.
> struct gfc_loopinfo {
>  stmtblock_t pre, post;
>  gfc_ss *ss;
> }
>
> Concerning the expression evaluation, we haven't really started talking about
> it, but we can outline a simple struct for it.
> struct gfc_se {
>  stmtblock_t pre, post;
>  tree expr;
> }
> The pre and post blocks contain code to be generated before and after
> expression. Field expr contains the value of the expression after preliminary
> code and before cleanup code have been run.
> Most of the time, the pre and post blocks of each expression will eventually
> be collected into the pre and post blocks of the loop.
>
> * Preliminary functions
>
> The scalarizer usage can now be summarized as follows:
> lss = gfc_walk_expr (lhs);
> rss = gfc_walk_variable (rhs);
> // if rhs is scalar (rss == gfc_ss_terminator), generate a scalar ss for it
> // anyway
> gfc_init_loop_info (loop);
> gfc_add_ss_to_loop (loop, lss);
> gfc_add_ss_to_loop (loop, rss);
> // generate preliminary code
> gfc_start_scalarized_body(loop, body);
> // generate body code (body)
> gfc_generate_scalarizing_loops(loop);
>
>
> * Using pre-generated expressions
>
> Now let's look at the code that has to be generated inside the loops.
> In expressions such as:
>    b(:,:) + some_array_func() + some_complicated_scalar_expr'
> the function call to some_array_func has to be generated in the prologue, but
> inside the loop, the function call has to be generated as an array reference.
> The same goes for scalar expressions; the complex expression is evaluated to a
> variable before the loop, and a reference to the variable is made inside the
> loop.
>
> To achieve this behaviour, we use the linked list generated above, which
> contains all the expressions that the scalarizer will have to handle. For each
> one of them, we just have to generate a variable reference. More precisely,
> gfc_se structs (which will contain the code generated by the scalarizer) get a
> ss field initially pointing to the whole linked list generated above, and
> telling (if non-null) that we are inside a scalarization loop. Then the
> gfc_conv_expr_* functions have a short-circuit if (gfc_se->ss != NULL) which
> uses the current gfc_se->ss to create the variable reference and advance
> gfc_se->ss to the next one in the list. The above will work if at each step,
> the gfc_se->ss is the one corresponding to the expression being generated,
> that is the list is in the "right" order.
>
> This has a very strong shortcoming: the ss list has to be consumed in the same
> order as it has been generated, which requires that two completely separated
> parts of the code are kept synced (**). Besides, for the evaluation of complex
> expressions, one often need to evaluate subexpressions, whose gfc_se needs to
> also have the ss field properly set. As a result, the gfc_se structs get a
> parent field so that when the ss field get advanced in one (sub)expression,
> the same is done in parent expressions too.
>
> To be able to distinguish between the case of end of chain in a scalarizer
> loop and the case of no scalarizer loop at all, a constant "end of chain"
> gfc_ss pointer is introduced: gfc_ss_terminator.
>
> Now the gfc_se struct is pretty much finished:
> struct gfc_se {
>  stmtblock_t pre, post; // prologue and epilogue code
>  tree expr;             // value
>  gfc_se *parent;        // parent expression (if any) this subexpression is
> in
>  gfc_ss *ss;            // list of the remaining array refs to handle
>  gfc_loopinfo *loop;    // the scalarizer loop this expression is in
> }
> The loop field hasn't been talked about, but it is just an implementation
> detail avoiding to pass the loop around to each function.
>
> There are a bunch of additional flags, but those are implementation details
> too. TODO: There should be an explaination for each one of them.
>
>
> * Detailed implementation.
>
> As could be expected, the devil is there.
> So, for the assignment:
>  a(1:3,:) = b(:,2,n1:n2) + c(u(:),2:6)
>
> We want to generate the code:
> {
>  offa = a.offset;
>  offb = b.offset + 2 * b.stride[1];
>  offc = c.offset
>
>  for (s2 = 2; s2 < 6; s2++)
>  {
>   offa2 = offa + (s2 - 2) * a.stride[1];
>   offb2 = offb + (s2 - 2) * b.stride[2];
>   offc2 = offc + (s2 - 2) * c.stride[1];
>
>   for (s1 = 0; s1 < 2; s1++)
>    {
>     a.data[offa2 + (s1 + 1)] = b.data[offb2 + (s1 + 1)] + c.data[offc2 +
> u.data[offu + s1]];
>    }
>  }
> }
>
> We can notice that for every dimension, each array has its own set of bounds;
> and for a single array, the set of bounds can be different on every dimension
> (vector subscripts, explicit bounds, implicit bounds). On the other hand,
> there is a single loop index, which is used to access all arrays.
> So we must have delta fields, one for every array and every dimension, equal
> to the difference between loop bounds and array bounds.
> The loop bounds are picked from the array bound providing the most information
> (constant bounds, zero-based, ...), so the scheme is as follows:
>  - In each array and for each dimension, collect bounds (this is in
> gfc_conv_ss_startstride, strides will be collected too).
>  - For each dimension, choose the array providing the "best" set of bounds
>  - For each dimension, for each array (each but the one chosen, as it has a
> zero delta), set the delta between loop bounds and array bounds.
>
>
> In the example above, b is a bit special as its rank is more than the other,
> that is only a partial reference of b is used in the scalarizer.
> It means that the array dimensions are not necessarily the same as the
> corresponding loop dimensions. Furthermore one of the array could be
> transposed, in which case its dimensions would not have the same order as
> those of the loop.
>
> To handle both case, the gfc_ss structs get a dim array (with a dimen field
> for the size of that dim array/the rank of the loop) mapping loop dimensions
> to array dimensions. The array bounds are indexed by array dimension.
> Then, we can outline the gfc_ss_info contents (part of gfc_ss in the array
> case):
> struct gfc_ss_info {
>  int    dimen;
>  int    dim[GFC_MAX_DIMENSIONS];
>  tree   descriptor;
>  tree   data;
>  tree   offset;
>  gfc_ss *subscript[GFC_MAX_DIMENSIONS];
>  tree   start[GFC_MAX_DIMENSIONS];
>  tree   end[GFC_MAX_DIMENSIONS];
>  tree   stride[GFC_MAX_DIMENSIONS];
>  tree   delta[GFC_MAX_DIMENSIONS];
> }
>
> The field subscript hasn't been presented yet. It is there to handle both
> vector subscripts and partial array references (like b above). In the first
> case, the subscript is a ss of type GFC_SS_VECTOR, and its descriptor is
> generated before the loop. In the second case the subscript is of type
> GFC_SS_SCALAR, whose value is precalculated before the loop too.
>
> At this point, scalarizer usage is as follows:
> gfc_init_se (lse, parent_se | NULL);
> gfc_init_se (rse, parent_se | NULL);
> lss = gfc_walk_expr (lhs);
> rss = gfc_walk_expr (rhs);
> // if rhs is scalar, generate a rss.
> gfc_init_loopinfo (loop);
> gfc_add_ss_to_loop (loop, lss);
> gfc_add_ss_to_loop (loop, rss);
> gfc_conv_ss_startstride (loop); // collect array bounds
> gfc_conv_loop_setup (loop); // choose loopspec, generate prologue and epilogue
> code, calculate delta.
> lse.ss = lss;
> rse.ss = rss;
> gfc_start_scalarized_body (loop, body);
> // generate body code (body):
> //   gfc_conv_expr (lse, lhs);
> //   gfc_conv_expr (rse, rhs);
> //   gfc_add_block_to_block (loop.pre, lse.pre);
> //   (...) etc
> gfc_trans_scalarizing_loops (loop);
>
>
> * Partial offset generation
>
> Before moving to the handling of temporaries, some words about the partial
> offsets. As can be seen in the snippet at the beginning of the previous
> section, some partial offsets are calculated for each array and at every loop
> level, so that common expressions are factored out of loops as much as
> possible. Again, this uses gfc_create_var, which uses current binding level,
> so that the variables can be created only when we are in their scope, that is
> they are created in gfc_start_scalarized_body (more exactly in
> gfc_trans_preloop_setup). At every loop level, the partial offset is
> calculated, and gfc_ss_info's offset field is updated with the new value. This
> means that once gfc_start_scalarized_body has been called, the offset field
> doesn't contain the regular descriptor offset, but a combined offset. This has
> some consequences for temporary management, see below.
>
>
> * Temporaries handling
>
> We have seen previously how temporaries were handled for function calls. But
> temporaries can be needed in other cases where there is a dependency between
> lhs and rhs of an assignment. There is a specific code for that. Consider the
> case of vector subscripts:
>  a(:) = a(u(:))
> Here, as writes to a(i,j) will impact the values of a(u(i), u(j)), a temporary
> is needed. Thus, the code will be as follows:
>  allocate(tmp)
>  do j=1,p
>  tmp(i) = a(u(i))
>  end do
>  do j=1,p
>  a(i) = tmp(i)
>  end do
>  deallocate(tmp)
> Note that the temporary is on the lhs so that only one temp is needed, even if
> there is more than one reference to a in the rhs.
>
> To generate this, we use a single loop information, as arrays are of the same
> size in both loops.
> Of course, the temporary can't be used to guess the loop bounds; it's quite
> the contrary in fact. Then it can't have a regular gfc_ss struct. Thus, the
> temporary's gfc_ss has its own type: GFC_SS_TEMP. Array bounds are not
> collected for it, it is not used to guess array bounds. Then, when
> gfc_conv_loop_setup has determined the loop bounds, those can be used to set
> temporary bounds which can then be allocated. This requires the loop's gfc_ss
> struct to be identified, so the gfc_loopinfo struct gets an additional temp_ss
> field.
>
> We can see in the snippet above that there are two loops, but each one of them
> uses only a partial set of the arrays involved. As the partial offsets are
> generated for all the involved arrays, we need to distinguish between those
> needed in the first loop, and those needed in the second. The gfc_ss structs
> get a useflags field telling whether they are used in the first loop (flag=1)
> or the second (flag=2). Then gfc_trans_preloop_setup (called by
> gfc_start_scalarized_body) skips arrays whose useflags don't match its flag
> argument.
> As gfc_trans_scalarizing loops has the side effect of clearing the useflags,
> one can't use it to finish the first loop (and then call
> gfc_start_scalarized_body for the second loop). One has to use
> gfc_trans_scalarized_loop_boundary dedicated to that purpose.
> In fact, the need for gfc_trans_scalarized_loop_boundary comes from the
> temporary's offset field (see below).
>
> So, in the non-temporary case, the code is:
> gfc_mark_ss_chain_used (lss, 1);
> gfc_mark_ss_chain_used (rss, 1);
> gfc_start_scalarized_body (loop, body);
> // generate body code
> gfc_trans_scalarizing_loops (loop);
>
> whilst in the temporary case, it is:
> gfc_mark_ss_chain_used (lss, 1);
> gfc_mark_ss_chain_used (rss, 2);
> gfc_mark_ss_chain_used (temp_ss, 3);
> gfc_start_scalarized_body (loop, body);
> // generate first body code
> gfc_trans_scalarized_loop_boundary (loop, body);
> // generate second body code
> gfc_trans_scalarizing_loops (loop, body);
>
>
> Now concerning the temporary array, it was seen before that
> gfc_trans_preloop_setup overwrites the regular descriptor offset with a
> combined offset value. This is annoying for the temporary array, as it is used
> in both loops, and it will have the wrong value in the second one. To avoid
> this, the gfc_ss_info struct gets a saved_offset field set to the initial
> offset, and it is used in gfc_trans_scalarized_loop_boundary to restore the
> initial value.
>
> * TODO
>
> Document gfc_loopinfo fields
> Document stride0
> Document gfc_ss flags
>
>
> (*): I have been thinking of changing this, but it has never been anything
> more than an idea.
>
> (**): I have been thinking of changing this too, adding in the gfc_expr struct
> a pointer to the corresponding gfc_ss struct, so that they can be used in any
> order.
>
>



-- 
The knack of flying is learning how to throw yourself at the ground and miss.
       --Hitchhikers Guide to the Galaxy