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