x=a+b

Global Optimization
by Suppression of
Partial Redundancies
について
野崎晋也
部分冗長性除去(PRE)とは
• PRE:Partial Redundancy Elimination
• プログラム内において不要な部分を取り除く
• 最初に提案したのはE. Morel and C. Renviose
– Global Optimization by Suppression of Partial
Redundancies
Communications of the ACM, 22(2):96--103, February
1979
概要
• 冗長な計算の除去と、不変な計算のループ
外への移動は別に行われる事が多い
• 2回実行される部分の削除によって、
上記2つを一度にやり、最外ループへ移動
• プログラムの形に関係なくコストはほぼ線形
Local Properties(1)
• ブロックi内のあるexpression(式)に対して
– Transparency:TRANSP
• ブロックi内のコマンドの実行によって、その式のオ
ペランドに修正がなければその式は“transparent”
・・・
y=c+d
x=a+b
z=e
･･･
青の式の
オペランドに対する
変更文がない
Local Properties(2)
• ブロックi内のあるexpression(式)に対して
– Local Availability:COMP
• ブロックi内に最低1つ式の計算があり、その式の
最後の計算より後に出てくるコマンドがオペランド
を修正しなければ“locally available”
・・・
a=c
x=a+b
z=e
･･･
・・・
a=c
z=e
･･･
x=a+b
Local Properties(3)
• ブロックi内のexpression(式)に対して
– Local Anticipability:ANTLOC
• ブロックi内に最低1つ式の計算があり、その式の
最初の計算より前に出てくるコマンドがオペランド
を修正しなければ“locally anticipated”
・・・
z=e
x=a+b
a=c
･･･
x=a+b
・・・
z=e
a=c
･･･
Global Properties(1)
Availability=上安全(up-safe)
• Iの入口挿入点で上安全であるのは、Iのすべて
の先行ブロックが、出口計算を持つか出口挿入
点で上安全である場合
• ※開始ノードでは上安全ではない
• Iの出口挿入点で上安全であるのは、Iに変更文
がなく、かつ、Iに入り口計算があるかIの入口挿
入点で上安全である場合
上安全の例
• プログラムの入口からIに達するどの道に
も同じ値を与える計算がある場合
x=a+b
x=a+b
I
Anticipability=下安全
Global Properties(2)
(downsafe)
• Iの入口挿入点で下安全であるのは、Iに入口計
算があるか、Iの出口挿入点で下安全かつIに変
更文がない場合
• Iの出口挿入点で下安全であるのは、Iに出口計
算があるか、Iのすべての後続ブロックの入口挿
入点で下安全である場合
• ※後続ブロックがない場合は、後続ブロックは下
安全ではないと考える
下安全の例
• Iからプログラムの出口へのどの道へも同じ値を
与える計算がある(変更文を通らずにその計算に
達する)
I
x=a+b
x=a+b
Global Properties(3)
Global Utilization of Partial
Redundancy Elimination
• The steps of the algorithm are as follows:
– (a)Resolution of the Boolean systems for availability ,
anticipability , and partial availability.
– 上安全、下安全、そして部分的に上安全である場所
の決定
Global Utilization of Partial
Redundancy Elimination
• The steps of the algorithm are as follows:
– (b)Determination of predecessors of the blocks
containing the partial redundancies and where a new
computation may be introduced. This involves the
computation of the Boolean properties PPIN and
PPOUT (Placement Possible on Entry and Placement
Possible on Exit).
– 部分冗長を含み、新しい計算を挿入できる先行ノード
の決定
Determination of PPIN and PPOUT
• PPINの決定の為の各block iのCONSTi
– CONSTi :
• 各blockのPPIN/PPOUT
Global Utilization of Partial
Redundancy Elimination
• The steps of the algorithm are as follows:
– (c)Determination of a subset of these blocks on exit of
which a computation must be inserted. These blocks
satisfy the Boolean property INSERT.
– プログラム中の各block iのINSERTi
Global Utilization of Partial
Redundancy Elimination
• The steps of the algorithm are as follows:
– (d)Insertion of new computations at the exit of the
blocks satisfying INSERT = TRUE and suppression of
the partially redundant computations which are now
redundant.
– その後、INSERT=TRUEを満たす部分に新た
な計算を挿入
–
を満たすものは
部分冗長から冗長に→除去可能
Local Boolean Properties.
ANTLOC is TRUE for nodes 6,7,8,9; FALSE elsewhere.
COMP is TRUE for nodes 6,7,8,9; FALSE elsewhere.
TRANSP is FALSE for node 4;
TRUE elsewhere.
Global Boolean Properties(obtained by resolution of Boolean Systems).
ANTIN is FALSE for nodes 1,2,4; TRUE elsewhere.
AVOUT is TRUE for nodes 6,7,8,9; FALSE elsewhere.
PAVIN is FALSE for node 1;
TRUE elsewhere.
a
a+b
Value of PPIN and PPOUT (obtained by resolution of Boolean Systems).
PPIN isa+b FALSE for nodes 1,2,3,4; TRUE elsewhere.
PPOUT is FALSE for nodes 1,2,8,9; TRUE elsewhere.
a+b
Computation of INSERT.
INSERT is TRUE for nodes 3,4;
FALSE elsewhere.
a+b
Insertion and Suppression of Computations.
ANLOC . PPIN is TRUE for nodes 6,7,8,9;FALSE elsewhere.
a+b
a
a+b
Lazy Code Motion
M2 小川健一
従来の PRE 技術
• PREのアルゴリズムはデータフロー方程式を分
析する
• データは前向きの流れと、後向きの流れ、両方
向分析が主流
→しかし最もよい手法でもO(n^2)
• 1979年ビットベクトルアルゴリズムが生み出され
る（Morel等）
→単方向分析に変化
→計算量がO(n log n)に
PREのアルゴリズムのひとつ
• Code Motion
→不必要な再計算を避け効率のよい改良を行う技術
予備変数を利用し、出来るだけ前で計算
(Busyな手法)
問題点
・過剰なレジスタプレッシャーを引き起こす
→予備変数を長時間保持してしまう
解決策
・lazyな方法を用いる(安全かつ適当なところで計算)
Busy Code Motionの特徴
• 単方向分析
→計算量はO(n log n)
• コードの安全性の保ちながら改良
→2つの集合(D-safe,Earliest)を求めてコード移動を
• 出来るだけ前で計算を行う
○→冗長な計算の多くを削除できる
×→レジスタを長く占有する可能性がある
→不必要なコード移動の存在
１
Code Motion (Busy) の具体例
１
２
h=x+y
２
a=x+y
a=h
３
４ a=x+y
５
４
６ a=x+y
７
３
a=h
６
５
a=h
７
ブロック１から７まで変数h,x,yがレジスタを占有
Lazy Code Motionの特徴
• 単方向分析
→計算量はO(n log n)
• コードの安全性の保ちながら改良
→４つの集合(D-safe,Earliest,Latest,Isolated)
を求めてコード移動を
• 可能な限り遅く計算を行う
○→レジスタプレッシャーの軽減
→不必要なコードを除去できる
×→正確な除去が出来ない
Code Motion (Lazy) の具体例
１
２
１
a=x+y
３
４ a=x+y
２
a=x+y
５
４
６ a=x+y
７
３
h=x+y
a=h
６
５ h=x+y
a=h
７
レジスタ占有時間を減らすことに成功
Code Motion Algorithm
0.危険辺の除去
1.vを変数、tを計算式、G(N,E,s,e)をフローグラフとする
2.Used、Transp を求める
3.D-Safe、Earliestを求める（busyなら4、Lazyなら5へ）
4.コードの変形を行う → Busy
5.Delayを求める
6.Isolated、Latestを求める
7.OCP、ROを求めコードの変形を行う → Lazy
安全なポイントをさがすために
• 危険辺(Critical Edge)の除去
1 a=x+y
3
2
1
h=x+y
a=h
2
4 h=x+y
b=x+y
3
b=h
Used Transp の計算
• 両値ともにTかFで表現されるため、ノード１つに必要
な情報量は1ビット
• Used：対象式tがノードNに含まれていればTrue
• Transp：透過性の意、対象式がx+yの時にノードN
にxやyへの代入文が含まれていないとTrue
Used(n,t´) = t´ ∈ SubTerms(t)
Transp(n,t´) = v ∈ Var(t´)
集合計算１
The Busy Code Motion
Transformation
• 対象計算式 t のために新たな変数 h を作
成
• D-Safe と Earliest を満たすノード全ての入
口部分に h = t を挿入
• 全ての対象計算式 t を h で置換する
集合計算２
The Lazy Code Motion
Transformation
• 対象計算式 t のために新たな変数 h を作成
• OCPを満たすノード全ての入り口部分に h = t
を挿入
• ROを満たすノード全てに計算式 t を h で置換
OCP = { n|Latest(n)∧￢ Isolated(n) }
RO = { n|Used(n)∧￢(Latest(n)∧Isolated(n)) }
OCP ( optional computation point )
RO ( redundant occurrence )

Download Report