From 2f11c7ffbb4907bc02714ad87d4351237459194c 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: Wed, 12 Sep 2018 17:13:07 +0900
Subject: [PATCH] [enco] Generate bypass shuffle (#1470)

This commit introduces bypass shuffle generation pass in enco NNAPI
backend.

Signed-off-by: Jonghyun Park <jh1302.park@samsung.com>
---
 contrib/enco/core/src/Backend.cpp                  |  3 +
 contrib/enco/core/src/Transforms/Optimizations.cpp | 80 ++++++++++++++++++++++
 contrib/enco/core/src/Transforms/Optimizations.h   | 14 ++++
 3 files changed, 97 insertions(+)
 create mode 100644 contrib/enco/core/src/Transforms/Optimizations.cpp
 create mode 100644 contrib/enco/core/src/Transforms/Optimizations.h

diff --git a/contrib/enco/core/src/Backend.cpp b/contrib/enco/core/src/Backend.cpp
index 40e14b0..1d5728c 100644
--- a/contrib/enco/core/src/Backend.cpp
+++ b/contrib/enco/core/src/Backend.cpp
@@ -6,6 +6,7 @@
 #include "Transforms/Duplicate.h"
 #include "Transforms/Rewrite.h"
 #include "Transforms/Normalize.h"
+#include "Transforms/Optimizations.h"
 #include "Transforms/Split.h"
 
 #include <stdexcept>
@@ -61,6 +62,8 @@ void Backend::compile(coco::Module *m, coco::Data *d)
   NormalizePass normalize;
   normalize.runOnCode(&code);
 
+  generate_bypass_shuffle(&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
new file mode 100644
index 0000000..ab5c4db
--- /dev/null
+++ b/contrib/enco/core/src/Transforms/Optimizations.cpp
@@ -0,0 +1,80 @@
+#include "Optimizations.h"
+
+#include <cassert>
+
+namespace enco
+{
+
+void generate_bypass_shuffle(enco::Code *code)
+{
+  auto m = code->module();
+
+  for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n)
+  {
+    auto bag = m->entity()->bag()->at(n);
+
+    // NOTE The current implementation assumes that all the updates occurs before the first read
+    // TODO Remove this assumption
+    for (auto u : coco::updaters(bag))
+    {
+      if ((u->loc() == nullptr) || (u->loc()->asShuffle() == nullptr))
+      {
+        // Skip if updater is not a Shuffle instruction
+        continue;
+      }
+
+      for (auto r : coco::readers(bag))
+      {
+        if ((r->loc() == nullptr) || (r->loc()->asShuffle() == nullptr))
+        {
+          // Skip if reader is not a Shuffle instruction
+          continue;
+        }
+
+        auto shuffle_1 = u->loc()->asShuffle();
+        auto shuffle_2 = r->loc()->asShuffle();
+
+        // Construct a shuffle instruction
+        auto shuffle_3 = m->entity()->instr()->create<coco::Shuffle>();
+
+        shuffle_3->from(shuffle_1->from());
+        shuffle_3->into(shuffle_2->into());
+
+        // Attempt to construct a valid bypass shuffle instruction
+        bool valid = true;
+
+        for (const auto &C : shuffle_2->range())
+        {
+          auto B = shuffle_2->at(C.value());
+
+          if (!shuffle_1->defined(B))
+          {
+            valid = false;
+            break;
+          }
+
+          auto A = shuffle_1->at(B);
+
+          shuffle_3->insert(A, C);
+        }
+
+        if (valid)
+        {
+          // Insert shuffle_3 before shuffle_2 if shuffle_3 is a valid bypass of shuffle_2
+          shuffle_3->insertBefore(shuffle_2);
+
+          // NOTE shuffle_2 SHOULD BE detached and destroyed after shuffle_3 is inserted
+          shuffle_2->detach();
+          m->entity()->instr()->destroy(shuffle_2);
+        }
+        else
+        {
+          // Destroy shuffle_3 (bypass shuffle) if it is invalid
+          m->entity()->instr()->destroy(shuffle_3);
+        }
+      }
+    }
+  }
+}
+
+} // namespace enco
diff --git a/contrib/enco/core/src/Transforms/Optimizations.h b/contrib/enco/core/src/Transforms/Optimizations.h
new file mode 100644
index 0000000..249174e
--- /dev/null
+++ b/contrib/enco/core/src/Transforms/Optimizations.h
@@ -0,0 +1,14 @@
+#ifndef __ENCO_OPTIMIZATIONS_H__
+#define __ENCO_OPTIMIZATIONS_H__
+
+#include "Code.h"
+
+namespace enco
+{
+
+// TODO Add a comment
+void generate_bypass_shuffle(enco::Code *code);
+
+} // namespace enco
+
+#endif // __ENCO_OPTIMIZATIONS_H__
-- 
2.7.4