From 9f452c0920e291d7e9e1ce97737ad6cac1ff5535 Mon Sep 17 00:00:00 2001
From: =?utf8?q?=EB=B0=95=EC=A2=85=ED=98=84/=EB=8F=99=EC=9E=91=EC=A0=9C?=
 =?utf8?q?=EC=96=B4Lab=28SR=29/Staff=20Engineer/=EC=82=BC=EC=84=B1?=
 =?utf8?q?=EC=A0=84=EC=9E=90?= <jh1302.park@samsung.com>
Date: Thu, 13 Sep 2018 08:01:15 +0900
Subject: [PATCH] [enco] Eliminate dead bags (#1473)

This commit implements dead bag elimination optimization pass in enco
NNAPI backend.

Signed-off-by: Jonghyun Park <jh1302.park@samsung.com>
---
 contrib/enco/core/src/Backend.cpp                  |  2 +
 contrib/enco/core/src/Transforms/Optimizations.cpp | 58 ++++++++++++++++++++++
 contrib/enco/core/src/Transforms/Optimizations.h   | 10 ++++
 3 files changed, 70 insertions(+)

diff --git a/contrib/enco/core/src/Backend.cpp b/contrib/enco/core/src/Backend.cpp
index 1d5728c..ae1a6b0 100644
--- a/contrib/enco/core/src/Backend.cpp
+++ b/contrib/enco/core/src/Backend.cpp
@@ -64,6 +64,8 @@ void Backend::compile(coco::Module *m, coco::Data *d)
 
   generate_bypass_shuffle(&code);
 
+  eliminate_dead_bag(&code);
+
   // Split instructions into a set of phases (each block serves as a phase)
   SplitPass split;
   split.runOnCode(&code);
diff --git a/contrib/enco/core/src/Transforms/Optimizations.cpp b/contrib/enco/core/src/Transforms/Optimizations.cpp
index ab5c4db..f48c343 100644
--- a/contrib/enco/core/src/Transforms/Optimizations.cpp
+++ b/contrib/enco/core/src/Transforms/Optimizations.cpp
@@ -78,3 +78,61 @@ void generate_bypass_shuffle(enco::Code *code)
 }
 
 } // namespace enco
+
+//
+// Dead Bag Elimination
+//
+#include <set>
+
+namespace
+{
+
+// @brief Return true if a given bag is marked as either input or output
+bool is_public(const coco::Bag *b) { return b->isInput() || b->isOutput(); }
+
+// @brief Return the set of "dead" bags in a given module
+std::set<coco::Bag *> dead_bags(const coco::Module *m)
+{
+  std::set<coco::Bag *> res;
+
+  for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n)
+  {
+    auto bag = m->entity()->bag()->at(n);
+
+    if (coco::readers(bag).empty() && !is_public(bag))
+    {
+      res.insert(bag);
+    }
+  }
+
+  return res;
+}
+
+} // namespace
+
+namespace enco
+{
+
+void eliminate_dead_bag(enco::Code *code)
+{
+  auto m = code->module();
+
+  // Destroy a dead bag and its updaters
+  for (auto bag : dead_bags(m))
+  {
+    for (auto updater : coco::updaters(bag))
+    {
+      auto ins = updater->loc();
+
+      assert(ins != nullptr);
+
+      ins->detach();
+      m->entity()->instr()->destroy(ins);
+    }
+
+    bag->replaceWith(nullptr);
+    m->entity()->bag()->destroy(bag);
+  }
+}
+
+} // namespace enco
diff --git a/contrib/enco/core/src/Transforms/Optimizations.h b/contrib/enco/core/src/Transforms/Optimizations.h
index 249174e..2a9f1c8 100644
--- a/contrib/enco/core/src/Transforms/Optimizations.h
+++ b/contrib/enco/core/src/Transforms/Optimizations.h
@@ -9,6 +9,16 @@ namespace enco
 // TODO Add a comment
 void generate_bypass_shuffle(enco::Code *code);
 
+/**
+ * @brief Eliminate dead bags
+ *
+ * A bag is referred to as dead if it is neither input nor output, and has no read. If a bag is
+ * dead, it is unnecessary to updates its values as these values are never used.
+ *
+ * "eliminate_dead_bag" removes all the dead bags and its updaters from IR.
+ */
+void eliminate_dead_bag(enco::Code *code);
+
 } // namespace enco
 
 #endif // __ENCO_OPTIMIZATIONS_H__
-- 
2.7.4