Skip to content

PS2 games in the browser: static recompilation to WebAssembly with a native runtime

C++
11.1 KB
Raw Blame
#include "analysis.hpp"

#include <algorithm>
#include <deque>

namespace recomp {

namespace {

constexpr std::size_t kTentativeLimit = 16384;

class Explorer {
public:
    Explorer(const Image &image, Program &program) : image_(image), p_(program) {}

    bool valid_target(std::uint32_t address) const {
        return (address & 3u) == 0 && address >= p_.base && address < p_.end && image_.executable(address);
    }

    void strong(std::uint32_t address, bool function) {
        if (!valid_target(address)) return;
        if (function) p_.functions.insert(address);
        p_.entries.insert(address);
        if (!p_.is_code(address)) queue_.push_back(address);
    }

    void drain() {
        while (!queue_.empty()) {
            const std::uint32_t start = queue_.front();
            queue_.pop_front();
            walk(start);
        }
    }

    bool tentative(std::uint32_t start) {
        std::deque<std::uint32_t> pending{start};
        std::set<std::uint32_t> seen;
        while (!pending.empty()) {
            std::uint32_t pc = pending.front();
            pending.pop_front();
            while (true) {
                if (!valid_target(pc)) return false;
                if (p_.is_code(pc) || seen.count(pc)) break;
                if (seen.size() > kTentativeLimit) return false;
                seen.insert(pc);
                const Insn insn = decode(*image_.word(pc), pc);
                if (insn.op == Op::Invalid) return false;
                const Flow f = flow(insn.op);
                if (f == Flow::Stop) break;
                if (f == Flow::None) { pc += 4; continue; }
                if (!valid_target(pc + 4) || decode(*image_.word(pc + 4), pc + 4).op == Op::Invalid) return false;
                if (has_delay_slot(decode(*image_.word(pc + 4), pc + 4).op)) return false;
                seen.insert(pc + 4);
                if (f == Flow::Branch || f == Flow::BranchLikely || (f == Flow::Jump && !p_.dynamic.count(pc))) {
                    // Fixed-address modules can tail-call a routine in the main
                    // executable. Like an external jal, that does not make the
                    // caller invalid; dispatch resolves the target at run time.
                    if (!valid_target(insn.branch_target_of())) {
                        if (f == Flow::Jump) break;
                        return false;
                    }
                    pending.push_back(insn.branch_target_of());
                }
                if (f == Flow::Jump || f == Flow::JumpRegister) break;
                pc += 8;
            }
        }
        return true;
    }

private:
    void walk(std::uint32_t pc) {
        while (valid_target(pc) && !p_.is_code(pc)) {
            const Insn insn = decode(*image_.word(pc), pc);
            if (insn.op == Op::Invalid) return;
            mark(pc);
            const Flow f = flow(insn.op);
            if (f == Flow::Stop) return;
            if (insn.op == Op::Syscall) p_.entries.insert(pc + 4);
            if (f == Flow::None) { pc += 4; continue; }
            if (valid_target(pc + 4) && decode(*image_.word(pc + 4), pc + 4).op != Op::Invalid) mark(pc + 4);
            switch (f) {
            case Flow::Branch:
            case Flow::BranchLikely:
                local(insn.branch_target_of(), pc);
                break;
            case Flow::Jump:
                if (!p_.dynamic.count(pc)) local(insn.branch_target_of(), pc);
                return;
            case Flow::Call:
                if (!p_.dynamic.count(pc)) strong(insn.branch_target_of(), true);
                p_.entries.insert(pc + 8);
                break;
            case Flow::CallRegister:
                p_.entries.insert(pc + 8);
                break;
            case Flow::JumpRegister:
                return;
            default:
                break;
            }
            pc += 8;
        }
    }

    void local(std::uint32_t target, std::uint32_t from) {
        if (!valid_target(target)) return;
        if (target <= from) p_.entries.insert(target);
        if (!p_.is_code(target)) queue_.push_back(target);
    }

