这条终点把支配作用域值编号理路支配作用域值编号Dominance-scoped value numbering · Dominator-based value numbering · DVNT沿 SSA 支配树维护可回退的表达式表，用值代表识别跨块冗余，区分等值与载体可用，保守处理未解循环φ并执行变换后的程序。与边局部部分冗余消除理路边局部部分冗余消除Edge-local partial redundancy elimination · Incoming-edge PRE · 入边部分冗余消除对选定块首表达式按原图可用性保存载体，只在缺失入边补算并拆分关键边，以逐状态模拟证明正确及对应路径上的运算计数不增加。放在同一个小执行器里，但先分开运行各自的输入接口。前者接收经过验证的 SSA，后者接收无 φ 的可变标量程序。两者都只使用数学整数上的纯总运算，没有内存、异常、溢出或调用。

完成标准不是说出“同一表达式只算一次”，而是交出一个确实可读的结果名字，或者把这个名字在缺失入边上初始化。你要提交源与目标的状态轨迹、逐条替换或拆边证据、实际运行次数，以及至少三个失败变体。路线入口见从等值名字到边上补算。

运行准备 ​

下载标准库参考执行器，保存到当前目录。需要 Python 3.10 或更新版本，无第三方包、网络、输入文件或磁盘写入依赖。以下两个命令均把检查结果写到标准输出；重定向是你选择保留证据的方式。

python foundation-value-redundancy-check.py > result.json
python -O foundation-value-redundancy-check.py > optimized.json
cmp result.json optimized.json

正常输出的顶层 status 是 PASS。regressions 包含1000次生成 SSA 运行、400次分支 PRE 运行、13个 SSA 循环输入与26个 PRE 循环输入；这些是带固定种子的真实检查，不是一般正确性的代替品。普通与 -O 输出应逐字节相同，接口拒绝和核对使用显式异常，不依赖会被优化关闭的 assert。

下面的独立命令从同一目录加载参考器。PYTHONDONTWRITEBYTECODE=1 只是避免导入产生缓存，不改变检查。

任务一：交出代表与载体，而不只交出结果 ​

先运行并保存完整 JSON 中的 value_numbering。入口的 t=a+b 与 u=a 使 VN(u)=a；T 的 x=u+b 与 F 的 y=a+b 因此都可读取 t。请写出 H 进入 F、退出 F、进入 T 时的键，并解释为什么两条乘法仍各自保留。

PYTHONDONTWRITEBYTECODE=1 python - <<'PY'
import runpy
m=runpy.run_path('foundation-value-redundancy-check.py')
p=m['value_example'](); q=m['scoped_value_numbering'](p)
print('representatives', q['representatives'])
print('replacements', [(x['block'],x['destination'],x['carrier']) for x in q['replacements']])
print('phis', [(x['name'],x['representative'],x['reason']) for x in q['phis']])
for bit in (0,1):
    inp={'a':2,'b':3,'c':4,'p':bit}
    a=m['execute'](p,inp); b=m['execute'](q['program'],inp)
    print(bit,a['value'],b['value'],a['trace']==b['trace'],a['counts'],b['counts'])
PY

应得到 u→a、x→t、y→t、w→z、k→r。参考遍历顺序下，替换证据依次是 (F,y,t)、(T,x,t)、(J,k,r)。z 是新的 φ 代表，w 与同块 z 有相同的逐前驱输入，因此取 z。不要把遍历显示顺序误当成实际运行顺序；一次执行只经过 T 或 F 之一。

两个输入都返回 (40,40,10)，所有原块末状态相等。源动态计数为 add=5、mul=1、copy=1，目标为 add=3、mul=1、copy=3。静态算术8→5，动态算术6→4。新增复制还需要成本；两项减少不能直接当成机器时间比例。

现在把 J 的两个 φ 换成 x=φ(T:1,F:2)、y=φ(T:2,F:1)，返回 x−y。p=1 时为−1，p=0 时为1。它们拥有相同的无标签输入集合，却不是同一个值。提交的比较键必须包含前驱标签，不接受只给出排序后的 {1,2}。

任务二：让错误的兄弟分支借用真正失败 ​

完整 JSON 的 counterexamples.sibling_reuse 应为 uninitialized x。这个坏例在 T 计算 x=a+b、F 计算 y=a+b，错误变体把 F 改成 y:=x。取 p=0，T 没有执行，x 不能作为载体。

请另做一份错误变体：在任务一的目标程序中，把 F 的 right:=y*c 改成 right:=left，保留其他代码。取 a=2、b=3、c=4、p=0，执行同样应拒绝未初始化的 left。数值上 left 与 right 都可为20，不代表两个名字在同一运行中都已产生。

随后运行 value_loop。其循环头 i 和 sum 的 φ 含尚未处理的 next、acc，输出的 inputs_known 均为 false；算法保留独立代表，不假装已经求解回边。n=3 返回6，循环体加法12→6；n=0 返回0且加法0。提交前后全部块末状态相等的检查，而不仅是最终返回值。

你的说明应指出 one 每轮仍被执行，依次为1、2、3。again 与 next 读取当轮 one。把 one 提到循环外并缓存第一次运行值，会改变后续轮次；本页没有进行那项移动。

任务三：保存被覆盖的结果，再只补缺失的边 ​

运行 pre_example，再针对 J 调用 edge_local_pre。原图中 T 先算 x=a+b，再覆盖 x=0；这不杀掉表达式 a+b，却毁掉旧载体 x。F 不计算该表达式，且可绕过 J 直接返回−1。

