[neurun] Apply code for merging node into subgraph to Graph (#5019)

Apply code for merging node into subgraph to Graph instead of 1 subrgaph
1 node code

Signed-off-by: Yongseop Kim <yons.kim@samsung.com>

1 files changed, 168 insertions, 22 deletions

diff --git a/runtimes/neurun/core/src/graph/Graph.cc b/runtimes/neurun/core/src/graph/Graph.cc
index 3a5166382..bc52095b0 100644
--- a/runtimes/neurun/core/src/graph/Graph.cc
+++ b/runtimes/neurun/core/src/graph/Graph.cc
@@ -110,8 +110,77 @@ void Graph::lower(void)
     _backend_resolver = nnfw::cpp14::make_unique<compiler::BackendResolver>(_model->operands);
     _lower_info_map = nnfw::cpp14::make_unique<LowerInfoMap>();
 
-    const auto &make_subgraph = [&](const model::OperationIndex &node_index,
-                                    const model::Operation &node) {
+    // Are they mergeable?
+    // 1. the same backend id?
+    // 2. if 1 is true, the subg and a node are connected?
+    auto mergeable = [&](const model::OperationIndex &subg_index,
+                         const model::OperationIndex &node_index) {
+      const auto &subg = _subg_ctx->at(subg_index);
+      const auto &node = _model->operations.at(node_index);
+
+      // The same backend id?
+      {
+        const auto &subg_backend_id = getLowerInfo(subg_index)->backend()->config()->id();
+        const auto &node_backend_id = _backend_resolver->getBackend(typeid(node))->config()->id();
+        VERBOSE(Lower) << "SUBG#" << subg_index.value() << " { " << subg_backend_id << " } "
+                       << " NODE#" << node_index.value() << " (" << node.getName() << ") { "
+                       << node_backend_id << " }" << std::endl;
+        if (subg_backend_id != node_backend_id)
+          return false;
+      }
+
+      // Connected?
+      // an input of one node is an output of the other node? or vice-versa?
+      {
+        const auto &node_inputs = node.getInputs();
+        const auto &node_outputs = node.getOutputs();
+
+        // subg's operations are in order so that we just check the first and the last
+        std::vector<model::operation::Element> subg_ops{subg.operations()[0]};
+        if (subg.operations().size() > 1)
+          subg_ops.emplace_back(subg.operations()[subg.operations().size() - 1]);
+
+        for (const auto &elem : subg_ops)
+        {
+          const auto &n_index = elem.index;
+          const auto &n = *elem.node;
+
+          // node's output == subg's input?
+          const auto &n_inputs = n.getInputs();
+          for (auto input : n_inputs)
+          {
+            if (node_outputs.contains(input))
+            {
+              VERBOSE(Lower) << "SUBG#" << subg_index.value() << " 's NODE#" << n_index.value()
+                             << "(" << n.getName() << ") is connected to NODE#"
+                             << node_index.value() << "(" << node.getName() << ")" << std::endl;
+              return true;
+            }
+          }
+
+          // node's input == subg's output?
+          const auto &n_outputs = n.getOutputs();
+          for (auto output : n_outputs)
+          {
+            if (node_inputs.contains(output))
+            {
+              VERBOSE(Lower) << "SUBG#" << subg_index.value() << " 's NODE#" << n_index.value()
+                             << " (" << n.getName() << ") is connected to NODE#"
+                             << node_index.value() << std::endl;
+              return true;
+            }
+          }
+        }
+
+        VERBOSE(Lower) << "SUBG#" << subg_index.value() << " is not connected to NODE#"
+                       << node_index.value() << "(" << node.getName() << ")" << std::endl;
+      }
+
+      return false;
+    };
+
+    auto make_subgraph = [&](const model::OperationIndex &node_index,
+                             const model::Operation &node) {
       auto subg_index = _subg_ctx->append(node_index, node);
       auto &subg = _subg_ctx->at(subg_index);
       subg.setOutputs(node.getOutputs());
@@ -119,30 +188,107 @@ void Graph::lower(void)
       return subg_index;
     };
 
-    // TODO Add code for merging(exactly appending properly) nodes in subgraph
-    // 1 subgraph 1 node
-    _model->operations.iterate([&](const model::OperationIndex &node_index,
-                                   model::Operation &node) {
-      auto new_subg_index = make_subgraph(node_index, node);
+    model::operation::Subgraph *subg = nullptr;
+    model::OperationIndex subg_index;
+
+    // Make subgraphs while checking whether a node can be merged into a subgraph.
+    // NOTE: The below method appends nodes while making one subgraph if needed. If something better
+    // ways, happy to update this code.
+    Graph::PostDfsConstIterator().iterate(
+        *this, [&](const model::OperationIndex &node_index, const model::Operation &node) {
+          // LowerInfo for in/output operands
+          auto backend = _backend_resolver->getBackend(typeid(node));
+          for (auto operand : node.getInputs())
+          {
+            auto &&lower_info = operands_lower_info.at(operand);
+            lower_info->addUseBackend(backend);
+          }
+          for (auto operand : node.getOutputs())
+          {
+            auto &&lower_info = operands_lower_info.at(operand);
+            lower_info->addDefBackend(backend);
+          }
 
-      auto backend = _backend_resolver->getBackend(typeid(node));
+          if (!subg || !mergeable(subg_index, node_index))
+          {
+            auto new_subg_index = make_subgraph(node_index, node);
 
-      // Operation LowerInfo
-      setLowerInfo(new_subg_index, nnfw::cpp14::make_unique<graph::operation::LowerInfo>(backend));
+            // Subgraph LowerInfo
+            setLowerInfo(new_subg_index, nnfw::cpp14::make_unique<graph::operation::LowerInfo>(
+                                             _backend_resolver->getBackend(typeid(node))));
 
-      // LowerInfo for in/output operands
-      for (auto operand : node.getInputs())
-      {
-        auto &&lower_info = operands_lower_info.at(operand);
-        lower_info->addUseBackend(backend);
-      }
-      for (auto operand : node.getOutputs())
-      {
-        auto &&lower_info = operands_lower_info.at(operand);
-        lower_info->addDefBackend(backend);
-      }
+            subg_index = new_subg_index;
+            subg = &(_subg_ctx->at(new_subg_index));
+
+            VERBOSE(Lower) << "SUBG#" << subg_index.value() << " is created for "
+                           << "NODE#" << node_index.value() << "(" << node.getName() << ")"
+                           << std::endl;
+          }
+          else
+          {
+            subg->appendOperation(node_index, node);
+            subg->setInputs(node.getInputs());
+
+            VERBOSE(Lower) << "SUBG#" << subg_index.value() << " merges "
+                           << "NODE#" << node_index.value() << "(" << node.getName() << ")"
+                           << std::endl;
+          }
+
+          bool finish = false;
+          {
+            size_t prev_op_cnt = 0;
+            for (auto input : node.getInputs())
+            {
+              // only valid_inputs
+              const auto &operand = _model->operands.at(input);
+              if (operand.usage() == model::operand::Usage::CONSTANT)
+                continue;
+
+              // This operand is input of operation, not weight or bias
+              if (operand.getDef().list().size() > 0)
+                ++prev_op_cnt;
+
+              // Test the node is Concat or BeginningBranch
+              // About (1)isConcat and (2)isBeginningBranch
+              //   (1) Current node has multiple inputs as concat?
+              //     - Does current node have two or more than previous operation?
+              //
+              //        [CONV] [CONV] [CONV]  [MAX_POOL]
+              //         |      |      |       |
+              //        [0]    [1]    [2]     [3]
+              //         \      |      |      /
+              //          [    C O N C A T   ]  # current node
+              //
+              //   (2) Current node is on the separated branch at the beginning?
+              //     - Does current node's input operand's uses have two or more than?
+              //
+              //       [CONV]
+              //         |
+              //        [0]----.
+              //         |     |
+              //       [CONV] [CONV]  # current node
+              //         |      |
+              //        [1]    [2]
+              //         \      /
+              //         [CONCAT]
+              if (prev_op_cnt > 1 || operand.getUses().list().size() > 1)
+              {
+                finish = true;
+                break;
+              }
+            }
+          }
+
+          if (finish)
+            subg = nullptr;
+        });
+
+    _subg_ctx->iterate([&](const model::OperationIndex &, model::operation::Subgraph &subg) {
+      assert(subg.operations().size() > 0);
+      std::reverse(std::begin(subg.operations()), std::end(subg.operations()));
     });
-    _subg_ctx->dump("1 subgraph 1 node without permutation");
+
+    _subg_ctx->dump("merged and sorted operations without permutation");
 
 // NOTE This is desired way to handle model input and outputs however getDefaultBackend() is
 // cpu backend dependent for now we cannot use it.