IVGCVSW-3031 Finer grained backend optimization API

Change-Id: I9b93bc81b97f3d89fa046ba001854f732040e63a
Signed-off-by: Derek Lamberti <derek.lamberti@arm.com>

12 files changed, 242 insertions, 54 deletions

diff --git a/src/armnn/BackendSettings.hpp b/src/armnn/BackendSettings.hpp
index 931a0681db..e1344ab650 100644
--- a/src/armnn/BackendSettings.hpp
+++ b/src/armnn/BackendSettings.hpp
@@ -26,6 +26,14 @@ struct BackendSettings
         Initialize(preferredBackends, deviceSpec);
     }
 
+    BackendSettings(const BackendSettings& other)
+        : m_PreferredBackends(other.m_PreferredBackends)
+        , m_SupportedBackends(other.m_SupportedBackends)
+        , m_SelectedBackends(other.m_SelectedBackends)
+        , m_IgnoredBackends(other.m_IgnoredBackends)
+    {
+    }
+
     bool IsBackendPreferred(const BackendId& backend) const
     {
         return IsBackendInCollection(backend, m_PreferredBackends);
diff --git a/src/armnn/Graph.cpp b/src/armnn/Graph.cpp
index 9827b70de9..8c2b232ead 100644
--- a/src/armnn/Graph.cpp
+++ b/src/armnn/Graph.cpp
@@ -298,21 +298,18 @@ void Graph::AddCopyLayers()
     }
 }
 
-void Graph::SubstituteSubgraph(std::unique_ptr<SubgraphView> subgraph, IConnectableLayer* substituteLayer)
+void Graph::SubstituteSubgraph(SubgraphView& subgraph, IConnectableLayer* substituteLayer)
 {
-    BOOST_ASSERT(subgraph != nullptr);
     BOOST_ASSERT(substituteLayer != nullptr);
 
-    ReplaceSubgraphConnections(*subgraph, substituteLayer);
-    EraseSubgraphLayers(*subgraph);
+    ReplaceSubgraphConnections(subgraph, substituteLayer);
+    EraseSubgraphLayers(subgraph);
 }
 
-void Graph::SubstituteSubgraph(std::unique_ptr<SubgraphView> subgraph, const SubgraphView& substituteSubgraph)
+void Graph::SubstituteSubgraph(SubgraphView& subgraph, const SubgraphView& substituteSubgraph)
 {
-    BOOST_ASSERT(subgraph);
-
-    ReplaceSubgraphConnections(*subgraph, substituteSubgraph);
-    EraseSubgraphLayers(*subgraph);
+    ReplaceSubgraphConnections(subgraph, substituteSubgraph);
+    EraseSubgraphLayers(subgraph);
 }
 
 void Graph::ReplaceSubgraphConnections(const SubgraphView& subgraph, IConnectableLayer* substituteLayer)
@@ -377,12 +374,13 @@ void Graph::ReplaceSubgraphConnections(const SubgraphView& subgraph, const Subgr
     }
 }
 
-void Graph::EraseSubgraphLayers(const SubgraphView &subgraph)
+void Graph::EraseSubgraphLayers(SubgraphView &subgraph)
 {
     for (auto layer : subgraph.GetLayers())
     {
         EraseLayer(layer);
     }
+    subgraph.Clear();
 }
 
 void Graph::InferTensorInfos()
diff --git a/src/armnn/Graph.hpp b/src/armnn/Graph.hpp
index cc0ccaea77..88d2002112 100644
--- a/src/armnn/Graph.hpp
+++ b/src/armnn/Graph.hpp
@@ -163,8 +163,8 @@ public:
 
     /// Substitutes the given sub-graph with either a new layer or a new sub-graph.
     /// In either case, the given layer or all the layers in the given sub-graph must belong to this graph.
