Add OpenMP code generation to isl backend
This backend supports besides the classical code generation the upcoming SCEV
based code generation (which the existing CLooG backend does not support
robustly).
OpenMP code generation in the isl backend benefits from our run-time alias
checks such that the set of loops that can possibly be parallelized is a lot
larger.
The code was tested on LNT. We do not regress on builds without -polly-parallel.
When using -polly-parallel most tests work flawlessly, but a few issues still
remain and will be addressed in follow up commits.
SCEV/non-SCEV codegen:
- Compile time failure in ldecod and TimberWolfMC due a problem in our
run-time alias check generation triggered by pointers that escape through
the OpenMP subfunction (OpenMP specific).
- Several execution time failures. Due to the larger set of loops that we now
parallelize (compared to the classical code generation), we currently run
into some timeouts in tests with a lot loops that have a low trip count and
are slowed down by parallelizing them.
SCEV only:
- One existing failure in lencod due to llvm.org/PR21204 (not OpenMP specific)
OpenMP code generation is the last feature that was only available in the CLooG
backend. With the isl backend being the only one supporting features such as
run-time alias checks and delinearization, we will soon switch to use the isl
ast generator by the default and subsequently remove our dependency on CLooG.
http://reviews.llvm.org/D5517
llvm-svn: 222088
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp
index 6c38782..40f1d91 100644
--- a/polly/lib/Support/SCEVValidator.cpp
+++ b/polly/lib/Support/SCEVValidator.cpp
@@ -461,6 +461,48 @@
};
namespace polly {
+/// Find all loops referenced in SCEVAddRecExprs.
+class SCEVFindLoops {
+ SetVector<const Loop *> &Loops;
+
+public:
+ SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
+
+ bool follow(const SCEV *S) {
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
+ Loops.insert(AddRec->getLoop());
+ return true;
+ }
+ bool isDone() { return false; }
+};
+
+void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
+ SCEVFindLoops FindLoops(Loops);
+ SCEVTraversal<SCEVFindLoops> ST(FindLoops);
+ ST.visitAll(Expr);
+}
+
+/// Find all values referenced in SCEVUnknowns.
+class SCEVFindValues {
+ SetVector<Value *> &Values;
+
+public:
+ SCEVFindValues(SetVector<Value *> &Values) : Values(Values) {}
+
+ bool follow(const SCEV *S) {
+ if (const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S))
+ Values.insert(Unknown->getValue());
+ return true;
+ }
+ bool isDone() { return false; }
+};
+
+void findValues(const SCEV *Expr, SetVector<Value *> &Values) {
+ SCEVFindValues FindValues(Values);
+ SCEVTraversal<SCEVFindValues> ST(FindValues);
+ ST.visitAll(Expr);
+}
+
bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R) {
return SCEVInRegionDependences::hasDependences(Expr, R);
}