introduce schedule tree representation
commitb0c84f7bfce2eef324688abd2ec80fd5cc018608
authorSven Verdoolaege <skimo@kotnet.org>
Sun, 28 Jul 2013 16:40:18 +0000 (28 18:40 +0200)
committerSven Verdoolaege <skimo@kotnet.org>
Mon, 9 Feb 2015 14:07:07 +0000 (9 15:07 +0100)
treed301fad45b7cb5c19b1762fac831d635b13eb682
parent74ad4336c73819af8694164e5e39da5e6e772771
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:
Makefile.am
doc/user.pod
include/isl/schedule.h
include/isl/schedule_node.h [new file with mode: 0644]
include/isl/schedule_type.h [new file with mode: 0644]
isl_schedule.c
isl_schedule_band.c [new file with mode: 0644]
isl_schedule_band.h [new file with mode: 0644]
isl_schedule_node.c [new file with mode: 0644]
isl_schedule_node_private.h [new file with mode: 0644]
isl_schedule_private.h
isl_schedule_tree.c [new file with mode: 0644]
isl_schedule_tree.h [new file with mode: 0644]
isl_scheduler.c