4.4 LLVM の型と LLVM アセンブリの主な命令 令 result = load [volatile] ロード命令。 pointer が指すメモリアドレスから値を読み出す。 <type>* <pointer> [ , align <alignment>] vo t ⅱ e が指定されている場合、最適化は load 命令の実 [ , !nontemporal !<index>] 行順や実行数をほかの vo t ⅱ e な命令に変更することがで [ , !invariant 」 oad !<index>] きない result = load atomic [volatile] <type>* く pointer> <singlethread> <ordering>, !index = ! i32 1 align <alignment> store [volatile] <type> <value>, <type>* <pointer> [ , align <alignment>] [ , !nontemporal!<index>] store atomic [volatile] く type> <value>, <type>* <pointer> [singlethread] <ordering>, align <alignment> getelementptr result = getelementptr <ptype>* <ptrval> result = getelementptr inbounds <ptype>* <ptrval> result = getelementptr <ptr vector> く ptrval>, <vector index type> <idx> load ストア命令。 pointer が指すメモリアドレスに値を格納する。 vo t ⅱ e が指定されている場合、最適化は sto 「 e 命令の実 行順や実行数をほかの volatile な命令に変更することがで きない store 要素アドレス取得命令。 合成型内の要素のアドレスを計算する。 prtval が指すアドレスをベースとして idx で指定したイン デックスの要素アドレスを計算する 4.4.7 型変換演算子 代表的な型変換演算子を表 4.9 に示します。型変換演算子にはその名のとおり、 オペランドとして渡され た値の型を変換する命令が分類されています。 ■表 4.9 LLVM の型変換演算子 切り捨て命令。 result = trunc <type> <value> tO <type2> trunc tO value を type から type2 へ切り捨てる。 2 つの型は整数か整数のべクタ。 また、 type は type2 よりビットサイスが大きい ゼロ拡張命令。 value を type2 へキャストし、高位ビットを 0 で埋 める。 2 つの型は整数か整数のべクタ。 また、 type2 は type よりビットサイスが大きい result = zext <type> <value> tO <type2> zext to 35

第 4 章 sext tO LLVM 旧 、戛 ~ 構文 fptrunc tO ptrtoint tO bitcast to fpext tO fptoui tO fptosi tO uitOfp tO sitOfp tO inttoptr tO result = sext <type> <value> tO <type2> result = fptrunc <type> <value> tO <type2> result = fpext <type> <value> tO <type2> result = fptoui <type> <value> tO <type2> result = fptosi <type> <value> tO <type2> result = uitofp <type> <value> tO <type2> result = sitofp <type> <value> tO <type2> result = ptrtoint <type> <value> tO <type2> result = inttoptr <type> <value> tO <type2> result = bitcast <type> <value> tO <type2> 概要 符号拡張命令。 value を type2 へキャストし、高位ビットを value の符号ビットで埋める。 2 つの型は整数か整数のペクタ。 また、 type2 は type よりヒ、ツトサイズが大きい 切り捨て命令。 value を浮動小数点数型 type から type2 へ切り捨 てる。 type は type2 よりピットサイズが大きい 拡張命令。 value を浮動小数点数型 type から type2 へ拡張す る。 type2 は type よりヒ、ツトサイズが大きい 変換命令。 浮動小数点数 va 旧 e を符号無整数型 type2 へ変換 する 変換命令。 浮動小数点数 va 旧 e を符号付整数型 type2 へ変換 する 変換命。 符号なし整数 va e を浮動小数点数型 type2 へ変 換する 変換命令。 符号付き整数 value を浮動小数点数型 type2 へ変 換する 変換命令。 ホインタ value を整数型 type2 へ変換する 変換命令。 整数 value をポインタ type2 へ変換する ピット変換命令。 value を各ビットを変更せすに type2 へ変換する 4.4.8 その他の命令 ManualJ の「その他の命令 (Other Operations) 」の項目では、ほかに select 命令や va-arg 命令などが の関数に相当します。また、 call 命令は関数呼び出しに使用する命令です。「 LLVM Language Reference 令を紹介しておきます。 icmp 命令や fcmp 命令は値を比較する命令で、 phi 命令は SSA の説明で紹介した その他の命令を表 4.10 に示します。ここでは、その他の命令として icmp 、 fcmp 、 phi 、 call の 4 つの命 紹介されています。 ■表 4.10 LLVM のその他の命令 result = icmp <cond> <type> く 0P1 > , く 0P2 > lCmp 命令を構文 36 比較命令。 0P1 、 0P2 を cond で指定した条件で比較し、真偽を返 す。 0P1 、 0P2 は整数かポインタか整数のべクタ ー : 概要

