optionally group chains of statements

optionally group chains of statements

In particular, group statement instances from pairs of statements
that are executed immediately after each other in the input schedule
if all instances of the second statement depend on the corresponding
instance of the first statement and if they should be executed
close to each other according to the schedule constraints.

The main motivation is to combine pairs of statements where the first
stores a result in a scalar that is then read by the next statement.
There is usually no reason to schedule these statements differently,
so it is better to combine them into one statement.
Such a combination improves the efficiency of the scheduler,
especially if there is more than one instance of the statements,
i.e., if they are executed inside one or more loops in the input program.
However, the way the grouping is constructed does not depend
on the fact that a scalar is written and read by the two statements.
For example, the heuristic also kicks in on the following pair
of statements in PolyBench's nussinov benchmark:

   if (j-1>=0)
      table[i][j] = max_score(table[i][j], table[i][j-1]);
   if (i+1<_PB_N)
      table[i][j] = max_score(table[i][j], table[i+1][j]);

Note that conditions on these two statements are redundant
within the loop bounds so that each instance of the second
statement does in fact depend on an instance of the first
statement.  Further experiments are needed to determine
whether this is a good heuristic, but it should be
a reasonably good initial version.

This form of grouping exploits both the schedule constraints and
the input schedule, the schedule constraints to find out which
pairs of statement instances both depend on each other and should
be executed close to each other; and the input schedule to determine
which statement instances are executed next to each other.
Since only statements that are executed next to each other in
the input schedule are combined, the input schedule remains
a valid solution to the schedule constraints.
However, some scheduling freedom may be removed by this grouping,
as for example in the nussinov benchmark mentioned above.

The grouping is applied to the schedule constraints to ease
the job of the scheduler.  The resulting schedule is then
formulated in terms of these groups and is subsequently
extended with expansions to refer back to the original
statement instances.  While it would be possible to modify
the entire schedule to refer to the original statement instances,
this extended schedule is preferred because it explicitly
keeps track of the grouping that was performed.
If the isl scheduler is ever changed to introduce its own
groupings and expansions, then it can easily be composed
with the grouping performed by PPCG.
The grouping may also make it possible to perform some
operations more efficiently in the future.  At the moment,
all schedule related information is expanded before it is
combined with dependence information, but it may be more
efficient to contract the dependence information to
the group instances instead.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>