inference-engine/thirdparty/fluid/modules/gapi/src/compiler/passes/exec.cpp

   1 // This file is part of OpenCV project.
   2 // It is subject to the license terms in the LICENSE file found in the top-level directory
   3 // of this distribution and at http://opencv.org/license.html.
   4 //
   5 // Copyright (C) 2018-2019 Intel Corporation
   6
   7
   8 #include "precomp.hpp"
   9
  10 #include <string>
  11 #include <list> // list
  12 #include <iomanip>  // setw, etc
  13 #include <fstream> // ofstream
  14 #include <memory>
  15 #include <functional>
  16
  17 #include <ade/util/algorithm.hpp>   // contains
  18 #include <ade/util/chain_range.hpp> // chain
  19
  20 #include "opencv2/gapi/util/optional.hpp"  // util::optional
  21 #include "logger.hpp"    // GAPI_LOG
  22
  23 #include "compiler/gmodel.hpp"
  24 #include "compiler/gislandmodel.hpp"
  25 #include "compiler/passes/passes.hpp"
  26 #include "compiler/passes/helpers.hpp"
  27 #include "compiler/transactions.hpp"
  28
  29 ////////////////////////////////////////////////////////////////////////////////
  30 //
  31 // N.B.
  32 // Merge is a binary operation (LHS `Merge` RHS) where LHS may be arbitrary
  33 //
  34 // After every merge, the procedure starts from the beginning (in the topological
  35 // order), thus trying to merge next "unmerged" island to the latest merged one.
  36 //
  37 ////////////////////////////////////////////////////////////////////////////////
  38
  39 // Uncomment to dump more info on merge process
  40 // FIXME: make it user-configurable run-time option
  41 // #define DEBUG_MERGE
  42
  43 namespace cv
  44 {
  45 namespace gimpl
  46 {
  47 namespace
  48 {
  49     bool fusionIsTrivial(const ade::Graph &src_graph)
  50     {
  51         // Fusion is considered trivial if there only one
  52         // active backend and no user-defined islands
  53         // FIXME:
  54         // Also check the cases backend can't handle
  55         // (e.x. GScalar connecting two fluid ops should split the graph)
  56         const GModel::ConstGraph g(src_graph);
  57         const auto& active_backends = g.metadata().get<ActiveBackends>().backends;
  58         return active_backends.size() == 1 &&
  59                 ade::util::all_of(g.nodes(), [&](ade::NodeHandle nh) {
  60             return !g.metadata(nh).contains<Island>();
  61         });
  62     }
  63
  64     void fuseTrivial(GIslandModel::Graph &g, const ade::Graph &src_graph)
  65     {
  66         const GModel::ConstGraph src_g(src_graph);
  67
  68         const auto& backend = *src_g.metadata().get<ActiveBackends>().backends.cbegin();
  69         const auto& proto = src_g.metadata().get<Protocol>();
  70         GIsland::node_set all, in_ops, out_ops;
  71
  72         all.insert(src_g.nodes().begin(), src_g.nodes().end());
  73
  74         for (const auto nh : proto.in_nhs)
  75         {
  76             all.erase(nh);
  77             in_ops.insert(nh->outNodes().begin(), nh->outNodes().end());
  78         }
  79         for (const auto nh : proto.out_nhs)
  80         {
  81             all.erase(nh);
  82             out_ops.insert(nh->inNodes().begin(), nh->inNodes().end());
  83         }
  84
  85         auto isl = std::make_shared<GIsland>(backend,
  86                                              std::move(all),
  87                                              std::move(in_ops),
  88                                              std::move(out_ops),
  89                                              util::optional<std::string>{});
  90
  91         auto ih = GIslandModel::mkIslandNode(g, std::move(isl));
  92
  93         for (const auto nh : proto.in_nhs)
  94         {
  95             auto slot = GIslandModel::mkSlotNode(g, nh);
  96             g.link(slot, ih);
  97         }
  98         for (const auto nh : proto.out_nhs)
  99         {
 100             auto slot = GIslandModel::mkSlotNode(g, nh);
 101             g.link(ih, slot);
 102         }
 103     }
 104
 105     struct MergeContext
 106     {
 107         using CycleCausers = std::pair< std::shared_ptr<GIsland>,
 108                                         std::shared_ptr<GIsland> >;
 109
 110         struct CycleHasher final
 111         {
 112             std::size_t operator()(const CycleCausers& p) const
 113             {
 114                 std::size_t a = std::hash<GIsland*>()(p.first.get());
 115                 std::size_t b = std::hash<GIsland*>()(p.second.get());
 116                 return a ^ (b << 1);
 117             }
 118         };
 119
 120         // Set of Islands pairs which cause a cycle if merged.
 121         // Every new merge produces a new Island, and if Islands were
 122         // merged (and thus dropped from GIslandModel), the objects may
 123         // still be alive as included into this set.
 124         std::unordered_set<CycleCausers, CycleHasher> cycle_causers;
 125     };
 126
 127     bool canMerge(const GIslandModel::Graph &g,
 128                   const ade::NodeHandle a_nh,
 129                   const ade::NodeHandle /*slot_nh*/,
 130                   const ade::NodeHandle b_nh,
 131                   const MergeContext &ctx = MergeContext())
 132     {
 133         auto a_ptr = g.metadata(a_nh).get<FusedIsland>().object;
 134         auto b_ptr = g.metadata(b_nh).get<FusedIsland>().object;
 135         GAPI_Assert(a_ptr.get());
 136         GAPI_Assert(b_ptr.get());
 137
 138         // Islands with different affinity can't be merged
 139         if (a_ptr->backend() != b_ptr->backend())
 140             return false;
 141
 142         // Islands which cause a cycle can't be merged as well
 143         // (since the flag is set, the procedure already tried to
 144         // merge these islands in the past)
 145         if (ade::util::contains(ctx.cycle_causers, std::make_pair(a_ptr, b_ptr))||
 146             ade::util::contains(ctx.cycle_causers, std::make_pair(b_ptr, a_ptr)))
 147             return false;
 148
 149         // There may be user-defined islands. Initially user-defined
 150         // islands also are built from single operations and then merged
 151         // by this procedure, but there is some exceptions.
 152         // User-specified island can't be merged to an internal island
 153         if (   ( a_ptr->is_user_specified() && !b_ptr->is_user_specified())
 154             || (!a_ptr->is_user_specified() &&  b_ptr->is_user_specified()))
 155         {
 156             return false;
 157         }
 158         else if (a_ptr->is_user_specified() && b_ptr->is_user_specified())
 159         {
 160             // These islads are _different_ user-specified Islands
 161             // FIXME: today it may only differ by name
 162             if (a_ptr->name() != b_ptr->name())
 163                 return false;
 164         }
 165
 166         // FIXME: add a backend-specified merge checker
 167         return true;
 168     }
 169
 170     inline bool isProducedBy(const ade::NodeHandle &slot,
 171                              const ade::NodeHandle &island)
 172     {
 173         // A data slot may have only 0 or 1 producer
 174         if (slot->inNodes().size() == 0)
 175             return false;
 176
 177         return slot->inNodes().front() == island;
 178     }
 179
 180     inline bool isConsumedBy(const ade::NodeHandle &slot,
 181                              const ade::NodeHandle &island)
 182     {
 183         auto it = std::find_if(slot->outNodes().begin(),
 184                                slot->outNodes().end(),
 185                                [&](const ade::NodeHandle &nh) {
 186                                    return nh == island;
 187                                });
 188         return it != slot->outNodes().end();
 189     }
 190
 191     /**
 192      * Find a candidate Island for merge for the given Island nh.
 193      *
 194      * @param g Island Model where merge occurs
 195      * @param nh GIsland node, either LHS or RHS of probable merge
 196      * @param ctx Merge context, may contain some cached stuff to avoid
 197      *      double/triple/etc checking
 198      * @return Tuple of Island handle, Data slot handle (which connects them),
 199      *      and a position of found handle with respect to nh (IN/OUT)
 200      */
 201     std::tuple<ade::NodeHandle, ade::NodeHandle, Direction>
 202     findCandidate(const GIslandModel::Graph &g,
 203                   ade::NodeHandle nh,
 204                   const MergeContext &ctx = MergeContext())
 205     {
 206         using namespace std::placeholders;
 207
 208         // Find a first matching candidate GIsland for merge
 209         // among inputs
 210         for (const auto& input_data_nh : nh->inNodes())
 211         {
 212             if (input_data_nh->inNodes().size() != 0)
 213             {
 214                 // Data node must have a single producer only
 215                 GAPI_DbgAssert(input_data_nh->inNodes().size() == 1);
 216                 auto input_data_prod_nh = input_data_nh->inNodes().front();
 217                 if (canMerge(g, input_data_prod_nh, input_data_nh, nh, ctx))
 218                     return std::make_tuple(input_data_prod_nh,
 219                                            input_data_nh,
 220                                            Direction::In);
 221             }
 222         } // for(inNodes)
 223
 224         // Ok, now try to find it among the outputs
 225         for (const auto& output_data_nh : nh->outNodes())
 226         {
 227             auto mergeTest = [&](ade::NodeHandle cons_nh) -> bool {
 228                 return canMerge(g, nh, output_data_nh, cons_nh, ctx);
 229             };
 230             auto cand_it = std::find_if(output_data_nh->outNodes().begin(),
 231                                         output_data_nh->outNodes().end(),
 232                                         mergeTest);
 233             if (cand_it != output_data_nh->outNodes().end())
 234                 return std::make_tuple(*cand_it,
 235                                        output_data_nh,
 236                                        Direction::Out);
 237         } // for(outNodes)
 238         // Empty handle, no good candidates
 239         return std::make_tuple(ade::NodeHandle(),
 240                                ade::NodeHandle(),
 241                                Direction::Invalid);
 242     }
 243
 244     // A cancellable merge of two GIslands, "a" and "b", connected via "slot"
 245     class MergeAction
 246     {
 247         ade::Graph &m_g;
 248         const ade::Graph &m_orig_g;
 249         GIslandModel::Graph m_gim;
 250         ade::NodeHandle m_prod;
 251         ade::NodeHandle m_slot;
 252         ade::NodeHandle m_cons;
 253
 254         Change::List m_changes;
 255
 256         struct MergeObjects
 257         {
 258             using NS = GIsland::node_set;
 259             NS all;      // same as in GIsland
 260             NS in_ops;   // same as in GIsland
 261             NS out_ops;  // same as in GIsland
 262             NS opt_interim_slots;    // can be dropped (optimized out)
 263             NS non_opt_interim_slots;// can't be dropped (extern. link)
 264         };
 265         MergeObjects identify() const;
 266
 267     public:
 268         MergeAction(ade::Graph &g,
 269                     const ade::Graph &orig_g,
 270                     ade::NodeHandle prod,
 271                     ade::NodeHandle slot,
 272                     ade::NodeHandle cons)
 273             : m_g(g)
 274             , m_orig_g(orig_g)
 275             , m_gim(GIslandModel::Graph(m_g))
 276             , m_prod(prod)
 277             , m_slot(slot)
 278             , m_cons(cons)
 279         {
 280         }
 281
 282         void tryMerge(); // Try to merge islands Prod and Cons
 283         void rollback(); // Roll-back changes if merge has been done but broke the model
 284         void commit();   // Fix changes in the model after successful merge
 285     };
 286
 287     // Merge proceduce is a replacement of two Islands, Prod and Cons,
 288     // connected via !Slot!, with a new Island, which contain all Prod
 289     // nodes + all Cons nodes, and reconnected in the graph properly:
 290     //
 291     // Merge(Prod, !Slot!, Cons)
 292     //
 293     //                                  [Slot 2]
 294     //                                    :
 295     //                                    v
 296     //     ... [Slot 0] -> Prod -> !Slot! -> Cons -> [Slot 3] -> ...
 297     //     ... [Slot 1] -'           :           '-> [Slot 4] -> ...
 298     //                               V
 299     //                              ...
 300     // results into:
 301     //
 302     //     ... [Slot 0] -> Merged  -> [Slot 3] ...
 303     //     ... [Slot 1] :         :-> [Slot 4] ...
 304     //     ... [Slot 2] '         '-> !Slot! ...
 305     //
 306     // The rules are the following:
 307     // 1) All Prod input slots become Merged input slots;
 308     //    - Example: Slot 0 Slot 1
 309     // 2) Any Cons input slots which come from Islands different to Prod
 310     //    also become Merged input slots;
 311     //    - Example: Slot 2
 312     // 3) All Cons output slots become Merged output slots;
 313     //    - Example: Slot 3, Slot 4
 314     // 4) All Prod output slots which are not consumed by Cons
 315     //    also become Merged output slots;
 316     //    - (not shown on the example)
 317     // 5) If the !Slot! which connects Prod and Cons is consumed
 318     //    exclusively by Cons, it is optimized out (dropped) from the model;
 319     // 6) If the !Slot! is used by consumers other by Cons, it
 320     //    becomes an extra output of Merged
 321     // 7) !Slot! may be not the only connection between Prod and Cons,
 322     //    but as a result of merge operation, all such connections
 323     //    should be handles as described for !Slot!
 324
 325     MergeAction::MergeObjects MergeAction::identify() const
 326     {
 327         auto lhs = m_gim.metadata(m_prod).get<FusedIsland>().object;
 328         auto rhs = m_gim.metadata(m_cons).get<FusedIsland>().object;
 329
 330         GIsland::node_set interim_slots;
 331
 332         GIsland::node_set merged_all(lhs->contents());
 333         merged_all.insert(rhs->contents().begin(), rhs->contents().end());
 334
 335         GIsland::node_set merged_in_ops(lhs->in_ops());     // (1)
 336         for (auto cons_in_slot_nh : m_cons->inNodes())      // (2)
 337         {
 338             if (isProducedBy(cons_in_slot_nh, m_prod))
 339             {
 340                 interim_slots.insert(cons_in_slot_nh);
 341                 // at this point, interim_slots are not sync with merged_all
 342                 // (merged_all will be updated with interim_slots which
 343                 // will be optimized out).
 344             }
 345             else
 346             {
 347                 const auto extra_in_ops = rhs->consumers(m_g, cons_in_slot_nh);
 348                 merged_in_ops.insert(extra_in_ops.begin(), extra_in_ops.end());
 349             }
 350         }
 351
 352         GIsland::node_set merged_out_ops(rhs->out_ops());   // (3)
 353         for (auto prod_out_slot_nh : m_prod->outNodes())    // (4)
 354         {
 355             if (!isConsumedBy(prod_out_slot_nh, m_cons))
 356             {
 357                 merged_out_ops.insert(lhs->producer(m_g, prod_out_slot_nh));
 358             }
 359         }
 360
 361         // (5,6,7)
 362         GIsland::node_set opt_interim_slots;
 363         GIsland::node_set non_opt_interim_slots;
 364
 365         auto is_non_opt = [&](const ade::NodeHandle &slot_nh) {
 366             // If a data object associated with this slot is a part
 367             // of GComputation _output_ protocol, it can't be optimzied out
 368             const auto data_nh = m_gim.metadata(slot_nh).get<DataSlot>().original_data_node;
 369             const auto &data = GModel::ConstGraph(m_orig_g).metadata(data_nh).get<Data>();
 370             if (data.storage == Data::Storage::OUTPUT)
 371                 return true;
 372
 373             // Otherwise, a non-optimizeable data slot is the one consumed
 374             // by some other island than "cons"
 375             const auto it = std::find_if(slot_nh->outNodes().begin(),
 376                                          slot_nh->outNodes().end(),
 377                                          [&](ade::NodeHandle &&nh)
 378                                          {return nh != m_cons;});
 379             return it != slot_nh->outNodes().end();
 380         };
 381         for (auto slot_nh : interim_slots)
 382         {
 383             // Put all intermediate data nodes (which are BOTH optimized
 384             // and not-optimized out) to Island contents.
 385             merged_all.insert(m_gim.metadata(slot_nh)
 386                               .get<DataSlot>().original_data_node);
 387
 388             GIsland::node_set &dst = is_non_opt(slot_nh)
 389                 ? non_opt_interim_slots // there are consumers other than m_cons
 390                 : opt_interim_slots;    // there's no consumers other than m_cons
 391             dst.insert(slot_nh);
 392         }
 393
 394         // (4+6).
 395         // BTW, (4) could be "All Prod output slots read NOT ONLY by Cons"
 396         for (auto non_opt_slot_nh : non_opt_interim_slots)
 397         {
 398             merged_out_ops.insert(lhs->producer(m_g, non_opt_slot_nh));
 399         }
 400         return MergeObjects{
 401             merged_all, merged_in_ops, merged_out_ops,
 402             opt_interim_slots, non_opt_interim_slots
 403         };
 404     }
 405
 406     // FIXME(DM): Probably this procedure will be refactored dramatically one day...
 407     void MergeAction::tryMerge()
 408     {
 409         // _: Understand the contents and I/O connections of a new merged Island
 410         MergeObjects mo = identify();
 411         auto lhs_obj = m_gim.metadata(m_prod).get<FusedIsland>().object;
 412         auto rhs_obj = m_gim.metadata(m_cons).get<FusedIsland>().object;
 413         GAPI_Assert(   ( lhs_obj->is_user_specified() &&  rhs_obj->is_user_specified())
 414                     || (!lhs_obj->is_user_specified() && !rhs_obj->is_user_specified()));
 415         cv::util::optional<std::string> maybe_user_tag;
 416         if (lhs_obj->is_user_specified() && rhs_obj->is_user_specified())
 417         {
 418             GAPI_Assert(lhs_obj->name() == rhs_obj->name());
 419             maybe_user_tag = cv::util::make_optional(lhs_obj->name());
 420         }
 421
 422         // A: Create a new Island and add it to the graph
 423         auto backend = m_gim.metadata(m_prod).get<FusedIsland>()
 424             .object->backend();
 425         auto merged = std::make_shared<GIsland>(backend,
 426                                                            std::move(mo.all),
 427                                                            std::move(mo.in_ops),
 428                                                            std::move(mo.out_ops),
 429                                                            std::move(maybe_user_tag));
 430         // FIXME: move this debugging to some user-controllable log-level
 431 #ifdef DEBUG_MERGE
 432         merged->debug();
 433 #endif
 434         auto new_nh = GIslandModel::mkIslandNode(m_gim, std::move(merged));
 435         m_changes.enqueue<Change::NodeCreated>(new_nh);
 436
 437         // B: Disconnect all Prod's input Slots from Prod,
 438         //    connect it to Merged
 439         std::vector<ade::EdgeHandle> input_edges(m_prod->inEdges().begin(),
 440                                                  m_prod->inEdges().end());
 441         for (auto in_edge : input_edges)
 442         {
 443             m_changes.enqueue<Change::NewLink>(m_g, in_edge->srcNode(), new_nh);
 444             m_changes.enqueue<Change::DropLink>(m_g, m_prod, in_edge);
 445         }
 446
 447         // C: Disconnect all Cons' output Slots from Cons,
 448         //    connect it to Merged
 449         std::vector<ade::EdgeHandle> output_edges(m_cons->outEdges().begin(),
 450                                                   m_cons->outEdges().end());
 451         for (auto out_edge : output_edges)
 452         {
 453             m_changes.enqueue<Change::NewLink>(m_g, new_nh, out_edge->dstNode());
 454             m_changes.enqueue<Change::DropLink>(m_g, m_cons, out_edge);
 455         }
 456
 457         // D: Process the intermediate slots (betweed Prod n Cons).
 458         // D/1 - Those which are optimized out are just removed from the model
 459         for (auto opt_slot_nh : mo.opt_interim_slots)
 460         {
 461             GAPI_Assert(1      == opt_slot_nh->inNodes().size() );
 462             GAPI_Assert(m_prod == opt_slot_nh->inNodes().front());
 463
 464             std::vector<ade::EdgeHandle> edges_to_drop;
 465             ade::util::copy(ade::util::chain(opt_slot_nh->inEdges(),
 466                                              opt_slot_nh->outEdges()),
 467                             std::back_inserter(edges_to_drop));
 468             for (auto eh : edges_to_drop)
 469             {
 470                 m_changes.enqueue<Change::DropLink>(m_g, opt_slot_nh, eh);
 471             }
 472             m_changes.enqueue<Change::DropNode>(opt_slot_nh);
 473         }
 474         // D/2 - Those which are used externally are connected to new nh
 475         //       as outputs.
 476         for (auto non_opt_slot_nh : mo.non_opt_interim_slots)
 477         {
 478             GAPI_Assert(1      == non_opt_slot_nh->inNodes().size() );
 479             GAPI_Assert(m_prod == non_opt_slot_nh->inNodes().front());
 480             m_changes.enqueue<Change::DropLink>(m_g, non_opt_slot_nh,
 481                                                 non_opt_slot_nh->inEdges().front());
 482
 483             std::vector<ade::EdgeHandle> edges_to_probably_drop
 484                 (non_opt_slot_nh->outEdges().begin(),
 485                  non_opt_slot_nh->outEdges().end());;
 486             for (auto eh : edges_to_probably_drop)
 487             {
 488                 if (eh->dstNode() == m_cons)
 489                 {
 490                     // drop only edges to m_cons, as there's other consumers
 491                     m_changes.enqueue<Change::DropLink>(m_g, non_opt_slot_nh, eh);
 492                 }
 493             }
 494             m_changes.enqueue<Change::NewLink>(m_g, new_nh, non_opt_slot_nh);
 495         }
 496
 497         // E. All Prod's output edges which are directly related to Merge (e.g.
 498         //    connected to Cons) were processed on step (D).
 499         //    Relink the remaining output links
 500         std::vector<ade::EdgeHandle>  prod_extra_out_edges
 501             (m_prod->outEdges().begin(),
 502              m_prod->outEdges().end());
 503         for (auto extra_out : prod_extra_out_edges)
 504         {
 505             m_changes.enqueue<Change::NewLink>(m_g, new_nh, extra_out->dstNode());
 506             m_changes.enqueue<Change::DropLink>(m_g, m_prod, extra_out);
 507         }
 508
 509         // F. All Cons' input edges which are directly related to merge (e.g.
 510         //    connected to Prod) were processed on step (D) as well,
 511         //    remaining should become Merged island's input edges
 512         std::vector<ade::EdgeHandle> cons_extra_in_edges
 513             (m_cons->inEdges().begin(),
 514              m_cons->inEdges().end());
 515         for (auto extra_in : cons_extra_in_edges)
 516         {
 517             m_changes.enqueue<Change::NewLink>(m_g, extra_in->srcNode(), new_nh);
 518             m_changes.enqueue<Change::DropLink>(m_g, m_cons, extra_in);
 519         }
 520
 521         // G. Finally, drop the original Island nodes. DropNode() does
 522         //    the sanity check for us (both nodes should have 0 edges).
 523         m_changes.enqueue<Change::DropNode>(m_prod);
 524         m_changes.enqueue<Change::DropNode>(m_cons);
 525     }
 526
 527     void MergeAction::rollback()
 528     {
 529         m_changes.rollback(m_g);
 530     }
 531     void MergeAction::commit()
 532     {
 533         m_changes.commit(m_g);
 534     }
 535
 536 #ifdef DEBUG_MERGE
 537     void merge_debug(const ade::Graph &g, int iteration)
 538     {
 539         std::stringstream filename;
 540         filename << "fusion_" << static_cast<const void*>(&g)
 541                  << "_" << std::setw(4) << std::setfill('0') << iteration
 542                  << ".dot";
 543         std::ofstream ofs(filename.str());
 544         passes::dumpDot(g, ofs);
 545     }
 546 #endif
 547
 548     void fuseGeneral(ade::Graph& im, const ade::Graph& g)
 549     {
 550         GIslandModel::Graph gim(im);
 551         MergeContext mc;
 552
 553         bool there_was_a_merge = false;
 554         std::size_t iteration = 0u;
 555         do
 556         {
 557             there_was_a_merge = false;
 558
 559             // FIXME: move this debugging to some user-controllable log level
 560     #ifdef DEBUG_MERGE
 561             GAPI_LOG_INFO(NULL, "Before next merge attempt " << iteration << "...");
 562             merge_debug(g, iteration);
 563     #endif
 564             iteration++;
 565             auto sorted = pass_helpers::topoSort(im);
 566             for (auto nh : sorted)
 567             {
 568                 if (NodeKind::ISLAND == gim.metadata(nh).get<NodeKind>().k)
 569                 {
 570                     ade::NodeHandle cand_nh;
 571                     ade::NodeHandle cand_slot;
 572                     Direction dir = Direction::Invalid;
 573                     std::tie(cand_nh, cand_slot, dir) = findCandidate(gim, nh, mc);
 574                     if (cand_nh != nullptr && dir != Direction::Invalid)
 575                     {
 576                         auto lhs_nh = (dir == Direction::In  ? cand_nh : nh);
 577                         auto rhs_nh = (dir == Direction::Out ? cand_nh : nh);
 578
 579                         auto l_obj = gim.metadata(lhs_nh).get<FusedIsland>().object;
 580                         auto r_obj = gim.metadata(rhs_nh).get<FusedIsland>().object;
 581                         GAPI_LOG_INFO(NULL, r_obj->name() << " can be merged into " << l_obj->name());
 582                         // Try to do a merge. If merge was succesfull, check if the
 583                         // graph have cycles (cycles are prohibited at this point).
 584                         // If there are cycles, roll-back the merge and mark a pair of
 585                         // these Islands with a special tag - "cycle-causing".
 586                         MergeAction action(im, g, lhs_nh, cand_slot, rhs_nh);
 587                         action.tryMerge();
 588                         if (pass_helpers::hasCycles(im))
 589                         {
 590                             GAPI_LOG_INFO(NULL,
 591                                           "merge(" << l_obj->name() << "," << r_obj->name() <<
 592                                           ") caused cycle, rolling back...");
 593                             action.rollback();
 594                             // don't try to merge these two islands next time (findCandidate will use that)
 595                             mc.cycle_causers.insert({l_obj, r_obj});
 596                         }
 597                         else
 598                         {
 599                             GAPI_LOG_INFO(NULL,
 600                                           "merge(" << l_obj->name() << "," << r_obj->name() <<
 601                                           ") was successful!");
 602                             action.commit();
 603     #ifdef DEBUG_MERGE
 604                             GIslandModel::syncIslandTags(gim, g);
 605     #endif
 606                             there_was_a_merge = true;
 607                             break; // start do{}while from the beginning
 608                         }
 609                     } // if(can merge)
 610                 } // if(ISLAND)
 611             } // for(all nodes)
 612         }
 613         while (there_was_a_merge);
 614     }
 615 }  // anonymous namespace
 616
 617 void passes::fuseIslands(ade::passes::PassContext &ctx)
 618 {
 619     std::shared_ptr<ade::Graph> gptr(new ade::Graph);
 620     GIslandModel::Graph gim(*gptr);
 621
 622     if (fusionIsTrivial(ctx.graph))
 623     {
 624         fuseTrivial(gim, ctx.graph);
 625     }
 626     else
 627     {
 628         GIslandModel::generateInitial(gim, ctx.graph);
 629         fuseGeneral(*gptr.get(), ctx.graph);
 630     }
 631     GModel::Graph(ctx.graph).metadata().set(IslandModel{std::move(gptr)});
 632 }
 633
 634 void passes::syncIslandTags(ade::passes::PassContext &ctx)
 635 {
 636     GModel::Graph gm(ctx.graph);
 637     std::shared_ptr<ade::Graph> gptr(gm.metadata().get<IslandModel>().model);
 638     GIslandModel::Graph gim(*gptr);
 639     GIslandModel::syncIslandTags(gim, ctx.graph);
 640 }
 641 }} // namespace cv::gimpl