E.F.S.F. E.F.S.F.

销声匿迹 沉默是金

目录
Static Single Assignment Form
/  

Static Single Assignment Form

Static Single Assignment Form

静态单一分配形式,每个变量只赋值一次

intermediate representation(IR): 中间代码表示

作用

  1. 常数传播(constant propagation)
  2. 值域传播(value range propagation)
  3. 稀疏有条件的常数传播(sparse conditional constant propagation)
  4. 消除无用的程式码(dead code elimination)
  5. 全域数值编号(global value numbering)
  6. 消除部分的冗余(partial redundancy elimination)
  7. 强度折减(strength reduction)
  8. 寄存器分配(register allocation)

demo

x = 1
y = x

变成了

y = 1

转化

{ "title": { "text": "Graph 简单示例" }, "tooltip": {}, "animationDurationUpdate": 1500, "animationEasingUpdate": "quinticInOut", "series": [{ "type": "graph", "layout": "none", "symbolSize": 50, "roam": true, "label": { "show": true }, "edgeSymbol": ["circle", "arrow"], "edgeSymbolSize": [4, 10], "edgeLabel": { "fontSize": 20 }, "data": [{ "name": "x=5;x=x-3;x<3?", "x": 400, "y": 0 }, { "name": "y=x*2;w=y", "x": 300, "y": 100 }, { "name": "y=x-3", "x": 500, "y": 100 }, { "name": "w=x-y;z=x+y", "x": 400, "y": 200 }], "links": [{ "source": "x=5;x=x-3;x<3?", "target": "y=x*2;w=y" }, { "source": "x=5;x=x-3;x<3?", "target": "y=x-3" }, { "source": "y=x-3", "target": "w=x-y;z=x+y" }, { "source": "y=x*2;w=y", "target": "w=x-y;z=x+y" }], "lineStyle": { "opacity": 0.9, "width": 2, "curveness": 0 } }] }

全域数值编号 + 静态单一分配形式 转化代码

{ "title": { "text": "Graph 简单示例" }, "tooltip": {}, "animationDurationUpdate": 1500, "animationEasingUpdate": "quinticInOut", "series": [{ "type": "graph", "layout": "none", "symbolSize": 50, "roam": true, "label": { "show": true }, "edgeSymbol": ["circle", "arrow"], "edgeSymbolSize": [4, 10], "edgeLabel": { "fontSize": 20 }, "data": [{ "name": "x1=5;x2=x1-3;x2<3?", "x": 400, "y": 0 }, { "name": "y1=x2*2;w1=y1", "x": 300, "y": 100 }, { "name": "y2=x2-3", "x": 500, "y": 100 }, { "name": "w2=x2-y?;z1=x2+y?", "x": 400, "y": 200 }], "links": [{ "source": "x1=5;x2=x1-3;x2<3?", "target": "y1=x2*2;w1=y1" }, { "source": "x1=5;x2=x1-3;x2<3?", "target": "y2=x2-3" }, { "source": "y1=x2*2;w1=y1", "target": "w2=x2-y?;z1=x2+y?" }, { "source": "y2=x2-3", "target": "w2=x2-y?;z1=x2+y?" }], "lineStyle": { "opacity": 0.9, "width": 2, "curveness": 0 } }] }

全域数值编号把每个静态量都编号了,也保证每个静态量一定是静态的是单一的,只被赋值一次单最后出现了 y 的编号不知道是多少的问题

所以在最后一步加入了

Φ (Phi) function.

y3 = Φ(y1,y2)

所以转换以后为

{ "title": { "text": "Graph 简单示例" }, "tooltip": {}, "animationDurationUpdate": 1500, "animationEasingUpdate": "quinticInOut", "series": [{ "type": "graph", "layout": "none", "symbolSize": 50, "roam": true, "label": { "show": true }, "edgeSymbol": ["circle", "arrow"], "edgeSymbolSize": [4, 10], "edgeLabel": { "fontSize": 20 }, "data": [{ "name": "x1=5;x2=x1-3;x2<3?", "x": 400, "y": 0 }, { "name": "y1=x2*2;w1=y1", "x": 300, "y": 100 }, { "name": "y2=x2-3", "x": 500, "y": 100 }, { "name": "y3 = Φ(y1,y2);w2=x2-y3;z1=x2+y3", "x": 400, "y": 200 }], "links": [{ "source": "x1=5;x2=x1-3;x2<3?", "target": "y1=x2*2;w1=y1" }, { "source": "x1=5;x2=x1-3;x2<3?", "target": "y2=x2-3" }, { "source": "y1=x2*2;w1=y1", "target": "y3 = Φ(y1,y2);w2=x2-y3;z1=x2+y3" }, { "source": "y2=x2-3", "target": "y3 = Φ(y1,y2);w2=x2-y3;z1=x2+y3" }], "lineStyle": { "opacity": 0.9, "width": 2, "curveness": 0 } }] }

SSA 的主要作用是对代码进行优化,所以它是编译器后端的一部分


标题:Static Single Assignment Form
作者:devcui
地址:https://blog.eiyouhe.com/articles/2020/08/25/1598362816494.html