brainfuck

[Sakura1609]

在brainfuck的三个用例中都出现了形如 的多条件判断。clang的做法是判断输入是否介于最大和最小之间，然后把每个具体的条件都做了编码，来进行判断。具体编码方式是：把get - min（也就是35）然后把编码数移动相应的位数，和1做与运算判断是否为0来进行跳转，如下图箭头指向位置所示

[Sakura1609]

对于这几个code的判断也做了同样的处理。同时对tape这一全局数组的基地址加载做了外提(见下图中t6)

[Sakura1609]

对于形如上图的循环，clang做了如下的处理 语义大概是loop = loop - (a == 93) + (a == 91)，然后判断loop

[answerer2930]

上面几个例子实际上还是做了短路的，只是判断跳转条件的时候用了编码的方式。 由于ast归约、生成条件指令的节点只能得到节点本身的信息，无法获得整个表达式的与或关系。 所以在irgen过程中添加代码识别上面提到的这些情况会使得节点间多很多信息传递(且对于嵌套的与或表达式会很复杂)，不太符合原有的代码结构，加上原实现短路的代码不能轻易修改(改了可能会有很多bug),可以考虑在ir优化中识别这些情况，替换原有条件指令

[answerer2930]

Todo: 1)无条件跳转或条件指令为eq(操作数之一为constint)、ne(操作数之一为constint)或一个int表达式 目标：识别、标记并替换一段连续的符合1)条件的块结构。

所需识别的连续块结构的起点块: 块中有条件跳转指令且该指令符合1)中条件 所需识别的连续块结构的终点块: 该块符合1）中条件(或该块为起始块)且下一块不符合1)中条件

遍历顺序：从函数入口块开始，dfs,bfs都行(注意记录,不要遍历已经遍历过的块,记录还未遍历的块的头块 一次扫描结束后,判断是否能将此次扫描的符合条件的条件跳转指令全部进行优化(constint_max-constin_min是否小于最大编码位数),能则编码、替换原有条件指令；若不能，试探最大能替换几条条件指令

从块结构识别这类情况的优点： 更抽象，扩大了可优化的范围，就算源代码文件未显式地给出形如"get != 62 && get != 60 && get != 43 && get != 45"的代码结构也能优化 优化时不用纠结如何识别源代码文件中是与还是或表达式或嵌套结构，利用ssa，只关注是否能够将连续的符合条件的条件指令重新以编码的形式呈现

[Sakura1609]

手动验证似乎这种优化提升并不大？

[answerer2930]

手动验证似乎这种优化提升并不大？

如果优化提升很小的话我觉得可以不做这个优化(实现起来有点麻烦，而且可替换的指令太少的话会不会反而是负优化?)

[answerer2930]

手动验证似乎这种优化提升并不大？

要做这个优化的话，我需要知道连续替换几条符合条件的指令才能保证优化是正优化以及最大编码长度