runtime/onert/core/src/interp/Interpreter.cc

   1 /*
   2  * Copyright (c) 2019 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 "Interpreter.h"
  18
  19 #include <stack>
  20 #include <unordered_set>
  21
  22 #include "Registration.h"
  23
  24 #include "ir/OperandIndexMap.h"
  25 #include "util/logging.h"
  26 #include "ir/OperationVisitor.h"
  27
  28 namespace onert
  29 {
  30 namespace interp
  31 {
  32
  33 // TODO more structured execution kernel implementation
  34 // TODO use cker for execution
  35 // TODO divide tensor prepare and execution
  36 // TODO introduce memory manager (buffer allocate and free)
  37 class OperationExecutor
  38 {
  39 public:
  40   OperationExecutor(ExecEnv *env) : _env{env}
  41   {
  42 #define INTERP_OP(InternalName) _kernels[ir::OpCode::InternalName] = get##InternalName();
  43 #include "InterpOps.lst"
  44 #undef INTERP_OP
  45   }
  46
  47   void execute(const ir::OperationIndex &idx)
  48   {
  49     const ir::Operation &node = _env->graph().operations().at(idx);
  50     const auto nodeName = node.name();
  51     VERBOSE(INTERPRETER) << "Prepare output operands and execute " << nodeName
  52                          << " operation (id: " << idx.value() << ")" << std::endl;
  53
  54     const auto nodeOpCode = node.opcode();
  55     if (_kernels.find(nodeOpCode) == _kernels.end())
  56     {
  57       throw std::runtime_error{"Interpreter: Operation " + nodeName + " is not yet implemented"};
  58     }
  59
  60     if (_kernels[nodeOpCode]->prepare != nullptr)
  61     {
  62       _kernels[nodeOpCode]->prepare(_env, node);
  63     }
  64     _kernels[nodeOpCode]->invoke(_env, node);
  65   }
  66
  67 private:
  68   ExecEnv *_env;
  69   std::unordered_map<ir::OpCode, OpKernel *> _kernels;
  70 };
  71
  72 void Interpreter::run()
  73 {
  74   VERBOSE(INTERPRETER) << "Interpreter is invoked " << std::endl;
  75
  76   // operand_stack: save operands prepared to use
  77   std::stack<ir::OperandIndex> operand_stack;
  78
  79   // Note: We should push input first, then constant.
  80   //       We use use-def for find operators ready to execution,
  81   //       but Use-Def cannot handle parameters (maybe constant, but not always)
  82   // Note: If all model inputs are constant, it may not work (depend on tensors' order).
  83   //       But that scenario may not exist
  84   for (auto ind : _env->graph().getInputs())
  85   {
  86     VERBOSE(INTERPRETER) << "Input: Push to operand stack " << ind.value() << std::endl;
  87
  88     operand_stack.push(ind);
  89   }
  90
  91   _env->graph().operands().iterate([&](const ir::OperandIndex &ind, const ir::Operand &obj) {
  92     if (obj.isConstant())
  93     {
  94       VERBOSE(INTERPRETER) << "Constant: Push to operand stack " << ind.value() << std::endl;
  95
  96       operand_stack.push(ind);
  97     }
  98   });
  99
 100   // Execution
 101   std::unordered_set<ir::OperandIndex> ready_check;
 102   std::unordered_set<ir::OperationIndex> executed;
 103   OperationExecutor executor{_env.get()};
 104   while (!operand_stack.empty())
 105   {
 106     const auto current_operand_index = operand_stack.top();
 107     operand_stack.pop();
 108     VERBOSE(INTERPRETER) << "Poped operand " << current_operand_index.value()
 109                          << " is checked ready to use" << std::endl;
 110
 111     assert(ready_check.find(current_operand_index) == ready_check.end());
 112     ready_check.insert(current_operand_index);
 113
 114     // Find prepared operations by scan use of current operand
 115     std::stack<ir::OperationIndex> operation_stack;
 116     const auto use_operators = _env->graph().operands().at(current_operand_index).getUses();
 117     for (const auto &use_operator : use_operators)
 118     {
 119       // Assumption: all parameters are ready to use
 120       bool operator_ready = true;
 121       for (auto input_index : _env->graph().operations().at(use_operator).getInputs())
 122       {
 123         if (ready_check.find(input_index) == ready_check.end())
 124         {
 125           operator_ready = false;
 126           break;
 127         }
 128       }
 129
 130       if (operator_ready)
 131       {
 132         VERBOSE(INTERPRETER) << "Ready to execute operation " << use_operator.value() << std::endl;
 133         operation_stack.push(use_operator);
 134       }
 135     }
 136
 137     while (!operation_stack.empty())
 138     {
 139       const auto current_operation_index = operation_stack.top();
 140       operation_stack.pop();
 141       VERBOSE(INTERPRETER) << "Poped operation: " << current_operation_index.value() << "("
 142                            << _env->graph().operations().at(current_operation_index).name() << ")"
 143                            << std::endl;
 144
 145       // execution
 146       // 1. Prepare output tensor
 147       // 2. Call operation kernel
 148       executor.execute(current_operation_index);
 149       executed.insert(current_operation_index);
 150
 151       // 3. Push each output into operand stack
 152       const auto def_operands = _env->graph().operations().at(current_operation_index).getOutputs();
 153       for (auto def_operand : def_operands)
 154       {
 155         VERBOSE(INTERPRETER) << "Buffer: Push to operand stack " << def_operand.value()
 156                              << std::endl;
 157         operand_stack.push(def_operand);
 158       }
 159
 160       // 4. Free if lifetime of buffer operands used by input is finished
 161       for (auto input_index : _env->graph().operations().at(current_operation_index).getInputs())
 162       {
 163         const auto use_operators = _env->graph().operands().at(input_index).getUses();
 164         bool dead_buffer = true;
 165         for (const auto &use_operator : use_operators)
 166         {
 167           if (executed.find(use_operator) == executed.end())
 168           {
 169             dead_buffer = false;
 170             break;
 171           }
 172         }
 173
 174         if (dead_buffer)
 175         {
 176           _env->freeIfAllocated(input_index);
 177         }
 178       }
 179     }
 180   }
 181 }
 182
 183 } // namespace interp
 184 } // namespace onert