introduce schedule tree representation
The schedule tree representation is meant to replace the current
band forest representation. With this commit, an isl_schedule
may internally be represented by either a schedule tree or
a band forest. In a subsequent commit we will make the scheduler
return a schedule tree based schedule, after which the band forest
will be removed.
This commit includes a conversion from schedule trees to band
forest to ease the transition. When band forests are removed,
this conversion will be removed as well.
A schedule tree has several advantages over a band forest.
- a schedule tree has nodes of different types. This allows
us to explicitly express the fact that a sequence of nodes
may be executed in any order rather than this property being
implicit in the representation. It also allows us to introduce
additional types of nodes in the future.
- an ordering of groups of domain elements can be represented
explicitly, rather than having to be encoded in a piecewise
constant function.
- band forests are modified in-place whereas schedule trees are not.
Band forests formed an exception to the general rule that
from the user point of view an operation never performs
any in-place modification. In particular, a modification to
one copy of an object does not affect any other copy of
the same object. Schedule trees follow the general rule and
return a pointer to a new schedule tree on any modification.
- schedule trees can be used as a generic representation of schedule
trees and not just to represent the output of the scheduler.
The schedule tree implementation introduced by this commit
is sufficient to represent the output of the scheduler.
In later commits, we will add additional functionality and
we will allow schedule trees as input to the dependence analysis and
the AST generator.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
14 files changed: