Identifying Loop Invariant Data Members: Mark Mitchell's Approach

[Jeffrey Oldham]

        The attached patch partially implements Mark Mitchell's idea
to mark loop-invariant Engine data members so the KCC optimizer can
move them out of inner loops.

        Without this patch or a similar idea by Stephen Smith, the
intermediate C code produced by KCC for the loops in
src/Evaluator/InlineEvaluator.h's evaluate() reveals reloading of
engine data members such as strides_m.  These data values are
invariant during the evaluate() loop.  To notify the optimizer of the
invariance, a separate constant structure containing these values is
constructed just before the loop begins.  This constant information is
passed into the operations performed within the loop.  Thus, the
optimizer can determine the values are loop-invariant and may be
hoisted out of the loop.  For example, consider the evaluate() loop
for the two-dimensional version of src/Evaluator/InlineEvaluator.h:

    for (int i1=0; i1<e1; ++i1)
      for (int i0=0; i0<e0; ++i0)
        op(lhs(i0,i1),rhs.read(i0,i1));

This is modified to

    const LHSLoopInvariant_t lli = lhs.loopInvariant();
    const RHSLoopInvariant_t rli = rhs.loopInvariant();
    for (int i1=0; i1<e1; ++i1)
      for (int i0=0; i0<e0; ++i0)
        op(lhs(lli, i0,i1),rhs.read(rli, i0,i1));

        Implementing this idea requires three steps:

1) modifying src/Evaluator/InlineEvaluator.h and other similar loops,
2) modifying containers, e.g., Array and Field, and related classes to
   create loop-invariant structures, and
3) modifying operations that use these structures.

        The first step is sketched above.  Containers are assumed to
have a 'loopInvariant' member function returning a 'LoopInvariant_t'
structure.  These containers' 'read' and 'operator()' members are
assumed to accept and use these packages.

        Implementing containers' 'LoopInvariant_t' structures mostly
involves passing the work onto the containers' engines.  For example,
Array's 'loopInvariant' consists of

    inline const
    LoopInvariant_t loopInvariant() const { return engine_m.loopInvariant(); }

Each engine has its own 'LoopInvariant_t' nested class storing its
loop-invariant data members.  For example, the Brick engine, derived
from BrickBase, stores the 'strides_m' data member.

   class LoopInvariant_t {
   public:
 
     inline int *strides() { return strides_m; }
     inline int& strides(const int i) { return strides_m[i]; }
     inline const int *strides() const { return strides_m; }
     inline int strides(const int i) const { return strides_m[i]; }
 
   private:
 
     int strides_m[Dim];
   };

The engine's 'loopInvariant' returns this structure:

   inline const LoopInvariant_t loopInvariant() const { return invariant_m; }

from its 'invariant_m' data member.

        Unfortunately, the creation of loop-invariant structures must
also ripple through the expression code, as created by PETE.  The
loop-invariant structure for a PETE expression, represented by a tree,
is an analogous tree of loop-invariant structures.  For example, a
binary node's loop-invariant structure consists of its two children's
loop-invariant structures.

        Using containers' LoopInvariant_t structures consists of
changing containers' and engines' 'read' and 'operator()' member
functions and the PETE evaluation mechanisms.

        The 'read' and 'operator()' member functions receive an
additional LoopInvariant_t parameter, whose contents are used if
appropriate.  For example, a Brick 'read' function changes from

    template <int Dim, class T>
    inline T Engine<Dim,T,Brick>::
    read(int i1, int i2) const
    {
      PAssert(Dim == 2);
      return data_m[offset(i1,i2)];
    }

to

    template <int Dim, class T>
    inline T Engine<Dim,T,Brick>::
    read(const LoopInvariant_t& li, int i1, int i2) const
    {
      PAssert(Dim == 2);
      return li.data()[offset(li,i1,i2)];
    }

Here, li's data() returns a loop-invariant copy of the 'data_m'
pointer and 'offset' also uses the loop-invariant object li.

        The PETE evaluation functions also need to support
loop-invariant objects.  The forEach functions in src/PETE/ForEach.h
propagate evaluation through the expression objects.  A copy of the
ForEach 'apply' member functions accepting loop-invariant objects need
to be added.  Evaluation at the expression leaves are handled by
'apply' functions, which should be modified in a way similar to the
'read' and 'operator()' functions so the loop-invariant objects'
contents are used.

        Stencil writers supply 'operator()' functions.  Stephen Smith
supplied a patch so these functions' parameters need not include
loop-invariant objects.  This idea is not incorporated in the first
attached patch.  Stephen Smith's patch is also attached.

        To permit Pooma users to directly call 'read' and 'operator()'
functions, the original interface should be maintained, at least for
containers.  Thus, parallel code must be maintained, a disadvantage of
this technique.

Thanks,
Jeffrey D. Oldham
address@hidden

LoopInvariant.02Nov.18.3b.patch
Description: Text document

stencil.patch
Description: Text document