1 files changed, 360 insertions, 0 deletions

diff --git a/rcc-legacy/src/mid/copy.cc b/rcc-legacy/src/mid/copy.cc
new file mode 100644
index 0000000..8a35498
--- /dev/null
+++ b/rcc-legacy/src/mid/copy.cc
@@ -0,0 +1,360 @@
+/* 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 copy.cc
+/// @brief copy equivalence check + narrow parameter sinking - for GVN, no independent driver.
+///
+/// See docs/copy.md for architectural notes.
+
+#include "rcc/all.h"
+
+#include <algorithm>
+
+namespace rcc {
+
+namespace {
+
+struct Ext {
+    char zext;
+    char nopw;
+    char usew;
+};
+
+bool decode_ext(int op, Ext* e) {
+    switch (op) {
+        case Oextsb:
+            *e = Ext{0, 7, 8};
+            return true;
+        case Oextub:
+            *e = Ext{1, 8, 8};
+            return true;
+        case Oextsh:
+            *e = Ext{0, 15, 16};
+            return true;
+        case Oextuh:
+            *e = Ext{1, 16, 16};
+            return true;
+        case Oextsw:
+            *e = Ext{0, 31, 32};
+            return true;
+        case Oextuw:
+            *e = Ext{1, 32, 32};
+            return true;
+    }
+    return false;
+}
+
+int bitwidth(uint64_t v) {
+    return v ? 64 - __builtin_clzll(v) : 0;
+}
+
+template <typename Walk>
+int walk_phi_memo(Fn* fn, Ref r, int w, Walk walk) {
+    int ret = walk(fn, r, w);
+    for (Blk* b = fn->start; b; b = b->link)
+        for (Phi* p = b->phi; p; p = p->link)
+            p->visit = 0;
+    return ret;
+}
+
+int uwl(Fn* fn, Ref r, int w);
+
+bool phi_use_ok(Fn* fn, Phi* p, int w) {
+    if (p->visit || req(p->to, Ref::none()))
+        return true;
+    p->visit = 1;
+    return uwl(fn, p->to, w) != 0;
+}
+
+bool ins_use_ok(Fn* fn, Ins* i, Ref r, int w) {
+    Ext e;
+    if (i->op == Ocopy && uwl(fn, i->to, w))
+        return true;
+    if (decode_ext(i->op, &e)) {
+        if (e.usew <= w)
+            return true;
+        return uwl(fn, i->to, w) != 0;
+    }
+    if (i->op == Oand) {
+        Ref rc;
+        if (req(r, i->arg[0])) {
+            rc = i->arg[1];
+        } else {
+            assert(req(r, i->arg[1]));
+            rc = i->arg[0];
+        }
+        int64_t v;
+        return isconbits(fn, rc, &v) && bitwidth(static_cast<uint64_t>(v)) <= w;
+    }
+    return false;
+}
+
+int uwl(Fn* fn, Ref r, int w) {
+    assert(rtype(r) == RTmp);
+    Tmp* t = &fn->tmp[r.val];
+    for (Use* u = &t->use[0]; u < &t->use[t->nuse]; ++u) {
+        bool ok;
+        switch (u->type) {
+            case Use::UPhi:
+                ok = phi_use_ok(fn, u->u.phi, w);
+                break;
+            case Use::UIns:
+                assert(u->u.ins);
+                ok = ins_use_ok(fn, u->u.ins, r, w);
+                break;
+            default:
+                ok = false;
+                break;
+        }
+        if (!ok)
+            return 0;
+    }
+    return 1;
+}
+
+/* no more than w bits are used */
+int usewidthle(Fn* fn, Ref r, int w) {
+    return walk_phi_memo(fn, r, w, uwl);
+}
+
+int dwl(Fn* fn, Ref r, int w) {
+    int64_t v;
+    if (isconbits(fn, r, &v) && bitwidth(static_cast<uint64_t>(v)) <= w)
+        return 1;
+    if (w <= 0)
+        return 0;
+    if (rtype(r) != RTmp)
+        return 0;
+    Tmp* t = &fn->tmp[r.val];
+    if (t->cls != Kw)
+        return 0;
+
+    if (!t->def) {
+        Phi* p = fn->rpo[t->bid]->phi;
+        for (; p; p = p->link)
+            if (req(p->to, r))
+                break;
+        assert(p);
+        if (p->visit && p->visit <= w)
+            return 1;
+        p->visit = w;
+        for (uint n = 0; n < p->narg; ++n)
+            if (!dwl(fn, p->arg[n], w))
+                return 0;
+        return 1;
+    }
+
+    Ins* i = t->def;
+    if (i->op == Ocopy)
+        return dwl(fn, i->arg[0], w);
+
+    if (i->op == Oshr || i->op == Osar) {
+        if (isconbits(fn, i->arg[1], &v) && 0 < v && v <= 32) {
+            if (i->op == Oshr && w + v >= 32)
+                return 1;
+            if (w < 32) {
+                int cap = (i->op == Osar) ? 31 : 32;
+                w = std::min(cap, static_cast<int>(w + v));
+            }
+        }
+        return dwl(fn, i->arg[0], w);
+    }
+
+    int x;
+    if (iscmp(i->op, &x, &x))
+        return w >= 1;
+
+    if (i->op == Oand)
+        return (dwl(fn, i->arg[0], w) || dwl(fn, i->arg[1], w)) ? 1 : 0;
+
+    if (i->op == Oor || i->op == Oxor)
+        return (dwl(fn, i->arg[0], w) && dwl(fn, i->arg[1], w)) ? 1 : 0;
+
+    Ext e;
+    if (decode_ext(i->op, &e)) {
+        if (e.zext && e.usew <= w)
+            return 1;
+        w = std::min(w, static_cast<int>(e.nopw));
+        return dwl(fn, i->arg[0], w);
+    }
+
+    return 0;
+}
+
+/* is the ref narrower than w bits */
+int defwidthle(Fn* fn, Ref r, int w) {
+    return walk_phi_memo(fn, r, w, dwl);
+}
+
+int isw1(Fn* fn, Ref r) {
+    return defwidthle(fn, r, 1);
+}
+
+bool phieq(Phi* pa, Phi* pb) {
+    assert(pa->narg == pb->narg);
+    for (uint n = 0; n < pa->narg; ++n)
+        if (!req(pa->arg[n], phiarg(pb, pa->blk[n])))
+            return false;
+    return true;
+}
+
+}  // namespace
+
+Ref copyref(Ctx* ctx, Fn* fn, Blk* b, Ins* i) {
+    static const bits extcpy[] = {
+        /*WFull*/ 0,
+        /*Wsb*/ BIT(Tmp::Wsb) | BIT(Tmp::Wsh) | BIT(Tmp::Wsw),
+        /*Wub*/ BIT(Tmp::Wub) | BIT(Tmp::Wuh) | BIT(Tmp::Wuw),
+        /*Wsh*/ BIT(Tmp::Wsh) | BIT(Tmp::Wsw),
+        /*Wuh*/ BIT(Tmp::Wuh) | BIT(Tmp::Wuw),
+        /*Wsw*/ BIT(Tmp::Wsw),
+        /*Wuw*/ BIT(Tmp::Wuw),
+    };
+    MAKESURE(extcpy_covers_all_widths, sizeof(extcpy) / sizeof(extcpy[0]) == Tmp::Wuw + 1);
+
+    if (i->op == Ocopy)
+        return i->arg[0];
+
+    const Op& od = optab[i->op];
+
+    if (od.hasid && KBASE(i->cls) == 0 && req(i->arg[1], ctx->gvn_con01[od.idval]) &&
+        (!od.cmpeqwl || isw1(fn, i->arg[0])))
+        return i->arg[0];
+
+    if (od.idemp && req(i->arg[0], i->arg[1]))
+        return i->arg[0];
+
+    if ((od.cmpeqwl || od.cmplgtewl) && req(i->arg[0], i->arg[1]))
+        return ctx->gvn_con01[od.eqval];
+
+    int z;
+    if (od.cmpeqwl && req(i->arg[1], Ref::con_z()) && zeroval(fn, b, i->arg[0], argcls(i, 0), &z))
+        return ctx->gvn_con01[od.eqval ^ z ^ 1];
+
+    int64_t v;
+    if (i->op == Oand && isconbits(fn, i->arg[1], &v) && v > 0 && ((v + 1) & v) == 0 &&
+        defwidthle(fn, i->arg[0], bitwidth(static_cast<uint64_t>(v))))
+        return i->arg[0];
+
+    if (i->cls == Kw && (i->op == Oextsw || i->op == Oextuw))
+        return i->arg[0];
+
+    Ext e;
+    if (decode_ext(i->op, &e) && rtype(i->arg[0]) == RTmp) {
+        Tmp* t = &fn->tmp[i->arg[0].val];
+        assert(KBASE(t->cls) == 0);
+
+        if (KWIDE(i->cls) > KWIDE(t->cls))
+            return Ref::none();
+
+        int w = Tmp::Wsb + (static_cast<int>(i->op) - Oextsb);
+        if (BIT(w) & extcpy[t->width])
+            return i->arg[0];
+
+        if ((!t->def || !ispar(t->def->op)) && usewidthle(fn, i->to, e.usew))
+            return i->arg[0];
+
+        if (defwidthle(fn, i->arg[0], e.nopw))
+            return i->arg[0];
+    }
+
+    return Ref::none();
+}
+
+Ref phicopyref(Ctx* ctx, Fn* fn, Blk* b, Phi* p) {
+    Ref r = Ref::none();
+    uint n = 0;
+    for (; n < p->narg; ++n)
+        if (!req(p->arg[n], p->to)) {
+            if (req(r, Ref::none()))
+                r = p->arg[n];
+            else if (!req(p->arg[n], r))
+                break;
+        }
+    if (n == p->narg)
+        return r;
+
+    for (Phi* p1 = b->phi; p1 != p; p1 = p1->link) {
+        assert(p1);
+        if (phieq(p1, p))
+            return p1->to;
+    }
+
+    Blk* d = b->idom;
+    if (p->narg != 2 || d->jmp.type != Jjnz || !isw1(fn, d->jmp.arg))
+        return Ref::none();
+
+    Blk* s[2] = {nullptr, nullptr};
+    for (uint k = 0; k < 2; ++k)
+        for (uint c = 0; c < 2; ++c)
+            if (req(p->arg[k], ctx->gvn_con01[c]))
+                s[c] = p->blk[k];
+
+    if (d->s1 == s[1] && d->s2 == s[0] && d->s1->jmp.type == Jjmp && d->s2->jmp.type == Jjmp)
+        return d->jmp.arg;
+
+    return Ref::none();
+}
+
+void narrowpars(Ctx* ctx, Fn* fn) {
+    bool has_loop = false;
+    for (Blk* b = fn->start; b; b = b->link)
+        if (b->loop > 1) {
+            has_loop = true;
+            break;
+        }
+    if (!has_loop)
+        return;
+
+    Blk* b = fn->start;
+
+    uint npar = 0;
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+        if (!ispar(i->op))
+            break;
+        ++npar;
+    }
+    if (npar == 0)
+        return;
+
+    uint nins = b->nins + npar;
+    Ins* ins = static_cast<Ins*>(vnew(ctx, nins, sizeof(Ins), PFn));
+    icpy(ins, b->ins, npar);
+    icpy(ins + 2 * npar, b->ins + npar, b->nins - npar);
+    b->ins = ins;
+    b->nins = nins;
+
+    for (Ins* i = b->ins; i < &b->ins[b->nins]; ++i) {
+        if (!ispar(i->op))
+            break;
+        Ins extins = {};
+        extins.op = Onop;
+        if (i->cls == Kw && usewidthle(fn, i->to, 16)) {
+            extins.op = usewidthle(fn, i->to, 8) ? Oextub : Oextuh;
+            Ref r = newtmp(ctx, "vw", i->cls, fn);
+            extins.cls = i->cls;
+            extins.to = i->to;
+            extins.arg[0] = r;
+            i->to = r;
+        }
+        *(i + npar) = extins;
+    }
+}
+
+}  // namespace rcc