第 5 章フロントエンドの作成 第 1 引数には戻り値の型を Type で指定します。第 2 引数には引数の型を示す Type を格納したべクタ を与えます。第 3 引数には可変長引数かどうかを b 。 ol 型で指定します。なお、 Type の生成には複数の方 法があるのですが、本書では次に示す Type クラスのメソッドを使用します。 IIvm::Type::getInt32Ty static 工 ntegerType * get 工 nt32Ty(LLVMContext &C) Type クラスの宣言は「 llvm/Type. h 」にあります。なお、 DummyC はすべて int 型という制約を設 けているので Type の生成はどれも getInt32Ty ( ) メソッドを用いればよいのですが、 void 型の場合は getVoidTy 、 float 型の場合は getFloatPtrTy などのほかのメソッドを使用しなければなりません。以上をま ・リスト 5.37 generatePrototype とめた generatePrototype をリスト 5.37 に示します。 2 3 4 5 6 7 8 9 14 17 20 22 23 24 26 27 28 29 30 114 ☆関数宣言生成メソッド * @param PrototypeAST ′ Module ま @return 生成した Function のポインタ Function *CodeGen : : generatePrototype ( PrototypeAST *proto ′ / / already declared? Function *func=mod—>getFunction (proto—>getName ( ) if(func){ ModuIe *mod ) { if( func->arg—size ( )==prot0->getParamNum( ) & & func->empty( ) ) { return func ー }else{ fprintf ( stderr, return NULL ー "error: : function is redefined",proto—>getName( ) . c—str( ) 房 / / create arg—types std : : vector く Type*> int—types ( proto—>getParamNum( ) ′ Type: :getInt32Ty(getG10ba1Context( ) ) ); / / create func type FunctionType *func—type = FunctionType : : get ( Type: :getInt32Ty( getG10ba1Context( ) )' int—types ′ false / / create function func=Function : : Create ( func—type ー Function : : ExternalLinkage ′ prot0->getName ( )'

5.5 構文解析 26 27 / ☆ * * 変数宣言を表す AST 28 29 30 class VariabIeDec1AST: public BaseAST { public : typedef enum{ 32 33 param, 10Ca1 34 }Dec1Type ー 35 36 private : 37 std: : string Name; 38 DecIType Type; 39 public : 40 VariableDec1AST(const std: : string &name) 42 43 44 46 47 48 49 50 53 54 55 56 58 59 60 62 63 / * ☆ まニ項演算を表す AST 64 public BaseAST { class BinaryExprAST 66 std: :string 0 BaseAST *LHS, *RHS ー public : 70 BinaryExprAST( std: :string op ′ BaseAST *lhs ′ BaseAST *rhs ) : BaseAST(BinaryExprID), Op ( op ) ′ LHS(1hs) ′ RHS(rhs){} BaseAST(VariableDec11D) ′ Name(name) { / / VariabIeDec1AST なので true を返す static inline b001 classof (Variab1eDecIAST const* ) {return true;} / / 渡された BaseAST クラスが Variab1eDec1AST か判定する static inline b001 c1assof(BaseAST const* base) { return base—>getValueID ( ) ==Variab1eDec1 工 D; -Variab1eDec1AST ( ) { } / / 変数名を取得する std: : string getName( ) {return Name;} / / 変数の宣言種別を設定する b001 setDec1Type ( Dec1Type type ) {Type=type; return true : / / 変数の宣下種別を設定する Dec1Type getType ( ) {return Type 73

第 4 章 switch LLVM 旧 構文 switch <intty> <value>,label <default> [<intty> <val>,label <dest> … ] 概要 複数の分岐先を持つ b 「命令のようなもの。 value と一致する v 引があれは該当 v の dest へ遷移 する。一致しなければ defau はに遷移する 4.4.3 ニ項演算子 ない命令や定数式が予期せぬ動作を引き起こすことを検知した、という意味を含んでいます。 value は Undef value( 未定義の値 ) に似たものです。ただし、 Poison Value は、副作用を起こしてはいけ poison value になるというフラグと思われます。「 LLVM Language Reference ManualJ によれば P0ison value になるというフラグを意味します。また、 udiv 命令の exact は叩 1 が叩 2 の倍数でないときに Signed wrap 」の略で、それぞれ Unsigned と Signed の演算でオーバーフローが発生したときに P0ison 算命令が分類されます。なお、 add 命令や sub 命令に現れる nsw や nuw は「 No Unsigned Wrap と No 代表的な二項演算子を表 4.5 に示します。二項演算子には加算や乗算などの 2 つのオペランドをとる演 ■表 4.5 LLVM のニ項演算子 add 命令 fadd sub fsub mul fmul udiV SdiV 3 2 葺構文 「 esult = sdiv exact <type> く 0P1 > , < 0P2 > result = sdiv <type> < 0P1 > , く 0P2 > result = udiv exact <type> く 0P1 > , く 0P2 > result = udiv <type> く 0P1 > , く 0P2 > result = fmul <type> く 0P1 > , く 0P2 > result = mul nuw nsw <type> く 0P1 > , く 0P2 > result = mul nsw <type> く 0P1 > , く 0P2 > result = mul nuw <type> < 0P1 > , く 0P2 > result = mul <type> く 0P1 > , く 0P2 > result = fsub <type> く 0P1 > , く 0P2 > result = sub nuw nsw <type> く 0P1 > , く 0P2 > result = sub nsw <type> く 0P1 > , く 0P2 > result = sub nuw <type> く 0P1 > , く 0P2 > result = sub <type> く 0P1 > , く 0P2 > result = fadd <type> く 0P1 > , く 0P2 > result = add nuw nsw <type> < 0P1 > , く 0P2 > result = add nsw <type> く 0P1 > , く 0P2 > result = add nuw <type> く 0P1 > , く 0P2 > result = add <type> く 0P1 > , く 0P2 > 概要 加算命令。 0P1 と 0P2 を足して結果を返す。 0P1 、 0P2 は整数か整数のペクタ 加算命令。 0P1 と 0P2 を足して結果を返す。 0P1 、 0P2 は浮動小数点数か浮動小数点数のべクタ 減算命令。 0P1 から 0P2 を引いて結果を返す。 0P1 、 0P2 は整数か整数のべクタ 減算命令。 0P1 から 0P2 を引いて結果を返す。 0P1 、 0P2 は浮動小数点数か浮動小数点数のべクタ 乗算命令。 0P1 と 0P2 をかけて結果を返す。 0P1 、 0P2 は整数か整数のべクタ 乗算命令。 0P1 と 0P2 をかけて結果を返す。 0P1 、 0P2 は浮動小数点数か浮動小数点数のペクタ 除算命令 (unsigned)o 0P1 を 0P2 で割って商を返す。 0P1 、 0P2 は整数か整数のべクタ 除算命令 (signed)o 0P1 を 0P2 で割って商を返す。 0P1 、 0P2 は整数か整数のべクタ

4.4 概要 LLVM の型と LLVM アセンブリの主な命令 命令 fdiv urem srem frem 構文 「 esult = fdiv <type> < 0P1 > , く 0P2 > result = frem <type> く 0P1 > , く 0P2 > result = srem <type> く 0P1 > , く 0P2 > result = urem <type> く 0P1 > , く 0P2 > 除算命令。 0P1 を 0P2 で割って結果を返す。 0P1 、 0P2 は浮動小数点数か浮動小数点数のべクタ 剰余命令 (unsigned)o 0P1 を 0P2 で割って余りを返す。 0P1 、 0P2 は整数か整数のペクタ 剰余命令 (signed)o 0P1 を 0P2 で割って余りを返す。 0P1 、 0P2 は整数か整数のペクタ 剰余命令。 0P1 を 0P2 で割って余りを返す。 0P1 、 0P2 は浮動小数点数か浮動小数点数のべクタ 4.4.4 ビット演算子 ふれたいずれかのビットが 0 でないときに poison Value になるというフラグです。 poison VaIue となることを意味するようです。また、 lshr 命令や ashr 命令の exact は、シフトによってあ で、 nsw はシフトした結果得られる値の符号ビットと一致しない値 ( 0 / 1 ) がシフトによってあふれたときに shl 命令に現れる nuw は、 0 でない値がシフトによって外された場合に Poison VaIue になるというフラグ れます。 代表的なビット演算子を表 4.6 に示します。ビット演算子にはシフトや論理和、論理積等の命令が含ま ・表 4.6 LLVM のビット演算子 lshr ashr and 0 「 XO 「 構文 result = xor <type> く 0P1 > , く 0P2 > result = 0 「 <type> く 0P1 > , く 0P2 > result = and <type> < 0P1 > , く 0P2 > result = ashr exact <type> く 0P1 > , く 0P2 > result = ashr <type> く 0P1 > , < 0P2 > result = lshr exact <type> く 0P1 > , く 0P2 > result = h 「 <type> く 0P1 > , く 0P2 > result = shl nuw nsw <type> く 0P1 > , く 0P2 > result = shl nsw く type> く 0P1 > , く 0P2 > result = shl nuw <type> く 0P1 > , く 0P2 > result = shl <type> く 0P1 > , く 0P2 > 概要 左シフト命令。 0P1 を 0P2 で指定したビット数左に算術シフトする。 0P1 、 0P2 は整数か整数のペクタ 論理右シフト命令。 0P1 を 0P2 で指定したヒ、ツト数右に論理シフトする。 0P1 、 0P2 は整数か整数のペクタ 算術右シフト命令。 0P1 を 0P2 で指定したヒ、ツト数右に算術シフトする。 0P1 、 0P2 は整数か整数のペクタ 言侖王里番責ロ卩 -rzo 0P1 、 0P2 の論理積をとる。 0P1 、 0P2 は整数か整数のべクタ 論理和命令。 0P1 、 0P2 の論理和をとる。 0P1 、 0P2 は整数か整数のべクタ 排他的論理和命令。 0P1 、 0P2 の排他的論理和をとる。 0P1 、 0P2 は整数か整数のべクタ 33

第 5 章フロントエンドの作成 18 20 22 23 24 25 26 27 28 29 30 32 33 34 35 36 37 38 39 40 42 43 TokenType Type; std: : string TokenString; int Number; int Line; public : TOken ( std: : string string ′ TokenType type ′土 n セ line ) TokenString(string), Type(type) ′ Line( line) { -Token( ) { else Number if ( type Number = 0x7fffffff; atoi( string ・ c—str( ) ) : = TOK—D 工 GIT) int getLine( ) {return Line;} / / トークンの出現した行数を取得 int getNumberVa1ue ( ) {return Number; / / トークンの数値を取得 ( 種別が数字である場合に使用 ) std: : string getTokenString( ) {return TokenString;} ー / / トークンの文字列表現を取得 TokenType getTokenType ( ) {return Type ー / / トークンの種別を取得 44 5.4.3 TokenStream クラスの実装 先ほどの Token クラスを格納する TokenStream クラスを作成します。 TokenStream は、切り出したす べての Token の格納と、格納した Token の読み出しの機能を提供するものです。 TokenStream クラス は Token を格納するためのクラスなので、基本的には Token を保存するリストや配列を用意して setter / getter を作成すればよいのですが、構文解析で「〇個分前のトークンまで戻る」あるいは「〇番目のトーク ンまで戻る」といった操作を行うため、 TokenStream にはこれらの機能も持たせる必要があります。 このことから、ま $TokenStream クラスでは表 5.1 に挙げるメンバ変数を持つものとします。 ・表 5.1 TokenStream クラスのメンノヾ変数 TokenStream クラス名 std::vector<Token*> Tokens int Curlndex Token を格納するべクタ 呼び出し対象の Token のインデックス 補足 切り出した Token は Tokens べクタに格納しておき、 Token を取得するメソッドが呼び出された際には CurIndex 番目のトークンを返却することにします。また、インデックスをインクリメントするメソッド、およ 62

第 4 章 LLVM 旧 4.4.5 合成演算子 合成演算子を表 4.7 に示します。合成演算子は合成型の値を操作する命令です。 ・表 4.7 LLVM の合成演算子 命令 insertvalue extractvalue 構文 result ー <type> く e は > , <index>{, く index>}* <aggreagate type> く v 引 > , ー insertvalue <index>{, <index>}* <aggreagate type> く v 引 > , result = extractvalue 第概要 i32 1 , O %result = insertvalue { i32 , float} %agg_val, する。 次の例では % agg ー v 引の i32 型要素に O を挿入 る。 index には挿入する要素のインデックスを指定す ランドは挿入する first-class の値となる。 第 1 オペランドは構造体か配列であり、第 2 オペ 値を挿入する。 val 内の index で指定したインデックスの要素に 合成型への値挿入命令。 val, O %result = extractvalue { i32 , float} %agg_ す。 次の例では %agg_val から i32 型の値を取り出 取り出す要素のインデックスを定数で指定する。 第 1 オペランドは構造体か配列であり、 index には 出す。 val から index で指定したインデックスの値を取り 合成型からの値取り出し命令。 4.4.6 メモリアクセス演算子 cmpxchg 命令があります。なお、 getelementptr 命令に inbound が付与された場合は、 getelementptr 命 クセス演算子の特殊さがわかるでしよう。ここで示した以外のメモリアクセス演算子としては、 fence 命令や 意図が伝わりにくいかもしれませんが、ここで紹介する store 命令や I 。 ad 命令の役割を見ると、メモリア トですが、 LLVM においては、メモリ配置は SSA 形式にしないことでシンプルにしているようです。少し ストアなどの命令が含まれます。 SSA 形式においてメモリをどのように表現するかというのは重要なポイン 代表的なメモリアクセス演算子を表 4.8 に示します。メモリアクセス演算子にはメモリの確保やロード、 令が確保された領域の範囲外へアクセスした場合に結果が Poison Value となることを意味します。 ・表 4.8 LLVM のメモリアクセス演算子 alloca 34 result = alloca <type> [ , <type> <NumElements>] [ , align <alignment>] 構文 メモリ確保命令。 type x NumElements の領域を関数のスタックフレーム 上に確保 概要

4.4 LLVM の型と LLVM アセンブリの主な命令 ・表 4.3 derived に含まれる型 配列型。次に示すように、 [ く要素数 > x く型名 > ] という形式で表す。 array 例 ) [IO x i32 ] ・ i32 型の要素を 10 個持つ配列 ; i32 型の要素を 10 x 10 個持つニ次元配列 [IO x [IO x i32 ] ] Function のシグネチャを表す型。関数の戻り値や引数の型のリストとして表す。 例 ) i32 ( i32 ) ・ i32 型の引数を 1 っとり、 i32 型の値を返す function ポインタ型。メモリ配置を表すために使用する。 オプションとしてポインタが指すオブジェクトを配置するアドレス空間を指定できる。 次に示すようにく型名 > ☆という形式で表す。 例 ) i32 ☆ ; i32 型の値を指すポインタ ; アドレス空間 1 にある i32 型の値を指すポインタ i32 addrspace(l)* 構造体を表す型。 % 名前 =type { < 型のリスト > } という形式で表す。 % 名前 = type く { く型のリスト > } > という構文で記述された場合は packed structure と呼はれる。 この場合は構造体が 1 パイトアライメントで配置され、構造体の要素間にハディングが詰められないことを 意味する。 例 ) %struct. mytype = type { i32 , float} ; i32 型と float 型を持つ structure %struct. mytype = type く { i8 , i32 , i32 } > ; サイスが 9 バイトとなる packed structure ペクタ型。 SIMD 命令のオペランドのように、複数の要素を持つ値を表すために使用する。 次に示すように、くく要素数 > x く型名 > > という形式で表す。 例 ) < 4 x i32 > ; i32 型の要素を 4 個持つべクタ opaque 構造体。本体が未定義な structure を表すために使用する。 C 言語で言うところの前方宣言に相当する。次のように使用される。 例 ) %struct. mytype = type opaque 概要 function pointer structure vector 第 4 章 opaque 4.4.2 終端命 -ra ここからは LLVM IR の各種命令を紹介していきます。はじめに代表的な終端命令を表 4.4 に示します。 表 4.4 の return 命令は C 衄における return 文に相当し、 br 命令は if - else 文などの分岐に相当します。 に 1 ロロ また、 switch 命令はそのまま switch 文に相当します。 このほかの終端命令としては、 indirectbr 命令や invoke 命令などがあります。 ■表 4.4 LLVM の終端命令 ret ret <type><value> ret void 概要 卩 -n 皀構文 return 叩 -po 関数の呼び出し元へ制御を移す。 value が指定されていれば va 旧 e を返す 分岐命令。 br il <cond>,label <ift 「 ue>,label <iffalse> cond の true/false に応して分岐先が変わる。 brlabel <dest> cond が指定されていなけれはラベル名 dest の BasicBIock へ分岐する 31

第 7 章バックエンドを作る class や def をまとめて定義する方法として、 multiclass と defm があります。これらはマクロのようなも ので、一定のパターンの定義を一度に実体化させることができます。使える場面も多くあると思いますが、 class と def だけでできないことではないので、こでは紹介しません。 ほかにも制御構造として f 。 reach を使ったループや !if を使った条件分岐などを記述可能です。これらの ■表 7.3 Tab 厄 Gen で利用できる型の種類 7.3 に、値の一覧を表 7.4 に、構文を表 7.5 に示します。 TabIeGen を記述するために専用の型や構文が用意されています。 TabIeGen で利用できる型の一覧を表 7.6.3 TabIeGen の記述形式 利用できる式などを以降で列挙しています。 細かい説明は本書では取り上げないので、公式のドキュメントやソースコードなどを参考にしてください。 bit int code dag CIass type list<ty> bits<n> string boolean 型。 O か 1 を保持できる 32 ビット整数型 文字列型 固定長の整数型 ほかの型のリスト クラス型 有向グラフ ソースコード ■表 7.4 TabIeGen で利用できる値の種類 Ob101 0707 190 O x7f " fo び [X,Y,Z]<type> {a, b, c} value vaIue{17} va 旧 e { 15-17 } DEF CLASS<val list> X. Y ⅱ st [ 4-7 , 17 , 2-3 ] 値の例 224 未初期化値 2 進数値 8 進数値 10 進数値 16 進数値 文字列 ソースコード type 型のリスト bits<3> の初期化 値の参照 値の特定ヒ、ツトにアクセス 値の複数ビットにアクセス 定義の参照 引数付きの匿名クラスの参照 値のサプフィールドの参照 リストスライス