-    void SubstituteSubgraph(std::unique_ptr<SubgraphView> subgraph, IConnectableLayer* substituteLayer);
-    void SubstituteSubgraph(std::unique_ptr<SubgraphView> subgraph, const SubgraphView& substituteSubgraph);
+    void SubstituteSubgraph(SubgraphView& subgraph, IConnectableLayer* substituteLayer);
+    void SubstituteSubgraph(SubgraphView& subgraph, const SubgraphView& substituteSubgraph);
 
     void InferTensorInfos();
 
@@ -219,7 +219,7 @@ private:
 
     void ReplaceSubgraphConnections(const SubgraphView& subgraph, IConnectableLayer* substituteLayer);
     void ReplaceSubgraphConnections(const SubgraphView& subgraph, const SubgraphView& substituteSubgraph);
-    void EraseSubgraphLayers(const SubgraphView &subgraph);
+    void EraseSubgraphLayers(SubgraphView &subgraph);
 
     /// Mutable to allow sorting on const object.
     mutable LayerList m_Layers;
diff --git a/src/armnn/Network.cpp b/src/armnn/Network.cpp
index 1047567cc4..1eb40d5ba0 100644
--- a/src/armnn/Network.cpp
+++ b/src/armnn/Network.cpp
@@ -365,53 +365,57 @@ OptimizationResult ApplyBackendOptimizations(OptimizedNetwork* optNetObjPtr,
         for (auto& subgraph : subgraphs)
         {
             // Try to optimize the current sub-graph
-            bool optimizationAttempted = false;
-            SubgraphView::SubgraphViewPtr optSubgraph = backendObjPtr->OptimizeSubgraphView(*subgraph,
-                                                                                            optimizationAttempted);
-
-            // Check if the optimization has been attempted
-            if (!optimizationAttempted)
-            {
-                // No optimization attempted, keep the current sub-graph as it is and move to the next one
-                continue;
-            }
+            OptimizationViews optViews = backendObjPtr->OptimizeSubgraphView(*subgraph);
+            BOOST_ASSERT(optViews.Validate(*subgraph));
 
             // Optimization attempted, check the resulting optimized sub-graph
-            if (optSubgraph)
+            for (auto& substitution : optViews.GetSubstitutions())
             {
                 // Sub-graph optimized, substitute the sub-graph with the new optimized one in the main optimized graph
-                optGraph.SubstituteSubgraph(std::move(subgraph), *optSubgraph);
+                SubgraphView& optSubgraph = substitution.m_ReplacementSubgraph;
+                optGraph.SubstituteSubgraph(substitution.m_SubstitutableSubgraph, optSubgraph);
 
                 // Assign the current backend to the optimized sub-graph
-                std::for_each(optSubgraph->begin(), optSubgraph->end(), [&selectedBackend](Layer* l)
-                {
-                    BOOST_ASSERT(l);
-                    l->SetBackendId(selectedBackend);
-                });
+                std::for_each(optSubgraph.begin(), optSubgraph.end(), [&selectedBackend](Layer* l)
+                    {
+                        BOOST_ASSERT(l);
+                        l->SetBackendId(selectedBackend);
+                    });
             }
-            else
+
+            if (!optViews.GetFailedSubgraphs().empty())
             {
-                // An error occurred: the optimization was attempted but not performed, try different backends
                 std::stringstream warningMsg;
-                warningMsg << "Sub-graph failed to get optimized on " << backendObjPtr->GetId() << ". "
-                           << "Re-assigning backends to " << subgraph->GetLayers().size() << " layers inside sub-graph";
+                warningMsg << "Some sub-graph(s) failed to optimized on " << backendObjPtr->GetId() << " backend.";
                 ReportWarning(warningMsg.str(), errMessages);
 
                 // Failed to optimize the given sub-graph, re-assign the sub-graph layers to other available backends
+                BackendSettings settingsCopy(backendSettings);
                 if (!backendObjPtr->GetId().IsCpuRef())
                 {
                     // Add the current backend to the list of backends to ignore
-                    backendSettings.m_IgnoredBackends.insert(backendObjPtr->GetId());
+                    settingsCopy.m_IgnoredBackends.insert(backendObjPtr->GetId());
                 }
-                OptimizationResult reassignmentResult = AssignBackends(optNetObjPtr,
-                                                                       backendSettings,
-                                                                       *subgraph,
-                                                                       errMessages);
-                if (reassignmentResult.m_Error)
+
+                int count=0;
+                for (auto& failedSubgraph : optViews.GetFailedSubgraphs())
                 {
-                    // Failed to re-assign one of the remaining backends to each layer of the sub-graph
-                    result.m_Error = true;
-                    return result;
+                    // An error occurred: the optimization was attempted but not performed, try different backends
+                    std::stringstream subgraphMsg;
+                    subgraphMsg << "Re-assigning backends to " << failedSubgraph.GetLayers().size()
+                                << " layers inside sub-graph " << count++;
+                    ReportWarning(warningMsg.str(), errMessages);
+
+                    OptimizationResult reassignmentResult = AssignBackends(optNetObjPtr,
+                                                                           settingsCopy,
+                                                                           *subgraph,
+                                                                           errMessages);
+                    if (reassignmentResult.m_Error)
+                    {
+                        // Failed to re-assign one of the remaining backends to each layer of the sub-graph
+                        result.m_Error = true;
+                        return result;
+                    }
                 }
             }
         }
diff --git a/src/armnn/SubgraphView.cpp b/src/armnn/SubgraphView.cpp
index 9426f1eefc..a87cc9b268 100644
--- a/src/armnn/SubgraphView.cpp
+++ b/src/armnn/SubgraphView.cpp
@@ -92,6 +92,17 @@ SubgraphView::SubgraphView(IConnectableLayer* layer)
     CheckSubgraph();
 }
 
