runtime/onert/core/src/compiler/LoweredGraph.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 "compiler/LoweredGraph.h"
  18
  19 #include <assert.h>
  20 #include <sstream>
  21 #include "util/logging.h"
  22 #include "compiler/pass/ConstantInsertionPass.h"
  23 #include "compiler/pass/ConstantLoweringPass.h"
  24 #include "compiler/pass/PermutationOperationPass.h"
  25 #include "compiler/pass/PermutationInsertionPass.h"
  26 #include "compiler/pass/PermutationEliminationPass.h"
  27 #include "ir/GraphIterator.h"
  28 #include "ir/verifier/Verifier.h"
  29 #include "backend/Backend.h"
  30 #include "backend/IConfig.h"
  31 #include "compiler/BackendResolver.h"
  32 #include "compiler/ManualScheduler.h"
  33 #include "compiler/HEScheduler.h"
  34
  35 namespace onert
  36 {
  37 namespace compiler
  38 {
  39
  40 LoweredGraph::LoweredGraph(const ir::Graph &graph, const CompilerOptions &options) : _graph{graph}
  41 {
  42   bool linear_executor = (options.executor == "Linear");
  43
  44   // Build backend contexts
  45   auto &backend_manager = BackendManager::get();
  46
  47   // Always create Controlflow backend context
  48   auto cf_backend = backend_manager.getControlflow();
  49   _backend_contexts.emplace(
  50       cf_backend, cf_backend->newContext(_graph, _graph.getKernelBuilder(), linear_executor));
  51
  52   // Create contexts for other backends
  53   for (auto backend_str : options.backend_list)
  54   {
  55     backend_manager.loadBackend(backend_str);
  56     auto backend = backend_manager.get(backend_str);
  57
  58     // TODO As the default value of backend list contains "cpu", "acl_cl" and "acl_neon", and some
  59     // are not available on x64 or some other platforms. So this may be a workaround for x64 and
  60     // we should change it back(throw if backend is not loaded) later.
  61     if (!backend)
  62     {
  63       VERBOSE(LoweredGraph) << "Cannot load backend - " << backend_str;
  64       continue;
  65     }
  66
  67     _backend_contexts.emplace(
  68         backend, backend->newContext(_graph, _graph.getKernelBuilder(), linear_executor));
  69   }
  70   if (backend_manager.num_backends() == 0)
  71     throw std::runtime_error{"No available backends loaded."};
  72
  73   // TODO Move "schedule" phase out of here
  74   // Schedule
  75   std::unique_ptr<BackendResolver> backend_resolver;
  76   if (options.he_scheduler)
  77   {
  78     auto scheduler = HEScheduler(_backend_contexts, options);
  79     backend_resolver = scheduler.schedule(_graph);
  80     _indexed_ranks = scheduler.getIndexedRanks();
  81   }
  82   else
  83   {
  84     auto scheduler = ManualScheduler(_backend_contexts, options);
  85     backend_resolver = scheduler.schedule(_graph);
  86   }
  87
  88   {
  89     // operand::LowerInfo holder
  90     ir::OperandIndexMap<std::unique_ptr<ir::operand::LowerInfo>> operands_lower_info;
  91
  92     _graph.operands().iterate([&](const ir::OperandIndex &index, const ir::Operand &) {
  93       operands_lower_info[index] = std::make_unique<ir::operand::LowerInfo>();
  94     });
  95
  96     // Make op_seqs while checking whether a node can be merged into a op_seq.
  97     makeOpSequences(operands_lower_info, options, *backend_resolver);
  98
  99     _op_seqs.iterate([&](const ir::OpSequenceIndex &, ir::OpSequence &op_seq) {
 100       assert(op_seq.operations().size() > 0);
 101       std::reverse(std::begin(op_seq.operations()), std::end(op_seq.operations()));
 102     });
 103
 104     VERBOSE(OpSequences) << "dump without permutation" << std::endl;
 105     dumpOpSequences(_op_seqs, _graph.operations());
 106
 107     pass::ConstantInsertionPass ci_pass(*this);
 108     ci_pass.run();
 109
 110     pass::ConstantLoweringPass cl_pass(*this);
 111     cl_pass.run();
 112
 113     // Set LowerInfo for each operand from the operand::LowerInfo holder
 114     manipulateLowerInfo(operands_lower_info, options.is_primary_subgraph);
 115
 116     dumpLowerInfo();
 117   }
 118
 119   // Run Permutation Passes
 120   {
 121     pass::PermutationOperationPass po_pass(*this);
 122     po_pass.run();
 123
 124     pass::PermutationInsertionPass pi_pass(*this);
 125     pi_pass.run();
 126
 127     pass::PermutationEliminationPass pe_pass(*this);
 128     pe_pass.run();
 129
 130     VERBOSE(OpSequences) << "dump with permutation" << std::endl;
 131     dumpOpSequences(_op_seqs, _graph.operations());
 132   }
 133
 134   // Graph verifications
 135   {
 136     assert(ir::verifier::DAGChecker().verify(_graph));
 137     assert(ir::verifier::EdgeConsistencyChecker().verify(_graph));
 138   }
 139 }
 140
 141 const ir::operation::LowerInfo *
 142 LoweredGraph::getLowerInfo(const ir::OpSequenceIndex &op_seq_index) const
 143 {
 144   auto itr = _lower_info_map.op_seq.find(op_seq_index);
 145   if (itr == _lower_info_map.op_seq.end())
 146     return nullptr;
 147   return itr->second.get();
 148 }
 149
 150 void LoweredGraph::setLowerInfo(const ir::OpSequenceIndex &op_seq_index,
 151                                 std::unique_ptr<ir::operation::LowerInfo> &&lower_info)
 152 {
 153   _lower_info_map.op_seq.insert(std::make_pair(op_seq_index, std::move(lower_info)));
 154 }
 155
 156 void LoweredGraph::removeLowerInfo(const ir::OpSequenceIndex &op_seq_index)
 157 {
 158   auto &op_seq_lower_info = _lower_info_map.op_seq;
 159   assert(op_seq_lower_info.find(op_seq_index) != op_seq_lower_info.end());
 160   for (auto it = op_seq_lower_info.begin(); it != op_seq_lower_info.end(); ++it)
 161   {
 162     if (it->first == op_seq_index)
 163     {
 164       op_seq_lower_info.erase(it);
 165       break;
 166     }
 167   }
 168 }
 169
 170 const ir::operand::LowerInfo *LoweredGraph::getLowerInfo(const ir::OperandIndex &index) const
 171 {
 172   auto itr = _lower_info_map.operand.find(index);
 173   if (itr == _lower_info_map.operand.end())
 174     return nullptr;
 175   return itr->second.get();
 176 }
 177
 178 ir::operand::LowerInfo *LoweredGraph::getLowerInfo(const ir::OperandIndex &index)
 179 {
 180   auto itr = _lower_info_map.operand.find(index);
 181   if (itr == _lower_info_map.operand.end())
 182     return nullptr;
 183   return itr->second.get();
 184 }
 185
 186 void LoweredGraph::setLowerInfo(const ir::OperandIndex &index,
 187                                 std::unique_ptr<ir::operand::LowerInfo> &&lower_info)
 188 {
 189   _lower_info_map.operand.insert(std::make_pair(index, std::move(lower_info)));
 190 }
 191
 192 void LoweredGraph::removeLowerInfo(const ir::OperandIndex &index)
 193 {
 194   _lower_info_map.operand.erase(index);
 195 }
 196
 197 void LoweredGraph::iterateTopolOpSeqs(
 198     const std::function<void(const ir::OpSequenceIndex &, const ir::OpSequence &)> &fn) const
 199 {
 200   // Topological Sorting for ir::OpSequences
 201   std::vector<ir::OpSequenceIndex> topol_sorted;
 202   ir::PostDfsIterator<true>{}.iterateOpSeqs(
 203       *this, [&](const ir::OpSequenceIndex &index, const ir::OpSequence &) {
 204         topol_sorted.emplace_back(index);
 205       });
 206   std::reverse(topol_sorted.begin(), topol_sorted.end());
 207   for (const auto op_seq_idx : topol_sorted)
 208   {
 209     const auto &op_seq = _op_seqs.at(op_seq_idx);
 210     fn(op_seq_idx, op_seq);
 211   }
 212 }
 213
 214 void LoweredGraph::iterateTopolOpSeqs(
 215     const std::function<void(const ir::OpSequenceIndex &, ir::OpSequence &)> &fn)
 216 {
 217   // Topological Sorting for ir::OpSequences
 218   std::vector<ir::OpSequenceIndex> topol_sorted;
 219   ir::PostDfsIterator<false>{}.iterateOpSeqs(
 220       *this, [&](const ir::OpSequenceIndex &index, ir::OpSequence &) {
 221         topol_sorted.emplace_back(index);
 222       });
 223   std::reverse(topol_sorted.begin(), topol_sorted.end());
 224   for (const auto op_seq_idx : topol_sorted)
 225   {
 226     auto &op_seq = _op_seqs.at(op_seq_idx);
 227     fn(op_seq_idx, op_seq);
 228   }
 229 }
 230
 231 ir::OpSequenceIndex LoweredGraph::appendFreshSingleOpSequence(const ir::OperationIndex &node_index,
 232                                                               const ir::Operation &node)
 233 {
 234   // Create a fresh op_seq with one operation, and append it to op_seqs
 235   // Create a fresh op_seq
 236   auto op_seq = std::make_unique<ir::OpSequence>(_graph.layout());
 237
 238   // Add an operation
 239   op_seq->appendOperation(node_index);
 240
 241   // Update input/output
 242   op_seq->setOutputs(node.getOutputs());
 243   op_seq->setInputs(node.getInputs());
 244
 245   return _op_seqs.emplace(std::move(op_seq));
 246 }
 247
 248 void LoweredGraph::makeOpSequences(
 249     ir::OperandIndexMap<std::unique_ptr<ir::operand::LowerInfo>> &operands_lower_info,
 250     const CompilerOptions &options, const BackendResolver &backend_resolver)
 251 {
 252   // if SUBG_MAX_NODE == 0, no limit on nodes of a op_seq
 253   const int op_seq_max_node = options.op_seq_max_node;
 254   assert(op_seq_max_node >= 0);
 255
 256   bool is_profiling = options.he_profiling_mode;
 257   ir::OpSequence *op_seq = nullptr;
 258   ir::OpSequenceIndex op_seq_index;
 259
 260   // NOTE: The below method appends nodes while making one op_seq if needed. If something better
 261   // ways, happy to update this code.
 262   ir::PostDfsConstIterator{}.iterate(
 263       _graph, [&](const ir::OperationIndex &node_index, const ir::Operation &node) {
 264         // LowerInfo for in/output operands
 265         auto backend = backend_resolver.getBackend(node_index);
 266
 267         // Get frontend's layout
 268         auto frontend_layout = _graph.layout();
 269
 270         // The layout of each backend should be set at another place
 271         // TODO Change setting layout of each backend at another place
 272         auto backend_layout = backend->config()->supportLayout(node, frontend_layout);
 273
 274         for (auto operand : node.getInputs() | ir::Remove::UNDEFINED)
 275         {
 276           auto &&lower_info = operands_lower_info.at(operand);
 277           lower_info->addUsePermuteFactor(ir::operand::PermuteFactor{backend, backend_layout});
 278         }
 279         for (auto operand : node.getOutputs())
 280         {
 281           auto &&lower_info = operands_lower_info.at(operand);
 282           lower_info->addDefPermuteFactor(ir::operand::PermuteFactor{backend, backend_layout});
 283         }
 284
 285         bool new_op_seq = (op_seq == nullptr ||
 286                            (op_seq_max_node != 0 &&
 287                             op_seq->operations().size() >= static_cast<size_t>(op_seq_max_node)));
 288
 289         // for profiling each op_seq must contain just one node,
 290         // so that we can measure a node separately
 291         if (new_op_seq || is_profiling ||
 292             !mergeable(op_seq_index, node_index, backend_layout, backend_resolver))
 293         {
 294           auto new_op_seq_index = appendFreshSingleOpSequence(node_index, node);
 295
 296           // ir::OpSequence LowerInfo
 297           setLowerInfo(new_op_seq_index,
 298                        std::make_unique<ir::operation::LowerInfo>(backend, backend_layout));
 299
 300           op_seq_index = new_op_seq_index;
 301           op_seq = &(_op_seqs.at(new_op_seq_index));
 302
 303           VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " is created for "
 304                          << "NODE#" << node_index.value() << "(" << node.name() << ")" << std::endl;
 305         }
 306         else
 307         {
 308           op_seq->appendOperation(node_index);
 309           // Set inputs
 310           auto new_inputs = node.getInputs();
 311           // Add inputs except outputs of the previous node
 312           for (auto ind : op_seq->getInputs())
 313           {
 314             if (!node.getOutputs().contains(ind))
 315               new_inputs.append(ind);
 316           }
 317           op_seq->setInputs(new_inputs);
 318
 319           VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " merges "
 320                          << "NODE#" << node_index.value() << "(" << node.name() << ")" << std::endl;
 321         }
 322       });
 323 }
 324
 325 void LoweredGraph::manipulateLowerInfo(
 326     ir::OperandIndexMap<std::unique_ptr<ir::operand::LowerInfo>> &operands_lower_info,
 327     bool is_primary)
 328 {
 329   const auto controlflow_backend = BackendManager::get().getControlflow();
 330
 331   // TODO Rather than handling primary graph specially,
 332   //      let the permute inserted and remove it later
 333   if (is_primary)
 334   {
 335     // TODO Rather than using NHWC Get frontend layout of this node from IR
 336     auto factor = ir::operand::PermuteFactor{controlflow_backend, ir::Layout::NHWC};
 337     for (auto index : _graph.getInputs() | ir::Remove::UNDEFINED)
 338     {
 339       auto &&lower_info = operands_lower_info.at(index);
 340       assert(lower_info->def_factors().empty());
 341       lower_info->addDefPermuteFactor(factor);
 342     }
 343     for (auto index : _graph.getOutputs())
 344     {
 345       auto &&lower_info = operands_lower_info.at(index);
 346       lower_info->addUsePermuteFactor(factor);
 347     }
 348   }
 349   else
 350   {
 351     for (auto index : _graph.getInputs() | ir::Remove::UNDEFINED)
 352     {
 353       auto &&lower_info = operands_lower_info.at(index);
 354       if (!(lower_info->def_factors().size() == 0 && lower_info->use_factors().size() == 0))
 355       {
 356         // In case of not that Graph's input is not used in any operation and not the graph's
 357         // output.
 358         // In other words, it is not unused input in Graph.
 359         lower_info->addDefPermuteFactor(*lower_info->use_factors().begin());
 360       }
 361       else
 362       {
 363         // In case of that an operand is Graph's input and not input or output of any operation
 364         lower_info->addDefPermuteFactor(ir::operand::PermuteFactor{
 365             controlflow_backend,
 366             ir::Layout::NHWC // TODO Get frontend layout of this node from IR
 367         });
 368       }
 369     }
 370   }
 371   for (auto index : _graph.getOutputs())
 372   {
 373     auto &&lower_info = operands_lower_info.at(index);
 374     if (lower_info->def_factors().size() == 0)
 375     {
 376       // In case of that an operand is Graph's output and not input or output of any operation
 377       lower_info->addDefPermuteFactor(ir::operand::PermuteFactor{
 378           controlflow_backend,
 379           ir::Layout::NHWC // TODO Get frontend layout of this node from IR
 380       });
 381     }
 382   }
 383
 384   // Set LowerInfo for each operand from the operand::LowerInfo holder
 385   _graph.operands().iterate([&](const ir::OperandIndex &index, ir::Operand &) {
 386     setLowerInfo(index, std::move(operands_lower_info[index]));
 387   });
 388 }
 389
 390 void LoweredGraph::dumpLowerInfo()
 391 {
 392   if (::onert::util::logging::ctx.enabled() == false)
 393     return;
 394
 395   std::map<uint32_t, std::string> dumps;
 396
 397   _graph.operands().iterate([&](const ir::OperandIndex &index, ir::Operand &object) {
 398     std::stringstream sstream;
 399     if (!getLowerInfo(index)->def_factors().empty() || !getLowerInfo(index)->use_factors().empty())
 400     {
 401       auto factors_to_string = [](const ir::operand::PermuteFactorSet &factors) {
 402         std::string str;
 403         for (auto factor : factors)
 404         {
 405           str += factor.backend()->config()->id();
 406           str += "(" + to_string(factor.layout()) + ")";
 407           str += " ";
 408         }
 409         return "{ " + str + "}";
 410       };
 411
 412       auto operation_index_to_string = [](const ir::OperationIndexSet &operations) {
 413         std::string str;
 414         for (auto op : operations)
 415         {
 416           str += std::to_string(op.value());
 417           str += " ";
 418         }
 419         return "{ " + str + "}";
 420       };
 421
 422       const auto lower_info = getLowerInfo(index);
 423       const auto &shape = object.shape();
 424       std::string def_ops =
 425           object.getDef().valid() ? std::to_string(object.getDef().value()) : "N/A";
 426       std::string use_ops = operation_index_to_string(object.getUses());
 427       std::string def_layouts = factors_to_string(lower_info->def_factors());
 428       std::string use_layouts = factors_to_string(lower_info->use_factors());
 429       sstream << "Operand #" << index.value() << " LowerInfo" << std::endl;
 430       sstream << "  - Shape           : { ";
 431       for (auto i = 0; i < shape.rank(); ++i)
 432       {
 433         sstream << (shape.dim(i)) << " ";
 434       }
 435       sstream << "}" << std::endl;
 436       sstream << "  - Def ir::Operations  : " << def_ops << std::endl;
 437       sstream << "  - Use ir::Operations  : " << use_ops << std::endl;
 438       sstream << "  - Lower Info" << std::endl;
 439       sstream << "    - Def Backends    : " << def_layouts << std::endl;
 440       sstream << "    - Use Backends    : " << use_layouts << std::endl;
 441     }
 442     dumps.emplace(index.value(), sstream.str());
 443   });
 444
 445   for (const auto &e : dumps)
 446   {
 447     if (!e.second.empty())
 448     {
 449       VERBOSE(Lower) << e.second;
 450     }
 451   }
 452 }
 453
 454 bool LoweredGraph::mergeable(const ir::OpSequenceIndex &op_seq_index,
 455                              const ir::OperationIndex &node_index, ir::Layout layout,
 456                              const BackendResolver &backend_resolver)
 457 {
 458   // Are they mergeable?
 459   // 1. the same backend id and layout?
 460   // 2. Is op_seq or node branched?
 461   // 3. if 1 is true, the op_seq and a node are connected?
 462   const auto &op_seq = _op_seqs.at(op_seq_index);
 463   const auto &node = _graph.operations().at(node_index);
 464
 465   // The same backend id and layout?
 466   {
 467     const auto op_seq_backend_layout = getLowerInfo(op_seq_index)->layout();
 468     const auto &op_seq_backend_id = getLowerInfo(op_seq_index)->backend()->config()->id();
 469     const auto &node_backend_id = backend_resolver.getBackend(node_index)->config()->id();
 470     VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " { " << op_seq_backend_id << "("
 471                    << to_string(op_seq_backend_layout) << ") } "
 472                    << " NODE#" << node_index.value() << " (" << node.name() << ") { "
 473                    << node_backend_id << "(" << to_string(layout) << ") } " << std::endl;
 474     if (op_seq_backend_id != node_backend_id || op_seq_backend_layout != layout)
 475       return false;
 476   }
 477
 478   // Branched?
 479   {
 480     std::unordered_set<ir::OperationIndex> branched_set;
 481
 482     // Check for branching up
 483     for (const auto &input : op_seq.getInputs() | ir::Remove::DUPLICATED | ir::Remove::UNDEFINED)
 484     {
 485       const auto &input_obj = _graph.operands().at(input);
 486       auto def = input_obj.getDef();
 487       if (def.valid())
 488       {
 489         branched_set.insert(def);
 490         if (branched_set.size() > 1)
 491         {
 492           return false;
 493         }
 494       }
 495     }
 496     branched_set.clear();
 497
 498     // Check for branching down
 499     for (const auto &output : node.getOutputs() | ir::Remove::DUPLICATED)
 500     {
 501       // TODO Fix this workaround for the case of model outputs that are used by another operation
 502       //      This is needed since the branching is decided by operation, but for model outputs,
 503       //      there is controlflow backen(use backend) but no actual use operation exists
 504       if (_graph.getOutputs().contains(output))
 505         return false;
 506
 507       const auto &output_obj = _graph.operands().at(output);
 508       for (const auto &use : output_obj.getUses())
 509       {
 510         branched_set.insert(use);
 511         if (branched_set.size() > 1)
 512         {
 513           return false;
 514         }
 515       }
 516     }
 517   }
 518
 519   // Connected?
 520   // an input of one node is an output of the other node? or vice-versa?
 521   {
 522     const auto &node_inputs = node.getInputs();
 523     const auto &node_outputs = node.getOutputs();
 524
 525     // op_seq's operations are in order so that we just check the first and the last
 526     std::vector<ir::OperationIndex> op_seq_ops{op_seq.operations()[0]};
 527     if (op_seq.operations().size() > 1)
 528       op_seq_ops.emplace_back(op_seq.operations()[op_seq.operations().size() - 1]);
 529
 530     for (const auto &n_index : op_seq_ops)
 531     {
 532       const auto &n = _graph.operations().at(n_index);
 533
 534       // node's output == op_seq's input?
 535       for (const auto input : n.getInputs() | ir::Remove::UNDEFINED)
 536       {
 537         if (node_outputs.contains(input))
 538         {
 539           VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " 's NODE#" << n_index.value()
 540                          << "(" << n.name() << ") is connected to NODE#" << node_index.value()
 541                          << "(" << node.name() << ")" << std::endl;
 542           return true;
 543         }
 544       }
 545
 546       // node's input == op_seq's output?
 547       for (const auto output : n.getOutputs())
 548       {
 549         if (node_inputs.contains(output))
 550         {
 551           VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " 's NODE#" << n_index.value()
 552                          << " (" << n.name() << ") is connected to NODE#" << node_index.value()
 553                          << std::endl;
 554           return true;
 555         }
 556       }
 557     }
 558
 559     VERBOSE(Lower) << "OpSequence#" << op_seq_index.value() << " is not connected to NODE#"
 560                    << node_index.value() << "(" << node.name() << ")" << std::endl;
 561   }
 562
 563   return false;
 564 }
 565
 566 } // namespace compiler
 567 } // namespace onert