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.
5 // Copyright (C) 2018 Intel Corporation
11 #include <list> // list
12 #include <iomanip> // setw, etc
13 #include <fstream> // ofstream
17 #include <ade/util/algorithm.hpp> // contains
18 #include <ade/util/chain_range.hpp> // chain
20 #include <opencv2/gapi/util/optional.hpp> // util::optional
21 #include "logger.hpp" // GAPI_LOG
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"
29 ////////////////////////////////////////////////////////////////////////////////
32 // Merge is a binary operation (LHS `Merge` RHS) where LHS may be arbitrary
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.
37 ////////////////////////////////////////////////////////////////////////////////
39 // Uncomment to dump more info on merge process
40 // FIXME: make it user-configurable run-time option
41 // #define DEBUG_MERGE
49 bool fusionIsTrivial(const ade::Graph &src_graph)
51 // Fusion is considered trivial if there only one
52 // active backend and no user-defined islands
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>();
64 void fuseTrivial(GIslandModel::Graph &g, const ade::Graph &src_graph)
66 const GModel::ConstGraph src_g(src_graph);
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;
72 all.insert(src_g.nodes().begin(), src_g.nodes().end());
74 for (const auto nh : proto.in_nhs)
77 in_ops.insert(nh->outNodes().begin(), nh->outNodes().end());
79 for (const auto nh : proto.out_nhs)
82 out_ops.insert(nh->inNodes().begin(), nh->inNodes().end());
85 auto isl = std::make_shared<GIsland>(backend,
89 util::optional<std::string>{});
91 auto ih = GIslandModel::mkIslandNode(g, std::move(isl));
93 for (const auto nh : proto.in_nhs)
95 auto slot = GIslandModel::mkSlotNode(g, nh);
98 for (const auto nh : proto.out_nhs)
100 auto slot = GIslandModel::mkSlotNode(g, nh);
107 using CycleCausers = std::pair< std::shared_ptr<GIsland>,
108 std::shared_ptr<GIsland> >;
110 struct CycleHasher final
112 std::size_t operator()(const CycleCausers& p) const
114 std::size_t a = std::hash<GIsland*>()(p.first.get());
115 std::size_t b = std::hash<GIsland*>()(p.second.get());
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;
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())
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());
138 // Islands with different affinity can't be merged
139 if (a_ptr->backend() != b_ptr->backend())
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)))
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()))
158 else if (a_ptr->is_user_specified() && b_ptr->is_user_specified())
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())
166 // FIXME: add a backend-specified merge checker
170 inline bool isProducedBy(const ade::NodeHandle &slot,
171 const ade::NodeHandle &island)
173 // A data slot may have only 0 or 1 producer
174 if (slot->inNodes().size() == 0)
177 return slot->inNodes().front() == island;
180 inline bool isConsumedBy(const ade::NodeHandle &slot,
181 const ade::NodeHandle &island)
183 auto it = std::find_if(slot->outNodes().begin(),
184 slot->outNodes().end(),
185 [&](const ade::NodeHandle &nh) {
188 return it != slot->outNodes().end();
192 * Find a candidate Island for merge for the given Island nh.
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)
201 std::tuple<ade::NodeHandle, ade::NodeHandle, Direction>
202 findCandidate(const GIslandModel::Graph &g,
204 const MergeContext &ctx = MergeContext())
206 using namespace std::placeholders;
208 // Find a first matching candidate GIsland for merge
210 for (const auto& input_data_nh : nh->inNodes())
212 if (input_data_nh->inNodes().size() != 0)
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,
224 // Ok, now try to find it among the outputs
225 for (const auto& output_data_nh : nh->outNodes())
227 auto mergeTest = [&](ade::NodeHandle cons_nh) -> bool {
228 return canMerge(g, nh, output_data_nh, cons_nh, ctx);
230 auto cand_it = std::find_if(output_data_nh->outNodes().begin(),
231 output_data_nh->outNodes().end(),
233 if (cand_it != output_data_nh->outNodes().end())
234 return std::make_tuple(*cand_it,
238 // Empty handle, no good candidates
239 return std::make_tuple(ade::NodeHandle(),
244 // A cancellable merge of two GIslands, "a" and "b", connected via "slot"
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;
254 Change::List m_changes;
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)
265 MergeObjects identify() const;
268 MergeAction(ade::Graph &g,
269 const ade::Graph &orig_g,
270 ade::NodeHandle prod,
271 ade::NodeHandle slot,
272 ade::NodeHandle cons)
275 , m_gim(GIslandModel::Graph(m_g))
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
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:
291 // Merge(Prod, !Slot!, Cons)
296 // ... [Slot 0] -> Prod -> !Slot! -> Cons -> [Slot 3] -> ...
297 // ... [Slot 1] -' : '-> [Slot 4] -> ...
302 // ... [Slot 0] -> Merged -> [Slot 3] ...
303 // ... [Slot 1] : :-> [Slot 4] ...
304 // ... [Slot 2] ' '-> !Slot! ...
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;
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!
325 MergeAction::MergeObjects MergeAction::identify() const
327 auto lhs = m_gim.metadata(m_prod).get<FusedIsland>().object;
328 auto rhs = m_gim.metadata(m_cons).get<FusedIsland>().object;
330 GIsland::node_set interim_slots;
332 GIsland::node_set merged_all(lhs->contents());
333 merged_all.insert(rhs->contents().begin(), rhs->contents().end());
335 GIsland::node_set merged_in_ops(lhs->in_ops()); // (1)
336 for (auto cons_in_slot_nh : m_cons->inNodes()) // (2)
338 if (isProducedBy(cons_in_slot_nh, m_prod))
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).
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());
352 GIsland::node_set merged_out_ops(rhs->out_ops()); // (3)
353 for (auto prod_out_slot_nh : m_prod->outNodes()) // (4)
355 if (!isConsumedBy(prod_out_slot_nh, m_cons))
357 merged_out_ops.insert(lhs->producer(m_g, prod_out_slot_nh));
362 GIsland::node_set opt_interim_slots;
363 GIsland::node_set non_opt_interim_slots;
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)
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();
381 for (auto slot_nh : interim_slots)
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);
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
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)
398 merged_out_ops.insert(lhs->producer(m_g, non_opt_slot_nh));
401 merged_all, merged_in_ops, merged_out_ops,
402 opt_interim_slots, non_opt_interim_slots
406 // FIXME(DM): Probably this procedure will be refactored dramatically one day...
407 void MergeAction::tryMerge()
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())
418 GAPI_Assert(lhs_obj->name() == rhs_obj->name());
419 maybe_user_tag = cv::util::make_optional(lhs_obj->name());
422 // A: Create a new Island and add it to the graph
423 auto backend = m_gim.metadata(m_prod).get<FusedIsland>()
425 auto merged = std::make_shared<GIsland>(backend,
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
434 auto new_nh = GIslandModel::mkIslandNode(m_gim, std::move(merged));
435 m_changes.enqueue<Change::NodeCreated>(new_nh);
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)
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);
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)
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);
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)
461 GAPI_Assert(1 == opt_slot_nh->inNodes().size() );
462 GAPI_Assert(m_prod == opt_slot_nh->inNodes().front());
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)
470 m_changes.enqueue<Change::DropLink>(m_g, opt_slot_nh, eh);
472 m_changes.enqueue<Change::DropNode>(opt_slot_nh);
474 // D/2 - Those which are used externally are connected to new nh
476 for (auto non_opt_slot_nh : mo.non_opt_interim_slots)
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());
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)
488 if (eh->dstNode() == m_cons)
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);
494 m_changes.enqueue<Change::NewLink>(m_g, new_nh, non_opt_slot_nh);
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)
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);
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)
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);
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);
527 void MergeAction::rollback()
529 m_changes.rollback(m_g);
531 void MergeAction::commit()
533 m_changes.commit(m_g);
537 void merge_debug(const ade::Graph &g, int iteration)
539 std::stringstream filename;
540 filename << "fusion_" << static_cast<const void*>(&g)
541 << "_" << std::setw(4) << std::setfill('0') << iteration
543 std::ofstream ofs(filename.str());
544 passes::dumpDot(g, ofs);
548 void fuseGeneral(ade::Graph& im, const ade::Graph& g)
550 GIslandModel::Graph gim(im);
553 bool there_was_a_merge = false;
554 std::size_t iteration = 0u;
557 there_was_a_merge = false;
559 // FIXME: move this debugging to some user-controllable log level
561 GAPI_LOG_INFO(NULL, "Before next merge attempt " << iteration << "...");
562 merge_debug(g, iteration);
565 auto sorted = pass_helpers::topoSort(im);
566 for (auto nh : sorted)
568 if (NodeKind::ISLAND == gim.metadata(nh).get<NodeKind>().k)
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)
576 auto lhs_nh = (dir == Direction::In ? cand_nh : nh);
577 auto rhs_nh = (dir == Direction::Out ? cand_nh : nh);
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 successful, 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);
588 if (pass_helpers::hasCycles(im))
591 "merge(" << l_obj->name() << "," << r_obj->name() <<
592 ") caused cycle, rolling back...");
594 // don't try to merge these two islands next time (findCandidate will use that)
595 mc.cycle_causers.insert({l_obj, r_obj});
600 "merge(" << l_obj->name() << "," << r_obj->name() <<
601 ") was successful!");
604 GIslandModel::syncIslandTags(gim, g);
606 there_was_a_merge = true;
607 break; // start do{}while from the beginning
613 while (there_was_a_merge);
615 } // anonymous namespace
617 void passes::fuseIslands(ade::passes::PassContext &ctx)
619 std::shared_ptr<ade::Graph> gptr(new ade::Graph);
620 GIslandModel::Graph gim(*gptr);
622 if (fusionIsTrivial(ctx.graph))
624 fuseTrivial(gim, ctx.graph);
628 GIslandModel::generateInitial(gim, ctx.graph);
629 fuseGeneral(*gptr.get(), ctx.graph);
631 GModel::Graph(ctx.graph).metadata().set(IslandModel{std::move(gptr)});
634 void passes::syncIslandTags(ade::passes::PassContext &ctx)
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);
641 }} // namespace cv::gimpl