    void mark(std::uint32_t pc) { p_.code[(pc - p_.base) >> 2] = 1; }

    const Image &image_;
    Program &p_;
    std::deque<std::uint32_t> queue_;
};

std::vector<std::uint32_t> address_constants(const Image &image, const Program &p) {
    std::vector<std::uint32_t> found;
    for (std::uint32_t pc = p.base; pc < p.end; pc += 4) {
        if (!p.is_code(pc)) continue;
        const Insn lui = decode(*image.word(pc), pc);
        if (lui.op != Op::Lui) continue;
        const bool saved = (lui.rt() >= 16 && lui.rt() <= 23) || lui.rt() == 30;
        std::uint32_t stop = pc + (saved ? 1024 : 160);
        for (std::uint32_t next = pc + 4; next < stop && p.is_code(next); next += 4) {
            const Insn insn = decode(*image.word(next), next);
            if ((insn.op == Op::Addiu || insn.op == Op::Ori) && insn.rs() == lui.rt()) {
                const std::uint32_t high = lui.uimm() << 16;
                found.push_back(insn.op == Op::Addiu ? high + static_cast<std::uint32_t>(insn.simm()) : high | insn.uimm());
            }
            if (insn.rt() == lui.rt() && insn.op == Op::Lui) break;
            const Flow f = flow(insn.op);
            if (f == Flow::Jump || f == Flow::JumpRegister || f == Flow::Stop) stop = std::min(stop, std::max(pc + 40, next + 8));
        }
    }
    return found;
}

std::uint32_t constant_in(const Image &image, const Program &p, std::uint32_t from, std::uint32_t reg) {
    for (std::uint32_t pc = from - 4; from - pc <= 64 && p.is_code(pc); pc -= 4) {
        const Insn low = decode(*image.word(pc), pc);
        if ((low.op != Op::Addiu && low.op != Op::Ori) || low.rt() != reg || low.rs() != reg) continue;
        for (std::uint32_t at = pc - 4; pc - at <= 64 && p.is_code(at); at -= 4) {
            const Insn lui = decode(*image.word(at), at);
            if (lui.op != Op::Lui || lui.rt() != reg) continue;
            const std::uint32_t high = lui.uimm() << 16;
            return low.op == Op::Addiu ? high + static_cast<std::uint32_t>(low.simm()) : high | low.uimm();
        }
        return 0;
    }
    return 0;
}

std::uint32_t scale_of(const Image &image, const Program &p, std::uint32_t from, std::uint32_t reg) {
    for (std::uint32_t pc = from - 4; from - pc <= 64 && p.is_code(pc); pc -= 4) {
        const Insn insn = decode(*image.word(pc), pc);
        if (insn.op == Op::Sll && insn.rd() == reg) return std::clamp<std::uint32_t>(insn.sa(), 2, 6);
    }
    return 2;
}

std::vector<std::uint32_t> computed_branches(const Image &image, const Program &p) {
    std::vector<std::uint32_t> found;
    for (std::uint32_t pc = p.base; pc < p.end; pc += 4) {
        if (!p.is_code(pc)) continue;
        const Insn jr = decode(*image.word(pc), pc);
        if (jr.op != Op::Jr || jr.rs() == 31) continue;
        for (std::uint32_t at = pc - 4; pc - at <= 64 && p.is_code(at); at -= 4) {
            const Insn add = decode(*image.word(at), at);
            if ((add.op != Op::Addu && add.op != Op::Daddu) || add.rd() != jr.rs()) continue;
            const std::uint32_t regs[2] = {add.rs(), add.rt()};
            for (int i = 0; i < 2; ++i) {
                const std::uint32_t table = constant_in(image, p, at, regs[i]);
                if (!table || (table & 3u) || !image.word(table)) continue;
                const std::uint32_t stride = 1u << scale_of(image, p, at, regs[i ^ 1]);
                std::uint32_t last = table;
                while (last < table + 64 * stride && image.word(last)) {
                    const Flow f = flow(decode(*image.word(last), last).op);
                    if (f == Flow::JumpRegister || f == Flow::Stop) break;
                    last += 4;
                }
                for (std::uint32_t slot = table; slot <= last; slot += stride) found.push_back(slot);
            }
            break;
        }
    }
    return found;
}

std::vector<std::uint32_t> frame_starts(const Image &image, std::uint32_t begin, std::uint32_t end) {
    std::vector<std::uint32_t> found;
    for (std::uint32_t pc = begin + 8; pc < end; pc += 4) {
        const std::uint32_t w = image.word(pc).value_or(0);
        if ((w & 0xFFFF8000u) != 0x27BD8000u && (w & 0xFFFF8000u) != 0x67BD8000u) continue;
        std::uint32_t at = pc - 4;
        while (at > begin + 4 && pc - at < 20 && image.word(at).value_or(1) == 0) at -= 4;
        if (image.word(at).value_or(0) == 0x03E00008u || image.word(at - 4).value_or(0) == 0x03E00008u) found.push_back(pc);
    }
    return found;
}

}

Program analyse(const Image &image, const std::vector<std::uint32_t> &extra_entries, const std::set<std::uint32_t> &dynamic) {
    Program p;
    p.dynamic = dynamic;
    p.base = UINT32_MAX;
    for (const auto &segment : image.segments()) {
        if (!segment.executable) continue;
        p.base = std::min(p.base, segment.address & ~3u);
        p.end = std::max<std::uint32_t>(p.end, segment.address + static_cast<std::uint32_t>(segment.bytes.size()));
    }
    p.end &= ~3u;
    p.code.assign((p.end - p.base) >> 2, 0);

    Explorer explorer(image, p);
    explorer.strong(image.entry(), true);
    for (const auto &[address, name] : image.symbols()) explorer.strong(address, true);
    for (std::uint32_t address : extra_entries) explorer.strong(address, true);
    explorer.drain();

    std::uint32_t text_begin = p.end, text_end = p.base;
    for (std::uint32_t pc = p.base; pc < p.end; pc += 4) {
        if (p.is_code(pc)) {
            text_begin = std::min(text_begin, pc);
            text_end = pc + 4;
        }
    }
    if (image.text().second > image.text().first) {
        text_begin = std::min(text_begin, image.text().first);
        text_end = std::max(text_end, image.text().second);
    }

    for (int round = 0; round < 8; ++round) {
        std::vector<std::uint32_t> candidates = address_constants(image, p);
        const std::vector<std::uint32_t> branches = computed_branches(image, p);
        candidates.insert(candidates.end(), branches.begin(), branches.end());
        const std::vector<std::uint32_t> frames = frame_starts(image, text_begin, text_end);
        candidates.insert(candidates.end(), frames.begin(), frames.end());
        for (const auto &segment : image.segments())
            for (std::size_t offset = 0; offset + 4 <= segment.bytes.size(); offset += 4)
                candidates.push_back(*image.word(segment.address + static_cast<std::uint32_t>(offset)));
        std::sort(candidates.begin(), candidates.end());
        candidates.erase(std::unique(candidates.begin(), candidates.end()), candidates.end());

        std::size_t added = 0;
        for (std::uint32_t target : candidates) {
            if (target < text_begin || target >= text_end || !explorer.valid_target(target)) continue;
            if (p.entries.count(target) || p.rejected.count(target)) continue;
            if (p.is_code(target) || explorer.tentative(target)) {
                p.entries.insert(target);
                if (!p.is_code(target)) explorer.strong(target, false);
                ++added;
            } else {
                p.rejected.insert(target);
            }
        }
        explorer.drain();
        if (!added) break;
    }
    return p;
}

}