gtagsのスタックをscreen毎に管理するelscreen-gtagsを書いてみた

Emacs

Emacsでelscreenを使っていてコードリーディングなどをしているとgtagsのタグジャンプを複数のスクリーンでしてしまい、
gtags-pop-stackで元の場所に戻ろうと思ったら別のスクリーンのジャンプ元に戻ったりすることがあります。
gtagsはかなり便利で昔から使っていますが、この点がずっと悩みどころでした。
最近Emacs24の対応でelscreen.elやelscreen-buffer-list.elのソースを読んでだいたい仕組みがわかったのでこの問題を解決しようと思いました。

ソースコードはこちら(github)。
load-pathにおいて(require 'elscreen-gtags)するだけで有効になります。
とりあえずで作った状態なので設定項目が全くないし、細かいところでバグがあります。
気が向いたら更新していきたいと思います。

ちなみにelscreen-buffer-list.elはあまり知られていないマイナーなものかもしれないですが、
これもスクリーン毎にバッファリストを管理してくれるようになるelispです。
Emacs24になってelscreen.elとelscreen-buffer-list.elに若干修正が必要になっています。
elscreen-gtagsは修正済みのelscreen.elを前提としています。
後日修正方法をまとめようと思いますが、基本的にはこちらの通りです。

LLVMのフロントエンドとバックエンド

LLVM

LLVMを使っている言語ってどんなものがあるのか聞かれたり、自分でもどれくらいあるのか気になっていたのでまとめてみた。
フロントエンドはある言語からLLVM IRに変換するもののこと。
バックエンドはLLVM IRから他の言語に変換するもの(トランスレータ)のことで、x86やARM等のようなターゲットに関しては挙げていません。

フロントエンドに関してはここで挙げているものは一般的な言語のみ。有名なのに名前が挙がってないのは忘れているだけ。DSLのようなものを含めるともっとあるはず。
バックエンドは何があるのか調べるのが面倒なので適当に挙げてるだけ。

他にこれも書いておけというのがあれば追加していきます。

フロントエンド

バックエンド

LLVM解説本をC82で出します

LLVM


LLVMの解説本をC82の2日目(8/11)西し39aで出します。
タイトルは「3日で出来るLLVM」です．
LLVMを使ってコンパイラを作るという内容になっています。
フロントエンドとミドルエンドはid:motipizza(@)が担当し、自分はバックエンドの担当です。
表紙は矢上さん(blog)に書いていただきました。かわいい表紙でよくできているのでこれだけでも売れそうです。

目次は以下のようになっています。

  • はしがき
  • 第一章：はじめに
  • 第二章：コンパイラとLLVM
  • 第三章：環境構築
  • 第四章：LLVM IR
  • 第五章：フロントエンドを作る
  • 第六章：Pass について
  • 第七章：バックエンドを作る
  • あとがき

LLVM解説本を作ると決まってからLLVMについていろいろと調べ始めましたが、
ほとんど資料が無く特にバックエンドに関しては皆無のような状態で苦労しました。
自分が理解できている範囲もそれほど多くなく間違っているところもありそうですがなんとか形になりました。
LLVMについての全てを解説できているわけではもちろん無く、自分が知っている範囲も全て残せているわけではないですが、
LLVMを使う上での重要な部分はだいたいわかると思います。

本に書かれていることで間違っていることやこうした方がいいなどの意見があればコメントやTwitterなどで連絡していただければ幸いです。
もし次に書くことがあれば参考させていただきます。

C82として書いていなかったですが詳細を追記しておきます。
コミックマーケット82
場所:東京ビッグサイト
サークル名：MotiPizza
日程：2日目 (8月11日)
スペース番号：西し39a

思ったより話題になって驚愕しているので更に追記。
趣味でLLVMさわっているだけの二人がなんとなく作っただけの本なので内容の正確性は保証できません。
初心者向けとしているのでLLVMについて既によくわかっている方には特に新しい内容は無いかもしれません。
値段は1部800円です。身内配布用を除いて全部で60部になります。

増刷や電子書籍について。
増刷や委託の予定は完全にありません。申し訳ないですが、会場に足をお運びいただくか他の方にお願いして下さい。
売り切れても見本はたぶんおいておくのでそこでゆっくり読んで頂いても結構です。
電子書籍はノーコメントとしたいところですが、正直わかりません。
理由は著者二人ともが今回の内容では質が微妙だと思ってるからです。
特に内容の正確性を全く保証できない程度の状態で執筆したので、間違った情報を広げたくないというのがあります。
とりあえず買って頂いた方の感想などを見てから考えようというのが今のスタンスです。

Emacs 24(RC)のnox11でxterm-mouse-modeを使う

Emacs

Emacs24のリリース候補版(Release Candidate)がでました。http://alpha.gnu.org/gnu/emacs/pretest/
自分はEmacsでもホイールスクロールが使えるようにxterm-mouse-modeを使っていますが、Emacs24ではちょっとだけ挙動が変わったようで追加設定をしないと変になったので詳細をここにまとめておきます。

以下の設定でEmacs23でも24でも動作します。もちろんnox11(configure時に--without-xをつける)でも動作します。

;; xterm-mouse-mode
(unless (fboundp 'track-mouse)
  (defun track-mouse (e)))
(xterm-mouse-mode t)
(require 'mouse)
(require 'mwheel)
(mouse-wheel-mode t)

ついでにxterm-mouse-modeの宣伝をしておきます。
xterm-mouse-modeを使うことで一般的なエディタと同様に、

  • クリックでカーソルの移動
  • ホイールスクロール
  • ドラッグで範囲選択
  • 右ダブルクリックでなぜかカット

が可能になります。
puttyなどでEmacsを使っている場合、以前のペーストなどのマウス操作はシフトを押しながらで可能になります。
ただし、「Shiftがアプリケーションのマウス使用を無効にする」を有効にしている必要があります(おそらく)。
コーディング時には無くても良い機能だとは思いますが、ソースを眺めたりするときには便利だと思います。

LLVM 3.1 リリースノートの訳

LLVM

LLVM3.1が予定より一週間ほど遅れてリリースされました。
今回もいろいろなアップデートがあるのでLLVM 3.1 Release Notesを翻訳します。
訳がかなり怪しいところが一部あります。

イントロダクション

このドキュメントはLLVMコンパイラ基盤のリリース3.1に関するリリースノートです。前回のリリースからの大きな改善点, サブプロジェクトの改善点, コードの利用者などを含むLLVMの状況を記しています。LLVMリリースの全てはLLVMリリースサイトからダウンロードできます。

LLVMについての最新情報などの詳細はLLVMメインサイトを参照して下さい。疑問や感想などがありましたらLLVM開発者メーリングリストに投稿して下さい。

サブプロジェクトの更新状況

LLVM3.1ディストリビューションはLLVMのコアリポジトリ(最適化機構, コード生成器, サポートツールなど)とClangリポジトリで構成されています。更に、LLVMプロジェクトには開発中のサブプロジェクトを含んでいます。ここでは3つのサブプロジェクトの更新を記します。

Clang: C/C++/Objective-C Frontend Toolkit

ClangはC,C++,Objective-CのためのLLVMフロントエンドです。Clangはわかりやすい診断メッセージ, 言語標準規格に忠実, 高速かつメモリ使用量の少ないコンパイルという特徴を持ち、
より良いユーザ体験を提供することを目的としています。Clangはx86(32,64ビット),Darwin,ARM環境では、プロダクションで利用できる品質のC,C++,Objective-C,Objective-C++のコンパイラと考えられています。

LLVM3.1ではClangチームが大きな改善を果たしています。以下が主な変更点です。

Clangのリリース3.0からの変更点についての詳細はClangリリースノートを参照して下さい。もしClangで拒否しているコードが他のコンパイラでは採用されている場合、意図的なものではないかもしくは既知の問題点かどうか確認するために、言語互換性ガイドを参照して下さい。

DragonEgg: GCC front-ends, LLVM back-end

DragonEggはGCCの最適化機構とコード生成器をLLVMのものと取り替えるGCCプラグインです。GCC4.5, GCC4.6(部分的にGCC4.7)で動作し、Darwin, FreeBSD, KFreeBSD, LinuxそしてOpenBSD上でx86-32/x86-64とARMプロセッサファミリーをターゲットとして利用できます。Ada, C, C++そしてFortranを完全にサポートし、Go, Java, Obj-CそしてObj-C++は部分的なサポートをしています。

リリース3.1では主に次のような変更点があります。

  • GCC4.7の部分的なサポート。Adaサポートが不十分だがそれ以外の言語は正しく動作する。
  • ARMプロセッサのサポート。ARM向けにDragonEggをビルドするために必要とされるGCCヘッダのいくつかがGCCによってインストールされないため、動作させるにはGCCソースツリーから必要なヘッダをコピーする必要がある。
  • Fortranの最適化。Fortranのスカラ引数は'restrict'セマンティクスを持つことを利用している。
  • 全言語向けの最適化。type aliasingとtype rangesに関する情報をLLVM最適化機構に渡している。
  • リグレッションテスト(回帰テスト)スイートの追加。
compiler-rt: Compiler Runtime Library

LLVMの新しいプロジェクトであるcompiler-rtプロジェクトは、コード生成器や他の実行時コンポーネントで必要とされる低レベルでtarget-spcificなフックの実装を提供するシンプルなライブラリです。例えば、32ビットターゲット向けにコンパイル時に、double型から64ビット符号無し整数への変換は"__fixunsdfdi"関数の実行時呼び出しへコンパイルされる。compiler-rtライブラリは高度に最適化されたこれらの実装および他の低レベルルーチン(libgccよりも3倍速い)を提供する。

3.1ではcompiler-rtは、任意サイズの量に対するatomic操作を許可するatomic操作のヘルパ関数を含んでいる。これらの関数はgccで定義された仕様に従い、clangで利用される。

LLDB: Low Level Debugger

LLDBはコマンドラインデバッガの基礎からの実装であり、他のアプリケーションから利用されるデバッガAPIです。LLDBは(特にC++向けの)忠実な式解析(expression parsing)を提供するためにClangの解析器を利用しており、ターゲットサポートのためにLLVM JITを利用している。

libc++: C++ Standard Library

compiler-rtと同様、libc++は更に寛容的に利用できるようにMITとUIUCのデュアルライセンスを採用している。LLVM3.1では次の見所がある。

  • compiler-rtでできたサポートコードをclangでコンパイル時に、ヘッダが全てのテストが通った。
  • FreeBSDが基盤システムの一部としてlibc++を含んでいる。
  • libc++がSolarisに移植され、libcxxrtとclangの組み合わせが既存コードの大部分で動作している。
VMKit

VMKitプロジェクトは静的もしくはjust-in-timeコンパイラとしてLLVM利用して、Java Virtual Machine(Java VM or JVM)を実装するものです。

LLVM3.1では、VMKitは実行速度と起動速度の両方で大きな改善を行った。

Polly: Polyhedral Optimizer

Pollyはデータ局所性と並列性のだめの実験的な最適化機構です。現在、高レベルなループ最適化と(OpenMPランタイムを利用した)自動並列化を提供している。自動SIMD化とアクセラレータコード生成のあたりはまだ始まったばかりです。

LLVM3.1では次の見所がある。

  • PollyがLLVMの公式プロジェクトになった。
  • Pollyがclangに直接ロードできるようになった。('-O3 -mllvm -polly'で有効化)
  • 自動スケジュール最適化(Pluto由来の)が統合された。この最適化ではデータ局所性と並列性のためのループ変換を行う。ループ変換に含まれているものとしては、interchange, fusion, fission, skewingそしてtilingなどがあります。

LLVM3.1を利用している外部のオープンソースプロジェクト

LLVMの興味深い点として、多くの言語やツールのプロジェクトで何かを実現する(実現技術)ために使われていることです。この節ではLLVM3.1とともに既に更新されているプロジェクトの一部を挙げる。

Crack

Crackはコンパイル言語のパフォーマンスをもったスクリプト言語を容易に開発できるようにすることを目的としている。Crackの言語自体はC++, Java, Pythonからコンセプトを得て、オブジェクト指向や演算子オーバーロード,強い型付けを取り入れたものです。

FAUST

FAUSTはリアルタイム音声信号処理のためのコンパイル言語です。FAUSTはFunctional AUdio STreamを表す。プログラミングモデルは関数型プログラミングとブロック図構成(block diagram composition)の2つのアプローチを結合させたものです。C, C++, Java, JavaScriptのアウトプットに加えて、LLVM2.7から3.1で動作するLLVMビットコードを生成できる。

Glasgow Haskell Compiler (GHC)

GHCは遅延評価関数型プログラミング言語であるHaskellのオープンソースのコンパイラおよびプログラミングスイートです。様々なプラットフォーム向けに最適化されたコードを生成する静的コンパイラや開発時用のインタラクティブなシステムを含んでいる。GHC7.0以降はLLVM2.8以降をサポートしたLLVMコード生成器を含んでいる。

Julia

Juliaは技術計算向け高レベル高性能の動的言語です。洗練されたコンパイラ、分散並列処理、数値精度、豊富な数値演算ライブラリを提供する。コンパイラでは型推論を用いて型宣言無しで高速なコードを生成しており、LLVMの最適化パスやJITコンパイラも利用している。Julia言語は複数ディスパッチやプログラムに大幅な柔軟性を与えるように設計されている。多くの問題に利用可能です。

LLVM D Compiler

LLVM D Compiler(LDC)はD言語用のコンパイラです。DMDフロントエンドに基づいてLLVMをバックエンドとして利用している。

Open Shading Language

Open Shading Language(OSL)はプログラマブルなシェーディング向けの小さいが高機能な言語です。先進的なグローバルイルミネーションレンダラーや他のアプリケーションで利用され、物質, 照明, 転移, パターン生成の表現に適している。実行時に複雑なシェーダネットワークをx86コードにJIT変換するためにLLVMを利用している。

Portable OpenCL (pocl)

簡単で移植性のあるオープンソースのOpenCL実装の実現に加えて、poclのもう1つの主な目的は、コンパイラの最適化を利用しターゲットに依存した手動最適化の必要性を減らすことで、
OpenCLプログラムの性能の移植性を改善することです。poclの重要な部分は、カーネルコンパイラを用いて静的に複数の仕事に並列化させるために使われるLLVMパスの集合です。これによって複数の方法(SIMD, VLIW, superscalarなど)でワークグループの静的な細流度並列化が可能になる。

Pure

Pureはterm rewritingを基にした代数/関数型プログラミング言語です。プログラムはsymbolic fashionで式を評価するのに利用される方程式の集合です。インタプリタはPureプログラムを高速なネイティブコードにJITコンパイルするためにLLVMをバックエンドとして利用している。Pureは動的型付け, 先行評価と遅延評価, レキシカルクロージャ, 衛生的なマクロシステム(term rewritingを基にしたもの), 組み込みのリストと行列のサポート, そしてCや他のプログラミング言語への使いやすいインタフェース(LLVMビットコードモジュールのロードや対応するLLVMコンパイラが利用可能であればPureプログラム内にC, C++, Fortran, Faustコードのインライン記述が可能)

Pureバージョン0.54はテストされてLLVM3.1で動作するようになった。また、LLVMリリース2.5以降の古いバージョンでも動作するように開発している。

TTA-based Co-design Environment (TCE)

TCEはTransport triggered architecture(TTA)を基にしたApplication-specificプロセッサ(ASP)をデザインするためのツールセットです。このツールセットではC/C++プログラムから下は合成可能なVHDL/Verilogや並列プログラムのバイナリまでの完全な共創(co-design)フローを提供する。プロセッサの設定可能な項目としてはレジスタファイルや機能ユニット, サポート操作, 相互接続ネットワークが含まれる。

LLVM 3.1の変更点

このリリースには大量のバグフィックス、性能修正そして細かい改善点を含んでいます。この節ではいくつかの主な改善点と新機能を挙げています。

主な新機能

LLVM3.1はいくつかの主な変更天と大きな新機能があります。

LLVM IR(中間表現)とコアの改善点

LLVM IRは新しいターゲットのより良いサポートのためにいくつかの新機能があり、それによって新たな最適化が可能になります。

  • 16ビットの半精度浮動小数点の追加。
  • 中間表現がベクタGEPを含むポインタのベクタをサポート。
  • モジュールフラグが導入された。モジュールに関する情報がまとめてLLVMのサブシステムに渡されます。今のところObjective-CのABI情報をエンコードするために利用されています。
  • ロードされる可能性がある値を表現するために、ロードは添付されたメタデータの範囲を持つ。
  • llvm.ctlzとllvm.cttz命令は追加引数を持つようになった。この引数によってゼロ入力のときに命令の振る舞いが未定義になるかどうか決まる。これは0のビットを数えるときに型サイズを返さない命令を持つプラットフォームにおいて更に最適化されたコードを生成するために利用される。
最適化機構の改善点

多くの細かい性能修正とバグフィックスに加えて、このリリースでは最適化機構に対する細かい強化と追加が少し含まれている。

  • ループアンロールパスで実行時にループ回数をカウントしながらループをアンロール可能に。この機能はデフォルトで無効化されており、-unroll-runtimeフラグで有効化できる。
  • 基本ブロック自動ベクトル化パスが利用可能に。このパスを実行するには、-vectorizeオプションを関連するpost-vectorization cleanupパスとともに渡すこと。詳細な情報はEuroLLVM2012のスライド(Autovectorization with LLVM)を参照して下さい。
  • インラインのコストヒューリスティックが完全に整備され、関数呼び出しを通した定数伝播や自明なデッドコードコストの無視、そしてC++ STLのイテレータパターンの厳密なモデル化が可能に。
MCレベルの改善点

LLVMマシンコード(MC)サブシステムはアセンブリ, ディスアセンブリ, オブジェクトファイルフォーマットの扱いなどやCPUの命令セットレベルのツールに関連する数多くの問題を解決するため作られた。詳細な情報はIntro to the LLVM MC Project Blog Postを参照してください。

  • アセンブリファイル(.s)をアセンブル時に統合アセンブラがオプションでデバッグ情報を出力できるようになった。これはllvm-mcに-gオプションを渡すことで有効化できる。
ターゲット独自のコード生成器の改善点

Type Legalizerがベクタを認証する方法を変更した。今後はType Legalizerは整数要素を昇格しようとする。これによりvector-selectの実装が可能になった。更に、charやshortのベクタを使うような場面では、SIMD命令が有効な32ビット型として昇格されるため、性能が大きく改善されたことを確認した。浮動小数点型は従来通り拡張される。

コード生成器の基盤に著しい改良を行った。その結果、更に積極的なアルゴリズムの実装が可能になり、速度が向上した。

  • TableGenは、制約の組み合わせを表すためだけに使われるレジスタクラスを命令とサブレジスタから合成することができるようになった。合成レジスタクラスは直近のユーザ定義の親クラスから性質を継承するようになった。
  • MachineRegisterInfoは、レジスタ割り当ての開始時に予約レジスタの固定をできるようにした。
  • MachineOperandの新しい種類は命令呼び出しで破壊されるレジスタ(clobber)の一覧をコンパクトな表現で提供する。レジスタマスクオペランドは保存されたレジスタのビットマスクで参照し、それ以外は破壊されている。
  • name accelerator tables DWARF extensionのためのデータ出力がサポートされた。これは名前参照の高速化のためにLLDBで使われている。

Very Long Instruction Word(VLIW)アーキテクチャ用のビルドをサポートするためにTableGen基盤を追加した。TableGenは、命令群を束にできるかどうかを定義したVLIWターゲットのスケジュール記述から決定性有限オートマトン(DFA)を自動生成する。

マシン命令をまとめるためのDFA基盤を基にしたターゲット非依存の新しいVLIW packetizer(パケット化)を追加した。

基本ブロック配置

確率を基にしたブロック配置とコードレイアウトアルゴリズムがLLVMのコード生成器に追加された。レイアウトパスは__builtin_expectのようなソースコードアノテーションと同様の静的ヒューリスティックスから算出される確率をサポートする。

X86-32とX86-64ターゲットの改善点

X86ターゲットにおける新しい特徴と主な変更点は以下の通りです。

  • AVX2サポートの大きな改善
  • AVX1の改善と大量のバグ修正
  • FMA4とXOP命令セット拡張のサポート
  • 高速なコンパイルと異なる呼び出し規約サポートのためにCall命令はレジスタマスクオペランドを利用する
  • DW2例外ハンドリングがCygwinとMinGWで有効化
  • MSVCランタイムで使われる暗黙的TLSモデルのサポート
ARMターゲットの改善点

ARMターゲットの新機能は以下の通りです。

  • constant islandパスは基本ブロックとconstant pool entryの4バイト以上のアラインメントをサポート
  • DarwinにおいてARMターゲットのフル機能の統合アセンブラが対応
ARM統合アセンブラ

clang向けの直接オブジェクト化モジュールを含む、ARMターゲットのフル機能のマクロアセンブラが対応された。アセンブラはDarwinでのみデフォルトで有効化されており、Linuxではテストやプラットフォーム特有の追加サポートが未解決です(訳自信無し)。

Thumb1, Thumb2とARMモードが完全サポートされており、サブターゲットと特定CPU拡張としてはVFP2, VFP3とNEONがサポートされている。

アセンブラはUnified Syntax(詳細はARM Architecural Reference Manualを参照)のみが使える。いくつか発展途上のサポートされているpre-unfied(divided) syntaxあるが、未だサポートと大きな差がある。

MIPSターゲットの改善点

MIPSターゲットにおける新機能と主な変更点は以下の通りです。

  • MIPS32リトルエンディアンの直接オブジェクトコード出力が実用的に
  • long double型(f128)の例外ハンドリング付きのアセンブリ出力(assembly printing)モードにおいて、N64 ABI向けのMIPS64リトルエンディアンのコード生成器がかなり実用的に
  • 新命令に対するサポートが追加。swap-bytes命令(WSBHとDSBH)、浮動小数点のmultiply-add/subtractと負数のmultiply-add/subtract命令、レジスタ+レジスタアドレッシング付きの浮動小数点load/store命令(LWXC1)など。
  • 性能を改善するいくつかの修正
  • Post-RAスケジューリングが-O3オプションで有効化
  • soft-floatのコード生成のサポートが追加
  • MIPS64ビットターゲット向けのclangドライバがサポート
  • clangにおけるMIPS浮動小数点ABIオプションのサポート
PTXターゲットの改善点

極めて目立った条件的逆転(conditional inversion)のバグ修正がこのリリースに含まれています。

注意: LLVM3.1は現時点のものをPTXバックエンドの最後のリリースとしている。PTXバックエンドは現在NVPTXバックエンドに置き換えられている途中であり、SVNにある。

他のターゲット特有の改善点
  • QualcommのHexagon VLIWプロセッサのサポートが追加
主な変更点と削除された機能

あなたが既にLLVM3.1の変更点の一部を利用しているLLVMのユーザか開発者なら、この節ではいくつか既知の情報を挙げている。

  • LLVMのビルドシステムはビルド時にpython2インタプリタを必要とする。Perlインタプリタはもはや必要とされない。
  • Cバックエンドは削除された。いくつかの重要なプログラムがコンパイルできないという問題点があったためです。
  • Alpha, Blackfin, SystemZターゲットがメンテナンスが不十分なため削除されました。
  • LLVM3.1はLLVM2.9のビットコードファイルを読み込みのサポートを削除しました。将来はLLVMの未来の全てのバージョン向けに、LLVM3.0以降で生成されたビットコードファイルと.llファイルを読むことを目指す。
  • unwind命令が無くなりました。LLVM3.0では新しい例外ハンドリングシステムの命令があるため、unwind命令は廃止されました。
  • LLVM3.0とそれ以前は名前に応じてsetjmpのような関数に対してreturns_twiceを自動的に追加していました。この機能は3.1では削除されました。-ffreestandingオプションが使われると有効になります。
内部APIの変更点

多くのAPIがこのリリースで変更されました。以下がLLVM APIの主な変更点の一部です。

  • 新しいTargetOptionsクラスではターゲット特有のオプションがグローバル変数からメンバ変数に移動されました。結果として、関連するフラグがclangの-mllvmオプションによって対応されなくなりました。
    • llvm::PrintMachineCode
    • llvm::NoFramePointerElim
    • llvm::NoFramePointerElimNonLeaf
    • llvm::DisableFramePointerElim(const MachineFunction &)
    • llvm::LessPreciseFPMADOption
    • llvm::LessPrecideFPMAD()
    • llvm::NoExcessFPPrecision
    • llvm::UnsafeFPMath
    • llvm::NoInfsFPMath
    • llvm::NoNaNsFPMath
    • llvm::HonorSignDependentRoundingFPMathOption
    • llvm::HonorSignDependentRoundingFPMath()
    • llvm::UseSoftFloat
    • llvm::FloatABIType
    • llvm::NoZerosInBSS
    • llvm::JITExceptionHandling
    • llvm::JITEmitDebugInfo
    • llvm::JITEmitDebugInfoToDisk
    • llvm::GuaranteedTailCallOpt
    • llvm::StackAlignmentOverride
    • llvm::RealignStack
    • llvm::DisableJumpTables
    • llvm::EnableFastISel
    • llvm::getTrapFunctionName()
    • llvm::EnableSegmentedStacks
  • MDBuilderクラスがメタデータの生成を簡易化するために追加されました。
ツールの変更点

いくつかのツールがこのリリースで変更されました。変更点の一部は以下の通りです。

  • llvm-stressは異なるLLVMコンポーネントを覆うためにランダムで.llファイルを生成するためのコマンドラインツールです。
  • llvm-ldツールが削除されました。clangドライバが複数のビットコードファイルをバイナリに変換するためのより信頼できる方法を提供します。ビットコードファイルをマージするにはllvm-linkが利用できます。
Pythonバインディング

公式にサポートされたPythonバインディングが追加されました。完全な機能のサポートはまだまだです。現在のバインディングでサポートしているインタフェースは以下の通りです。

  • オブジェクトファイルインタフェース
  • ディスアセンブラ

オブジェクトファイルインタフェースを使うことで、バイナリオブジェクトファイルを検査することができます。readelfやllvm-objdumpのpython版だと思って下さい。

追加機能のサポートはコミュニティ貢献者によって現在開発中です。Pythonバインディングの方向性に興味がある方は、IRCか開発者MLで意志を表明して下さい。

既知の問題点

ほとんどの場合、LLVMはプロダクション品質のコンパイラであり、幅広いアプリケーションで使われて多くの製品を輩出しています。全てのサブシステムが総体として成熟しているとは言えません(特にマイナーなターゲットにおいては)。もし問題に遭遇した場合は、LLVMバグデータベースをチェックし、既知でない場合はバグを提出するかLLVM開発者MLで質問してください。

既知の問題点としては以下の通りです。

  • CellSPU, MSP430, PTXそしてXCoreバックエンドは実験的な段階です。
  • 統合アセンブラ, ディスアセンブラそしてJITはいくつかのターゲットではサポートされていません。統合アセンブラがサポートされていない場合、システムアセンブラが必要とされています。詳細はTarget Features Matrixを参照して下さい。

追加情報

LLVMウェブページ、特にドキュメントでは様々な追加情報が利用できます。ウェブページにはSubversionにある最新のコードのAPIドキュメントもあります。LLVMツリーの"llvm/doc/"ディレクトリに行くと特定のリリースに対するドキュメントが取得可能です。

LLVMに関する質問やコメント等がありましたらメーリングリストを通してお気軽にご連絡下さい。

putty上のEmacsのkill-ringとWindowsのクリップボードを同期する

Emacs

puttyでサーバにアクセスしてEmacsを使っているとどうしても不便なのはクリップボードにコピーしにくいことです。
マウスでドラッグすればコピーできますが、画面分割しているとうまくできずにいらっとします。
Emacsに慣れるとクリップボードに入れるつもりで自然にM-wしてしまうこともよくあります。

puttyの機能を調べていたらputtyからWindowsクリップボードを操作する方法(puttyclip)があることを発見！
これを使ってEmacsのkill-ringとWindowsのクリップボードを同期*1させます。

用意するもの

シェルスクリプト(winclip)

#!/bin/sh
OUT=$SSH_TTY
echo -n "\033[5i" > $OUT
cat $* | sed 's/\x1B\[\([0-9]\)\{0,2\}m//g' | nkf -Lu -s > $OUT
echo -n "\033[4i" > $OUT

puttyclipにあるwinclipに少し変更を加えています。パスを通すか.emacsでフルパスで設定してください。

  • 標準出力ではなく$SSH_TTYに出力しているのはEmacsから標準出力に出すとバッファ出力になってしまうためです*2
  • sedはANSIエスケープシーケンスを削除しています
  • nkfは-sでS-JISで出力しています。-LuでUnix改行コードとなっているのはputtyが勝手に改行コードを変更してくれているようなので。

.emacsの設定

(defun putty-windows-select-text (text &optional push)
  (with-temp-buffer
    (insert text)
    (when (executable-find "winclip")
      (call-process-region (point-min) (point-max) "winclip" nil nil))
    ))
(setq interprogram-cut-function 'putty-windows-select-text)

winclipにクリップボードに送る機能があるのでEmacsからはほぼ実行するだけです。

  • interprogram-cut-functionに関数をセットするとkill-ringの内容をとれます
    • 逆にinterprogram-paste-functionというのもあります
  • 処理内容としては一時バッファにテキストをはき出してからcall-process-regionでバッファの内容を入力としてwinclipを実行しています
    • start-processをつかってパイプで流す方法もありますが、それだとEmacsのメッセージまでクリップボードに入ってしまいます
  • putty clipboard patchが適用されていないputtyでこれを使うとひどいことになります

使ってみる

puttyの設定でTerminal(端末)のRemote-controlled printing(遠隔操作の印刷)でWindows clipboardを選択して起動します。

コマンドラインからwinclipを通してクリップボードに入るか確認します。
文字化けとかエスケープシーケンスが残ってたら、適当にwinclipを修正してください。

$ ls -l | winclip

あとはEmacsを起動してM-wやC-kでkill-ringの内容とクリップボードを確認してみてください！

その他

参考

*1:タイトルは同期としてますが、実際にはEmacs=>Windows方向のみです。インタフェースさえあれば双方向にもできます。

*2:他に良い方法があれば教えて下さい

MIPSのアドレス変換周り(TLB)の処理をまとめてみた

MIPS OS

1年ほど前にTLB(Translation Look-aside Buffer)を使ったアドレス変換処理を実装したのだけど、もう一回実装しようと思ったらあまり覚えてなかったのでまとめておくことにしました。
See MIPS Runを参考にしました。間違っているところがあればご連絡ください。

アドレス変換とは

通常プログラムで扱うアドレスは仮想アドレス(Virtual Address)と呼ばれ、(32bitマシンでは)32bitのアドレスを自由に使えます。しかし、実際のデータは物理メモリ上のどこかに格納されています。物理メモリ上の位置を示すものが物理アドレス(Phisical Address)と呼ばれます。
データにアクセスするためには仮想アドレスから物理アドレスに変換する必要があり、この処理をアドレス変換と呼びます。

単純な実装では、仮想アドレス = 物理アドレスとすることも可能です。しかし、物理メモリサイズ以上のプログラムを動かすことができなくなります。アドレス変換があることにより、少ない物理メモリ上で大量のメモリを使用するプログラムを実行することが可能になります。

基本的な仕組み

アドレス変換の基本的な仕組みは、仮想アドレスと物理アドレスの対応表を持っておき、それを利用するというものです。1アドレス毎に対応を持つと表の量が莫大になってしまうので、どれくらいの粒度で対応表を持つかというのが、ページサイズになります。32bit環境では通常、ページサイズは4KBなことが多いです。ページ毎の対応表のことをページテーブルと呼びます。

ページテーブルは基本的にはメモリ上に保持しておき、変換が必要なときに参照するということになります。しかし、プログラムを実行するときには必ずアドレス変換が必要なため、1サイクル毎にメモリにアクセスすることは非常に大きなボトルネックとなります。

毎回ページテーブルを参照するのが嫌なら対応を覚えておけば良いよねということで、ページテーブルのキャッシュのことをTLB(Translation Look-aside Buffer)と呼びます。CPUはまずTLBに欲しい情報があるかを探し、あればメモリアクセスすること無くアドレス変換が可能になります。

現在のプロセッサではどのような形であれTLBを持っているため、
アドレス変換がうまくできるようにするために、ページテーブルとTLBの管理がOSのお仕事になります。
TLBを管理する方法はプロセッサによって異なります。x86ではページテーブルのアドレスを指定する程度になりますが、MIPSではTLBの入れ替えなども全てOSで行う必要があります。

MIPSのアドレス変換の流れ


まず、アドレス変換の対照となる仮想アドレスは上位20bitsをVPN(Virtual Page Number)と呼び、下位12bitsをページ内オフセット(図ではIn-page address)などと呼びます。
その他に関連する情報として、現在のプロセスがどのアドレス空間に所属しているかを示す、ASID(Address Space Identifer)があります。ASIDは後に詳細を述べますが、EntryHiレジスタの下位8bitsになります。

VPNとASIDを用いて、TLBエントリと比較します。TLBエントリは1つのEntryHiと2つのEntryLoの複数セットからなり、VPN上位19bitsとASIDから対応するEntryHiを1つ探しだし、VPNの下位1bitでEntryLoを選びます。
有効なEntryLoが見つかった場合はTLBヒットとなり、EntryLoからPFN(Physical Frame Number)を得ることができます。
TLBミスの条件やTLBミス時の動作についての詳細は後で述べます。
PFNを得たら、仮想アドレスのVPNの部分をPFNに丸ごと取り替えた値が物理アドレスとなります。

TLBに関連するレジスタ

EntryHi
  • ASIDは現在のプロセスが属するアドレス空間を示す
  • VPN2は仮想アドレスの上位アドレス(ページサイズより上位)
  • なぜ2がついているかというとEntryHiに対応するEntryLoがペアになっているため
  • TLB命令を使った場合、EntryHiが変わる(ASIDが変わる)ため操作後に戻さないといけない
EntryLo
  • PFNはVPNに対応する物理アドレス
  • なぜ定義上でPFNよりbits数が多いのか謎
  • Cはキャッシュ設定。プロセッサによってライトスルー、キャッシュしないなどの設定を可
  • Dは書き込み可能かどうか。0で書き込みをすると例外(TLB Modified Exception)が発生する。初期状態で0にしておき、書き込みが起きたときに1にすることによってダーティかどうか判定できるようにする。
  • Vは有効なTLBかどうか。0の時に参照すると例外(TLB Invalid Exception)が発生する。無効化するときに0にする。
  • Gが1だとASIDを無視する。複数のプロセスで共有したい場合に1にする。
PageMask
  • ページサイズを決めるためのレジスタ
  • Maskのうち1になっている部分が無視される。
  • 定義で下位ビットが0になってる部分を1にして仮想アドレスとのandを取るとin-page addressになる。
Index
  • TLB命令で操作するTLBエントリを指定する
  • tlbp命令で結果をIndexに反映する。31bitが1だと失敗した(見つからなかった)ことを意味する。
Random
  • tlbwr命令で操作するTLBエントリを指定する
  • 1サイクル毎にカウントダウンする。Wiredレジスタの値より小さくならない。
  • TLBエントリの入れ替えは基本的にランダムで行う方針らしい
Wired
  • Randomレジスタが指定しない範囲を示す。TLBエントリの0からWired-1を指さなくなる。
  • TLBエントリを固定で使用したい場合に利用する。
Context
  • TLBの入れ替え(TLB Refill)を高速に行うためのレジスタ
  • PTEBaseに任意の値を入れておく。通常、ページテーブルのアドレスを入れておく。
  • BadVPN2はTLB Refill例外が発生したアドレス(BadVaddr)の上位19bits。
  • PTEBaseをうまくセットすることにより、例外時にContextのアドレスに欲しいTLBエントリが格納されているアドレスを参照できるため、高速にTLB入れ換えが可能になる。
XContext
  • 64bit用のContext
  • 32bitを対象にしているため説明しません
BadVAddr
  • TLBの例外が起きたアドレス

TLB操作命令

tlbr命令
  • Indexで指定したTLBエントリをEntryHiとEntryLo0,EntryLo1レジスタに読み込む
tlbw命令
  • Indexで指定したTLBエントリにEntryHiとEntryLo0,EntryLo1レジスタの内容を書き込む
tlbwi命令
  • Randomで指定したTLBエントリにEntryHiとEntryLo0,EntryLo1レジスタの内容を書き込む
tlbp命令
  • IndexにEntryHiレジスタにマッチするTLBエントリの番号を読み込む

TLB例外

TLB Refill Exception

対応するTLBエントリが見つからなかった。tlbwr命令などでTLBの入れ換えが必要。
TLB Refill例外のみ、専用の(例外処理の)エントリポイントが存在する。
ただし、例外処理中にTLB Refill例外が発生した場合(Nested TLB Refill例外)、汎用のエントリポイントに飛ぶ。

TLB Invalid Exception

TLBエントリは見つかったが無効化されている。tlbwr命令などでTLBの入れ換えが必要。
汎用の(例外処理の)エントリポイントに飛ぶ。

TLB Modified Exception

TLBエントリが見つかったが書き込みできない(D=0)。D=1に更新する。
汎用の(例外処理の)エントリポイントに飛ぶ。

TLBエントリの管理の例

Contextレジスタを最大限利用する場合、各ASID毎のページテーブルを4MB境界(PTEBaseが23bitからだから)で配置すると良い。
4MB境界で配置し、PTEBaseに上位ビットをセットしておくと、例外発生時にContextレジスタが入れ換えたいEntryLoが格納されているアドレスを指している状態になる。
よって、TLB Refill例外の処理は以下のように非常にシンプルになる。
(See MIPS Runから転載しました。)

TLBmiss32:
   mfc0    k1, C0_CONTEXT
   lw      k0, 0(k1)
   lw      k1, 8(k1)
   mtc0    k0, C0_CONTEXT
   mtc0    k1, C0_CONTEXT
   ehb
   tlbwr
   eret

この管理方法の問題点は、4MB境界という広い領域をどうやって確保するかという点にある。
1ASID毎に4MBということは、256ASIDで1GBになってしまう。
実際には4MBのページテーブルを作成したとしても使われる範囲はごくわずかであるため無駄が大きい。

そこで、ページテーブル自体を仮想アドレスに配置する。
仮想アドレスに配置することで、実際に4MBのページテーブルを作成したとしても使われない領域に物理メモリが使われなくなる。

物理メモリ上に直接ページテーブルを作成した場合には常にページテーブルを参照することができたが、
仮想アドレス上に配置した場合にはアドレス変換が必要になるため、
ページテーブルがあるアドレスのTLBエントリが無いという場合がありうる。
上記のサンプルコードの3,4行目のロード時に発生する可能性がある。
これはNested TLB Refill Exception(専用の名前があるわけではないのでネスト例外とでも呼ぶ)と呼ばれ、特別な例外処理となる。

ネスト例外は通常のTLB Refill Exceptionとは異なる汎用的な例外処理エントリポイントで処理される。
つまり、他の例外と同様に、Causeレジスタで例外発生理由を判断し、BadVAddrレジスタで例外が発生したアドレスを得て処理をする必要がある。
ネスト例外と通常の例外処理とが異なる点は、
EPC(例外処理が終わったあと戻る場所)の位置がネスト例外が発生した場所ではなく、最初に例外が発生した場所になることである。
ネスト例外を処理後、eret命令により例外発生前の場所に戻ろうとすると、TLBmiss32のロード命令の場所ではなく、ユーザプログラムまで戻ることになる。
ユーザプログラムに処理が戻ってもユーザプログラムが必要としているTLBに関しては処理されていないため、再びTLB Refill例外が発生する。
しかし、2回目の例外処理ではTLBmiss32でネスト例外が発生することなく処理が完了する。

(1回目)ユーザプログラムでload==(TLB Refill例外)==>TLBmiss32でload==(ネスト例外)==>汎用例外処理==>eret==>ユーザプログラム
(2回目)ユーザプログラムでload==(TLB Refill例外)==>TlBmiss32でload(例外発生せず)==>eret==>ユーザプログラム

このようにして仮想アドレス上にページテーブルを配置した場合でも問題なくTLBの入れ換え処理を行うことが可能である。
仮想アドレス上に配置することで、Contextレジスタを利用した高速なTLB Refill例外処理を実現しながら
領域を節約した実装が可能になる。