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

1. はじめに

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

2. 構成方法

  1. 各命令を基本ブロックとする。 各命令にはその行番号と、次に実行される命令の行番号(指すべき先行ブロックの開始位置)をタグ付けする。殆どの命令は行番号+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は必ずブロックの最後になり、そのブロックに先行ブロックは付かない。

  2. 基本ブロックをつなげていく。

    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\)を追加する。

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

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とかいう物体をねじ込んでみました。よかったです。いや本当は良くなくてね〜いや〜良い、良くない