Meets Jack and Jill

Experimental New Android Tool Chain - Jack and Jill
http://tools.android.com/tech-docs/jackandjill

Google が開発した新しい Android Tool Chain について続報が無く気になっていたのでリポジトリの観測情報と
ソースコードを読みながら現状をまとめてみました。
今後 Jack and Jill が正式に採用されるのかは未定です。

本内容について、勘違い、妄想、白昼夢と思われる箇所がありましたら、ご指摘いただけると幸いです。

コチラも参考にしました!
[Jack and Jill Compiler](https://speakerdeck.com/wasabeef/jack-and-jill-compiler)

# Jack and Jill って何?
Google が開発している新しい Android アプリの Toolchain(コンパイラやアセンブラ、リンカなどの一式）の呼称。
正式名称なのか、暫定名称なのかは不明。特に言及はされていない。

## Jack って?
新しいコンパイラの名称。Java Android Compiler Kit のアクロニウム。
Java ソースから .class(bytecode) を経由せずに DEX までコンパイルを行うのが特徴。
従来のコンパイルに比べて高速らしいが、今のところ体感的に「早いなー」とは思えない。

コレを書いてる時点では Jack について技術的な解説はないので詳細を知りたいなら Jack を読み解く以外には無い。

## Jill って?
新しいリンカの名称。Jack Intermediate Library Linker のアクロニウム。
jar,aac を含め Library Module を Jack で扱える独自の形式に変換するなどの処理を行う。
Jack で扱う独自の形式というのが「.jayce」と呼ばれる拡張子のファイル。

## Jack and Jill 概要
Jack が java ソースを dex に変換し、Jill が結合するライブラリを jayce に変換して、最後に Jack が APK形式にパッキングする。
難読が必要な場合は Jack が行う。
![alt](http://tools.android.com/_/rsrc/1418321714624/tech-docs/jackandjill/JackSitesDiagram.gif)


# 使い方
Android Studio では既に Jack and Jill は Jack.jar と Jill.jar と言う形で収められている。
[コチラ](http://tools.android.com/tech-docs/jackandjill)によると Gradle の設定の以下の記述を加える。

      useJack = true

# リポジトリ
Jack,Jill 共にブランチ上で開発が行われており master には何もコミットされていない。

* https://android.googlesource.com/toolchain/jack
* https://android.googlesource.com/toolchain/Jill

コミットログを見ると、開発当初からブランチに移行している。
リポジトリの構成は以下のとおり。

* master(一年以上たっても何もない)
* ub-jack(開発のメイン)
* ub-jack-arzon（最初にリリースされた Jack and Jill の開発ブランチ）
* ub-jack-brest（現在リリースされたてる Jack and Jill の開発ブランチ）
* ub-jack-dev-lang（Java8 対応などが行われている開発ブランチ）

この arzon や brest についてはあくまで推測にすぎないが Jack の実装内のコード内のコメントに、それらがリリースネームであることを示唆するコメントを見つけることが出来る。

```lang:JackProvider.java  
 /**
   * Gives the release name of this Jack compiler (e.g. Arzon, Brest, ...).
   *
   * @return the release name
   */
  @Nonnull
  String getCompilerReleaseName();
```

# 構造
フォルダ構造から以下のようなモジュールに分かれる。

* Jack-API(コマンドラインオプションなどを処理するフロントエンド）
* Jack-Server(API 部分との対話を行うインターフェースとJack のコンパイルプロセスを制御）
* Jack(コンパイラ)

# Jack and Jill のコンパイルに利用されるライブラリ

* ecj-jack
* guava-jack
* jsr305lib-jack
* dx-jack
* schedlib
* freemarker-jack
* watchmaker-jack
* maths-jack
* args4j-jack
* antlr-runtime-jack

###### ecj-jack
URL: http://download.eclipse.org/eclipse/downloads/drops4/S-4.5M1-201408062000/ 
Tag: I20140806-2000, jdt 4.5M1, ecj version 3.11.0.v20140806-1653

###### guava-jack
URL: http://code.google.com/p/guava-libraries/wiki/Release13
Tag: v13.0.1

###### jsr305lib-jack
URL: http://code.google.com/p/jsr-305/ 
Version: r49

###### dx-jack
これは dexlib とは別物で internal で開発されたライブラリの一部を使っているらしい。
URL: internal
Tag: 1.7 (commit 725531e58b3823e21f8350d718a2e600edd1b088)

###### schedlib
readme によると下記の通り。

> Some files of this project come from GWT as described:
> - com.android.sched.util.collect.* come from com.google.gwt.dev.util.collect
> - com.android.sched.util.json.* come from com.google.gwt.dev.json
> - com.android.sched.util.log and com.android.sched.util.log.speedtracer:
> Event, EvenType, Tracer, Format, SpeedTracer, SpeedTracerEventType was created with fragment of com.google.gwt.dev.util.log.speedtracer.*

###### freemarker-jack
URL: http://freemarker.org/ 
Tag: 2.3.19 (SVN revision 1657)

###### watchmaker
URL: http://watchmaker.uncommons.org/ 
Version: 0.7.1

###### maths
URL: http://watchmaker.uncommons.org/ 
Version: 0.7.1

###### args4j
URL: https://github.com/kohsuke/args4j 
Version: args4j-site-2.0.30

###### antlr-runtime
URL: https://github.com/antlr/antlr3/tree/antlr-3.4 
Tag: antlr-3.4

# 処理の流れ
* ビルドのためのコンフィグレーションを設定
    * 環境変数やコマンドラインパラメータから抽出・解析
* コンフィグレーションからビルドプランを決定
    * Jack と Jill 両方のビルドプランが決定される
* Jack and Jill を実行
    * Jack はターゲットモジュールを処理し apk の作成前にライブラリなどを Jill に処理してもらう
    * Jill の処理結果は .jayce として出力されコンパイル済みの中間コードとして Jack が処理する。
* APK を出力

# Jack はどんなコンパイラなの?

現時点では特に情報は出ていません。
コードを読むしかりませんが、事前準備として、そもそもコンパイラについて明るいわけではないので一般に呼ばれるコンパイラとは? という部分の視線がぶれないために Wikipedia から拾ってみた。

## コンパイラ

http://ja.wikipedia.org/wiki/コンパイラ
> コンパイラ（compiler）とは、プログラミング言語で書かれた、プログラムのソースコード（原始コード）を、機械語、ないしバイトコードなどの中間言語によるオブジェクトコード（目的コード）に翻訳(変換)するプログラムである。コンパイラによる翻訳(変換)工程をコンパイル(翻訳)と呼ぶ（ビルドと呼んでいるツール等もある。厳密にはコンパイルはビルドの一工程である）。直接バイナリを出力するものもあるが、コンパイラ自身はアセンブリ言語によるコード（アセンブリ ソース）を出力し、さらにアセンブラを呼んでいるものも多い。コンパイラー(Compiler)という名称は日本語では、翻訳者という意味を持ち、ソフトウェアとしてのコンパイラーは翻訳機という意味を持っている。

さらに Android ではプログラミング言語が Java なのでコチラも。
http://ja.wikipedia.org/wiki/Javaコンパイラ
> JavaコンパイラとはJavaのソースコードをJavaクラスファイルに翻訳（コンパイル）するコンピュータプログラムのことである。

確かに Jack の処理の流れから考えると Jack は 「javac + バイトコードのDEXファイルコンバータ」であると考えられます。

* Java ソースコード
* Jayce ファイル（中間コード)
* DEX ファイル（アセンブリソース）

DEX は Dalvik や ART といった VM で実行されるアセンブリソースなので、これを実際のCPUアーキテクチャに合わせて実行するには Dalvik の JIT で処理するか、ART であれば [AOT(事前コンパイラ)](http://ja.wikipedia.org/wiki/事前コンパイラ) によってアセンブリソースに変換されます。

他にプラットフォームに目を向けると[この記事](http://www.infoq.com/jp/news/2014/07/ahead-of-time-compiler-os)では下記のようになっているそうです。

>・iOSは基本的に静的なコンパイルを行う。アプリケーションのアップロードに先立って，最初のビルドプロセスで，最適化されたコードを開発者のマシンで生成する方法だ。
・Windows Phoneでは，アプリケーションがデバイスにインストールされる前にストア上でマシン依存のコードを生成するという，クラウドコンパイル手法を採用している。

推測ですが Windows Phone や Android は、iOS と異なり様々なデバイスベンダーが参入し採用されるCPUが異なるため事前にCPUアーキテクチャが決定されないため（=インストール時や実行時にならないと ARM なのか x86 なのか分からない）アセンブリリソースの生成を実行タイミングの直前で行う方式を採用していると思われる。

Jack and Jill の役割はアセンブリソースへの変換ではなく中間コードとなるDEXやAPKの生成」なので、必然的に実行環境に依存せずに出来る範囲のことが主たる作業となります。

同じく Wikipedia の引用ですが
> Java仮想マシン (Java VM) はJavaクラスファイルをロードし、Javaバイトコードをインタプリタで実行するか、または、JITコンパイラがそれをCPUネイティブの機械語にコンパイルして実行する。Jikesだけを除きほとんどのJavaコンパイラは、Javaバイトコードにコンパイルする段階で最適化をすると、Java VMでHotSpotなどが最適化するさいに混乱してしまい、かえって遅くなるという理由により、Java VMによってプログラムが実行されるまでほとんど最適化をしない。そのため、たとえ、異なるコンパイラを使おうと、だいたい同じJavaクラスファイルを生成する。

とあるので Jack and Jill は DEX に出力する時点では特別な最適化などは行わず「既存のコンパイルプロセスを、より効率的に行うためのツールチェインである。」とかんがえられる。ただし、従来の Bytecode への難読化でも利用されていた ProGuard で行われた Optimized Java Bytecode の出力処理も Jack に取り込まれている。今後に期待。

# コンパイラの構成
コンパイラは大きく2つの構造に別れる。
* 入力されたソースコードを解釈して中間コード生成するフロントエンド部分
* 中間コードからアセンブリソースへの変換を行うバックエンド部分

フロントエンドとバックエンドの途中にある中間コードは複数あり、それをリンクしてひとまとめのアセンブリソースに変換する補助ツールがリンカーの役割。

## フロントエンド
フロントエンド部分の役割はソースコードに記述されている文章や文法など整合性を確認し問題の発見を行うこと。
コンパイラが構文解析の結果コンパイルエラーとして通知するものはフロンエンド部分のチェックを通過できなかった文法上の誤りや整合性の不一致など。

* 字句解析:ソースコードから文章を抽出し字句(Token)に分割し解析を行う
* 構文解析:字句が構文原則（プログラミング言語の文法上の規約など）にしたがっているかを解析を行う
* 意味解析:プログラムの実行上での整合性（関数の引数の数や型が異なる呼び出しなど）の解析を行う。

## バックエンド
中間コードを読み込み、実行効率の向上を行いながら定められた形式のアセンブリソースを出力する。

* コード最適化:局所最適化、大域的最適化などを行う。
* コード生成:最終的な出力形式のフォーマット形式にあわせて出力行う。

Jack and Jill でも、同じように構造はフロントエンドとバックエンドに分かれており内容は追いかけやすい。
従来と違うのは ProGuard の処理が Jack に組み込まれたことにより Bytecode Optimize の実装も含まれている。

# Jack の起動処理
コンパイラ Jack の処理の流れを順を追って見る。

1. runJack()
2. commandLine#checkAndRun()
3. jack#checkAndRun()
4. jack#check() and Jack#run()
5. jack#check() -> SANITY CHECK jack#run() -> Run the jack compiler!

ココで実行されるコンパイル処理はスレッドとして Jack-Server によって管理されている。

## ビルドプロセス(Jack#run()の中身)
1. TargetProduction を設定
2. PlanBuilder
￼￼￼￼￼￼￼￼- PreProcessorApplier
3. DexFileProduct - DexFileWriter
4. DexFileProduct & Resources - ResourceWriter
5. JayceInLibraryProduct - LibraryMetaWriter

# ビルドプランの作成

Plan 作成処理

```java:jack.java
Plan<JSession> plan; try {
    // Try to build an automatic plan ... try {
    plan = request.buildPlan(JSession.class); } catch (PlanNotFoundException e) {
    throw new AssertionError(e);
} catch (IllegalRequestException e) {
    throw new AssertionError(e); }
} catch (UnsupportedOperationException e) {}
```

ビルドプランが確定するとスケジューラに登録してコンパイルを行う。

```java:
PlanPrinterFactory.getPlanPrinter().printPlan(plan); try {
    plan.getScheduleInstance().process(session); } finally {
    try {
        OutputLibrary jackOutputLibrary = session.getJackOutputLibrary(); 
        if (jackOutputLibrary != null) {
            jackOutputLibrary.close(); 
        }

        // TODO(jack-team): auto-close
        if (config.get(Options.GENERATE_DEX_FILE).booleanValue() && config.get(Options.DEX_OUTPUT_CONTAINER_TYPE) == Container.ZIP) {
        config.get(Options.DEX_OUTPUT_ZIP).close(); 
        }
        ...
}
```

# Jack IR
IR とは中間表現のことでプログラムの内部表現/中間表現のこと。
Jack では /ir/ast 以下に実装されている。
種類は以下の通り。

* Jack-FormatIR
* Non-JackFormatIR
* JavaSource-FomartIR

Jack は Jack の中間コード表現用。Non-Jack は bytecode用。
Jayce までのフロントエンド処理は ECJ(Eclipse Compiler for Java) を使って行われ結果を Jack IR として保存する。Java 言語の文法解析においては既存のOSSを利用し IR に必要不可欠なロジックは /frontend 以下に実装されているが Duplicate されたメソッドの削除と親クラス情報の付与。仮想メソッドの作成などを行う程度。

# Jayce
Jill が解釈・変換したライブラリプロジェクトや aar, jar などのライブラリの中間バイトコード表現のこと。
拡張子は .jayce と指定されている。
Jayce のヘッダ部分に出力時の Jack and Jill のバージョンが出力されており ver 2.14 以前と以降では処理が分かれている。
たぶん何か違うんだろう。

```java:
if (majorVersion == 2 && minorVersion == 14) {
    // Read jayce file header, after jayce version 2.14, header does no longer exists it was moved // to jack library properties
    try {
        new JayceHeader(in);
    } catch (JayceFormatException e) {
        logger.log(Level.SEVERE,"Library " + inputJackLibrary.getLocation().getDescription() + " is invalid", e);
        throw new LibraryFormatException(inputJackLibrary.getLocation()); 
    } catch (IOException e) {
        ReportableException exceptionToReport = new LibraryReadingException(e); 
        Jack.getSession().getReporter().report(Severity.FATAL, exceptionToReport); throw new JackAbortException(exceptionToReport);
    } 
}
```

Jayce の出力は下記に定義されている。
> {jack_root}/jack/src/com/android/jack/jayce/v0002/nodes

FileWriter を見ると整数型をLEB128に変換する以外は普通のフォーマットの様子。

```java:JayceFileWriter
// Jayce File Writer
out.writeInt(modifiers);
out.writeId(signature);
out.writeId(superClass);
out.writeIds(superInterfaces);
out.writeId(enclosingType); 
out.writeId(enclosingMethodClass); 
out.writeId(enclosingMethod);
out.writeIds(inners);
out.writeNodes(fields);
out.writeNodes(methods);
out.writeNodes(annotations);
out.writeNodes(markers);
```

# Jayce 出力以降のビルドプラン
Jayce 出力まで進むとコンパイラ処理としてはフロントエンドからバックエンドに進んだことになる。
順を追って処理を見てみる。

## プランの作成
プランはクラス情報、メソッド情報、フィールド情報と細分化され、ビルドプロセスのオプションに従って各プランでの処理が決定される。
各プランの中でビルドオプションの指定に従い、出力する DEX コードに対して Jack and Jill の中で変更(最適化）を加える事があります。

## 最適化
Jack and Jill の最適化については下記に定義されている。

呼び出し元
> {JACK_ROOT}/Options.java

各最適化ロジックの実装先
> {JACK_ROOT}/optimizations

ProGuard の形式で言う Optimized Java Bytecode の処理は、今のところ下記の処理が確認できる。
Jack and Jill の場合は Javac を経由しないので Optimized Dalvik Bytecode と記述してるケースが見られる。

* ConstantRefinerAndVariableRemover 
* DefUsesAndUseDefsChainsSimplifier
    * DefUsesChainsSimplifier
    * UseDefsChainsSimplifier 
* ExpressionSimplifierIfWithConstantSimplifier
* NotSimplifier
* UnusedDefinitionRemover
* /tasnsformations/booleanoperators/ConditionalAndOrRemover 

それぞれの最適化については、これを記述している時点でのコードを参考にしながら実際の TrasnformRequest で行われる処理を解析してみる。

### Remove and refine constant variables.
変数の畳み込みや純化を行う。
定義型がプリミティブである場合に、その型が数値型であれば利用しているメソッドを変形(Transfromation Request と定義されている)し実値の置換えを行う。
ソレ以外のケースでは不要なキャストなどを除外するなどのデータ型の再定義を行う。

畳み込みについては下記のような変形が行われるらしい。[Wikipedia 定数の畳込み](http://ja.wikipedia.org/wiki/定数畳み込み)から引用。
このような擬態コードがあったとして

```java:
 int x = 14;
 int y = 7 - x / 2;
 return y * (28 / x + 2);
```

これに一回、定数伝播を適用すると

```java:
 int x = 14;
 int y = 7 - 14 / 2; // 元の x が 14 という即値に書き換えられる
 return y * (28 / 14 + 2);
```

これを繰り返して単純化を行う。最終的に AOT 後では即値同士の計算は計算結果のみの定義にまで置き換えられる。

### DefUsesAndUseDefsChainsSimplifier
処理のパスを解析して不要な値代入の処理を変更し単純化する。

```java:
// Path 1 の結果
a = true;
...
// Path 2 の結果
a = false;
...
// path 1 & 2 の結果を踏まえた Path 3
b = a;
```
を

```java:
// Path 1
b = true
...
// Path 2
b = false
// Path 3 は何もしなくても b には適切な値が設定されている
```

と変形する。

### ExpressionSimplifierIfWithConstantSimplifier
定数を使った全ての評価式を評価後の結果への置換えを行い処理を単純化する。

例えば、このような処理を

```java:
  int a = 5;
  int b = 6;
  int c = a * b;
  if (0) {   /* DEBUG */
    printf("%d\n", c);
  }
  return c;
```

下記のように変形する。

```java:
   int c = 30;
   return c;
```

他の最適化ロジックと組み合わせると最終的には
> return 30;

だけがアセンブリリソース残る。

### NotSimplifier
論理演算子である `!`(否定/NOT)の最適化を行う。論理演算子は付与された条件式（変数値の場合もある）の結果を反転して boolean 値で返却する。
! が付与された評価式を参照した場合にいくつかのケースが考えられる。

* データ型が boolean(primitive型)である場合は true/false の値を入れ替えて ! を除去する
* 他の論理演算子/Binary Operator(論理和、論理積、排他的論理和）が付与されている場合は、その出現回数をカウントし展開後のカウントから変形を行う。

コチラも[参考](http://ja.wikipedia.org/wiki/ブール論理)に。
* 論理演算子が AND もしくは OR の場合は「Operator will be inverse, thus it exists before and after the transformation.」となる。
* 論理演算子が XOR もしくは = の場合は「Operator could not be inverse, thus it always exists after transformation and first enclosing '!' should also be added.」となる。
実際の処理ではANDかORの場合は「opAfterTransformation」を +1 し XOR か = の場合は +2 を行う。
その結果 NOT Operator を含む書式の中に論理演算が AND と OR しか存在しない場合は式を変形し ! を除去して値を反転させる。
!(Not Operator)は必ず Boolean の true/false のどちらかを返却するというルールなので返却する値を書き換える。
一つでもNANDやNORが含まれる演算子の場合は式の変形は行わない。

### UnusedDefinitionRemover
未使用の定義を削除する。そのまんま。

### ConditionalAndOrRemover
複雑なブール演算式を変換します。ショートサーキット演算子( || や && )を利用した書式を等価の単純な式に置き換える。

### TryWithResourcesTransformer
Try-Witdh-Resources 􏰁のハンドルを行うコードを自動整形する。
こんな形の処理を

```java:
try (
Res1 res1 = new Res1();
...
    ResN resN = new ResN(); ){
    // statements 
    }
    catch (...) {}
    finally {} 
}
```

こな感じで変形する。

```java:
try {
    exceptionToThrow = null; Res1 res1 = null;
    ...
    ResN resN = null;
    try {
        res1 = new Res1(); ...
        resN = new ResN(); // statements
    } catch (Throwable twrExceptionInTry) { exceptionToThrow = twrExceptionInTry; throw twrExceptionInTry;
    } finally { 
        try {
            if (resN != null) { resN.close();}
        } catch (Throwable twrExceptionThrownByClose_) {
            if (exceptionToThrow == null) {
                exceptionToThrow = twrExceptionThrownByClose_;
            } else if (exceptionToThrow != twrExceptionThrownByClose_) { 
                exceptionToThrow.addSupressed(twrExceptionThrownByClose_);
            } 
        }
        ... for all resources till res1 ... 
        if (exceptionToThrow != null) {
            throw exceptionToThrow 
        }
    }
} catch (...) {}
    finally {} 
}
```

# 感想
内部処理では JavaSrouceCodeバージョンというフラグを管理していて、扱える Java Source のバージョンは Java7 を上限とし
ソレ以上のバージョンで要求される機能はTokenの解釈機が存在しないので Java 8 の対応は事実上行われていない。
と、思ったら新しいブランチ(ub-jack-lang-dev)が作られて Java 8の対応が始まった。

現状で Jack and Jill について言える特徴は下記の通り。

* （今のところ）all Java で実装。
* Javac bytecode 変換を経由せずに DEX/APK まで出力が行える
* 今年に入って開発は活発になっている（コミット数が倍増）
* Jayce の登場により中間コードのフォーマットが明確になった
    * Java/jar/aar 以外でも jayce のフォーマットにさえ則れば他のプログラミング言語からも jayce エクスポートが可能?
* 訴訟対策?(Java のライセンス問題)
* API-Server 構造であるならコンパイルプロセスは API のフロントエンドには影響されないのでサーバーからのコンパイルプロセスで Jack の runJack() から Gack(Go Android Compiler Kit)ちかDack(Dart Android Compiler Kit)とかも可能か?
* ART が登場し、切り替わる頃から Jack and Jill はコンスタントに開発は行われていた。
* 最適化も継続的に修正中
    * （そんなこと出来るのかは分からないけど） Jack and Jill が吐き出す Optimized Dalvik Bytecode というのは Dalvik から ART で AOT にかかる時間を少しでも減らすため ART (の AOT)に最適化されていると言う意味か？


いくつかは ART が登場した時に言われていたことの繰り返しもあるが、予感として期待させるものはある。