我想编写一个 LLVM 传递来检测 C++ 中的冗余条件模式。
int a = ... , b = ..., c = ...
//first if condition
if(a == b + 1 - c){
...//compoundStmt1
}
// not change the val of a, b ,c
...
//second if condition which is equivalent to first one
if(c == b - a + 1){ // redundant condition
... //compoundStmt2
}
如果我能够找到等效的条件，我可以合并compoundStmt1和CompoundStmt2。（这是我的目标！）
对于这种情况，我的想法是通过检查最后一句是否是条件分支跳转指令以及条件是ICMP或FCMP指令，找到CFG上C++中的所有条件语句，并将它们添加到后续节点中，添加条件约束的当前节点，并继续传播给后继节点。
但后来我想，对于第二个if语句，其实会加上a == b + 1 - c和a != b + 1 - c，其实相当于不加。我该如何处理，判断第二次遇到的情况c == b - a + 1与之前第一次遇到的情况重复，找出这种多余的条件情况。
===================
对于复杂的情况（例如字符串的“==”运算符调用），我该如何做一些检查。
string s = "...."
//first if stmt
if(s == "abc"){
...
}
// not reassign s
...
...
//second if stmt with same condition
if("abc" == s){ // redundant condition
...
}
a == b + 1 - c
c == b - a + 1
在 LLVM IR 中，右侧只有两个用于算术运算的操作数。因此，为了简单起见，我们假设我们需要在以下之间建立等价关系：
a == b - c
c == b - a
在 LLVM 中，这可能看起来像：
%a1 = sub %b, %c
%cmp1 = ceq %a, a1
%c1 = sub %b, %a
%cmp2 = ceq %c, c1
目标是确定%cmp1和%cmp2是相同的。在大多数情况下，您可以根据DAG（有向无环图）或树来思考操作，例如，
cmp1(ceq)
/ \
%a1(sub) %a
/ \
%b %c
cmp2(ceq)
/ \
%c1(sub) %c
/ \
%b %a
要建立等效性，您需要进行一组树转换，使两棵树相同。有一些算法可以建立树的等价性，并且毫不奇怪的是，这些算法是由 Dragon Book 的作者首先提出的。对于小树（<=5 个节点）和有限操作数（算术）等简单情况，您可以选择一些启发式方法来查找等价性。如果子图无法简化为树并且您被 DAG 困住，那么为了编译时间的利益而放弃是更明智的做法，因为建立DAG 同构并不便宜
即使在建立等价性之后，您也需要检查某些不变量，例如优势、不相交的副作用等。我在下面描述了第二种情况的一些内容。
问题是没有内置运算符来比较字符串。所以等式看起来就像一个函数调用，然后它就变成了一个不平凡的问题。但假设您只想比较标量，例如int. 例如，
s == 10
// s is not modified
10 == s
在 LLVM IR 中，这可能看起来像：
%t1 = 10
%c1 = ceq %s, %t1 # ceq = compare equal
// s is not modified.
%t2 = 10
%c2 = ceq %t2, %s
s没有被修改。在某些情况下，您可以在 SSA 代表处“免费”获得此信息。SSA 是声明性表示，因此每个变量都定义一次。
因此 %t2 之后将被删除。
%t1 = 10
%c1 = ceq %s, %t1
// s is not modified.
%c2 = ceq %t1, %s
您可以按某种顺序对操作数进行排序，例如字典顺序
%t1 = 10
%c1 = ceq %s, %t1
// s is not modified.
%c2 = ceq %s, %t1
通过哈希，您可以找到相同的操作。编译器使用“GVN”作为哈希机制。GVN 还考虑了步骤 3 中所述的排序。因此，使用 GVN 您可以跳过第三步。
本质上，从函数开头 到 的所有路径都%c2必须经过%c1。那么只有一个可以替换%c2为%c1. 有一些 API 可以使此检查变得微不足道。
如果我们想要处理检测字符串比较是否相等的原始问题，我们需要对 的语义进行硬编码strcmp。例如，知道当 时strcmp(a, b)和strcmp(b, a)会返回相同的值 (0) a == b。然后执行“操作规范化”，然后执行上述其余步骤；这很棘手但可行。
参考文献： GVN-PRE是 LLVM 中的一种优化，它执行我针对第二种情况所描述的操作。根据操作数+操作类型，可能需要更多检查来实现可预测性和非相交副作用。我在这里描述的是一个非常简单的例子。
GVNHoist是另一种优化，它具有类似的检查，您会发现它很有用。