【ポストコンパイル時定数計算】.NET系言語でconstexprを実現する研究【Mono.Cecil, AssemblyBuilder】

.NET用プログラミング言語に新地平を切り開きました。

<details><summary>MITライセンスで[プロジェクト全体](https://booth.pm/ja/items/1609135)を配布中です。</summary><div>

## dotnet-constexpr.zipを解凍した後の導入方法

おそらく「dotnet-constexpr」フォルダの下に「post」「ConsoleTest」「ConstExpr」「target」の4フォルダがあると思われます。
dotnet-constexprをカレントディレクトリとして、PowerShellやbashなどのターミナルで `dotnet restore` と実行してください。
４プロジェクト全てがrestoreされます。
</div></details>

<details><summary>要約</summary><div>
# Abstract

## 背景

C++とD言語には`コンパイル時定数計算`という概念がある。
[C++の文献：constexpr](https://cpprefjp.github.io/lang/cpp11/constexpr.html)
[D言語の文献：ctfe](https://tour.dlang.org/tour/ja/gems/compile-time-function-evaluation-ctfe)

`コンパイル時定数計算`とは`コンパイル時に明記された値のみに依存する副作用を持たないメソッド呼び出しを全てその計算結果に置換する仕様`である。

この`コンパイル時定数計算`を用いることで[自明な計算をあらかじめ行っておいて結果をテーブルに保持](http://boleros.hateblo.jp/entry/20120615/1339750156)することが低コストで可能となる。
.NET言語で計算結果テーブルを作成する場合、外部ファイルからIOしてきて生成するか、あるいはstaticコンストラクタで計算をして静的変数に設定することとなる。
`コンパイル時定数計算`を用いれば **アプリケーションの起動速度を大幅に向上させる** ことが可能になる。

## 目的

普段筆者が使用するC#でも`コンパイル時定数計算`をおこないたい。

## 方法

コンパイルの成果物(DLLやEXEファイル)を[Mono.Cecil](https://www.mono-project.com/docs/tools+libraries/libraries/Mono.Cecil/)で解析し、[AssemblyBuilder](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.assemblybuilder?view=netframework-4.8)を用いて抽象マシンを作成し、定数式に関数呼び出しを置換した。

## 結果

ポインタを除くプリミティブ型の配列やプリミティブ型を返すstaticメソッドの呼び出しを効率的な配列や定数式に置換できた。
`ポストコンパイル時定数計算`を部分的に実現した。

## 結論

`ポストコンパイル時定数計算`の適用範囲の拡大について今後の研究が待たれる。
</div></details>

# Introduction

「最高の最適化とは、そもそも計算しないことである」

従来C#やVB.NET、F#では[関数呼び出しのインライン化](https://docs.microsoft.com/ja-jp/dotnet/api/system.runtime.compilerservices.methodimplattribute?view=netframework-4.8)までは実際行えた。
だが、関数呼び出し結果を定数に置換することはいずれの言語においてもサポートされていない。

定数を引数に取る副作用のない関数の呼び出しをその結果に置換すれば、アプリケーションの実行速度は向上するはずである。

実際`ポストコンパイル時定数計算`がどれほど役に立つのかは[C++erの成果であるコンパイル時レイトレーシングやコンパイル時Cコンパイラなど](https://www.slideshare.net/GenyaMurakami/constexpr-29223898)に示されている。

本研究ではコンパイル後のDLLやILに対して処理を施すことにより擬似的な`コンパイル時定数計算`を行った。

# Environments

 - .NET Core 3.1
 - C#8.0
 - Mono.Cecil
  - version 0.11.1
 - MicroBatchFramework
  - version 1.6.1
 - System.Runtime.CompilerServices.Unsafe
  - version 4.7.0

# Methods

.NET系言語において`ポストコンパイル時定数計算`を実現する際に、主にC++のconstexprを参考とした。
D言語のctfeは処理に掛かるコストが大きすぎるため参考としなかった。

C++のconstexprでは関数にconstexpr修飾子を付けることにより、その関数が副作用を持たず、戻り値がリテラル型であることをコンパイラに検証させ、コンパイル時呼び出しを可能にさせる。
constexprに倣い、本研究ではConstExpr属性を関数に付与させることとした。

## 全体構造

この研究では1つのソリューションの下に4つのプロジェクトを作成した。

 - ConstExpr
  - ConstExpr属性を定義したプロジェクト
  - Nugetにて公開中 https://www.nuget.org/packages/ConstExpr-Core/
 - post
  - `ポストコンパイル時定数計算`を実現するコンソールプログラム
 - Target
  - テスト用のプロジェクト
 - ConsoleTest
  - Targetを使用したプロジェクト
  - postの処理によりTargetが壊れていないかを確認するためのもの

## ConstExpr

```csharp:ConstExprAttribute.cs
using System;
namespace MetaProgramming
{
    [AttributeUsage(AttributeTargets.All, Inherited = false, AllowMultiple = true)]
    public sealed class ConstExprAttribute : Attribute
    {
    }
}
```

ConstExpr属性は次の型にのみ付与すべきである。

 - unmanagedでBlittableなstruct
 - static class
  - staticメソッドにも付与できる

## post

postはコンソールプログラムである。
DLLの集合を引数にとり、なんらかの処理を行う。

### CLIインターフェース

2つのコマンドが定義されている。

 - call
  - ConstExprな無引数のstaticメソッドを実行し、計算結果を表示する。
  - 第1引数:ConstExpr属性が付与されたstaticクラスの名前空間付きの名前
  - 第2引数:引数のないConstExpr属性が付与されたstaticメソッドの名前
  - 第3引数:.dllを含むディレクトリパス @テキストファイルパスと記述するとそのテキストファイルに記述された複数のディレクトリパスから.dllを探す
 - replace
  - ConstExpr呼び出しを可能な限り定数に置換する。
  - 第1引数:.dllを含むディレクトリ名 @テキストファイルパスと記述するとそのテキストファイルに記述された複数のディレクトリパスから.dllを探す
  - 第2引数(省略可):処理したdllを出力する先のディレクトリパス

これらコマンドは次のように使用する。
カレントディレクトリはpostである。

```
dotnet run call Target.Test D "../target\bin\Release\netstandard2.0"
dotnet run release "../target\bin\Release\netstandard2.0" -o "../target\bin\Release"
```

### 内部動作概説(Program.cs)

<details><summary>Program.cs全文</summary><div>

```csharp:Program.cs
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;
using MicroBatchFramework;
using Microsoft.Extensions.Hosting;
using Microsoft.Extensions.Logging;
using Mono.Cecil;
using post.ConstDynamicMethod;

namespace post
{
    class Program
    {
        static async Task Main(string[] args)
        {
            await new HostBuilder().RunBatchEngineAsync<ConstantExpressionInterpreter>(args);
        }
    }

    class ConstantExpressionInterpreter : BatchBase
    {
        private readonly ILogger<BatchEngine> logger;
        public ConstantExpressionInterpreter(ILogger<BatchEngine> logger) => this.logger = logger;

        [Command("call", "Call specific method")]
        public int ExecuteMethod
        (
            [Option(0, "Type Name")]string typeName,
            [Option(1, "Method Name")]string methodName,
            [Option(2, "Directory that includes dll")]string directory
        )
        {
            var directories = InterpretDirectory(directory);

            var builder = Build(directories);
            var type = builder.Type2dArray.SelectMany(x => x).FirstOrDefault(x => x.Item2.FullName == typeName).Item1;

            if (type is null)
            {
                Console.WriteLine(typeName + " not found.");
                return 1;
            }
            Console.WriteLine(type.GetMethod(methodName)?.Invoke(null, null)?.ToString());
            return 0;
        }

        private static string[] InterpretDirectory(string directory) => directory.StartsWith('@') ? File.ReadAllLines(directory.Substring(1)) : new[] { directory };

        [Command("replace", "Edit the DLLs")]
        public int ReplaceConstantExpression
        (
            [Option(0)] string directory,
            [Option("include")] string? referenceOnlyDirectory = default,
            [Option("o", "output directory")] string? output = default
        )
        {
            var directories = InterpretDirectory(directory);

            string[]? referenceOnlyDirectories = default;
            if (!(referenceOnlyDirectory is null))
            {
                referenceOnlyDirectories = InterpretDirectory(referenceOnlyDirectory);
            }

            var builder = Build(referenceOnlyDirectories is null ? directories : directories.Concat(referenceOnlyDirectories).ToArray(), !(string.IsNullOrEmpty(output)));

            var replacer = new ConstExprReplacer(builder.ModuleArray, builder.Type2dArray);

            for (var moduleIndex = 0; moduleIndex < directories.Length; moduleIndex++)
            {
                replacer.ProcessModule(moduleIndex);
                var module = builder.ModuleArray[moduleIndex].Item2;
                if (output is null)
                {
                    module.Write();
                }
                else
                {
                    module.Write(Path.Combine(output, Path.GetFileName(module.FileName)));
                }
            }

            return 0;
        }

        private static ConstExprBuilder Build(string[] directories, bool isReadWrite = false)
        {
            var moduleList = new List<ModuleDefinition>(directories.Length * 2);
            var readerParameters = new ReaderParameters()
            {
                AssemblyResolver = new DefaultAssemblyResolver(),
                ReadWrite = isReadWrite,
            };
            foreach (var directory in directories)
            {
                foreach (var file in Directory.EnumerateFiles(directory, "*.dll", SearchOption.AllDirectories))
                {
                    var assemblyDefinition = AssemblyDefinition.ReadAssembly(file, readerParameters);
                    moduleList.AddRange(assemblyDefinition.Modules);
                }
            }
            var builder = new ConstExprBuilder(moduleList.ToArray());
            return builder;
        }
    }
}
```
</div></details>

[MicroBatchFramework](https://tech.cygames.co.jp/archives/3241/)を使用してコマンドライン引数を解析し、コマンドを実行する。
callもreplaceもいずれもディレクトリパスを調べ、その直下に存在するDLL群を[ModuleDefinition](https://github.com/jbevain/cecil/blob/master/Mono.Cecil/ModuleDefinition.cs)の配列に変換する。
そしてModuleDefinition[]を引数に与えてConstExprBuilderを構築する。
ConstExprBuilderはコンストラクタですべての処理を行う。

<details><summary>ConstExprBuilder解説</summary><div>
<details><summary>ConstExprBuilder.cs抜粋</summary><div>

```csharp:ConstExprBuilder.cs
/*
using MethodAttributes = System.Reflection.MethodAttributes;
using MA = Mono.Cecil.MethodAttributes;
using MethodBody = Mono.Cecil.Cil.MethodBody;
using OpCodes = System.Reflection.Emit.OpCodes;
using MTuple = System.ValueTuple<System.Reflection.Emit.ModuleBuilder, Mono.Cecil.ModuleDefinition>;
using TTuple = System.ValueTuple<System.Reflection.Emit.TypeBuilder, Mono.Cecil.TypeDefinition>;
using TyTuple = System.ValueTuple<System.Type, Mono.Cecil.TypeDefinition>;
using MdTuple = System.ValueTuple<System.Reflection.Emit.MethodBuilder, Mono.Cecil.MethodDefinition>;
using CTuple = System.ValueTuple<System.Reflection.Emit.ConstructorBuilder, Mono.Cecil.MethodDefinition>;
using FieldAttributes = System.Reflection.FieldAttributes;
using FTuple = System.ValueTuple<System.Reflection.Emit.FieldBuilder, Mono.Cecil.FieldDefinition>;
using GenericParameterAttributes = System.Reflection.GenericParameterAttributes;
*/

private readonly AssemblyBuilder[] assemblyBuilders;
public readonly MTuple[] ModuleArray;
private readonly TTuple[][] typePairArrays;
private readonly MdTuple[][][] methodPairArray2ds;
private readonly CTuple[][][] constructorPairArray2ds;
private readonly FTuple[][][] fieldPairArray2ds;
private readonly FTuple[][][] staticFieldPairArray2ds;

public readonly TyTuple[][] Type2dArray;

private readonly IConverterWithGenericParameter converter;

public ConstExprBuilder(ModuleDefinition[] moduleDefinitions)
{
    assemblyBuilders = new AssemblyBuilder[moduleDefinitions.Length];
    for (var i = 0; i < assemblyBuilders.Length; i++)
        assemblyBuilders[i] = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName("ConstExpr" + i), AssemblyBuilderAccess.Run);
    ModuleArray = new MTuple[moduleDefinitions.Length];
    typePairArrays = new TTuple[ModuleArray.Length][];
    methodPairArray2ds = new MdTuple[ModuleArray.Length][][];
    constructorPairArray2ds = new CTuple[ModuleArray.Length][][];
    fieldPairArray2ds = new FTuple[ModuleArray.Length][][];
    staticFieldPairArray2ds = new FTuple[ModuleArray.Length][][];
    Type2dArray = new TyTuple[ModuleArray.Length][];

    ConstructTypeBuilders(moduleDefinitions);
    converter = new NotCreatedConverter(ModuleArray, typePairArrays, methodPairArray2ds, constructorPairArray2ds, fieldPairArray2ds, staticFieldPairArray2ds);
    ConstructFields();
    ConstructMethodBuilderSignatures();
    ConstructMethodBuilderBodies();
    ConstructConstructorBuilderBodies();
    Publish();
}

private void Publish()
{
    for (var moduleIndex = 0; moduleIndex < Type2dArray.Length; moduleIndex++)
    {
        ref TyTuple[] typeArray = ref Type2dArray[moduleIndex];
        ref TTuple[] sourceArray = ref typePairArrays[moduleIndex];
        typeArray = sourceArray.Length == 0 ? Array.Empty<TyTuple>() : new TyTuple[sourceArray.Length];
        for (var typeIndex = 0; typeIndex < typeArray.Length; typeIndex++)
        {
            TTuple source = sourceArray[typeIndex];
            TyTuple createType = source.Item1.CreateType();
            if (createType is null) throw new NullReferenceException(source.Item2.FullName);
            typeArray[typeIndex] = (createType, source.Item2);
        }
    }
}
```
</div></details>

ConstExprBuilderでは読み込んだModuleDefinitionの数だけ新規に[AssemblyBuilder](https://qiita.com/pCYSl5EDgo/items/9af7f5f1efaf8cd4ccdc)と[ModuleBuilder](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.modulebuilder?view=netframework-4.8)を定義する。
そしてConstExpr属性が付与された型に対応する[TypeBuilder](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.typebuilder?view=netframework-4.8)を[ModuleBuilderを用いて定義する](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.modulebuilder.definetype?view=netframework-4.8#System_Reflection_Emit_ModuleBuilder_DefineType_System_String_System_Reflection_TypeAttributes_System_Type_)。
型を一周巡回した後、改めてフィールド情報やメソッドのシグネチャ情報を取得して定義する。
大凡の外形が定まった後、初めて[MethodBuilder](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.methodbuilder?view=netframework-4.8)から[ILGenerator](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.ilgenerator?view=netframework-4.8)を得、メソッドの中身を再構築する。

そして全体を過不足なく再構成した後、Publish()内部で全てのTypeBuilderに対して[CreateTypeメソッド](https://docs.microsoft.com/ja-jp/dotnet/api/system.reflection.emit.typebuilder.createtype?view=netframework-4.8)を実行して再構築を完了し、実行可能なメソッドを得る。
</div></details>

## Target

<details><summary>Target.cs全文</summary><div>

```csharp:Target.cs
using MetaProgramming;

namespace Target
{
    [ConstExpr]
    public static class Test
    {
        [ConstExpr] public static int Field;

        [ConstExpr, ConstantInitializer(nameof(Field))]
        public static int Initializer()
        {
            return 14;
        }

        public static int Accessor() => Field;

        [ConstExpr]
        public static sbyte D()
        {
            return new Q<sbyte>(114).value;
            //return FFF<int>.PPT(14);
        }

        [ConstExpr]
        public static int D2()
        {
            return Q<long>.P(32);
            //return FFF<int>.PPT(14);
        }

        [ConstExpr]
        public static int Z() => D() << 4;

        [ConstExpr]
        public static int Z2() => D2() - 4;

        [ConstExpr]
        public static int Z3<T>() where T : unmanaged => Y(1);

        [ConstExpr]
        public static int Z4() => Z3<char>();

        [ConstExpr]
        public static int Y(int a)
        {
            var arr = Array(24);
            var arr2 = Array(12);
            var arr3 = Array(4);
            var arr4 = Array(1);
            var arr5 = Array(9);
            if (a == 1 && arr != null) return arr.Length;
            return Array(0).Length - 1;
        }

        [ConstExpr]
        public static double[] Array(int a)
        {
            var answer = new double[a];
            for (int i = 0; i < answer.Length; i++)
            {
                answer[i] = i + 0.5;
            }
            return answer;
        }
    }

    [ConstExpr]
    interface T {}

    [ConstExpr]
    public struct Q<J> where J : unmanaged
    {
        public J value;
        [ConstExpr]
        public Q(J value)
        {
            this.value = value;
        }

        [ConstExpr]
        public static T P<T>(T v) where T : unmanaged => new Q<T>(v).value;
    }

    /*[ConstExpr]
    public static class FFF<T> where T : unmanaged
    {
        [ConstExpr]
        public static T PPT(T d)
        {
            return new Q<T>(d).value;
        }
    }*/
}
```
</div></details>

## ConsoleTest

<details><summary>ConsoleTest.cs全文</summary><div>

```csharp:ConsoleTest.cs
using System;
using Target;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Test.Array(1)[0]);
        }
    }
}
```
</div></details>

# Discussion

.NET系言語に`ポストコンパイル時`という実行環境を作り出した意義は大きい。
C#やF#の可能性が大きく広がったことは間違いない。

以後の記述は現時点で何がこの研究において実現されていないかの補足であり、今後の課題である。

## メソッドの仕様

現在のpostはConstExprメソッドの扱いがシビアであるので、そこを課題として取り扱いを向上させるべきではある。具体的には次のような制約がある。

 - ref, in, outを許さない
 - 引数は全てリテラル型である必要がある
 - オーバーロードは定義可能
  - ただし、引数の個数がConstExprのついた物同士では互いに異なっていなくてはならない
  - Hoge(), Hoge(int i), Hoge(int i, int j)は定義可能
  - Hoge(int i), Hoge(long i)はエラーとなる

## ConstExprと属性が付けられていない副作用を持たない言語要素の使用

System.ValueTuple<T0, T1>やSystem.MathなどのConstExprメソッドの内部で使用する分には問題のない構造体やstaticメソッド群を利用したい。
だが、現在の抽象マシンはConstExprとマークされた型とメソッドのみを元に構築される。
この制約は何らかの方法で突破せねばなるまい。

## 文字列の使用

ILではSystem.String型も参照型でありながらリテラルとして使用可能である(ldstrやldnullなど)。
文字列も定数埋め込み可能となればさらに便利になるに違いない。

# 感想・まとめ・こぼれ話

[仮称「中３女子」](https://booth.pm/ja/items/1609135)として現在BOOTHで公開しています。
この「中３女子」という名前は[C++のconstexprで有名なボレロ村上氏](https://twitter.com/bolero_murakami)から来ています。
もっとおかたくて真面目でわかりやすく覚えやすい名前の案があれば「中３女子」から変更し、GitHubに公開するつもりです。

C#でconstexprを再現することにどれほどの需要があるのか正直実現した自分にもわからないのです。
憧れは止められないので、これから用途を考えます。

# 参考文献

1: [constexpr](https://cpprefjp.github.io/lang/cpp11/constexpr.html)
2: [ctfe](https://blog.kotet.jp/2017/07/compile-time-sort-in-d/)
3: [Mono.Cecil](https://qiita.com/pCYSl5EDgo/items/4146989d08e169dde81d)
4: [MicroBatchFramework](https://tech.guitarrapc.com/entry/2019/03/19/111620)