retrage.github.io

正規表現からLLVM IRを生成する

正規表現からLLVM IRを生成する

正規表現は文字列マッチングなどに広く用いられている形式言語であるが， 等価な決定性有限オートマトン(DFA)に変換できることが知られている． google/redgrep は与えられた正規表現から等価なDFAに相当するネイティブコードを LLVMにより生成する． ここではredgrepを改造して 正規表現からどのようなLLVM IRが生成されるのかをみてみる．

redllというツールを追加した．コードは

に置いてある．

使い方

最初にLLVMのソースコードをダウンロードして ビルドしてローカルの適当な場所にインストールしておく． redgrepは新しいLLVMを要求するのでLLVM 8.0.0あたりを入れておく． redgrepのビルドが通るようにパスを通す．

$ export LLVM_CONFIG=/path/to/bin/llvm-config

とかやってからredgrepをビルドする．

$ ./redll "regex"

で遊べる．

例: “a”

試しに正規表現パターン"a"がどのようになるのかを以下に示す．

$ ./redll "a"
; dfa is 3 states
; ModuleID = 'M'
source_filename = "M"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

; Function Attrs: norecurse nounwind readonly
define i1 @F(i8* nocapture readonly, i64) local_unnamed_addr #0 {
entry:
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %return_true, label %3

return_true:                                      ; preds = %3, %entry
  ret i1 false

; <label>:3:                                      ; preds = %entry
  %4 = load i8, i8* %0, align 1
  %cond = icmp eq i8 %4, 97
  br i1 %cond, label %5, label %return_true

; <label>:5:                                      ; preds = %3
  %6 = icmp eq i64 %1, 1
  ret i1 %6
}

attributes #0 = { norecurse nounwind readonly }

ここではFという関数があり， 入力が0であればfalseを返し， そうでなければ入力から1文字取り出し 97=aであれば1=trueを返す， というような状態機械になっていることがわかる．

まとめ

他にも色々面白く遊べるはずなので試してほしい．

参考文献