+SubgraphView& SubgraphView::operator=(SubgraphView&& other)
+{
+    m_InputSlots = std::move(other.m_InputSlots);
+    m_OutputSlots = std::move(other.m_OutputSlots);
+    m_Layers = std::move(other.m_Layers);
+
+    CheckSubgraph();
+
+    return *this;
+}
+
 void SubgraphView::CheckSubgraph()
 {
     // Check for invalid or duplicate input slots
@@ -179,4 +190,11 @@ SubgraphView::ConstIterator SubgraphView::cend() const
     return end();
 }
 
+void SubgraphView::Clear()
+{
+    m_InputSlots.clear();
+    m_OutputSlots.clear();
+    m_Layers.clear();
+}
+
 } // namespace armnn
diff --git a/src/armnn/SubgraphView.hpp b/src/armnn/SubgraphView.hpp
index d4d92bbf6c..d86f1c1c93 100644
--- a/src/armnn/SubgraphView.hpp
+++ b/src/armnn/SubgraphView.hpp
@@ -31,7 +31,7 @@ public:
     using ConstIterator = Layers::const_iterator;
 
     /// Constructs a sub-graph from the entire given graph.
-    SubgraphView(Graph& graph);
+    explicit SubgraphView(Graph& graph);
 
     /// Constructs a sub-graph with the given arguments.
     SubgraphView(InputSlots&& inputs, OutputSlots&& outputs, Layers&& layers);
@@ -45,6 +45,9 @@ public:
     /// Constructs a sub-graph with only the given layer.
     SubgraphView(IConnectableLayer* layer);
 
+    /// Move-assignment operator.
+    SubgraphView& operator=(SubgraphView&& other);
+
     const InputSlots& GetInputSlots() const;
     const OutputSlots& GetOutputSlots() const;
     const Layers& GetLayers() const;
@@ -67,6 +70,8 @@ public:
     ConstIterator cbegin() const;
     ConstIterator cend() const;
 
+    void Clear();
+
 private:
     void CheckSubgraph();
 
diff --git a/src/armnn/test/SubgraphViewTests.cpp b/src/armnn/test/SubgraphViewTests.cpp
index d580385797..7938171a33 100644
--- a/src/armnn/test/SubgraphViewTests.cpp
+++ b/src/armnn/test/SubgraphViewTests.cpp
@@ -159,7 +159,7 @@ BOOST_AUTO_TEST_CASE(SingleInputSingleOutput)
     Layer* const preCompiledLayer = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor, "pre-compiled");
 
     // Substitute sub-graph with pre-compiled layer
