制作一个互斥的代码路径列表

Question

这是一个比较笼统的问题，并不特定于某种语言。 基本上：如何将 1-deep 代码路径列表（即 if 条件列表）转换为互斥 if 条件列表？ IE。是否有一系列算法可以做到这一点？我感觉这是编译器中的一个常见问题。

让我们约束问题。我们有一种非常简单的语言。

• 整数变量
• 具有两个二元运算符 == 和 !=
的 if/else 条件
• 从上到下执行
• 没有副作用：下面如果 b = 1 然后 b = 2，我们可以删除第一个赋值

示例：

if a == 1 { b = 1 }
if a == 2 { b = 2 }
if a != 3 { b = 2 }
if a == 4 { b = 3 }

将转换为例如：

if a == 4 { b = 3 }
else if a != 3 { b = 2 }

如果这个问题得到解决，支持 <、>、&、| 将变得更具挑战性。

Answer 1

我做了更多的研究。所以有两个步骤：

1. 检测互斥
2. 使两个non-mutually互斥条件互斥

ad 1. 如 sepp2k 所述，可以使用 SAT 求解器检测互斥性。不确定它们在内部是如何工作的，但一位同事给出了使用以格为值的抽象解释的想法的提示。

ad 2. 在一种天真的方法中，对于两个 non-mutually 独占代码路径 A 和 B，我们只需将这两个替换为条件 A & B、A & ~B 和 ~A & B。