G-API feature proposal: endless loops detection for GAPI_TRANSFORM-related logic

[andrey-golubev]

Introduction

Recently I have been thinking about endless loops detection logic in GCompiler with regards to introduced graph transformations support. I have come up with an idea how we should be able to detect all (?) sorts of endless loops at the time of GCompiler constructor call by applying somewhat standard ideas.
I suggest this issue to be a discussion point for my idea where we could also share general thoughts on this feature's design.

related to #15313

Disclaimer: This is more of a feature request/design proposal for existing functionality rather than a bug or anything of the kind. Not finding any better place to discuss the idea, I decided to create this issue

Problem statement

Having transformation logic in G-API graphs can introduce potential problem of looping endlessly applying graph transformations defined with GAPI_TRANSFORM: mainly, due to the fact that some transformations can "recurse" into each other.

Simple example:

GAPI_TRANSFORM(EndlessLoopTransform, <cv::GMat(cv::GMat)>, "pattern in substitute")
{
    static cv::GMat pattern(const cv::GMat& in)
    {
        return cv::gapi::resize(in, cv::Size(100, 100), 0, 0, cv::INTER_LINEAR);
    }

    static cv::GMat substitute(const cv::GMat& in)
    {
        cv::GMat b, g, r;
        std::tie(b, g, r) = cv::gapi::split3(in);
        auto resize = std::bind(&cv::gapi::resize,
            std::placeholders::_1, cv::Size(100, 100), 0, 0, cv::INTER_LINEAR);
        cv::GMat out = cv::gapi::merge3(resize(b), resize(g), resize(r));
        return out;
    }
};

Needless to say, in the presence of the example transformation, applying transformations for "as long as it is possible" can cause us serious troubles. The problem is, however, that there are more complex, non-straightforward transformation dependencies that can cause similar issues but are much harder to detect.

Solution

In this section potential solution (algorithm) is proposed to address the problem stated.

Idea

Looking at patterns and substitutes and how they're handled within GCompiler reminds me of function calls:

• Imagine the following: compiler finds pattern p_1 in original graph and substitutes it with s_1. Now, on the next iteration, pattern p_2 is discovered being a part of newly substituted piece s_1
• In a sense, we can symbolically write this logic as p_1 => s_1 => p_2 => s_2 => ... sequence
• We don't really need to know about substitutes (s_1, s_2), but we do want to know about p_1 and p_2 and how they relate to each other. If the relation exists (as shown above), let's say that p_1 "calls" p_2: so we end up having p_1 => p_2 => ... sequence
• For each pattern p_i within transformation t_i, we would love to know which patterns { p_j | j = 0,...,transforms_num } are "called" by p_i directly
• Well, now this resembles a concept of a call graph
• It seems that finding loops in a call graph of p_i would automatically find loops in transformations with regards to t_i

Algorithm

Input: array of transformations (with patterns and substitutes), length N
Output: exception throw/return "false" if loop detected, nothing/return "true" otherwise

// 1. Call graph construction phase
call_graph - map<pattern*, vector<pattern*>>;
* - pattern is uniquely identified by an _index_ in an array of transformations,
    so we can simply use indices instead of actual patterns as key/values for call_graph

for (i in transformations)
  create new call_graph element: {pattern_i, {}}

  for (j in transformations)
    if (pattern_j is found in substitute_i)
      add new entry: call_graph[pattern_i].add(pattern_j)

// 2. Searching for loops
// we now have at most N graph components
for (i in range(0, N))
  traverse the graph starting from call_graph[i]:
    call_graph[i].key - "parent" node
    call_graph[i].value - "child" nodes
    at each iteration remember visited node
    __if "children" contain visited node, we have found a loop__

Concerns

• The algorithm is really a draft, I think it should work in principle but it might have some hidden flaws. Also it seems reasonable to think about some optimizations along to reduce the number of overall iterations
• Unsure if all possible loops are covered by such approach but it feels like that
• There were some concerns about the order of how transformations are applied. Unfortunately, I do not remember the details, but I think that anything concerning the order might be addressed at phase 1 - "call graph construction"

[andrey-golubev]

@dmatveev @AsyaPronina please take a look and comment if the approach is relevant