algorithm - 将递归函数调用转换为具有成本效益的表示

Question

我正在尝试使用一些静态分析工具来检查大量使用递归调用的程序。从概念上讲，它是这样的:

int counter = 0;
int access = 0;

extern int nd ();  // a nondeterministic value 
void compute1();
void compute2();

int get()
{
    static int fpa[2] = {2, 2};  // each function can be called for twice
    int k = nd() % 2;
    if (fpa[k] > 0) {
        fpa[k]--;
        return k+1;
    }
    else
       return 0;
}

void check_r(int* x) {
    if (x == &counter) {
        __VERIFIER_assert(!(access == 2));
        access = 1;
    }
}

void check_w(int* x) {
    if (x == &counter) {
         __VERIFIER_assert((access == 0));
         access = 2;
    }
}

void schedule() {        
    for (int i = 0; i < 5; i++) { 
       int fp = get();
       if (fp == 0)
         return;
       elif (fp == 1)
         compute1();
       elif (fp == 2)
         compute2();
    }
}

void compute1()
{
        // some computations
        ...
        schedule(); // recursive call
        check_w(&counter); // check write access
        ...
}

void compute2()
{
        // some computations
        ...
        schedule(); //recursive call
        check_r(&counter);
        ...
}

int main()
{
        schedule();
        return 0;
}

我的初步测试表明，由于递归调用，静态分析变得太慢而无法终止。

虽然原则上，我可以以某种方式将递归调用重写为 switch statement左右，但问题是在递归调用 schedule 之前，compute1 和 compute2 函数已经执行了大量的计算，并且很难保存程序上下文以供进一步使用。

几天来我一直在优化这个案例，但就是想不出一个特别的解决方案。谁能提供一些意见和建议来摆脱这里的递归调用？非常感谢。

Answer 1

对我来说，似乎所有的调度函数都在决定是调用compute1还是compute2，而所有get正在做的是确保永远不会调用单个函数超过两倍。我不认为从计算到调度的递归调用是必要的，因为调用永远不会超过两个。这里的递归似乎意味着每次我们可以成功调用其中一个计算函数时，我们都不想再有机会再次调用计算

void schedule() {
    int chances = 1; 
    for (int i = 0; i < 5 || chances > 0; i++) { 
       int fp = get();
       if (fp == 0){
           chances--;
           if(chances < 0)
              chances = 0;
           continue; 
       }
       elif (fp == 1){
         compute1(); chances++;
       }
       elif (fp == 2){
         compute2(); chances++;
       }
    }
}

void compute1()
{
        // some computations
        ...
        //schedule(); remove 
        check_w(&counter); // check write access
        ...
}

void compute2()
{
        // some computations
        ...
        //schedule(); remove 
        check_r(&counter);
        ...
}

这段代码有点困惑所以如果我做了任何不正确的假设请澄清