Halide - while loop equivalent

Question

I'm trying to implement Meijster distance transform algorithm in Halide. I've already rewritten this code to C++ (using openCV) and it's working fine. The paper about this algorithm is here. Right now my halide code is 50% complete - first phase is working fine, now i've got problem with phase 2 (scan 3 in the linked code) which (simplified) look like this:

//g is 2 dimensional cv::Mat (something like array) - result of previous stage
// m is g.width and n is g.height
int(*functionF)(int x, int i, int g_i) = EDT_f;
int(*functionSep)(int i, int u, int g_i, int g_u, int max_value) = EDT_Sep;
cv::Mat dt = cv::Mat(n, m, CV_32SC1);
int* s = new int[m];
int* t = new int[m];
int q = 0, w;

for (int y = 0; y<n; y++)
{
    q = 0;
    s[0] = 0;
    t[0] = 0;

    // Scan 3
    for (int u = 1; u<m; u++)
    {
    //how can i replace this loop:
        while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u)))
            q--;
        //some operations which might change value of q, s[] and t[]
    }
    // Scan 4 - not important here
}

Is there any halide-friendly way to replace this while loop? Right now the only solution i've come so far is smething like this (not tested yet):

Expr calculateQ(Expr currentQValue, Expr y, Func t, Func s, Func g)
{
    //while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u)))
        //q--;
    return select(currentQValue >= 0 && functionF(t[q], s[q], g[s[q], y]) > functionF(t[q], u, g[u, y]), calculateQ(currentQValue - 1, y, t, s, g), currentQValue);
}

but even if this will work, most likely halide will try to evaluate both values of select before checking the condition and recursion will make it very slow.

If there is no way to implement while loop in Halide is there any way to just use some part of your code inside Halide? Any other ideas?

Answer 1

You're right to note that it isn't obvious how to express a dynamically-terminating (while) loop—they are not possible to express in pure Halide right now! This may change in the (indefinite, long-term) future but adding these would make looping Halide programs Turing-complete; without them, we can always analyze the bounds of your loops, but we them, we'd face the halting problem.

There is an escape hatch for exactly this sort of thing, though: you can call external functions (implemented in C or anything else) from inside a Halide pipeline. The interface to an extern function looks the same as the interface to a compiled pipeline (it takes scalar and buffer arguments, with the final buffer being the output, and if called with null buffers it must compute the bounds required of its inputs given the bounds requested of its output). Check out the extern_* test programs for some examples, e.g., https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp. Glancing quickly at your code, I believe it should be easily implementable in an extern stage using the C code you already have.