2 * Copyright (c) 2020 Samsung Electronics Co., Ltd. All Rights Reserved
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "GraphIterator.h"
19 #include "ir/OperationIndexMap.h"
20 #include "ir/LoweredGraph.h"
28 // Graph::DefaultIterator
31 template <bool is_const>
32 void DefaultIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
34 graph.operations().iterate(
35 [&](const OperationIndex &index, NodeRef node) -> void { fn(index, node); });
39 // Graph::PostDfsIterator
42 template <bool is_const>
43 void PostDfsIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
45 assert(!graph.isBuildingPhase()); // Restrict iteration condition
47 OperationIndexMap<bool> visited;
48 graph.operations().iterate([&](const OperationIndex &index, NodeRef) { visited[index] = false; });
50 std::function<void(const OperationIndex &, NodeRef)> dfs_recursive =
51 [&](const OperationIndex &index, NodeRef node) -> void {
54 visited[index] = true;
56 for (const auto output : node.getOutputs() | Remove::DUPLICATED)
58 const auto &operand = graph.operands().at(output);
59 for (const auto &use : operand.getUses())
61 dfs_recursive(use, graph.operations().at(use));
68 graph.operations().iterate(dfs_recursive);
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; }));
75 template <bool is_const>
76 void PostDfsIterator<is_const>::iterateOpSeqs(LoweredGraphRef lowered_graph,
77 const OpSeqIterFn &fn) const
79 std::unordered_map<OpSequenceIndex, bool> visited;
80 lowered_graph.op_seqs().iterate(
81 [&](const OpSequenceIndex &index, OpSequenceRef) { visited[index] = false; });
83 std::function<void(const OpSequenceIndex &, OpSequenceRef)> dfs_recursive =
84 [&](const OpSequenceIndex &index, OpSequenceRef op_seq) -> void {
87 visited[index] = true;
89 for (const auto output : op_seq.getOutputs() | Remove::DUPLICATED)
91 const auto &operand = lowered_graph.graph().operands().at(output);
92 for (const auto &use : operand.getUses())
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));
102 lowered_graph.op_seqs().iterate(dfs_recursive);
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; }));
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)?)
114 template class DefaultIterator<true>;
115 template class DefaultIterator<false>;
117 template class PostDfsIterator<true>;
118 template class PostDfsIterator<false>;