From 161d29ca4091bb1ff79736a416978b49989fc622 Mon Sep 17 00:00:00 2001
From: Derek Lamberti <derek.lamberti@arm.com>
Date: Mon, 7 Dec 2020 13:54:12 +0000
Subject: Sort subgraphview layers on construction

Make it easier for backends to traverse the subgraph during optimization

Change-Id: I140cb11f78bab5f19c801a5b55efffb38c63837f
Signed-off-by: Derek Lamberti <derek.lamberti@arm.com>
---
 src/armnn/SubgraphView.cpp           | 15 +++++++++++++++
 src/armnn/SubgraphView.hpp           |  3 +++
 src/armnn/test/SubgraphViewTests.cpp | 27 +++++++++++++++++++++++++++
 3 files changed, 45 insertions(+)

diff --git a/src/armnn/SubgraphView.cpp b/src/armnn/SubgraphView.cpp
index 92ba5dfe1f..0d41889e15 100644
--- a/src/armnn/SubgraphView.cpp
+++ b/src/armnn/SubgraphView.cpp
@@ -45,6 +45,7 @@ SubgraphView::SubgraphView(Graph& graph)
     , m_OutputSlots{}
     , m_Layers(graph.begin(), graph.end())
 {
+    ArrangeBySortOrder();
     CheckSubgraph();
 }
 
@@ -53,6 +54,7 @@ SubgraphView::SubgraphView(InputSlots&& inputs, OutputSlots&& outputs, Layers&&
     , m_OutputSlots{outputs}
     , m_Layers{layers}
 {
+    ArrangeBySortOrder();
     CheckSubgraph();
 }
 
@@ -61,6 +63,7 @@ SubgraphView::SubgraphView(const SubgraphView& subgraph)
     , m_OutputSlots(subgraph.m_OutputSlots.begin(), subgraph.m_OutputSlots.end())
     , m_Layers(subgraph.m_Layers.begin(), subgraph.m_Layers.end())
 {
+    ArrangeBySortOrder();
     CheckSubgraph();
 }
 
@@ -69,6 +72,7 @@ SubgraphView::SubgraphView(SubgraphView&& subgraph)
     , m_OutputSlots(std::move(subgraph.m_OutputSlots))
     , m_Layers(std::move(subgraph.m_Layers))
 {
+    ArrangeBySortOrder();
     CheckSubgraph();
 }
 
@@ -199,4 +203,15 @@ void SubgraphView::Clear()
     m_Layers.clear();
 }
 
+void SubgraphView::ArrangeBySortOrder()
+{
+    using LayerList = std::list<Layer*>;
+    auto compareLayerPriority = [](const LayerList::value_type& layerA, const LayerList::value_type& layerB)
+        {
+            return layerA->GetPriority() < layerB->GetPriority();
+        };
+
+    m_Layers.sort(compareLayerPriority);
+}
+
 } // namespace armnn
diff --git a/src/armnn/SubgraphView.hpp b/src/armnn/SubgraphView.hpp
index 1b9c308daa..cb9e415dd2 100644
--- a/src/armnn/SubgraphView.hpp
+++ b/src/armnn/SubgraphView.hpp
@@ -86,6 +86,9 @@ public:
 private:
     void CheckSubgraph();
 
+    /// Arrange the order of layers topologically so that nodes can be visited in valid order
+    void ArrangeBySortOrder();
+
     /// The list of pointers to the input slots of the parent graph.
     InputSlots m_InputSlots;
 
diff --git a/src/armnn/test/SubgraphViewTests.cpp b/src/armnn/test/SubgraphViewTests.cpp
index a8cb797d17..73ef8bea91 100644
--- a/src/armnn/test/SubgraphViewTests.cpp
+++ b/src/armnn/test/SubgraphViewTests.cpp
@@ -1582,4 +1582,31 @@ BOOST_AUTO_TEST_CASE(SubgraphCycles)
     }
 }
 
+BOOST_AUTO_TEST_CASE(SubgraphOrder)
+{
+    Graph graph;
+
+    auto input      = graph.AddLayer<InputLayer>(0, "Input");
+    auto activation = graph.AddLayer<ActivationLayer>(ActivationDescriptor{}, "Activation");
+    auto output     = graph.AddLayer<OutputLayer>(1, "Output");
+
+    input->GetOutputSlot(0).Connect(activation->GetInputSlot(0));
+    activation->GetOutputSlot(0).Connect(output->GetInputSlot(0));
+
+    //Add in out of order
+    auto view = CreateSubgraphViewFrom({},
+                                       {},
+                                       {output, input, activation});
+
+    // Check the layers are sorted topologically in the view
+    int idx=0;
+    LayerType expectedSorted[] = {LayerType::Input, LayerType::Activation, LayerType::Output};
+    view->ForEachLayer([&idx, &expectedSorted](const Layer* l)
+        {
+            BOOST_TEST((expectedSorted[idx] == l->GetType()));
+            idx++;
+        }
+    );
+}
+
 BOOST_AUTO_TEST_SUITE_END()
-- 
cgit v1.2.1