path: root/runtimes/neurun/src/graph/Graph.cc

/*
 * 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 "Graph.h"

#include <algorithm>
#include <bitset>

#include "util/logging.h"
#include "verifier/Verifier.h"
#include "cpp14/memory.h"
#include "linear/Linear.h"
#include "operation/LowerInfo.h"
#include "operand/LowerInfo.h"
#include "operand/Shape4DConvert.h"
#include "compiler/BackendResolver.h"
#include "backend/interface/IConfig.h"
#include "pass/PermutationInsertionPass.h"
#include "pass/PermutationEliminationPass.h"

namespace neurun
{
namespace graph
{

Graph::Graph(void) = default;

Graph::~Graph(void) = default;

model::operand::Index Graph::addOperand(const model::operand::Shape &shape,
                                        const model::operand::TypeInfo &type)
{
  return _model->operands.append(shape, type);
}

model::operation::Index Graph::addOperation(std::unique_ptr<model::operation::Node> &&node)
{
  assert(isBuildingPhase());
  return _model->operations.append(std::move(node));
}

void Graph::setOperandValue(const model::operand::Index &ind,
                            std::unique_ptr<model::operand::Data> &&data)
{
  assert(isBuildingPhase());
  assert(_model->operands.exist(ind));
  _model->operands.at(ind).data(std::move(data));
}

void Graph::addInput(const model::operand::Index &ind)
{
  assert(isBuildingPhase());
  _model->inputs.append(ind);
}

void Graph::addOutput(const model::operand::Index &ind)
{
  assert(isBuildingPhase());
  _model->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);

  // Lower
  {
    // operand::LowerInfo holder
    std::unordered_map<model::operand::Index, std::unique_ptr<operand::LowerInfo>>
        operands_lower_info;

    _model->operands.iterate([&](const model::operand::Index &index,
                                 const model::operand::Object &object) {
      operands_lower_info[index] =
          nnfw::cpp14::make_unique<operand::LowerInfo>(graph::operand::asShape4D(object.shape()));
    });

    _backend_resolver = nnfw::cpp14::make_unique<compiler::BackendResolver>(_model->operands);

    _model->operations.iterate(
        [&](const model::operation::Index &index, model::operation::Node &node) {
          auto backend = _backend_resolver->getBackend(typeid(node));

          // Operation LowerInfo
          setLowerInfo(index, nnfw::cpp14::make_unique<graph::operation::LowerInfo>(backend));

          // LowerInfo for in/output operands
          for (auto operand : node.getInputs())
          {
            auto &&lower_info = operands_lower_info.at(operand);
            lower_info->addUseBackend(backend);
          }
          for (auto operand : node.getOutputs())
          {
            auto &&lower_info = operands_lower_info.at(operand);
            lower_info->addDefBackend(backend);
          }
        });

    // Add def backend to model input/output operand as default backend
    for (auto index : getInputs())
    {
      auto &&lower_info = operands_lower_info.at(index);
      lower_info->addDefBackend(_backend_resolver->getDefaultBackend());
    }

    for (auto index : getOutputs())
    {
      auto &&lower_info = operands_lower_info.at(index);
      lower_info->addUseBackend(_backend_resolver->getDefaultBackend());
    }

    // Add DefBackend constants same as UseBackend
    // NOTE This assumes a constant operand is used by only one operation
    _model->operations.iterate([&](const model::operation::Index &, model::operation::Node &node) {
      // LowerInfo for input operands
      for (auto operand : node.getInputs())
      {
        auto &&lower_info = operands_lower_info.at(operand);
        if (lower_info->def_backends().empty())
        {
          lower_info->addDefBackend(lower_info->use_backends().getOnlyElement());
        }
      }
    });

    // Set LowerInfo for each operand from the operand::LowerInfo holder
    _model->operands.iterate([&](const model::operand::Index &index,
                                 model::operand::Object &object) {
      object.lower_info(std::move(operands_lower_info[index]));

      // Dump operand LowerInfo
      // TODO Extract this dumping procedure to be reusable
      if (!object.lower_info()->def_backends().empty() ||
          !object.lower_info()->use_backends().empty())
      {
        auto backends_to_string = [](const operand::BackendSet &backends) {
          std::string str;
          for (auto backend : backends)
          {
            str += backend->config()->id();
            str += " ";
          }
          return "{ " + str + "}";
        };

        auto operation_index_to_string = [](const model::operation::IndexList &operations) {
          std::string str;
          for (auto op : operations.list())
          {
            str += std::to_string(op.value());
            str += " ";
          }
          return "{ " + str + "}";
        };

        const auto &lower_info = object.lower_info();
        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 = backends_to_string(lower_info->def_backends());
        std::string use_layouts = backends_to_string(lower_info->use_backends());
        VERBOSE(Lower) << "* Operand #" << index.value() << " LowerInfo" << std::endl;
        VERBOSE(Lower) << "  - Shape           : { " << shape.dim(0) << " "
                       << (shape.rank() > 1 ? shape.dim(1) : 0) << " "
                       << (shape.rank() > 2 ? shape.dim(2) : 0) << " "
                       << (shape.rank() > 3 ? shape.dim(3) : 0) << " "
                       << "}" << std::endl;
        VERBOSE(Lower) << "  - Def Operations  : " << def_ops << std::endl;
        VERBOSE(Lower) << "  - Use Operations  : " << use_ops << std::endl;
        VERBOSE(Lower) << "  - Lower Info" << std::endl;
        VERBOSE(Lower) << "    - 4D Shape (NHWC) : { " << lower_shape.n() << " " << lower_shape.h()
                       << " " << lower_shape.w() << " " << lower_shape.c() << " "
                       << "}" << std::endl;
        VERBOSE(Lower) << "    - Def Backends    : " << def_layouts << std::endl;
        VERBOSE(Lower) << "    - Use Backends    : " << use_layouts << std::endl;
      }
    });
  }

  // Run PermutationInsertionPass
  {
    pass::PermutationInsertionPass pi_pass(*this);
    pi_pass.run();
    pass::PermutationEliminationPass pe_pass(*this);
    pe_pass.run();
  }

  // Graph verifications for the LOWERED phase
  {
    assert(verifier::DAGChecker().verify(*this));
    assert(verifier::EdgeConsistencyChecker().verify(*this));
  }
}

std::unique_ptr<linear::Linear> Graph::linearize(void)
{
  assert(_phase == Phase::MODEL);

  auto linear = nnfw::cpp14::make_unique<linear::Linear>(*this);

  // TODO Move the operations and operands to linear object
  return std::move(linear);
}

void Graph::initializeUseDef()
{
  operations().iterate(
      [&](const model::operation::Index &index, const model::operation::Node &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 model::operation::Index &index) const
{
  auto itr = _operation_lower_info.find(index);
  if (itr == _operation_lower_info.end())
    return nullptr;
  return itr->second.get();
}

void Graph::setLowerInfo(const model::operation::Index &index,
                         std::unique_ptr<operation::LowerInfo> &&lower_info)
{
  _operation_lower_info.insert(std::make_pair(index, std::move(lower_info)));
}

} // namespace graph
} // namespace neurun

namespace neurun
{
namespace graph
{

// Explicit instantiations to have implementation in the source file.

template class Graph::DefaultIterator<true>;
template class Graph::DefaultIterator<false>;

template class Graph::PostDfsIterator<true>;
template class Graph::PostDfsIterator<false>;

//
// Graph::DefaultIterator
//

template <bool is_const>
void Graph::DefaultIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
{
  graph.operations().iterate(
      [&](const model::operation::Index &index, NodeRef node) -> void { fn(index, node); });
}

//
// Graph::PostDfsIterator
//

template <bool is_const>
void Graph::PostDfsIterator<is_const>::iterate(GraphRef graph, const IterFn &fn) const
{
  assert(!graph.isBuildingPhase()); // Restrict iteration condition

  std::unordered_map<model::operation::Index, bool> visited;
  graph.operations().iterate(
      [&](const model::operation::Index &index, NodeRef) { visited[index] = false; });

  std::function<void(const model::operation::Index &, NodeRef)> dfs_recursive =
      [&](const model::operation::Index &index, NodeRef node) -> void {
    if (visited[index])
      return;
    visited[index] = true;

    for (auto output : node.getOutputs())
    {
      const auto &operand = graph.operands().at(output);
      for (const auto &use : operand.getUses().list())
      {
        dfs_recursive(use, graph.operations().at(use));
      }
    }

    fn(index, node);
  };

  graph.operations().iterate(dfs_recursive);

  // All of the operations(nodes) must have been visited.
  assert(std::all_of(
      visited.begin(), visited.end(),
      [](const std::pair<const model::operation::Index, bool> &v) { return v.second; }));
}

} // namespace graph
} // namespace neurun