技術

7.7. ユーザ定義ローカル変数

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第7章 万華鏡: 言語の拡張: 変更可能な変数(Mutable Variables)
第7節 ユーザ定義ローカル変数

var/inという文法(我々が万華鏡に追加してきた拡張と同じような)を追加する。
字句解析器、構文解析器、AST、コード生成部分を拡張する。
最初の一歩は、字句解析器を拡張するためにvar/in構造を追加することである。
以前見たように、これは実に些細な事である。
そのコードは以下のようになる。

enum Token {
  ...
  // varの定義
  tok_var = -13
...
}
...
static int gettok() {
...
    if (IdentifierStr == "in") return tok_in;
    if (IdentifierStr == "binary") return tok_binary;
    if (IdentifierStr == "unary") return tok_unary;
    if (IdentifierStr == "var") return tok_var;
    return tok_identifier;
...

次の一歩は、構築されるASTノードの定義である。
var/inのためのASTは以下のようになる。

/// VarExprAST - var/inのための式クラス。
class VarExprAST : public ExprAST {
  std::vector<std::pair<std::string, ExprAST*> > VarNames;
  ExprAST *Body;
public:
  VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames,
             ExprAST *body)
  : VarNames(varnames), Body(body) {}

  virtual Value *Codegen();
};

var/inによって、名前のリストを一度に定義可能となり、各名前はオプションとして初期値を持つことが出来る。
したがって、この情報をVarNamesベクタとしてキャプチャする。
var/inは本文も持ち、その中でvar/inで定義される変数にアクセス可能となる。

これで、我々は構文解析器の一部を定義出来る。
最初に行うのは、var/inをプライマリ式として追加することである。

/// primary
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
///   ::= ifexpr
///   ::= forexpr
///   ::= varexpr
static ExprAST *ParsePrimary() {
  switch (CurTok) {
  default: return Error("unknown token when expecting an expression");
  case tok_identifier: return ParseIdentifierExpr();
  case tok_number:     return ParseNumberExpr();
  case '(':            return ParseParenExpr();
  case tok_if:         return ParseIfExpr();
  case tok_for:        return ParseForExpr();
  case tok_var:        return ParseVarExpr();
  }
}

つぎにParseVarExprを定義する。

/// varexpr ::= 'var' identifier ('=' expression)?
//                    (',' identifier ('=' expression)?)* 'in' expression
static ExprAST *ParseVarExpr() {
  getNextToken();  // varを消費する。

  std::vector<std::pair<std::string, ExprAST*> > VarNames;

  // 少なくとも1つの変数名が必要。
  if (CurTok != tok_identifier)
    return Error("expected identifier after var");

このコードの最初の部分では、識別子と、式のペアをローカルのVarNamesベクタに解析して格納する。

while (1) {
  std::string Name = IdentifierStr;
  getNextToken();  // 識別子を消費。

  // オプションの初期化子を読み取る。
  ExprAST *Init = 0;
  if (CurTok == '=') {
    getNextToken(); // =を消費。

    Init = ParseExpression();
    if (Init == 0) return 0;
  }

  VarNames.push_back(std::make_pair(Name, Init));

  // varのリストの最後ではループを抜ける。
  if (CurTok != ',') break;
  getNextToken(); // ,を消費。

  if (CurTok != tok_identifier)
    return Error("expected identifier list after var");
}

すべての変数が解析されたら、本文を解析しASTノードを生成する。

  // この時点では"in"でなければらなない。
  if (CurTok != tok_in)
    return Error("expected 'in' keyword after 'var'");
  getNextToken();  // inを消費。

  ExprAST *Body = ParseExpression();
  if (Body == 0) return 0;

  return new VarExprAST(VarNames, Body);
}

これで、構文解析しコードを表現することが出来る。
そしたらこれについてLLVM IRの生成をサポートする必要がある。
そのコードは以下のようにして始まる。

Value *VarExprAST::Codegen() {
  std::vector<AllocaInst *> OldBindings;

  Function *TheFunction = Builder.GetInsertBlock()->getParent();

  // 変数全てを登録し、それぞれの初期化子を生成する。
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
    const std::string &VarName = VarNames[i].first;
    ExprAST *Init = VarNames[i].second;

基本的には、全ての変数に対してループが行われ、一度にひとつずつ取り込まれる。
シンボルテーブルに登録された各変数について、以前の値をOldBindingsの中に保存する。

  // 変数をスコープに追加する前に初期化子を生成する。
  // これによって、変数そのものを参照する初期化子を防ぐ。
  // またこれによって、以下のような書き方が可能となる。
  //  var a = 1 in
  //    var a = a in ...   # 外側のaを参照。
  Value *InitVal;
  if (Init) {
    InitVal = Init->Codegen();
    if (InitVal == 0) return 0;
  } else { // 指定されなければ0.0を使う。
    InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0));
  }

  AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
  Builder.CreateStore(InitVal, Alloca);

  // var/inの本文の抜けたときに値を復元出来るようにするために、古い値を記憶しておく。
  OldBindings.push_back(NamedValues[VarName]);

  // 値を記憶。
  NamedValues[VarName] = Alloca;
}

初期化子を生成し、allocaを生成し、そしてシンボルテーブルをそれを指すよう更新するというのが基本的なアイデアである。
全ての変数がシンボルテーブルに登録されたら、var/in式の本文を評価する。

// ローカル変数をそのスコープに含む、var/inの本文のコード生成を行う。
Value *BodyVal = Body->Codegen();
if (BodyVal == 0) return 0;

最後に、呼び出し元に戻る前に、保存しておいた”以前の値”を復元する。

  // スコープから全ての変数を取り出し、以前の値をセットする。
  for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
    NamedValues[VarNames[i].first] = OldBindings[i];

  // 本文の計算結果を返す。
  return BodyVal;
}

以上のコードによって、正しくその作用範囲が定められた変数(スコープつき変数)を定義したり、さらに(自動的に)その変数への代入する事が可能となった。

これによって、目的は達成された。
7.4節にあった、反復的なfibの例を、コンパイルして実行出来るようになった。
mem2regパスによって、全てのスタック変数はSSAレジスタに最適化され、必要な箇所にphiノードが挿入されるので、我々のフロントエンドはシンプルさを保ったままである。
”反復的な支配辺境(iterated dominance frontier)”の計算は、我々のコードの見える部分には存在しない。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示