[legacy/mid] Add strength reduction for constant div and mul

2 files changed, 397 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/divopt.cc b/rcc-legacy/src/mid/divopt.cc
new file mode 100644
index 0000000..6e9269f
--- /dev/null
+++ b/rcc-legacy/src/mid/divopt.cc
@@ -0,0 +1,189 @@
+/* Source code for RCC-Legacy.
+   Copyright (C) 2026 Richard Qin
+
+This file is part of RCC.
+
+RCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+RCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with RCC; see the file LICENSE.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/// @file divopt.cc
+/// @brief Constant integer division/modulo strength reduction: rewrite `x / c`, `x % c`
+///        into mul + shift + sign correction sequence when c is a compile-time constant.
+///
+/// See docs/divopt.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cstdint>
+
+namespace rcc {
+
+namespace {
+
+struct Magic {
+    int32_t M;
+    int s;
+    bool need_add;
+};
+
+Magic compute_magic_s32(uint32_t ad) {
+    const uint32_t t = 0x80000000u;  // 2^31
+    uint32_t anc = t - 1 - t % ad;
+    uint32_t p = 31;
+    uint32_t q1 = t / anc, r1 = t - q1 * anc;
+    uint32_t q2 = t / ad, r2 = t - q2 * ad;
+    uint32_t delta;
+    do {
+        ++p;
+        q1 *= 2;
+        r1 *= 2;
+        if (r1 >= anc) {
+            ++q1;
+            r1 -= anc;
+        }
+        q2 *= 2;
+        r2 *= 2;
+        if (r2 >= ad) {
+            ++q2;
+            r2 -= ad;
+        }
+        delta = ad - r2;
+    } while (q1 < delta || (q1 == delta && r1 == 0));
+
+    Magic m;
+    uint32_t M_u = q2 + 1;
+    m.M = static_cast<int32_t>(M_u);
+    m.s = static_cast<int>(p - 32);
+    m.need_add = (M_u >= 0x80000000u);
+    return m;
+}
+
+void emit_pow2_div_into(Ctx* ctx, Fn* fn, Ref dst, Ref x, int k) {
+    Ref sign = newtmp(ctx, "divopt", Kw, fn);
+    Ref mask = newtmp(ctx, "divopt", Kw, fn);
+    Ref tmp = newtmp(ctx, "divopt", Kw, fn);
+
+    emit(ctx, Osar, Kw, dst, tmp, getcon(ctx, k, fn));
+    emit(ctx, Oadd, Kw, tmp, x, mask);
+    emit(ctx, Oshr, Kw, mask, sign, getcon(ctx, 32 - k, fn));
+    emit(ctx, Osar, Kw, sign, x, getcon(ctx, 31, fn));
+}
+
+void emit_magic_div_into(Ctx* ctx, Fn* fn, Ref dst, Ref x, int32_t d_abs, bool d_neg) {
+    Magic m = compute_magic_s32(static_cast<uint32_t>(d_abs));
+    int64_t M64 = static_cast<int64_t>(m.M);  // Sign extend i32 to i64
+
+    Ref xl = newtmp(ctx, "divopt", Kl, fn);
+    Ref prod = newtmp(ctx, "divopt", Kl, fn);
+    Ref hi = newtmp(ctx, "divopt", Kl, fn);
+    Ref hi2 = m.need_add ? newtmp(ctx, "divopt", Kl, fn) : hi;
+    Ref q1 = (m.s > 0) ? newtmp(ctx, "divopt", Kl, fn) : hi2;
+    Ref sg = newtmp(ctx, "divopt", Kl, fn);
+    Ref qpre = d_neg ? newtmp(ctx, "divopt", Kw, fn) : dst;
+
+    // Reverse emit:
+    if (d_neg)
+        emit(ctx, Oneg, Kw, dst, qpre, Ref::none());
+    emit(ctx, Osub, Kw, qpre, q1, sg);
+    emit(ctx, Osar, Kl, sg, xl, getcon(ctx, 63, fn));
+    if (m.s > 0)
+        emit(ctx, Osar, Kl, q1, hi2, getcon(ctx, m.s, fn));
+    if (m.need_add)
+        emit(ctx, Oadd, Kl, hi2, hi, xl);
+    emit(ctx, Osar, Kl, hi, prod, getcon(ctx, 32, fn));
+    emit(ctx, Omul, Kl, prod, xl, getcon(ctx, M64, fn));
+    emit(ctx, Oextsw, Kl, xl, x, Ref::none());
+}
+
+bool lower_div(Ctx* ctx, Fn* fn, Ins* i, Blk* b, bool* rebuilt) {
+    if (i->op != Odiv && i->op != Orem)
+        return false;
+    if (i->cls != Kw)
+        return false;
+    if (rtype(i->arg[1]) != RCon)
+        return false;
+    Con* c = &fn->con[i->arg[1].val];
+    if (c->type != Con::CBits)
+        return false;
+    int32_t d = static_cast<int32_t>(c->bits.i);
+    if (d == 0 || d == static_cast<int32_t>(0x80000000))
+        return false;  // Skip d=0 (leave to hardware) and d=INT_MIN (|d| overflows i32)
+
+    bool is_rem = (i->op == Orem);
+    Ref dst = i->to;
+    Ref x = i->arg[0];
+
+    // First hit: move unprocessed tail to end of insb (same as simpl.cc)
+    if (!*rebuilt) {
+        ctx->curi = ctx->insb + NIns;
+        ulong tail = static_cast<ulong>((b->ins + b->nins) - (i + 1));
+        ctx->curi -= tail;
+        icpy(ctx->curi, i + 1, tail);
+        *rebuilt = true;
+    }
+
+    // d = +-1 degenerate: rem -> 0; div(1)=x; div(-1)=-x.
+    if (d == 1 || d == -1) {
+        if (is_rem)
+            emit(ctx, Ocopy, Kw, dst, getcon(ctx, 0, fn), Ref::none());
+        else if (d == 1)
+            emit(ctx, Ocopy, Kw, dst, x, Ref::none());
+        else
+            emit(ctx, Oneg, Kw, dst, x, Ref::none());
+        return true;
+    }
+
+    // For rem: emit tail r = x - q*d first (reverse order), then div sequence.
+    Ref q_dst = is_rem ? newtmp(ctx, "divopt", Kw, fn) : dst;
+    if (is_rem) {
+        Ref qd = newtmp(ctx, "divopt", Kw, fn);
+        emit(ctx, Osub, Kw, dst, x, qd);
+        emit(ctx, Omul, Kw, qd, q_dst, getcon(ctx, static_cast<int64_t>(d), fn));
+    }
+
+    int32_t ad = (d < 0) ? -d : d;
+    if ((ad & (ad - 1)) == 0) {
+        // |d| is power of 2, k >= 1
+        int k = __builtin_ctz(static_cast<uint32_t>(ad));
+        if (d < 0) {
+            Ref q_pos = newtmp(ctx, "divopt", Kw, fn);
+            emit(ctx, Oneg, Kw, q_dst, q_pos, Ref::none());
+            emit_pow2_div_into(ctx, fn, q_pos, x, k);
+        } else {
+            emit_pow2_div_into(ctx, fn, q_dst, x, k);
+        }
+    } else {
+        emit_magic_div_into(ctx, fn, q_dst, x, ad, d < 0);
+    }
+    return true;
+}
+
+}  // namespace
+
+void divopt(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        bool rebuilt = false;
+        for (Ins* i = b->ins + b->nins; i != b->ins;) {
+            --i;
+            if (lower_div(ctx, fn, i, b, &rebuilt))
+                continue;
+            if (rebuilt)
+                emiti(ctx, *i);
+        }
+        if (rebuilt)
+            idup(ctx, b, ctx->curi, static_cast<ulong>(ctx->insb + NIns - ctx->curi));
+    }
+}
+
+}  // namespace rcc
diff --git a/rcc-legacy/src/mid/mulopt.cc b/rcc-legacy/src/mid/mulopt.cc
new file mode 100644
index 0000000..0a369db
--- /dev/null
+++ b/rcc-legacy/src/mid/mulopt.cc
@@ -0,0 +1,208 @@
+/* Source code for RCC-Legacy.
+   Copyright (C) 2026 Richard Qin
+
+This file is part of RCC.
+
+RCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+RCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with RCC; see the file LICENSE.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/// @file mulopt.cc
+/// @brief Constant integer multiplication strength reduction.
+///
+/// See docs/mulopt.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <cstdint>
+
+namespace rcc {
+
+namespace {
+
+enum Kind {
+    KZero,
+    KCopy,
+    KShl,
+    KShlAddShl,
+    KShlSubShl,
+};
+
+struct Rewrite {
+    Kind kind;
+    int sh1;  // Primary shift for KShl / KShlAddShl / KShlSubShl
+    int sh2;  // Secondary shift for KShlAddShl / KShlSubShl (0 means use x itself)
+};
+
+// Classify patterns.
+bool classify(uint64_t ac, int max_shift, Rewrite& out) {
+    if (ac == 0) {
+        out.kind = KZero;
+        return true;
+    }
+    if (ac == 1) {
+        out.kind = KCopy;
+        return true;
+    }
+    if ((ac & (ac - 1)) == 0) {
+        int k = __builtin_ctzll(ac);
+        if (k >= max_shift)
+            return false;
+        out.kind = KShl;
+        out.sh1 = k;
+        return true;
+    }
+    int a = 63 - __builtin_clzll(ac);  // floor log2(ac), 0 < ac, ac is not pow2
+    if (a >= max_shift)
+        return false;
+    uint64_t hi = static_cast<uint64_t>(1) << a;
+
+    // pow2 + pow2.
+    uint64_t low = ac - hi;
+    if ((low & (low - 1)) == 0) {
+        int b = __builtin_ctzll(low);
+        out.kind = KShlAddShl;
+        out.sh1 = a;
+        out.sh2 = b;
+        return true;
+    }
+
+    // pow2 - pow2.
+    if (a + 1 < max_shift) {
+        uint64_t hi2 = hi << 1;
+        uint64_t diff = hi2 - ac;
+        // Check diff.
+        if ((diff & (diff - 1)) == 0) {
+            int b = __builtin_ctzll(diff);
+            out.kind = KShlSubShl;
+            out.sh1 = a + 1;
+            out.sh2 = b;
+            return true;
+        }
+    }
+    return false;
+}
+
+// emit() prepends.
+bool lower_mul(Ctx* ctx, Fn* fn, Ins* i, Blk* b, bool* rebuilt) {
+    if (i->op != Omul)
+        return false;
+    if (i->cls != Kw && i->cls != Kl)
+        return false;
+    if (rtype(i->arg[1]) != RCon)
+        return false;
+    Con* c = &fn->con[i->arg[1].val];
+    if (c->type != Con::CBits)
+        return false;
+
+    int cls = i->cls;
+    int64_t cv;
+    int max_shift;
+    if (cls == Kw) {
+        cv = static_cast<int32_t>(
+            c->bits.i);  // Narrow to i32 to avoid interference from Kl residual bits
+        max_shift = 32;
+    } else {
+        cv = c->bits.i;
+        max_shift = 64;
+    }
+
+    bool neg = (cv < 0);
+    uint64_t ac = static_cast<uint64_t>(cv);
+    if (neg)
+        ac = -ac;  // wrap-around produces 2^31 / 2^63 for INT_MIN / INT64_MIN respectively
+
+    Rewrite r;
+    if (!classify(ac, max_shift, r))
+        return false;
+
+    Ref dst = i->to;
+    Ref x = i->arg[0];
+
+    // Move unprocessed tail.
+    if (!*rebuilt) {
+        ctx->curi = ctx->insb + NIns;
+        ulong tail = static_cast<ulong>((b->ins + b->nins) - (i + 1));
+        ctx->curi -= tail;
+        icpy(ctx->curi, i + 1, tail);
+        *rebuilt = true;
+    }
+
+    switch (r.kind) {
+        case KZero:
+            // 0 * x = 0.
+            emit(ctx, Ocopy, cls, dst, getcon(ctx, 0, fn), Ref::none());
+            break;
+        case KCopy:
+            if (neg)
+                emit(ctx, Oneg, cls, dst, x, Ref::none());
+            else
+                emit(ctx, Ocopy, cls, dst, x, Ref::none());
+            break;
+        case KShl: {
+            if (neg) {
+                Ref t = newtmp(ctx, "mulopt", cls, fn);
+                emit(ctx, Oneg, cls, dst, t, Ref::none());
+                emit(ctx, Oshl, cls, t, x, getcon(ctx, r.sh1, fn));
+            } else {
+                emit(ctx, Oshl, cls, dst, x, getcon(ctx, r.sh1, fn));
+            }
+            break;
+        }
+        case KShlAddShl: {
+            // sum.
+            Ref sum = neg ? newtmp(ctx, "mulopt", cls, fn) : dst;
+            Ref t1 = newtmp(ctx, "mulopt", cls, fn);
+            Ref t2 = (r.sh2 == 0) ? x : newtmp(ctx, "mulopt", cls, fn);
+            if (neg)
+                emit(ctx, Oneg, cls, dst, sum, Ref::none());
+            emit(ctx, Oadd, cls, sum, t1, t2);
+            if (r.sh2 != 0)
+                emit(ctx, Oshl, cls, t2, x, getcon(ctx, r.sh2, fn));
+            emit(ctx, Oshl, cls, t1, x, getcon(ctx, r.sh1, fn));
+            break;
+        }
+        case KShlSubShl: {
+            Ref diff = neg ? newtmp(ctx, "mulopt", cls, fn) : dst;
+            Ref t1 = newtmp(ctx, "mulopt", cls, fn);
+            Ref t2 = (r.sh2 == 0) ? x : newtmp(ctx, "mulopt", cls, fn);
+            if (neg)
+                emit(ctx, Oneg, cls, dst, diff, Ref::none());
+            emit(ctx, Osub, cls, diff, t1, t2);
+            if (r.sh2 != 0)
+                emit(ctx, Oshl, cls, t2, x, getcon(ctx, r.sh2, fn));
+            emit(ctx, Oshl, cls, t1, x, getcon(ctx, r.sh1, fn));
+            break;
+        }
+    }
+    return true;
+}
+
+}  // namespace
+
+void mulopt(Ctx* ctx, Fn* fn) {
+    for (Blk* b = fn->start; b; b = b->link) {
+        bool rebuilt = false;
+        for (Ins* i = b->ins + b->nins; i != b->ins;) {
+            --i;
+            if (lower_mul(ctx, fn, i, b, &rebuilt))
+                continue;
+            if (rebuilt)
+                emiti(ctx, *i);
+        }
+        if (rebuilt)
+            idup(ctx, b, ctx->curi, static_cast<ulong>(ctx->insb + NIns - ctx->curi));
+    }
+}
+
+}  // namespace rcc