-    graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer);
+    graph.SubstituteSubgraph(*subgraph, preCompiledLayer);
 
     // Check that connections are correct after substitution
     BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn);
@@ -208,7 +208,7 @@ BOOST_AUTO_TEST_CASE(MultiInputSingleOutput)
     Layer* const preCompiledLayer = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor, "pre-compiled");
 
     // Substitute sub-graph with pre-compiled layer
-    graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer);
+    graph.SubstituteSubgraph(*subgraph, preCompiledLayer);
 
     // Check that connections are correct after substitution
     BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1);
@@ -257,7 +257,7 @@ BOOST_AUTO_TEST_CASE(SingleInputMultiOutput)
     Layer* const preCompiledLayer = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor, "pre-compiled");
 
     // Substitute sub-graph with pre-compiled layer
-    graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer);
+    graph.SubstituteSubgraph(*subgraph, preCompiledLayer);
 
     // Check that connections are correct after substitution
     BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1);
@@ -309,7 +309,7 @@ BOOST_AUTO_TEST_CASE(MultiInputMultiOutput)
     Layer* const preCompiledLayer = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor, "pre-compiled");
 
     // Substitute sub-graph with pre-compiled layer
-    graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer);
+    graph.SubstituteSubgraph(*subgraph, preCompiledLayer);
 
     // Check that connections are correct after substitution
     BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1);
@@ -354,7 +354,7 @@ BOOST_AUTO_TEST_CASE(EraseReplacedLayers)
     const SubgraphView::Layers subgraphLayers = subgraph->GetLayers();
 
     // Substitute sub-graph with pre-compiled layer
-    graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer);
+    graph.SubstituteSubgraph(*subgraph, preCompiledLayer);
 
     // Check that the layers belonging to the sub-graph have been erased from the graph after substitution
     BOOST_CHECK(!AreAnySubgraphLayersPresentInGraph(subgraphLayers, graph));
@@ -923,7 +923,7 @@ BOOST_AUTO_TEST_CASE(SingleSubgraph)
             Layer* const preCompiledLayer = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor, "pre-compiled");
 
             // Substitute sub-graph with pre-compiled layer
-            graph.SubstituteSubgraph((std::move(subgraphs[0])), preCompiledLayer);
+            graph.SubstituteSubgraph(*subgraphs[0], preCompiledLayer);
 
             // Check that connections are correct after substitution
             BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1);
@@ -1013,8 +1013,8 @@ BOOST_AUTO_TEST_CASE(MultipleSubgraphs)
             Layer* const preCompiledLayer2 = graph.AddLayer<PreCompiledLayer>(preCompiledDescriptor2, "pre-compiled2");
 
             // Substitute sub-graph with pre-compiled layer
-            graph.SubstituteSubgraph((std::move(subgraphs[0])), preCompiledLayer1);
-            graph.SubstituteSubgraph((std::move(subgraphs[1])), preCompiledLayer2);
+            graph.SubstituteSubgraph(*subgraphs[0], preCompiledLayer1);
+            graph.SubstituteSubgraph(*subgraphs[1], preCompiledLayer2);
 
             // Check that connections are correct after substitution
             BOOST_CHECK_EQUAL(preCompiledLayer1->GetInputSlot(0).GetConnection(), subgraph1InputConn);
