2 files changed, 164 insertions, 8 deletions

diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 630726443b6..86b4762dc66 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -38,6 +38,7 @@
 #include "isl/constraint.h"
 #include "isl/set.h"
 #include "isl/map.h"
+#include "isl/union_map.h"
 #include "isl/aff.h"
 #include "isl/printer.h"
 #include "isl/local_space.h"
@@ -490,6 +491,14 @@ void MemoryAccess::setNewAccessRelation(isl_map *newAccess) {
 
 isl_map *ScopStmt::getScattering() const { return isl_map_copy(Scattering); }
 
+void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
+  assert(isl_set_is_subset(NewDomain, Domain) &&
+         "New domain is not a subset of old domain!");
+  isl_set_free(Domain);
+  Domain = NewDomain;
+  Scattering = isl_map_intersect_domain(Scattering, isl_set_copy(Domain));
+}
+
 void ScopStmt::setScattering(isl_map *NewScattering) {
   isl_map_free(Scattering);
   Scattering = NewScattering;
@@ -954,6 +963,90 @@ __isl_give isl_union_set *Scop::getDomains() {
   return Domain;
 }
 
+__isl_give isl_union_map *Scop::getWrites() {
+  isl_union_map *Write = isl_union_map_empty(this->getParamSpace());
+
+  for (Scop::iterator SI = this->begin(), SE = this->end(); SI != SE; ++SI) {
+    ScopStmt *Stmt = *SI;
+
+    for (ScopStmt::memacc_iterator MI = Stmt->memacc_begin(),
+                                   ME = Stmt->memacc_end();
+         MI != ME; ++MI) {
+      if (!(*MI)->isWrite())
+        continue;
+
+      isl_set *Domain = Stmt->getDomain();
+      isl_map *AccessDomain = (*MI)->getAccessRelation();
+
+      AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
+      Write = isl_union_map_add_map(Write, AccessDomain);
+    }
+  }
+  return isl_union_map_coalesce(Write);
+}
+
+__isl_give isl_union_map *Scop::getReads() {
+  isl_union_map *Read = isl_union_map_empty(this->getParamSpace());
+
+  for (Scop::iterator SI = this->begin(), SE = this->end(); SI != SE; ++SI) {
+    ScopStmt *Stmt = *SI;
+
+    for (ScopStmt::memacc_iterator MI = Stmt->memacc_begin(),
+                                   ME = Stmt->memacc_end();
+         MI != ME; ++MI) {
+      if (!(*MI)->isRead())
+        continue;
+
+      isl_set *Domain = Stmt->getDomain();
+      isl_map *AccessDomain = (*MI)->getAccessRelation();
+
+      AccessDomain = isl_map_intersect_domain(AccessDomain, Domain);
+      Read = isl_union_map_add_map(Read, AccessDomain);
+    }
+  }
+  return isl_union_map_coalesce(Read);
+}
+
+__isl_give isl_union_map *Scop::getSchedule() {
+  isl_union_map *Schedule = isl_union_map_empty(this->getParamSpace());
+
+  for (Scop::iterator SI = this->begin(), SE = this->end(); SI != SE; ++SI) {
+    ScopStmt *Stmt = *SI;
+    Schedule = isl_union_map_add_map(Schedule, Stmt->getScattering());
+  }
+  return isl_union_map_coalesce(Schedule);
+}
+
+bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
+  bool Changed = false;
+  for (Scop::iterator SI = this->begin(), SE = this->end(); SI != SE; ++SI) {
+    ScopStmt *Stmt = *SI;
+    isl_union_set *StmtDomain = isl_union_set_from_set(Stmt->getDomain());
+
+    isl_union_set *NewStmtDomain = isl_union_set_intersect(
+        isl_union_set_copy(StmtDomain), isl_union_set_copy(Domain));
+
+    if (isl_union_set_is_subset(StmtDomain, NewStmtDomain)) {
+      isl_union_set_free(StmtDomain);
+      isl_union_set_free(NewStmtDomain);
+      continue;
+    }
+
+    Changed = true;
+
+    isl_union_set_free(StmtDomain);
+    NewStmtDomain = isl_union_set_coalesce(NewStmtDomain);
+
+    if (isl_union_set_is_empty(NewStmtDomain)) {
+      Stmt->restrictDomain(isl_set_empty(Stmt->getDomainSpace()));
+      isl_union_set_free(NewStmtDomain);
+    } else
+      Stmt->restrictDomain(isl_set_from_union_set(NewStmtDomain));
+  }
+  isl_union_set_free(Domain);
+  return Changed;
+}
+
 ScalarEvolution *Scop::getSE() const { return SE; }
 
 bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
