Lowering in DMD

パッと思いついたので書いてみたけど、特にコード書くのに役立ったりとかはしないTrivialなネタです。

tldr;

コンパイラはこっそり効率的な形に式を変換してくれたりしなかったりするので、雰囲気で最適化するのは意味がなかったりする。
「powは遅いから乗算で書こう」とかいって思いつきで手動最適化とかやっても、コンパイラが勝手にやってくれたりするんですよね。

速度の最適化するときはちゃんと計測しよう(ってことでいいかな)

環境

• 執筆時点でのDMDリビジョン

$ git rev-parse HEAD
7c1a07c962b4e33b7e4a60ba00734f2737091771

What is lowering ?

プログラミング言語処理系におけるLoweringは(RustのAST -> HIRのように)ある表現からより低級な中間表現へ変換することをさしているっぽいです。

D言語の作者のWalter Bright氏は複雑な構文をよりシンプルに書き換えを行うこと を指してLoweringと呼んでいるようです。

DMD内ではSimple AST(元のソースコードから生成されたAST)からAST(lowered)への変換 の部分でLoweringが行われています。Simple AST is 何。。

このへんは定義とか厳密に調べてるわけではないので、あんまり自信がないです。

なにがうれしいの

憶測で語るんですが、まず単純にコンパイラの意味解析がシンプルになるのでそこが嬉しい。
あと最適化したりなんかのときに漏れたりということもなくなる。例えば for は最適化するパスを通るけど while の処理だと通らない、みたいなことが発生しなくなります。

あとは当然、結果は同じになるけどより速度が速くなる形式へと変換する、みたいなことをすると生成するコードは高速化されて嬉しい、ということがあります。
素直に書いてコンパイラが最適化された形に変換する、というのはコンパイラのあるべき姿ですね。

DMD内でのloweringの例

loweringの例をソースコードつきでいくつか紹介します。

• x ^^ 2 や x ^^ 3 はそれぞれ x * x と x * x * x の形に置き換えられる
  • 乗算のほうが速いためだと思われる
  • さすがに展開しまくって乗算の回数が多くなったら遅くなるので3回まで

src/dmd/expressionsem.d

        // Deal with x^^2, x^^3 immediately, since they are of practical importance.
        if (intpow == 2 || intpow == 3)
        {
            // Replace x^^2 with (tmp = x, tmp*tmp)
            // Replace x^^3 with (tmp = x, tmp*tmp*tmp)
            auto tmp = copyToTemp(0, "__powtmp", exp.e1);
            Expression de = new DeclarationExp(exp.loc, tmp);
            Expression ve = new VarExp(exp.loc, tmp);

            /* Note that we're reusing ve. This should be ok.
             */
            Expression me = new MulExp(exp.loc, ve, ve);
            if (intpow == 3)
                me = new MulExp(exp.loc, me, ve);
            e = new CommaExp(exp.loc, de, me);
            e = e.expressionSemantic(sc);
            result = e;
            return;
        }

• e1 ^^ 0.5 は std.math.sqrt(e1) を使う形に、e1 ^^ e2 は std.math.pow を使う形に置き換えられる
  • なのでPowExp使っても std.math.pow 使ってもだいたい一緒です
  • core.math.pow core.math.sqrt は標準Cライブラリ使うので違っている

src/dmd/expressionsem.d

        if (exp.e2.op == TOK.float64 && exp.e2.toReal() == CTFloat.half)
        {
            // Replace e1 ^^ 0.5 with .std.math.sqrt(x)
            e = new CallExp(exp.loc, new DotIdExp(exp.loc, e, Id._sqrt), exp.e1);
        }
        else
        {
            // Replace e1 ^^ e2 with .std.math.pow(e1, e2)
            e = new CallExp(exp.loc, new DotIdExp(exp.loc, e, Id._pow), exp.e1, exp.e2);
        }

• -1 ^^　x は (x&1) ? -1 : 1 に置き換えられる
  • ただし x が整数であるとき

src/dmd/optimize.d

            // Replace -1 ^^ x by (x&1) ? -1 : 1, where x is integral
            if (e.e2.type.isintegral() && e.e1.op == TOK.int64 && cast(sinteger_t)e.e1.toInteger() == -1)
            {
                ret = new AndExp(e.loc, e.e2, new IntegerExp(e.loc, 1, e.e2.type));
                ret.type = e.e2.type;
                ret = new CondExp(e.loc, ret, new IntegerExp(e.loc, -1, e.type), new IntegerExp(e.loc, 1, e.type));
                ret.type = e.type;
                return;
            }

• ((2 ^^ n) ^^ p) は 1 << n * p に置き換えられる
  • ただし p が自然数であるとき

src/dmd/optimize.d

            // (2 ^^ n) ^^ p -> 1 << n * p
            if (e.e1.op == TOK.int64 && e.e1.toInteger() > 0 && !((e.e1.toInteger() - 1) & e.e1.toInteger()) && e.e2.type.isintegral() && e.e2.type.isunsigned())
            {
                dinteger_t i = e.e1.toInteger();
                dinteger_t mul = 1;
                while ((i >>= 1) > 1)
                    mul++;
                Expression shift = new MulExp(e.loc, e.e2, new IntegerExp(e.loc, mul, e.e2.type));
                shift.type = e.e2.type;
                shift = shift.castTo(null, Type.tshiftcnt);
                ret = new ShlExp(e.loc, new IntegerExp(e.loc, 1, e.e1.type), shift);
                ret.type = e.type;
                return;
            }
        }

• static foreach (x; [1, 2, 3, 4]) は static foreach (x; AliasSeq!(1, 2, 3, 4) に書き換えられる
  • わざわざ AliasSeq!(...) を書かないでよくするというだけ

src/dmd/cond.d

    /*****************************************
     * Turn an aggregate which is an array into an expression tuple
     * of its elements. I.e., lower
     *     static foreach (x; [1, 2, 3, 4]) { ... }
     * to
     *     static foreach (x; AliasSeq!(1, 2, 3, 4)) { ... }
     */
    private extern(D) void lowerArrayAggregate(Scope* sc)
    {
        auto aggr = aggrfe.aggr;
        Expression el = new ArrayLengthExp(aggr.loc, aggr);
        sc = sc.startCTFE();
        el = el.expressionSemantic(sc);
        sc = sc.endCTFE();
        el = el.optimize(WANTvalue);
        el = el.ctfeInterpret();
        if (el.op == TOK.int64)
        {
            dinteger_t length = el.toInteger();
            auto es = new Expressions();
            foreach (i; 0 .. length)
            {
                auto index = new IntegerExp(loc, i, Type.tsize_t);
                auto value = new IndexExp(aggr.loc, aggr, index);
                es.push(value);
            }
            aggrfe.aggr = new TupleExp(aggr.loc, es);
            aggrfe.aggr = aggrfe.aggr.expressionSemantic(sc);
            aggrfe.aggr = aggrfe.aggr.optimize(WANTvalue);
        }
        else
        {
            aggrfe.aggr = new ErrorExp();
        }
    }