diff --git a/src/backends/backendsCommon/CMakeLists.txt b/src/backends/backendsCommon/CMakeLists.txt
index 1aa4d99dc3..e1e387bc6f 100644
--- a/src/backends/backendsCommon/CMakeLists.txt
+++ b/src/backends/backendsCommon/CMakeLists.txt
@@ -18,6 +18,8 @@ list(APPEND armnnBackendsCommon_sources
     MakeWorkloadHelper.hpp
     MemCopyWorkload.cpp
     MemCopyWorkload.hpp
+    OptimizationViews.cpp
+    OptimizationViews.hpp
     OutputHandler.cpp
     OutputHandler.hpp
     WorkloadDataCollector.hpp
diff --git a/src/backends/backendsCommon/IBackendInternal.hpp b/src/backends/backendsCommon/IBackendInternal.hpp
index b3ddb55676..f49a210988 100644
--- a/src/backends/backendsCommon/IBackendInternal.hpp
+++ b/src/backends/backendsCommon/IBackendInternal.hpp
@@ -10,6 +10,8 @@
 #include <ISubgraphViewConverter.hpp>
 #include <SubgraphView.hpp>
 
+#include "OptimizationViews.hpp"
+
 #include <vector>
 
 namespace armnn
@@ -54,8 +56,38 @@ public:
     virtual Optimizations GetOptimizations() const = 0;
     virtual ILayerSupportSharedPtr GetLayerSupport() const = 0;
 
-    virtual SubgraphViewUniquePtr OptimizeSubgraphView(const SubgraphView& subgraph, bool& optimizationAttempted)
-        const = 0;
+    // @deprecated Use "OptimizationViews OptimizeSubgraphView(const SubgraphView&);" instead.
+    virtual SubgraphViewUniquePtr OptimizeSubgraphView(const SubgraphView& subgraph, bool& optimizationAttempted) const
+    {
+        optimizationAttempted=false;
+        return nullptr;
+    }
+
+    // Default implementation of OptimizeSubgraphView for backward compatibility with old API.
+    // Override this method with a custom optimization implementation.
+    virtual OptimizationViews OptimizeSubgraphView(const SubgraphView& subgraph)
+    {
+        bool attempted=false;
+        SubgraphViewUniquePtr optSubgraph = OptimizeSubgraphView(subgraph, attempted);
+
+        OptimizationViews result;
+        if (!attempted)
+        {
+            result.AddUntouchedSubgraph(SubgraphView(subgraph));
+        }
+        else
+        {
+            if (optSubgraph)
+            {
+                result.AddSubstituion({*optSubgraph.get(), subgraph});
+            }
+            else
+            {
+                result.AddFailedSubgraph(SubgraphView(subgraph));
+            }
+        }
+        return result;
+    }
 };
 
 using IBackendInternalUniquePtr = std::unique_ptr<IBackendInternal>;