diff --git a/polly/lib/DeadCodeElimination.cpp b/polly/lib/DeadCodeElimination.cpp
index 04daeae340a..196200cbb7c 100644
--- a/polly/lib/DeadCodeElimination.cpp
+++ b/polly/lib/DeadCodeElimination.cpp
@@ -20,15 +20,34 @@
 //===----------------------------------------------------------------------===//
 
 #include "polly/Dependences.h"
-#include "isl/aff_type.h"
-#include "isl/union_map.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
+#include "llvm/Support/CommandLine.h"
+#include "isl/set.h"
+#include "isl/map.h"
+#include "isl/union_map.h"
 
 using namespace llvm;
 using namespace polly;
 
 namespace {
+enum DcePrecision {
+  DCE_PRECISION_AUTO,
+  DCE_PRECISION_HULL,
+  DCE_PRECISION_FULL
+};
+
+cl::opt<DcePrecision> DcePrecision(
+    "polly-dce-precision", cl::desc("Precision of Polyhedral DCE"),
+    cl::values(
+        clEnumValN(DCE_PRECISION_FULL, "full",
+                   "Live set is not approximated at each iteration"),
+        clEnumValN(
+            DCE_PRECISION_HULL, "hull",
+            "Live set is approximated with an affine hull at each iteration"),
+        clEnumValN(DCE_PRECISION_AUTO, "auto", "Currently the same as hull"),
+        clEnumValEnd),
+    cl::init(DCE_PRECISION_AUTO));
 
 class DeadCodeElim : public ScopPass {
 
@@ -37,25 +56,69 @@ public:
   explicit DeadCodeElim() : ScopPass(ID) {}
 
   virtual bool runOnScop(Scop &S);
+
   void printScop(llvm::raw_ostream &OS) const;
   void getAnalysisUsage(AnalysisUsage &AU) const;
+
+private:
+  isl_union_set *getLastWrites(isl_union_map *Writes, isl_union_map *Schedule);
+  bool eliminateDeadCode(Scop &S);
 };
 }
 
 char DeadCodeElim::ID = 0;
 
-bool DeadCodeElim::runOnScop(Scop &S) {
+/// Return the set of iterations that contains the last write for each location.
+isl_union_set *DeadCodeElim::getLastWrites(__isl_take isl_union_map *Writes,
+                                           __isl_take isl_union_map *Schedule) {
+  isl_union_map *WriteIterations = isl_union_map_reverse(Writes);
+  isl_union_map *WriteTimes =
+      isl_union_map_apply_range(WriteIterations, isl_union_map_copy(Schedule));
+
+  isl_union_map *LastWriteTimes = isl_union_map_lexmax(WriteTimes);
+  isl_union_map *LastWriteIterations = isl_union_map_apply_range(
+      LastWriteTimes, isl_union_map_reverse(Schedule));
+
+  isl_union_set *Live = isl_union_map_range(LastWriteIterations);
+  return isl_union_set_coalesce(Live);
+}
+
+/// Performs polyhedral dead iteration elimination by:
+/// o Assuming that the last write to each location is live.
+/// o Following each RAW dependency from a live iteration backwards and adding
+///   that iteration to the live set.
+bool DeadCodeElim::eliminateDeadCode(Scop &S) {
+  isl_union_set *Live = this->getLastWrites(S.getWrites(), S.getSchedule());
+
   Dependences *D = &getAnalysis<Dependences>();
+  isl_union_map *Dep = D->getDependences(Dependences::TYPE_RAW);
+  Dep = isl_union_map_reverse(Dep);
 
-  int Kinds =
-      Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
+  isl_union_set *OriginalDomain = S.getDomains();
+  while (true) {
+    isl_union_set *Extra;
 
-  isl_union_map *Deps = D->getDependences(Kinds);
+    Extra =
+        isl_union_set_apply(isl_union_set_copy(Live), isl_union_map_copy(Dep));
 
-  isl_union_map_free(Deps);
-  return false;
+    if (isl_union_set_is_subset(Extra, Live)) {
+      isl_union_set_free(Extra);
+      break;
+    }
+
+    Live = isl_union_set_union(Live, Extra);
+    if (DcePrecision != DCE_PRECISION_FULL)
+      Live = isl_union_set_affine_hull(Live);
+    Live = isl_union_set_intersect(Live, isl_union_set_copy(OriginalDomain));
+  }
+  isl_union_map_free(Dep);
+  isl_union_set_free(OriginalDomain);
+
+  return S.restrictDomains(isl_union_set_coalesce(Live));
 }
 
+bool DeadCodeElim::runOnScop(Scop &S) { return eliminateDeadCode(S); }
+
 void DeadCodeElim::printScop(raw_ostream &OS) const {}
 
 void DeadCodeElim::getAnalysisUsage(AnalysisUsage &AU) const {