こんにちは､びしょ〜じょです｡いつの間にか2017年､そして2月｡季節はめぐり､また俺達は―

1. はじめに

さて以前DU Chainがなんとかって話をしたんですが､その中に出てくるControl Flow Graphというものについてかなり適当に流しました｡本当はここは重要なので､重要じゃよ〜

2. 構成方法

各命令を基本ブロックとする｡各命令にはその行番号と､次に実行される命令の行番号(指すべき先行ブロックの開始位置)をタグ付けする｡殆どの命令は行番号+1だが､以下の命令は異なり､または複数の行き先がある｡

instructions destination(s)

JMP, FORPREP +RB+1

LOADBOOL +2 if RC == 1

TEST, TESTSET, LT, LE, EQ +1, +2

FORLOOP, TFORLOOP +1,+RB+1

RETURN, TAILCALL none

RETURN, TAILCALLは必ずブロックの最後になり､そのブロックに先行ブロックは付かない｡
基本ブロックをつなげていく｡
1. 基本ブロック\(B_1\)の行き先が基本ブロック\(B_2\)の開始位置を指している場合､\(B_1\)の後続ブロックにブ\(B_2\)を追加する｡\(B_2\)の先行ブロックに\(B_1\)を追加する｡
2. \(B_1\)が\(B_2\)の開始位置以外を指している場合､
  1. \(B_2\)を
    - \(B_2a\): 開始位置〜指している位置-1
    - \(B_2b\): 指している位置〜\(B_2\)の最後に分割し､
  2. \(B_2\)の先行ブロックを\(B_2a\)に移し､\(B_2\)の後続ブロックを\(B_2b\)に移す｡
  3. \(B_2a\)の後続ブロックに\(B_2b\)を追加する｡\(B_2b\)の先行ブロックに\(B_2a\)を追加する｡
  4. \(B_1\)の後続ブロックに\(B_2b\)を追加する｡\(B_2b\)の後続ブロックに\(B_1\)を追加する｡

instructions	destination(s)
`JMP`, `FORPREP`	+`RB`+1
`LOADBOOL`	+2 if `RC` == 1
`TEST`, `TESTSET`, `LT`, `LE`, `EQ`	+1, +2
`FORLOOP`, `TFORLOOP`	+1,+`RB`+1
`RETURN`, `TAILCALL`	none

流れるような説明ありがとうございます!

3. example

以下のようなコード

local x = 3

if x < 5 then
    print"hello"
else
    print"world"
end

また､これから成るVMの命令列

        1       [1]     LOADK           0 -1    ; 3
        2       [3]     LT              0 0 -2  ; - 5
        3       [3]     JMP             0 4     ; to 8
        4       [4]     GETTABUP        1 0 -3  ; _ENV "print"
        5       [4]     LOADK           2 -4    ; "hello"
        6       [4]     CALL            1 2 1
        7       [4]     JMP             0 3     ; to 11
        8       [6]     GETTABUP        1 0 -3  ; _ENV "print"
        9       [6]     LOADK           2 -5    ; "world"
        10      [6]     CALL            1 2 1
        11      [7]     RETURN          0 1

を考える｡

まず､各命令を基本ブロックとして見ていき､先行ブロック(の開始位置)をタグ付けする｡

{
  {op = "LOADK" line = 1, succ_pos = {2}},
  {op = "LT", line = 2, succ_pos = {3, 4}},
  {op = "JMP", line = 3, succ_pos = 8},
  {op = "GETTABUP", line = 4, succ_pos = {5}},
  {op = "LOADK", line = 5, succ_pos = {6}},
  {op = "CALL", line = 6, succ_pos = {7}},
  {op = "JMP", line = 7, succ_pos = {11}},
  {op = "GETTABUP", line = 8, succ_pos = {9}},
  {op = "LOADK", line = 9, succ_pos = {10}},
  {op = "CALL", line = 10, succ_pos = {11}},
  {op = "RETURN", line = 11, succ_pos = {}}
}

そしてつなげていく｡

{
  {start = 1, end = 2, succ = {2, 3}, prev = {}}, -- block 1
  {start = 3, end = 4, succ = {4}, prev = {1}}, -- block 2
  {start = 4, end = 7, succ = {5}, prev = {1}}, -- block 3
  {start = 8, end = 10, succ = {2}, prev = {2}},
  {start = 11, end = 11, succ = {}, prev = {3, 4}}
}

4. おわりに

最近は体調以外良好気味です｡

そういえばTwitter Cardとかいう物体をねじ込んでみました｡よかったです｡いや本当は良くなくてね〜いや〜良い､良くない