diff --git a/src/backends/backendsCommon/OptimizationViews.cpp b/src/backends/backendsCommon/OptimizationViews.cpp
new file mode 100644
index 0000000000..1190eea57d
--- /dev/null
+++ b/src/backends/backendsCommon/OptimizationViews.cpp
@@ -0,0 +1,67 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#include "OptimizationViews.hpp"
+
+
+namespace armnn
+{
+
+bool OptimizationViews::Validate(const armnn::SubgraphView& originalSubgraph) const
+{
+    //This needs to verify that:
+    // 1) the sum of m_SuccesfulOptimizations & m_FailedOptimizations & m_UntouchedSubgraphs contains subgraphviews
+    //    which cover the entire space of the originalSubgraph.
+    // 2) Each SubstitutionPair contains matching inputs and outputs
+    bool valid = true;
+
+    // Create a copy of the layer list from the original subgraph and sort it
+    SubgraphView::Layers originalLayers = originalSubgraph.GetLayers();
+    originalLayers.sort();
+
+    // Create a new list based on the sum of all the subgraphs and sort it
+    SubgraphView::Layers countedLayers;
+    for (auto& failed : m_FailedOptimizations)
+    {
+        countedLayers.insert(countedLayers.end(), failed.GetLayers().begin(), failed.GetLayers().end());
+    }
+    for (auto& untouched : m_UntouchedSubgraphs)
+    {
+        countedLayers.insert(countedLayers.end(), untouched.GetLayers().begin(), untouched.GetLayers().end());
+    }
+    for (auto& successful : m_SuccesfulOptimizations)
+    {
+        countedLayers.insert(countedLayers.end(),
+                             successful.m_SubstitutableSubgraph.GetLayers().begin(),
+                             successful.m_SubstitutableSubgraph.GetLayers().end());
+    }
+    countedLayers.sort();
+
+    // Compare the two lists to make sure they match
+    valid &= originalLayers.size() == countedLayers.size();
+
+    auto oIt = originalLayers.begin();
+    auto cIt = countedLayers.begin();
+    for (size_t i=0; i < originalLayers.size() && valid; ++i, ++oIt, ++cIt)
+    {
+        valid &= (*oIt == *cIt);
+    }
+
+    // Compare the substitution subgraphs to ensure they are compatible
+    if (valid)
+    {
+        for (auto& substitution : m_SuccesfulOptimizations)
+        {
+            bool validSubstitution = true;
+            const SubgraphView& replacement = substitution.m_ReplacementSubgraph;
+            const SubgraphView& old = substitution.m_SubstitutableSubgraph;
+            validSubstitution &= replacement.GetInputSlots().size() == old.GetInputSlots().size();
+            validSubstitution &= replacement.GetOutputSlots().size() == old.GetOutputSlots().size();
+            valid &= validSubstitution;
+        }
+    }
+    return valid;
+}
+} //namespace armnn
diff --git a/src/backends/backendsCommon/OptimizationViews.hpp b/src/backends/backendsCommon/OptimizationViews.hpp
new file mode 100644
index 0000000000..cf7051d887
--- /dev/null
+++ b/src/backends/backendsCommon/OptimizationViews.hpp
@@ -0,0 +1,53 @@
+//
+// Copyright © 2017 Arm Ltd. All rights reserved.
+// SPDX-License-Identifier: MIT
+//
+
+#pragma once
+#include <SubgraphView.hpp>
+
+namespace armnn
+{
+class OptimizationViews
+{
+public:
+    OptimizationViews() = default;
+
+    struct SubstitutionPair
+    {
+        /// Subgraph of Layers from the original graph which should be replaced
+        SubgraphView m_SubstitutableSubgraph;
+
+        /// A subgraph of new layers which will replace layers in m_SubstitutableSubgraph
+        SubgraphView m_ReplacementSubgraph;
+    };
+
+    using Subgraphs = std::vector<SubgraphView>;
+    using Substitutions = std::vector<SubstitutionPair>;
+
+    void AddSubstituion(SubstitutionPair&& substitution)
+    {
+        m_SuccesfulOptimizations.emplace_back(substitution);
+    }
+
+    void AddFailedSubgraph(SubgraphView&& subgraph)
+    {
+        m_FailedOptimizations.emplace_back(subgraph);
+    }
+
+    void AddUntouchedSubgraph(SubgraphView&& subgraph)
+    {
+        m_UntouchedSubgraphs.emplace_back(subgraph);
+    }
+
+    Substitutions GetSubstitutions() const { return m_SuccesfulOptimizations; }
+    Subgraphs GetFailedSubgraphs() const { return m_FailedOptimizations; }
+    Subgraphs GetUntouchedSubgraphs() const { return m_UntouchedSubgraphs; }
+    bool Validate(const SubgraphView& originalSubgraph) const;
+
+private:
+    Substitutions m_SuccesfulOptimizations;     ///< Proposed substitutions from successful optimizations
+    Subgraphs m_FailedOptimizations;            ///< Subgraphs from the original subgraph which cannot be supported
+    Subgraphs m_UntouchedSubgraphs;             ///< Subgraphs from the original subgraph which remain unmodified
+};
+} //namespace armnn
\ No newline at end of file
diff --git a/src/backends/backendsCommon/common.mk b/src/backends/backendsCommon/common.mk
index a1cc0c1b3a..c993bfb674 100644
--- a/src/backends/backendsCommon/common.mk
+++ b/src/backends/backendsCommon/common.mk
@@ -12,6 +12,7 @@ COMMON_SOURCES := \
     CpuTensorHandle.cpp \
     LayerSupportBase.cpp \
     MemCopyWorkload.cpp \
+    OptimizationViews.cpp \
     OutputHandler.cpp \
     WorkloadData.cpp \
     WorkloadFactory.cpp \