Add a sceleton for a polyhedral dead code elimination.

Such a dead code elimination can remove redundant stores to arrays. It can also
eliminate calculations where the results are stored to memory but where they are
overwritten before ever being read. It may also fix bugs like:
http://llvm.org/bugs/show_bug.cgi?id=5117

This commit just adds a sceleton without any functionality.

If anybody is interested to learn about polyhedral optimizations this would be
a good task. Well definined, self contained and pretty simple. Ping me if you
want to start and you need some pointers to get going.

llvm-svn: 149386

4 files changed, 89 insertions, 0 deletions

diff --git a/polly/include/polly/LinkAllPasses.h b/polly/include/polly/LinkAllPasses.h
index 9ddb6b8bb5b..07fb32275ff 100644
--- a/polly/include/polly/LinkAllPasses.h
+++ b/polly/include/polly/LinkAllPasses.h
@@ -33,6 +33,7 @@ namespace polly {
   Pass *createCloogInfoPass();
   Pass *createCodeGenerationPass();
   Pass *createCodePreparationPass();
+  Pass *createDeadCodeElimPass();
   Pass *createDependencesPass();
   Pass *createDOTOnlyPrinterPass();
   Pass *createDOTOnlyViewerPass();
@@ -79,6 +80,7 @@ namespace {
        createCloogInfoPass();
        createCodeGenerationPass();
        createCodePreparationPass();
+       createDeadCodeElimPass();
        createDependencesPass();
        createDOTOnlyPrinterPass();
        createDOTOnlyViewerPass();
@@ -111,6 +113,7 @@ namespace llvm {
   class PassRegistry;
   void initializeCodeGenerationPass(llvm::PassRegistry&);
   void initializeCodePreparationPass(llvm::PassRegistry&);
+  void initializeDeadCodeElimPass(llvm::PassRegistry&);
   void initializeIndependentBlocksPass(llvm::PassRegistry&);
   void initializeJSONExporterPass(llvm::PassRegistry&);
   void initializeJSONImporterPass(llvm::PassRegistry&);
diff --git a/polly/lib/CMakeLists.txt b/polly/lib/CMakeLists.txt
index f4af8a97fc8..05cfa0cbe77 100755
--- a/polly/lib/CMakeLists.txt
+++ b/polly/lib/CMakeLists.txt
@@ -21,6 +21,7 @@ add_polly_library(LLVMPolly
   Cloog.cpp
   CodePreparation.cpp
   CodeGeneration.cpp
+  DeadCodeElimination.cpp
   IndependentBlocks.cpp
   MayAliasSet.cpp
   Pocc.cpp
diff --git a/polly/lib/DeadCodeElimination.cpp b/polly/lib/DeadCodeElimination.cpp
new file mode 100644
index 00000000000..734a0ce1b56
--- /dev/null
+++ b/polly/lib/DeadCodeElimination.cpp
@@ -0,0 +1,75 @@
+//===- DeadCodeElimination.cpp - Eliminate dead iteration  ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// If values calculated within an iteration are not used later on the iteration
+// can be removed entirely. This pass removes such iterations.
+//===----------------------------------------------------------------------===//
+
+#include "polly/Dependences.h"
+#include "polly/LinkAllPasses.h"
+#include "polly/ScopInfo.h"
+
+#include "isl/union_map.h"
+
+using namespace llvm;
+using namespace polly;
+
+namespace {
+
+  class DeadCodeElim : public ScopPass {
+
+  public:
+    static char ID;
+    explicit DeadCodeElim() : ScopPass(ID) {}
+
+    virtual bool runOnScop(Scop &S);
+    void printScop(llvm::raw_ostream &OS) const;
+    void getAnalysisUsage(AnalysisUsage &AU) const;
+  };
+}
+
+char DeadCodeElim::ID = 0;
+
+bool DeadCodeElim::runOnScop(Scop &S) {
+  Dependences *D = &getAnalysis<Dependences>();
+
+  int dependencyKinds = Dependences::TYPE_RAW
+                          | Dependences::TYPE_WAR
+                          | Dependences::TYPE_WAW;
+
+  isl_union_map *dependences = D->getDependences(dependencyKinds);
+
+  // The idea of this pass is to loop over all statments and remove statement
+  // iterations that do not calculate any value that is read later on. We need
+  // to make sure to forward RAR and WAR dependences.
+  //
+  // A case where this pass might be useful is
+  // http://llvm.org/bugs/show_bug.cgi?id=5117
+  isl_union_map_free(dependences);
+  return false;
+}
+
+void DeadCodeElim::printScop(raw_ostream &OS) const {
+}
+
+void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {
+  ScopPass::getAnalysisUsage(AU);
+  AU.addRequired<Dependences>();
+}
+
+INITIALIZE_PASS_BEGIN(DeadCodeElim, "polly-dce",
+                      "Polly - Remove dead iterations", false, false)
+INITIALIZE_PASS_DEPENDENCY(Dependences)
+INITIALIZE_PASS_DEPENDENCY(ScopInfo)
+INITIALIZE_PASS_END(DeadCodeElim, "polly-dce",
+                      "Polly - Remove dead iterations", false, false)
+
+Pass* polly::createDeadCodeElimPass() {
+  return new DeadCodeElim();
+}
diff --git a/polly/lib/RegisterPasses.cpp b/polly/lib/RegisterPasses.cpp
index 68738b3aad4..b950c4ebc43 100644
--- a/polly/lib/RegisterPasses.cpp
+++ b/polly/lib/RegisterPasses.cpp
@@ -61,6 +61,12 @@ PollyViewer("polly-show",
        cl::desc("Enable the Polly DOT viewer in -O3"), cl::Hidden,
        cl::value_desc("Run the Polly DOT viewer at -O3"),
        cl::init(false));
+
+static cl::opt<bool>
+DeadCodeElim("polly-run-dce",
+             cl::desc("Run the dead code elimination"),
+             cl::Hidden, cl::init(false));
+
 static cl::opt<bool>
 PollyOnlyViewer("polly-show-only",
        cl::desc("Enable the Polly DOT viewer in -O3 (no BB content)"),
@@ -83,6 +89,7 @@ void initializePollyPasses(PassRegistry &Registry) {
   initializeCloogInfoPass(Registry);
   initializeCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);
+  initializeDeadCodeElimPass(Registry);
   initializeDependencesPass(Registry);
   initializeIndependentBlocksPass(Registry);
   initializeJSONExporterPass(Registry);
@@ -161,6 +168,9 @@ void registerPollyPasses(llvm::PassManagerBase &PM, bool DisableScheduler,
   if (ImportJScop)
     PM.add(polly::createJSONImporterPass());
 
+  if (DeadCodeElim)
+    PM.add(polly::createDeadCodeElimPass());
+
   if (RunScheduler) {
     if (Optimizer == "pocc") {
 #ifdef SCOPLIB_FOUND