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
diff --git a/polly/lib/DeadCodeElimination.cpp b/polly/lib/DeadCodeElimination.cpp
new file mode 100644
index 0000000..734a0ce
--- /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();
+}