diff options
Diffstat (limited to 'runtime/neurun/core/src/ir/Graph.cc')
| -rw-r--r-- | runtime/neurun/core/src/ir/Graph.cc | 551 |
1 files changed, 551 insertions, 0 deletions
diff --git a/runtime/neurun/core/src/ir/Graph.cc b/runtime/neurun/core/src/ir/Graph.cc new file mode 100644 index 000000000..a84ebb68b --- /dev/null +++ b/runtime/neurun/core/src/ir/Graph.cc @@ -0,0 +1,551 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "ir/Graph.h" + +#include <algorithm> +#include <bitset> +#include <sstream> + +#include "util/logging.h" +#include "verifier/Verifier.h" +#include "cpp14/memory.h" +#include "ir/operation/LowerInfo.h" +#include "ir/operand/LowerInfo.h" +#include "ir/operand/PermuteFactor.h" +#include "ir/GraphIterator.h" +#include "operand/Shape4DConvert.h" +#include "compiler/BackendResolver.h" +#include "backend/IConfig.h" +#include "pass/ConstantInsertionPass.h" +#include "pass/PermutationInsertionPass.h" +#include "pass/PermutationEliminationPass.h" +#include "pass/PermutationOperationPass.h" + +namespace neurun +{ +namespace ir +{ + +Graph::Graph() = default; + +Graph::~Graph(void) = default; + +OperandIndex Graph::addOperand(const Shape &shape, const TypeInfo &type) +{ + return _operands.emplace(shape, type); +} + +OperationIndex Graph::addOperation(std::unique_ptr<Operation> &&node) +{ + assert(isBuildingPhase()); + return _operations.push(std::move(node)); +} + +void Graph::setOperandValue(const OperandIndex &ind, std::unique_ptr<Data> &&data) +{ + assert(isBuildingPhase()); + assert(_operands.exist(ind)); + _operands.at(ind).data(std::move(data)); +} + +void Graph::addInput(const OperandIndex &ind) +{ + assert(isBuildingPhase()); + _inputs.append(ind); +} + +void Graph::addOutput(const OperandIndex &ind) +{ + assert(isBuildingPhase()); + _outputs.append(ind); +} + +void Graph::finishBuilding(void) +{ + assert(isBuildingPhase()); + _phase = Phase::MODEL; + + // Initialize operand use-def + initializeUseDef(); + + // Call graph verifications for the MODEL phase + { + assert(verifier::DAGChecker().verify(*this)); + assert(verifier::EdgeConsistencyChecker().verify(*this)); + } +} + +void Graph::lower(void) +{ + assert(_phase == Phase::MODEL); + + _op_seqs = nnfw::cpp14::make_unique<Subgraphs>(); + + // Lower + { + // operand::LowerInfo holder + OperandIndexMap<std::unique_ptr<operand::LowerInfo>> operands_lower_info; + + _operands.iterate([&](const OperandIndex &index, const Operand &object) { + operands_lower_info[index] = + nnfw::cpp14::make_unique<operand::LowerInfo>(operand::asShape4D(object.shape())); + }); + + _lower_info_map = nnfw::cpp14::make_unique<LowerInfoMap>(); + + // Make subgraphs while checking whether a node can be merged into a op_seq. + makeSubgraphs(operands_lower_info); + + _op_seqs->iterate([&](const SubgraphIndex &, OpSequence &subg) { + assert(subg.operations().size() > 0); + std::reverse(std::begin(subg.operations()), std::end(subg.operations())); + }); + + _op_seqs->dump("merged and sorted operations without permutation"); + + pass::ConstantInsertionPass ci_pass(*this); + ci_pass.run(); + + // Set LowerInfo for each operand from the operand::LowerInfo holder + manipulateLowerInfo(operands_lower_info); + + dumpLowerInfo(); + } + + // Run Permutation Passes + { + pass::PermutationOperationPass po_pass(*this); + po_pass.run(); + + pass::PermutationInsertionPass pi_pass(*this); + pi_pass.run(); + // Implemented code no longer works. + // pass::PermutationEliminationPass pe_pass(*this); + // pe_pass.run(); + + // TODO merge perm subgraphs if possible + _op_seqs->dump("merged and sorted operations with permutation"); + } + + // Graph verifications for the LOWERED phase + { + assert(verifier::DAGChecker().verify(*this)); + assert(verifier::EdgeConsistencyChecker().verify(*this)); + } +} + +void Graph::initializeUseDef() +{ + operations().iterate([&](const OperationIndex &index, const Operation &node) -> void { + auto outputs = node.getOutputs(); + for (auto output : outputs) + { + operands().at(output).appendDef(index); + } + + auto inputs = node.getInputs(); + for (auto input : inputs) + { + operands().at(input).appendUse(index); + } + }); +} + +const operation::LowerInfo *Graph::getLowerInfo(const SubgraphIndex &subg_index) const +{ + if (!_lower_info_map) + return nullptr; + auto itr = _lower_info_map->operation.find(subg_index); + if (itr == _lower_info_map->operation.end()) + return nullptr; + return itr->second.get(); +} + +void Graph::setLowerInfo(const SubgraphIndex &subg_index, + std::unique_ptr<operation::LowerInfo> &&lower_info) +{ + assert(_lower_info_map); + _lower_info_map->operation.insert(std::make_pair(subg_index, std::move(lower_info))); +} + +void Graph::removeLowerInfo(const SubgraphIndex &subg_index) +{ + auto &subg_lower_info = _lower_info_map->operation; + assert(subg_lower_info.find(subg_index) != subg_lower_info.end()); + for (auto it = subg_lower_info.begin(); it != subg_lower_info.end(); ++it) + { + if (it->first == subg_index) + { + subg_lower_info.erase(it); + break; + } + } +} + +const operand::LowerInfo *Graph::getLowerInfo(const OperandIndex &index) const +{ + if (!_lower_info_map) + return nullptr; + auto itr = _lower_info_map->operand.find(index); + if (itr == _lower_info_map->operand.end()) + return nullptr; + return itr->second.get(); +} + +operand::LowerInfo *Graph::getLowerInfo(const OperandIndex &index) +{ + if (!_lower_info_map) + return nullptr; + auto itr = _lower_info_map->operand.find(index); + if (itr == _lower_info_map->operand.end()) + return nullptr; + return itr->second.get(); +} + +void Graph::setLowerInfo(const OperandIndex &index, + std::unique_ptr<operand::LowerInfo> &&lower_info) +{ + assert(_lower_info_map); + _lower_info_map->operand.insert(std::make_pair(index, std::move(lower_info))); +} + +void Graph::removeLowerInfo(const OperandIndex &index) { _lower_info_map->operand.erase(index); } + +void Graph::makeSubgraphs(OperandIndexMap<std::unique_ptr<operand::LowerInfo>> &operands_lower_info) +{ + // if SUBG_MAX_NODE == 0, no limit on nodes of a op_seq + const int subg_max_node = util::getConfigInt(util::config::SUBG_MAX_NODE); + assert(subg_max_node >= 0); + + bool is_profiling = util::getConfigBool(util::config::PROFILING_MODE); + OpSequence *subg = nullptr; + SubgraphIndex subg_index; + + // NOTE: The below method appends nodes while making one op_seq if needed. If something better + // ways, happy to update this code. + PostDfsConstIterator{}.iterate(*this, [&](const OperationIndex &node_index, + const Operation &node) { + // LowerInfo for in/output operands + auto backend = _backend_resolver->getBackend(node_index); + + // TODO How to get frontend layout of this node from IR + auto frontend_layout = Layout::NHWC; + auto backend_layout = frontend_layout; + + // The layout of each backend should be set at another place + // TODO Change setting layout of each backend at another place + // TODO Remove getting id of backend + if (backend->config()->id() == "acl_cl" || backend->config()->id() == "acl_neon") + { + const std::string acl_layout_str = util::getConfigString(util::config::ACL_LAYOUT); + if (acl_layout_str == "NHWC") + { + backend_layout = Layout::NHWC; + } + else if (acl_layout_str == "NCHW") + { + backend_layout = Layout::NCHW; + } + } + else if (backend->config()->id() == "srcn") + { + const std::string ncnn_layout_str = util::getConfigString(util::config::NCNN_LAYOUT); + if (ncnn_layout_str == "NHWC") + { + backend_layout = Layout::NHWC; + } + else if (ncnn_layout_str == "NCHW") + { + backend_layout = Layout::NCHW; + } + } + else if (backend->config()->id() == "cpu") + { + backend_layout = Layout::NHWC; + } + + for (auto operand : node.getInputs()) + { + auto &&lower_info = operands_lower_info.at(operand); + lower_info->addUsePermuteFactor(operand::PermuteFactor{backend, backend_layout}); + } + for (auto operand : node.getOutputs()) + { + auto &&lower_info = operands_lower_info.at(operand); + lower_info->addDefPermuteFactor(operand::PermuteFactor{backend, backend_layout}); + } + + bool new_subg = + (subg == nullptr || + (subg_max_node != 0 && subg->operations().size() >= static_cast<size_t>(subg_max_node))); + + // for profiling each op_seq must contain just one node, + // so that we can measure a node separately + if (new_subg || is_profiling || !mergeable(subg_index, node_index, backend_layout)) + { + auto new_subg_index = appendFreshSingleOpSubgraph(node_index, node, frontend_layout); + + // OpSequence LowerInfo + setLowerInfo(new_subg_index, + nnfw::cpp14::make_unique<operation::LowerInfo>(backend, backend_layout)); + + subg_index = new_subg_index; + subg = &(_op_seqs->at(new_subg_index)); + + VERBOSE(Lower) << "SUBG#" << subg_index.value() << " is created for " + << "NODE#" << node_index.value() << "(" << node.name() << ")" << std::endl; + } + else + { + subg->appendOperation(node_index, node); + subg->setInputs(node.getInputs()); + + VERBOSE(Lower) << "SUBG#" << subg_index.value() << " merges " + << "NODE#" << node_index.value() << "(" << node.name() << ")" << std::endl; + } + }); +} + +void Graph::manipulateLowerInfo( + OperandIndexMap<std::unique_ptr<operand::LowerInfo>> &operands_lower_info) +{ + const auto default_backend = backend::BackendManager::get().getDefault(); + for (auto index : _inputs) + { + // Pick just any one from the uses, here the first one is chosen + // For the other uses, Permute operations will be inserted later + auto &&lower_info = operands_lower_info.at(index); + assert(lower_info->use_factors().size() > 0); + lower_info->addDefPermuteFactor(*lower_info->use_factors().begin()); + } + for (auto index : _outputs) + { + auto &&lower_info = operands_lower_info.at(index); + if (_operands.at(index).isConstant()) + { + lower_info->addDefPermuteFactor(operand::PermuteFactor{ + default_backend, + Layout::NHWC // TODO Get frontend layout of this node from IR + }); + } + } + + // Set LowerInfo for each operand from the operand::LowerInfo holder + _operands.iterate([&](const OperandIndex &index, Operand &) { + setLowerInfo(index, std::move(operands_lower_info[index])); + }); +} + +void Graph::dumpLowerInfo() +{ + if (::neurun::util::logging::ctx.enabled() == false) + return; + + std::map<uint32_t, std::string> dumps; + + _operands.iterate([&](const OperandIndex &index, Operand &object) { + std::stringstream sstream; + if (!getLowerInfo(index)->def_factors().empty() || !getLowerInfo(index)->use_factors().empty()) + { + auto factors_to_string = [](const operand::PermuteFactorSet &factors) { + std::string str; + for (auto factor : factors) + { + str += factor.backend()->config()->id(); + str += "(" + to_string(factor.layout()) + ")"; + str += " "; + } + return "{ " + str + "}"; + }; + + auto operation_index_to_string = [](const OperationIndexList &operations) { + std::string str; + for (auto op : operations.list()) + { + str += std::to_string(op.value()); + str += " "; + } + return "{ " + str + "}"; + }; + + const auto lower_info = getLowerInfo(index); + const auto &shape = object.shape(); + const auto &lower_shape = lower_info->shape(); + std::string def_ops = operation_index_to_string(object.getDef()); + std::string use_ops = operation_index_to_string(object.getUses()); + std::string def_layouts = factors_to_string(lower_info->def_factors()); + std::string use_layouts = factors_to_string(lower_info->use_factors()); + sstream << "Operand #" << index.value() << " LowerInfo" << std::endl; + sstream << " - Shape : { " << (shape.rank() > 0 ? shape.dim(0) : 0) << " " + << (shape.rank() > 1 ? shape.dim(1) : 0) << " " + << (shape.rank() > 2 ? shape.dim(2) : 0) << " " + << (shape.rank() > 3 ? shape.dim(3) : 0) << " " + << "}" << std::endl; + sstream << " - Def Operations : " << def_ops << std::endl; + sstream << " - Use Operations : " << use_ops << std::endl; + sstream << " - Lower Info" << std::endl; + sstream << " - 4D Shape (NHWC) : { " << lower_shape.n() << " " << lower_shape.h() << " " + << lower_shape.w() << " " << lower_shape.c() << " " + << "}" << std::endl; + sstream << " - Def Backends : " << def_layouts << std::endl; + sstream << " - Use Backends : " << use_layouts << std::endl; + } + dumps.emplace(index.value(), sstream.str()); + }); + + for (const auto &e : dumps) + { + if (!e.second.empty()) + { + VERBOSE(Lower) << e.second; + } + } +} + +bool Graph::mergeable(const SubgraphIndex &subg_index, const OperationIndex &node_index, + Layout layout) +{ + // Are they mergeable? + // 1. the same backend id and layout? + // 2. Is op_seq or node branched? + // 3. if 1 is true, the subg and a node are connected? + const auto &subg = _op_seqs->at(subg_index); + const auto &node = _operations.at(node_index); + + // The same backend id and layout? + { + const auto subg_backend_layout = getLowerInfo(subg_index)->layout(); + const auto &subg_backend_id = getLowerInfo(subg_index)->backend()->config()->id(); + const auto &node_backend_id = _backend_resolver->getBackend(node_index)->config()->id(); + VERBOSE(Lower) << "SUBG#" << subg_index.value() << " { " << subg_backend_id << "(" + << to_string(subg_backend_layout) << ") } " + << " NODE#" << node_index.value() << " (" << node.name() << ") { " + << node_backend_id << "(" << to_string(layout) << ") } " << std::endl; + if (subg_backend_id != node_backend_id || subg_backend_layout != layout) + return false; + } + + // Branched? + { + std::unordered_set<OperationIndex> branched_set; + + // Check for branching up + const auto &inputs = subg.getInputs(); + for (const auto &input : inputs) + { + const auto &input_obj = _operands.at(input); + for (const auto &def : input_obj.getDef().list()) + { + branched_set.insert(def); + if (branched_set.size() > 1) + { + return false; + } + } + } + branched_set.clear(); + + // Check for branching down + const auto &outputs = node.getOutputs(); + for (const auto &output : outputs) + { + const auto &output_obj = _operands.at(output); + for (const auto &use : output_obj.getUses().list()) + { + branched_set.insert(use); + if (branched_set.size() > 1) + { + 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<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.name() << ") is connected to NODE#" << node_index.value() << "(" + << node.name() << ")" << 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.name() << ") 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.name() << ")" << std::endl; + } + + return false; +} + +SubgraphIndex Graph::appendFreshSingleOpSubgraph(const OperationIndex &node_index, + const Operation &node, Layout layout) +{ + // Create a fresh op_seq with one operation, and append it to subgraphs + // Create a fresh op_seq + auto subg = nnfw::cpp14::make_unique<OpSequence>(layout); + + // Add an operation + subg->appendOperation(node_index, node); + + // Update input/output + subg->setOutputs(node.getOutputs()); + subg->setInputs(node.getInputs()); + + return _op_seqs->emplace(std::move(subg)); +} + +void Graph::setBackendResolver(std::unique_ptr<compiler::BackendResolver> &&br) +{ + _backend_resolver = std::move(br); +} + +} // namespace ir +} // namespace neurun |