runtime/onert/core/src/ir/GraphIterator.cc

   1 /*
   2  * Copyright (c) 2020 Samsung Electronics Co., Ltd. All Rights Reserved
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "GraphIterator.h"
  18
  19 #include "ir/OperationIndexMap.h"
  20 #include "ir/LoweredGraph.h"
  21
  22 namespace onert
  23 {
  24 namespace ir
  25 {
  26
  27 //
  28 // Graph::DefaultIterator
  29 //
  30
  31 template <bool is_const>
  32 void DefaultIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
  33 {
  34   graph.operations().iterate(
  35       [&](const OperationIndex &index, NodeRef node) -> void { fn(index, node); });
  36 }
  37
  38 //
  39 // Graph::PostDfsIterator
  40 //
  41
  42 template <bool is_const>
  43 void PostDfsIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
  44 {
  45   assert(!graph.isBuildingPhase()); // Restrict iteration condition
  46
  47   OperationIndexMap<bool> visited;
  48   graph.operations().iterate([&](const OperationIndex &index, NodeRef) { visited[index] = false; });
  49
  50   std::function<void(const OperationIndex &, NodeRef)> dfs_recursive =
  51       [&](const OperationIndex &index, NodeRef node) -> void {
  52     if (visited[index])
  53       return;
  54     visited[index] = true;
  55
  56     for (const auto output : node.getOutputs() | Remove::DUPLICATED)
  57     {
  58       const auto &operand = graph.operands().at(output);
  59       for (const auto &use : operand.getUses())
  60       {
  61         dfs_recursive(use, graph.operations().at(use));
  62       }
  63     }
  64
  65     fn(index, node);
  66   };
  67
  68   graph.operations().iterate(dfs_recursive);
  69
  70   // All of the operations(nodes) must have been visited.
  71   assert(std::all_of(visited.begin(), visited.end(),
  72                      [](const std::pair<const OperationIndex, bool> &v) { return v.second; }));
  73 }
  74
  75 template <bool is_const>
  76 void PostDfsIterator<is_const>::iterateOpSeqs(LoweredGraphRef lowered_graph,
  77                                               const OpSeqIterFn &fn) const
  78 {
  79   std::unordered_map<OpSequenceIndex, bool> visited;
  80   lowered_graph.op_seqs().iterate(
  81       [&](const OpSequenceIndex &index, OpSequenceRef) { visited[index] = false; });
  82
  83   std::function<void(const OpSequenceIndex &, OpSequenceRef)> dfs_recursive =
  84       [&](const OpSequenceIndex &index, OpSequenceRef op_seq) -> void {
  85     if (visited[index])
  86       return;
  87     visited[index] = true;
  88
  89     for (const auto output : op_seq.getOutputs() | Remove::DUPLICATED)
  90     {
  91       const auto &operand = lowered_graph.graph().operands().at(output);
  92       for (const auto &use : operand.getUses())
  93       {
  94         const auto use_op_seq_index = lowered_graph.op_seqs().getOperation(use);
  95         dfs_recursive(use_op_seq_index, lowered_graph.op_seqs().at(use_op_seq_index));
  96       }
  97     }
  98
  99     fn(index, op_seq);
 100   };
 101
 102   lowered_graph.op_seqs().iterate(dfs_recursive);
 103
 104   // All of the operations(nodes) must have been visited.
 105   assert(std::all_of(visited.begin(), visited.end(),
 106                      [](const std::pair<const OpSequenceIndex, bool> &v) { return v.second; }));
 107 }
 108
 109 // Explicit instantiations to have implementation in the source file.
 110 // NOTE If these instatiations were in the top of this file, `iterate` is compiled and saved in
 111 //      `GraphIterator.cc.o` but `iterateOpSeqs`. This happens only when cross-building for Android.
 112 //      (Maybe a bug of NDK toolchain(clang)?)
 113
 114 template class DefaultIterator<true>;
 115 template class DefaultIterator<false>;
 116
 117 template class PostDfsIterator<true>;
 118 template class PostDfsIterator<false>;
 119
 120 } // namespace ir
 121 } // namespace onert