3 min to read

RRVM 编译器优化-待定系数法降复杂度

Featured image

待定系数法降复杂度

注：这是在当时编译器比赛（全国大学生计算机系统能力大赛-编译系统设计赛）实现这个优化 pass 之前写的设计思路文档。big credit to Fuyuki
主要目的是把多次递归在特定情况下优化为一次递归，从而把复杂度从指数降到线性甚至常数。对于当时公开测例中 matmul 1,2,3,recursive call 1,2,3 有非常好的效果，这个算法的灵感来自于 Fuyuki，当时听到的时候惊为天人（同时感谢 Fuyuki 大 gg 在实现的时候多次帮忙 debug qaq）
项目仓库，主要与其中 commit 5ab76ea 有关
对于一些特定的函数，我们可以用待定系数法来把运算复杂度降低到O(n) 然后对通项进行模式匹配，进一步降复杂度到 O(1)

算法

float func(float data, int num) {
    if (num < 0) {
        return 0;
    }
    num=num-1;
    data = data + func(data, num);
    data = data - func(data, num);
    return data;
}

上述例子可以用如下算法降低复杂度
我们先对函数条件进行一些限制：1. 只有两个参数（这个可以扩展），2. 函数只会递归调用自身

  1. 我们先确定递归间的 index ,即存在一个变量，可以根据它的值确定是第几层递归调用，该变量由以下特征判断：
    1. 决定递归结束（cfg 中较前的位置存在叶节点，该叶节点的判断条件依赖于该变量）=> 加强条件： 函数基本块 branch 只依赖于该语句
    2. 同个递归调用周期，读取的值都是该变量的同个不变量，如 index-1,index/2 这类
  2. 待定系数
\[func(data,num)=[f1,f3](num)^T\cdot [data,1] =f1(num)\cdot data+g(num)\]

我们只需要求出来 f1,g 的值即可,在当前条件下，可以进一步简化，考虑 g(num) 在某次迭代后为 0 的情况
在每次递归调用函数自身的地方，我们都把表达式展开 belike（但是实际中端代码中会化成ssa的形式）: \(f1(num)\cdot data=data_now=data+f1(num-1)\cdot data-f1(num-1)\cdot (data+f1(num-1)\cdot data) = data-f1(num-1)\cdot f1(num-1) \cdot data\) 从而可得

\[f1(num)=1-f1(num-1)\cdot f1(num-1)\]

问题：怎么确定 g(num) 为0？

发现 g(num), 看 g(num)=一个东西*g(num-1),假设只有两个 return 在一个分支下是 g(num-1)*一个东西，另一个分支下是0，则可以确定

实现

白板上这一段 \(foo = \sum (k(d_1,d_2,...d_n) \pi(xi^{d_i}))\) 或者这一段 \(foo=\sum w(idx_1,idx_2,...idx_n) \pi(xi^{ij})\) w 的某一项都是指 f1(num) 的具体值这样子，然后在具体的运算中，我们可以调用 calc_coef （更精确的描述是 ）来计算该具体值
实现时，简化到双变量，一次的情况，相当于 k1(num)*data+k2(num) calc_coef 函数签名 belike: 接收一个传所有 w 的 array,然后返回填了所有 w 值的该 array，且需要保证该函数在每个基本块中只调用一次

实现位置

中端，放在 pure_check 之后

遍历求解

我们需要把函数中遇到的每一个变量都给替换成 data, num, constant（int,float）, 某次递归返回值 的线性组合的形式
具体来说，我们用一个 HashMap 存储变量到保存上述系数和对应运算的 AST (不能无脑数组保存因为无法应对除法等情况)，在另一个 HashMap 中存储递归返回值到该数组中对应项的 index 的映射 然后再是 dfs 基本块求解，在所有最后的返回的地方集中把递归返回值展开 然后进行后续的模式匹配
如果有乘积项这种就直接 return 不做了 算完 AST 后 update: （可以先不用 AST 了 sad）

todo

已经实现完了俩参数的版本，现在拓展到多参数

模常数

注：认为对所有常数取模都立即生成指令，但是还要赋值 mod_value，is_actived 便于返回值判断
要求取模的数是一个立即数才可以进行以下步骤

最后检查所有返回值是否都是有mod_value，是 actived 且 mod_value 都是同一个值，如果是这样就正常返回，在 wrapper_func 加取模指令