为何kiss_fft基4正反变换计算不同（第二部分）：能否交换m与m3消除循环内分支

kiss_fft的代码在循环内部存在如下分支：

do {
    if(st->inverse) {
        Fout[m].r = scratch[5].r - scratch[4].i;
        Fout[m].i = scratch[5].i + scratch[4].r;
        Fout[m3].r = scratch[5].r + scratch[4].i;
        Fout[m3].i = scratch[5].i - scratch[4].r;
    }else{
        Fout[m].r = scratch[5].r + scratch[4].i;
        Fout[m].i = scratch[5].i - scratch[4].r;
        Fout[m3].r = scratch[5].r - scratch[4].i;
        Fout[m3].i = scratch[5].i + scratch[4].r;
    }
    ++Fout;
} while (--k); // Fout[]包含k*4个元素

将代码稍作重排后如下：

if(st->inverse) {
    Fout[m].r = scratch[5].r - scratch[4].i;
    Fout[m].i = scratch[5].i + scratch[4].r;
    Fout[m3].r = scratch[5].r + scratch[4].i;
    Fout[m3].i = scratch[5].i - scratch[4].r;
}else{
    Fout[m3].r = scratch[5].r - scratch[4].i;
    Fout[m3].i = scratch[5].i + scratch[4].r
    Fout[m].r = scratch[5].r + scratch[4].i;
    Fout[m].i = scratch[5].i - scratch[4].r;;
}

两个代码块的差异仅在于m和m3的使用逻辑，而m和m3在循环执行过程中不会被修改。请问我是否可以通过提前交换m和m3的值来消除循环内部的分支，将代码优化为如下形式？

if(st->inverse) { swap(&m, &m3); }
do {
    Fout[m].r = scratch[5].r - scratch[4].i;
    Fout[m].i = scratch[5].i + scratch[4].r;
    Fout[m3].r = scratch[5].r + scratch[4].i;
    Fout[m3].i = scratch[5].i - scratch[4].r;
   ++Fout;
} while (--k);

解答 #

你的优化思路完全成立，这是非常经典的循环不变量分支消除手段，原因如下：

• 正逆变换的计算逻辑没有本质差异，仅仅是给m和m3两个索引位置赋值的内容做了互换，你重排后的代码逻辑和原代码完全等价
• m和m3属于循环不变量，在整个循环执行过程中不会被修改，完全可以在循环外完成一次交换操作，替代循环内每次都要执行的分支判断
• 优化后的代码收益非常明确：原本需要在循环内执行k次分支判断，现在只需要在循环外执行1次分支判断和最多1次变量交换，当k值较大时，可以大幅降低分支预测失败带来的性能开销，提升执行效率

唯一需要注意的是：如果后续代码还需要用到m、m3的原始值，需要在交换前先备份两个变量的取值，避免交换后影响后续逻辑；如果后续没有其他依赖，该优化没有任何问题。

内容的提问来源于stack exchange，提问作者MSalters