下向き解析

次に，代入先のデータサイズで決まる左辺値の有効ビットの集合を元にして，木を下向きに辿って 行きながら，上向き解析で得た値域が張る有効ビット集合（値域の値の全てを区別して表現できる最 小限のビット数だけ1を最下位ビットから並べた集合）と，上から与えられた有効ビット集合をつき 合わせていく「下向き解析」を行う．値域とそれが張る有効ビット集合の関係を表7.4に示す．

上から与えられる有効ビット集合とは，ノードの出力の中で上のノードが必要としているビットの

7.2. データサイズ推論 89

MEM:I32 FRAME:I32 VAR:I32

CONST :I32

BAND :I32

BOR :I32

CONVSX :I32 ADD :I32 ADD :I32 SET :I16

CONVIT :I16

"a"

"b" "c"

MEM :I16

1 1

CONVSX :I32

MEM:I32 FRAME:I32 VAR:I32

MEM:I32 FRAME:I32 VAR:I32

1 _CONST

:I32 CONST

:I32 MEM

:I16 MEM

:I16 RSHS

:I32

RSHS :I32 0..1

-32768..32767

-16384..16383

-32768..32766 -32768..32767

1..1

0..65535 1..1

-32768..32767

value range

lo..up

図7.6: 図7.3に対する上向き解析の結果 表7.4: 値域が張る有効ビット集合

値域 有効ビット集合

0≤lo≤up<2^size−1 cover(up)

0≤up<lo<2^size−1 2^size−1（全域）

2^size−1≤lo≤up≤2^size−1 cover(lo)

2^size−1≤up<lo≤2^size−1 2^size−1（全域）

2^size−1≤lo≤2^size−1かつ0≤up<2^size−1 y=cover(lo)|cover(up)としてy|y <<1 2^size−1≤up≤2^size−1かつ0≤lo<2^size−1 2^size−1（全域）

cover(x)：xを最上位ビットからみて最初の1のビットから下を全て1にした値

（ex. cover(0x0000ff00) =0x0000ffff）

x：xのビット毎の反転

その他演算子はC言語の記法に従う．

集合，言い換えれば 上のノードの演算結果に影響を及ぼす可能性のあるビットの集合を意味する．下 のノードに与える有効ビット集合は，表7.5の下向き解析の推論規則を用いて決定する．例えば，図 7.3のSETノードでは，0x0000ffffが左辺値の有効ビット集合となる．しかし，有効ビット集合は，

必ずしも最下位ビットから始まるわけではない．例えば右シフト演算子のノードが下のノードに有効

表7.5: 下向き解析の推論規則

Lノード 下向き解析の推論規則

(N EG:t x) cover(w)をxに伝える．

(ADD:t x y)，(SU B: t x y)

xもyも定数でなければcover(w)をxとyに伝える．どちらか が定数であるときは注1の通り．

(M U L:t x y) x，yのどちらも定数でないときはcover(w)をxとyに伝える．

x，y の片方(例えばx)が2のべき乗の定数ならwをxで割っ た値をyに伝える．そうでなければ注2の通り．

(CON V SX:t x) xの最上位(符号)ビットの位置をiとする．wのiより上のビッ トに1がなければ，wのiより下のビット．そうでなければ，w のiより下のビットのiビットを1にした値をxに伝える．

(CON V ZX:t x) xの最上位ビットの位置をiとして，wのiより下のビットをx に伝える．

(BAN D:t x y) x，yの片方(例えばx)が定数であるときは w∧xをyに，そ うでなければwをxとyに伝える．

(BXOR:t x y) wをxとyに伝える．

(BOR:t x y) x，yの片方(例えばx)が定数であるときは w∧xをyに，そ うでなければwをxとyに伝える．

(BN OT :t x) wをxに伝える．

(LSH:t x y) yが定数の時はwをyビット右にシフトした値を，そうでなけ

ればcover(w)をxに，全ビットをyに伝える．

(RSHS:t x y) yが定数の時はwをyビット左に符号残しシフトした値を，そ

うでなければover(w)をxに，全ビットをyに伝える．

(RSHU :t x y) yが定数ならwをyビット左にシフトした値を，そうでなけれ

ばover(w)をxに伝える．

(T ST cc:t x y) 全ビットをxとyに伝える．(cc∈EQ，LT S，LT U) (IF :t c x y) wをxとyに，全ビットをcに伝える．

w： 上からきた有効ビット集合（図7.8の下向き解析のパラメタ）

他の単項演算子はwをそのままxに伝える．

over(w)：wの最下位ビットから見て最初の1にビットより上を全て1にした値

（ex. over(0x0000ff00) = 0xffffff00）

その他の記号は表7.4に同じ．

ビット集合を渡す場合，集合はシフト量の分だけ左に移動したものになる．このように，上から必要 とされているビットは「最下位から何ビット」という形でなく，ビット集合の形で伝える．

図7.6でAVEの定義を(a)とするの場合に対応するL式に対して，下向きの解析を行った結果を 図7.7に示す．

7.2. データサイズ推論 91

MEM:I32 FRAME:I32 VAR:I32

CONST :I32

BAND :I32

BOR :I32

CONVSX :I32 ADD :I32 ADD :I32 SET :I16

CONVIT :I16

"a"

"b" "c"

MEM :I16

1 1

CONVSX :I32

MEM:I32 FRAME:I32 VAR:I32

MEM:I32 FRAME:I32 VAR:I32

1 _CONST

:I32 CONST

:I32 MEM

:I16 MEM

:I16 RSHS

:I32

RSHS :I32 0xffff

0xffff

0xffff 0xffff

0x1 0x7fff 0x7fff

0xfffe

0xfffe 0x1

0x1 0xffff

0xffff

lv (set of mea-ningful bits)

図7.7: 図7.6に対する下向き解析の結果