From 29c8370661a7dba309efca6b5e179e6bee8d54d5 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: Mon, 1 Oct 2018 16:19:53 +0900
Subject: [PATCH] [enco] Introduce Dead Object Elimination (#1691)

* [enco] Introduce Dead Object Elimination

This commit introduces Dead Object Elimination (DOE) pass in enco
compilation pipeline.

DOE is a special case of Dead Bag Elimination (DBE), but inserted in
order to reduce compilation overhead.

Signed-off-by: Jonghyun Park <jh1302.park@samsung.com>

* Fix a typo (updater -> producer)
---
 contrib/enco/core/src/Backend.cpp                  |  7 +++
 .../core/src/Transforms/DeadObjectElimination.cpp  | 67 ++++++++++++++++++++++
 .../core/src/Transforms/DeadObjectElimination.h    | 36 ++++++++++++
 3 files changed, 110 insertions(+)
 create mode 100644 contrib/enco/core/src/Transforms/DeadObjectElimination.cpp
 create mode 100644 contrib/enco/core/src/Transforms/DeadObjectElimination.h

diff --git a/contrib/enco/core/src/Backend.cpp b/contrib/enco/core/src/Backend.cpp
index 81a6ff0..2dbb66f 100644
--- a/contrib/enco/core/src/Backend.cpp
+++ b/contrib/enco/core/src/Backend.cpp
@@ -23,6 +23,7 @@
 #include "Transforms/FeatureUnification.h"
 #include "Transforms/Rewrite.h"
 #include "Transforms/Normalize.h"
+#include "Transforms/DeadObjectElimination.h"
 #include "Transforms/Optimizations.h"
 #include "Transforms/Split.h"
 
@@ -100,6 +101,12 @@ void BackendImpl::compile(coco::Module *m, coco::Data *d)
   NormalizePass normalize;
   normalize.runOnCode(&code);
 
+  // Eliminate dead object
+  //
+  // NOTE Dead Object Elimination (DOE) is performed before Copy lowering
+  //      in order to reduce compilation overhead.
+  eliminate_dead_object(&code);
+
   // Lower Copy as Shuffle
   lower_copy(&code);
 
diff --git a/contrib/enco/core/src/Transforms/DeadObjectElimination.cpp b/contrib/enco/core/src/Transforms/DeadObjectElimination.cpp
new file mode 100644
index 0000000..1f5970e
--- /dev/null
+++ b/contrib/enco/core/src/Transforms/DeadObjectElimination.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "DeadObjectElimination.h"
+
+#include <set>
+
+namespace
+{
+
+std::set<coco::Object *> dead_objects(const coco::Module *m)
+{
+  std::set<coco::Object *> res;
+
+  for (uint32_t n = 0; n < m->entity()->object()->size(); ++n)
+  {
+    auto obj = m->entity()->object()->at(n);
+    auto bag = obj->bag();
+
+    if (coco::readers(bag).empty() && !(bag->isOutput()))
+    {
+      res.insert(obj);
+    }
+  }
+
+  return res;
+}
+
+} // namespace
+
+namespace enco
+{
+
+void eliminate_dead_object(enco::Code *code)
+{
+  auto m = code->module();
+
+  // Destroy a dead object and its producer
+  for (auto obj : dead_objects(m))
+  {
+    if (auto producer = coco::producer(obj))
+    {
+      auto ins = producer->loc();
+      assert(ins != nullptr);
+
+      ins->detach();
+      m->entity()->instr()->destroy(ins);
+    }
+
+    m->entity()->object()->destroy(obj);
+  }
+}
+
+} // namespace enco
diff --git a/contrib/enco/core/src/Transforms/DeadObjectElimination.h b/contrib/enco/core/src/Transforms/DeadObjectElimination.h
new file mode 100644
index 0000000..8cefe92
--- /dev/null
+++ b/contrib/enco/core/src/Transforms/DeadObjectElimination.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__
+#define __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__
+
+#include "Code.h"
+
+namespace enco
+{
+
+/**
+ * @brief Eliminate dead objects in IR
+ *
+ * An object whose backing bag is unused is referred to as a dead object.
+ *
+ * Dead Object Elimination (DOE) eliminates such dead objects along with their producer.
+ */
+void eliminate_dead_object(enco::Code *code);
+
+} // namespace enco
+
+#endif // __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__
-- 
2.7.4