[COMMIT] Add isl based schedule pass

[Tobias Grosser]

commit cb2c63436b0a0352ffbc86e87330992b2dc76c12
Author: Tobias Grosser <tob...@grosser.es>
Date: Thu Apr 28 10:18:04 2011 +0200

Add isl based schedule pass

diff --git a/include/polly/Dependences.h b/include/polly/Dependences.h
index 66cdf96..357099d 100755
--- a/include/polly/Dependences.h
+++ b/include/polly/Dependences.h
@@ -53,6 +53,7 @@ namespace polly {

public:
static char ID;
+ enum Type {TYPE_WAR, TYPE_RAW, TYPE_WAW};
typedef std::map<ScopStmt*, isl_map*> StatementToIslMapTy;

Dependences();
@@ -69,6 +70,8 @@ namespace polly {
/// valid for the scattering domain subset given.
bool isParallelDimension(isl_set *loopDomain, unsigned parallelDimension);

+ isl_union_map *getDependences(enum Type, bool must = true);
+
bool runOnScop(Scop &S);
void printScop(raw_ostream &OS) const;
virtual void releaseMemory();
diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h
index 8fd2db8..7f7e9cc 100644
--- a/include/polly/LinkAllPasses.h
+++ b/include/polly/LinkAllPasses.h
@@ -43,6 +43,7 @@ namespace polly {
Pass *createJSONImporterPass();
Pass *createRegionSimplifyPass();
Pass *createScopInfoPass();
+ Pass *createSchedulePass();

#ifdef OPENSCOP_FOUND
Pass *createScopExporterPass();
@@ -87,6 +88,7 @@ namespace {
createJSONImporterPass();
createRegionSimplifyPass();
createScopInfoPass();
+ createSchedulePass();

#ifdef OPENSCOP_FOUND
createScopExporterPass();
diff --git a/lib/Analysis/Dependences.cpp b/lib/Analysis/Dependences.cpp
index 8b36002..5eeb5c1 100644
--- a/lib/Analysis/Dependences.cpp
+++ b/lib/Analysis/Dependences.cpp
@@ -400,6 +400,17 @@ void Dependences::releaseMemory() {
sink = must_source = may_source = NULL;
}

+isl_union_map *Dependences::getDependences(enum Type type, bool must) {
+ switch (type) {
+ case TYPE_RAW:
+ return isl_union_map_copy(must_dep);
+ case TYPE_WAR:
+ return isl_union_map_copy(war_dep);
+ case TYPE_WAW:
+ return isl_union_map_copy(waw_dep);
+ }
+}
+
void Dependences::getAnalysisUsage(AnalysisUsage &AU) const {
ScopPass::getAnalysisUsage(AU);
}
diff --git a/lib/CMakeLists.txt b/lib/CMakeLists.txt
index 8881fea..4751aad 100755
--- a/lib/CMakeLists.txt
+++ b/lib/CMakeLists.txt
@@ -30,6 +30,7 @@ add_polly_library(LLVMPolly
MayAliasSet.cpp
Pocc.cpp
RegionSimplify.cpp
+ Schedule.cpp
json.c
json_helper.c
Exchange/JSONExporter.cpp
diff --git a/lib/Schedule.cpp b/lib/Schedule.cpp
new file mode 100644
index 0000000..0e0afbd
--- /dev/null
+++ b/lib/Schedule.cpp
@@ -0,0 +1,116 @@
+//===- Schedule.cpp - Calculate an optimized schedule ---------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass uses the isl to calculate a schedule that is optimized for
+// parallelism and tileablility. The algorithm used in isl is an optimized
+// version of the following papers:
+//
+// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. A Practical Auto-
+// matic Polyhedral Parallelizer and Locality Optimizer. In Proceedings of the
+// 2008 ACM SIGPLAN Conference On Programming Language Design and
+// Implementation, PLDI ’08, pages 101–113. ACM, 2008.
+//===----------------------------------------------------------------------===//
+
+#include "polly/Cloog.h"
+#include "polly/LinkAllPasses.h"
+
+#include "polly/Dependences.h"
+#include "polly/ScopInfo.h"
+
+#include "isl/dim.h"
+#include "isl/map.h"
+#include "isl/constraint.h"
+#include "isl/schedule.h"
+
+#define DEBUG_TYPE "polly-schedule"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+using namespace polly;
+
+namespace {
+
+ class Schedule : public ScopPass {
+
+ public:
+ static char ID;
+ explicit Schedule() : ScopPass(ID) {}
+
+ virtual bool runOnScop(Scop &S);
+ void printScop(llvm::raw_ostream &OS) const;
+ void getAnalysisUsage(AnalysisUsage &AU) const;
+ };
+
+}
+
+char Schedule::ID = 0;
+bool Schedule::runOnScop(Scop &S) {
+ Dependences *D = &getAnalysis<Dependences>();
+ isl_union_map *validity = D->getDependences(Dependences::TYPE_RAW);
+ validity = isl_union_map_union(validity,
+ D->getDependences(Dependences::TYPE_WAR));
+ validity = isl_union_map_union(validity,
+ D->getDependences(Dependences::TYPE_WAW));
+
+ isl_union_map *proximity = D->getDependences(Dependences::TYPE_RAW);
+ proximity = isl_union_map_union(proximity,
+ D->getDependences(Dependences::TYPE_WAR));
+ proximity = isl_union_map_union(proximity,
+ D->getDependences(Dependences::TYPE_WAW));
+
+ isl_union_set *domain = NULL;
+
+ for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI)
+ if (!domain)
+ domain = isl_union_set_from_set(isl_set_copy((*SI)->getDomain()));
+ else
+ domain = isl_union_set_union(domain,
+ isl_union_set_from_set(isl_set_copy((*SI)->getDomain())));
+
+ if (!domain)
+ return false;
+
+ DEBUG(dbgs() << "Domain: "; isl_union_set_dump(domain));
+ DEBUG(dbgs() << "Proximity: "; isl_union_map_dump(proximity));
+ DEBUG(dbgs() << "Validity: "; isl_union_map_dump(validity));
+
+ isl_schedule *schedule = isl_union_set_compute_schedule(domain, validity,
+ proximity);
+
+ isl_union_map *scheduleMap = isl_schedule_get_map(schedule);
+
+ DEBUG(dbgs() << "Schedule: "; isl_union_map_dump(scheduleMap));
+
+ for (int i = 0; i < isl_schedule_n_band(schedule); i++) {
+ isl_union_map *band = isl_schedule_get_band(schedule, i);
+ DEBUG(dbgs() << "Band " << i << ": "; isl_union_map_dump(band));
+ }
+
+
+
+ isl_schedule_free(schedule);
+
+ return false;
+}
+
+void Schedule::printScop(raw_ostream &OS) const {
+}
+
+void Schedule::getAnalysisUsage(AnalysisUsage &AU) const {
+ ScopPass::getAnalysisUsage(AU);
+ AU.addRequired<Dependences>();
+}
+
+static RegisterPass<Schedule> A("polly-optimize-schedules",
+ "Polly - Calculate optimized"
+ "schedules (using isl)");
+
+Pass* polly::createSchedulePass() {
+ return new Schedule();
+}

[ether zhhb]

hi tobi,

On Fri, Apr 29, 2011 at 2:24 PM, Tobias Grosser <tob...@grosser.es> wrote:
>
>
> commit cb2c63436b0a0352ffbc86e87330992b2dc76c12
> Author: Tobias Grosser <tob...@grosser.es>
> Date:   Thu Apr 28 10:18:04 2011 +0200
>
>    Add isl based schedule pass
>
> diff --git a/include/polly/Dependences.h b/include/polly/Dependences.h
> index 66cdf96..357099d 100755
> --- a/include/polly/Dependences.h
> +++ b/include/polly/Dependences.h
> @@ -53,6 +53,7 @@ namespace polly {
>
>   public:
>     static char ID;
> +    enum Type {TYPE_WAR, TYPE_RAW, TYPE_WAW};

I suggest we make these enums to be bit flags:
enum Type {
TYPE_WAR = 0x1,
TYPE_RAW = 0x2,
TYPE_WAW = 0x4,
TYPE_ALL = TYPE_WAR | TYPE_RAW | TYPE_RAR
};

So we can get the combination of these dependences with a single function call.
and
function getDependences becomes:

union_map ret = empty_union_map;
if (Type & TYPE_RAW) ret = union(ret, isl_union_map_copy(must_dep));
if (Type & TYPE_WAR) ret = union(ret, isl_union_map_copy(war_dep));
if (Type & TYPE_WAW) ret = union(ret, isl_union_map_copy(waw_dep));

return ret;

best regards
ether

[ether zhhb]

hi tobi,

And should the schedule pass update dependences analysis?

> +
> +  return false;
> +}
> +

best regards
ether

[Tobias Grosser]

On 05/01/2011 01:43 PM, ether zhhb wrote:
> hi tobi,
>
>
>> +
>> +char Schedule::ID = 0;
>> +bool Schedule::runOnScop(Scop&S) {

>> + Dependences *D =&getAnalysis<Dependences>();

No, it should not. The schedule will preserve all dependences.

I did not yet commit the schedule pass to the new svn repository as it
is still work in progress. Hope to have some basic pass working soon.

Cheers
Tobi