PYTHONDONTWRITEBYTECODE=1 python - <<'PY'
import runpy
m=runpy.run_path('foundation-value-redundancy-check.py')
p=m['pre_example'](); q=m['edge_local_pre'](p,'J')
print(q['status'],q['availability'],q['carrier'],q['carrier_sites'],q['insertions'])
for bit,other in ((1,0),(0,1),(0,0)):
    inp={'a':2,'b':3,'p':bit,'q':other}
    a=m['execute'](p,inp,selected=q['expression'])
    b=m['execute'](q['program'],inp,selected=q['expression'])
    print(bit,other,a['value'],b['value'],a['selected_count'],b['selected_count'])
    print([r['block'] for r in b['trace']],a['trace']==m['macro_trace'](b,p))
PY

状态为 partially_redundant。原 OUT(T) 与 OUT(J) 为 true，其他出口为 false；所有 IN 为 false，参考同步求解经过4轮达到稳定。新鲜载体是 __pre_value_0，保存站点为 (T,0)，新块 __pre_edge_0 插在 F→J，critical 为 true。

三条路径依次返回10、10、−1。选定加法次数依次为2→1、1→1、0→0；目标块路径依次为 E,T,J；E,F,__pre_edge_0,J；E,F,X。投影会隐藏新增边块和新鲜变量，但保留全部原变量，包括 T 路被覆盖成0的 x。

提交两个坏变体。第一种把 T 恢复成源代码，却保留 J 读取 h：走 T 路会读未初始化的 __pre_value_0。第二种把边块的计算移到 F 分支之前：走 p=q=0 的旁路仍返回−1，但加法由0变成1。前者违反语义载体条件，后者违反按对应路径不增加计算的保证。

只说“拆了关键边”不够。请说明为何 F 的两个后继和 J 的两个前驱使这条边不能由任一端的整块替代，以及为什么新块中的运算没有被计成凭空多出的工作：它恰配对到下一条原 z=a+b。

任务四：分别核对首次进入、回边和零轮 ​

执行 edge_loop(False)。H→J 只承担首次进入，B→J 是已经计算过 a+b 的回边。新块只插入 H→J，回边保留。用 a=2、b=3，n=0 与 n=3 验证：返回0与15，选定加法分别0→0与3→1。

PYTHONDONTWRITEBYTECODE=1 python - <<'PY'
import runpy
m=runpy.run_path('foundation-value-redundancy-check.py')
for kill in (False,True):
    p=m['edge_loop'](kill); q=m['edge_local_pre'](p,'J')
    print('kill',kill,q['status'],q['availability'],q['insertions'])
    for n in (0,3):
        inp={'a':2,'b':3,'n':n}
        a=m['execute'](p,inp,selected=q['expression'])
        b=m['execute'](q['program'],inp,selected=q['expression'])
        print(n,a['value'],b['value'],a['selected_count'],b['selected_count'],a['trace']==m['macro_trace'](b,p))
PY

执行 edge_loop(True) 时，B 在每轮令 b:=b+1。现在 OUT(B)=false，两条入边都缺失，状态必须为 no_available_edge，insertions 为空。n=3 返回18，加法保持3→3；若错误保留第一轮 h=5，则会返回15。n=0 仍返回0，没有循环加法。

继续把无 kill 版本的 B 终结符改为 ('branch',1,'J','X')，取 n=1。源一旦进入循环便只反复走 J、B；这是这份具体程序的结构性发散证明。分别用120与121个块的预算运行源和目标，隐藏唯一新增入口块后，前120个原块状态相等。两个 budget_exhausted 只记录本次有限前缀检查；若没有刚才的结构证明，不能从预算耗尽单独推出发散。

任务五：提交边界证据与分开的成本账 ​

先把 PRE 源程序增加参数 __pre_value_0，把 X 块改名为 __pre_edge_0，并同步更新 F 的后继。令新增参数为99。变换必须选 __pre_value_1 与 __pre_edge_1，且投影仍保留源参数 __pre_value_0=99。按字符串前缀删去所有“看起来像临时量”的名字，会错误隐藏用户原变量。

再提交一个全部入边已有的例子：给 pre_example 的 F 增加 y:=a+b。状态应为 fully_redundant，没有新增块；走 T 或 F→J 时目标 J 都读新鲜载体。F→X 原本也执行这次加法，变换只在原位置保存它，并没有新增一次 e。

最后交付至少四项错误输入：兄弟定义被直接使用、φ 缺前驱槽、重复 SSA 定义、PRE 在某条路径读未定义变量。它们应在相应验证器被拒绝。不能把执行器对一个恰好绕过错误的输入运行成功，当成全图接口合法。

成本报告分三部分。第一部分是数据流和支配验证，注明参考器采用集合迭代及确定性排序，不套用高效支配树构造的复杂度。第二部分是改写和输出体积：PRE 为每条缺失入边最多加一个块，原 e 计算多一条保存复制，不能承诺代码更短。第三部分是实际输入上的操作次数；只统计纯运算的收益时，注明复制、寄存器压力和大整数位成本仍未折算成时间。

最终提交物应包含原始输入、改写后的完整程序、分析事实、替换与插边证据、上述正常与错误轨迹，以及一段逐原块状态关系的解释。支配树作用域负责“旧载体现在可用”，入边 PRE 负责“没有载体的路径怎样补齐”。这两项保证都通过后，才有资格讨论进一步删除复制或选择机器指令。