// SPDX-License-Identifier: MIT
//
// SSA conversion
// Copyright (C) 2005 Luc Van Oostenryck
//

#include <assert.h>
#include "ssa.h"
#include "lib.h"
#include "sset.h"
#include "dominate.h"
#include "flowgraph.h"
#include "linearize.h"
#include "flow.h"                       // for convert_load_instruction()


// Is it possible and desirable for this to be promoted to a pseudo?
static inline bool is_promotable(struct symbol *type)
{
        struct symbol *member;
        int bf_seen;
        int nbr;

        if (type->type == SYM_NODE)
                type = type->ctype.base_type;
        switch (type->type) {
        case SYM_ENUM:
        case SYM_BITFIELD:
        case SYM_PTR:
        case SYM_RESTRICT:      // OK, always integer types
                return 1;
        case SYM_STRUCT:
                // we allow a single scalar field
                // but a run of bitfields count for 1
                nbr = 0;
                bf_seen = 0;
                FOR_EACH_PTR(type->symbol_list, member) {
                        if (is_bitfield_type(member)) {
                                if (bf_seen)
                                        continue;
                                bf_seen = 1;
                        } else {
                                bf_seen = 0;
                        }
                        if (!is_scalar_type(member))
                                return 0;
                        if (nbr++)
                                return 0;
                } END_FOR_EACH_PTR(member);
                if (bf_seen && (type->bit_size > long_ctype.bit_size))
                        return 0;
                return 1;
        case SYM_UNION:
                // FIXME: should be like struct but has problem
                //        when used with/for type cohercion
                // -----> OK if only same sized integral types
                FOR_EACH_PTR(type->symbol_list, member) {
                        if (member->bit_size != type->bit_size)
                                return 0;
                        if (!is_integral_type(member))
                                return 0;
                } END_FOR_EACH_PTR(member);
                return 1;
        default:
                break;
        }
        if (type->ctype.base_type == &int_type)
                return 1;
        if (type->ctype.base_type == &fp_type)
                return 1;
        return 0;
}

static bool insn_before(struct instruction *a, struct instruction *b)
{
        struct basic_block *bb = a->bb;
        struct instruction *insn;

        assert(b->bb == bb);
        FOR_EACH_PTR(bb->insns, insn) {
                if (insn == a)
                        return true;
                if (insn == b)
                        return false;
        } END_FOR_EACH_PTR(insn);
        assert(0);
}

static void kill_store(struct instruction *insn)
{
        remove_use(&insn->src);
        remove_use(&insn->target);
        insn->bb = NULL;
}

static void rewrite_local_var(struct basic_block *bb, pseudo_t addr, int nbr_stores, int nbr_uses)
{
        struct instruction *insn;
        pseudo_t val = NULL;

        if (!bb)
                return;

        FOR_EACH_PTR(bb->insns, insn) {

                if (!insn->bb || insn->src != addr)
                        continue;
                switch (insn->opcode) {
                case OP_LOAD:
                        if (!val)
                                val = undef_pseudo();
                        convert_load_instruction(insn, val);
                        break;
                case OP_STORE:
                        val = insn->target;
                        // can't use kill_instruction() unless
                        // we add a fake user to val
                        kill_store(insn);
                        break;
                }
        } END_FOR_EACH_PTR(insn);
}

static bool rewrite_single_store(struct instruction *store)
{
        pseudo_t addr = store->src;
        struct pseudo_user *pu;

        FOR_EACH_PTR(addr->users, pu) {
                struct instruction *insn = pu->insn;

                if (insn->opcode != OP_LOAD)
                        continue;

                // Let's try to replace the value of the load
                // by the value from the store. This is only valid
                // if the store dominate the load.

                if (insn->bb == store->bb) {
                        // the load and the store are in the same BB
                        // we can convert if the load is after the store.
                        if (!insn_before(store, insn))
                                continue;
                } else if (!domtree_dominates(store->bb, insn->bb)) {
                        // we can't convert this load
                        continue;
                }

                // OK, we can rewrite this load

                // undefs ?

                convert_load_instruction(insn, store->target);
        } END_FOR_EACH_PTR(pu);

        // is there some unconverted loads?
        if (pseudo_user_list_size(addr->users) > 1)
                return false;

        kill_store(store);
        return true;
}

static struct sset *processed;

// we would like to know:
// is there one or more stores?
// are all loads & stores local/done in a single block?
static void ssa_convert_one_var(struct entrypoint *ep, struct symbol *var)
{
        struct basic_block_list *alpha = NULL;
        struct basic_block_list *idf = NULL;
        struct basic_block *samebb = NULL;
        struct instruction *store = NULL;
        struct basic_block *bb;
        struct pseudo_user *pu;
        unsigned long mod = var->ctype.modifiers;
        bool local = true;
        int nbr_stores = 0;
        int nbr_uses   = 0;
        pseudo_t addr;

        /* Never used as a symbol? */
        addr = var->pseudo;
        if (!addr)
                return;

        /* We don't do coverage analysis of volatiles.. */
        if (mod & MOD_VOLATILE)
                return;

        /* ..and symbols with external visibility need more care */
        mod &= (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
        if (mod)
                goto external_visibility;

        if (!is_promotable(var))
                return;

        // 1) insert in the worklist all BBs that may modify var
        sset_reset(processed);
        FOR_EACH_PTR(addr->users, pu) {
                struct instruction *insn = pu->insn;
                struct basic_block *bb = insn->bb;

                switch (insn->opcode) {
                case OP_STORE:
                        nbr_stores++;
                        store = insn;
                        if (!sset_testset(processed, bb->nr))
                                add_bb(&alpha, bb);
                        /* fall through */
                case OP_LOAD:
                        if (local) {
                                if (!samebb)
                                        samebb = bb;
                                else if (samebb != bb)
                                        local = false;
                        }
                        nbr_uses++;
                        break;
                case OP_SYMADDR:
                        mod |= MOD_ADDRESSABLE;
                        goto external_visibility;
                default:
                        warning(var->pos, "symbol '%s' pseudo used in unexpected way",
                                show_ident(var->ident));
                }
        } END_FOR_EACH_PTR(pu);

        if (nbr_stores == 1) {
                if (rewrite_single_store(store))
                        return;
        }

        // if all uses are local to a single block
        // they can easily be rewritten and doesn't need phi-nodes
        // FIXME: could be done for extended BB too
        if (local) {
                rewrite_local_var(samebb, addr, nbr_stores, nbr_uses);
                return;
        }

        idf_compute(ep, &idf, alpha);
        FOR_EACH_PTR(idf, bb) {
                struct instruction *node = insert_phi_node(bb, var);
                node->phi_var = var->pseudo;
        } END_FOR_EACH_PTR(bb);
        var->torename = 1;

external_visibility:
        if (mod & (MOD_NONLOCAL | MOD_STATIC))
                return;
        kill_dead_stores(ep, addr, !mod);
}

static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var)
{
        do {
                pseudo_t val = phi_map_lookup(bb->phi_map, var);
                if (val)
                        return val;
        } while ((bb = bb->idom));
        return undef_pseudo();
}

static struct instruction_list *phis_all;
static struct instruction_list *phis_used;

static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn)
{
        struct symbol *var;
        pseudo_t addr;
        pseudo_t val;

        switch (insn->opcode) {
        case OP_STORE:
                addr = insn->src;
                if (addr->type != PSEUDO_SYM)
                        break;
                var = addr->sym;
                if (!var || !var->torename)
                        break;
                phi_map_update(&bb->phi_map, var, insn->target);
                kill_store(insn);
                break;
        case OP_LOAD:
                addr = insn->src;
                if (addr->type != PSEUDO_SYM)
                        break;
                var = addr->sym;
                if (!var || !var->torename)
                        break;
                val = lookup_var(bb, var);
                convert_load_instruction(insn, val);
                break;
        case OP_PHI:
                var = insn->type;
                if (!var || !var->torename)
                        break;
                phi_map_update(&bb->phi_map, var, insn->target);
                add_instruction(&phis_all, insn);
                break;
        }
}

static void ssa_rename_insns(struct entrypoint *ep)
{
        struct basic_block *bb;

        FOR_EACH_PTR(ep->bbs, bb) {
                struct instruction *insn;
                FOR_EACH_PTR(bb->insns, insn) {
                        if (!insn->bb)
                                continue;
                        ssa_rename_insn(bb, insn);
                } END_FOR_EACH_PTR(insn);
        } END_FOR_EACH_PTR(bb);
}

static void mark_phi_used(pseudo_t val)
{
        struct instruction *node;

        if (val->type != PSEUDO_REG)
                return;
        node = val->def;
        if (node->opcode != OP_PHI)
                return;
        if (node->used)
                return;
        node->used = 1;
        add_instruction(&phis_used, node);
}

static void ssa_rename_phi(struct instruction *insn)
{
        struct basic_block *par;
        struct symbol *var;

        if (!insn->phi_var)
                return;
        var = insn->phi_var->sym;
        if (!var->torename)
                return;
        FOR_EACH_PTR(insn->bb->parents, par) {
                struct instruction *term = delete_last_instruction(&par->insns);
                pseudo_t val = lookup_var(par, var);
                pseudo_t phi = alloc_phi(par, val, var);
                phi->ident = var->ident;
                add_instruction(&par->insns, term);
                use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi));
                mark_phi_used(val);
        } END_FOR_EACH_PTR(par);
}

static void ssa_rename_phis(struct entrypoint *ep)
{
        struct instruction *phi;

        phis_used = NULL;
        FOR_EACH_PTR(phis_all, phi) {
                if (has_users(phi->target)) {
                        phi->used = 1;
                        add_instruction(&phis_used, phi);
                }
        } END_FOR_EACH_PTR(phi);

        FOR_EACH_PTR(phis_used, phi) {
                if (!phi->bb)
                        continue;
                ssa_rename_phi(phi);
        } END_FOR_EACH_PTR(phi);
}

void ssa_convert(struct entrypoint *ep)
{
        struct basic_block *bb;
        pseudo_t pseudo;
        int first, last;

        // calculate the number of BBs
        first = ep->entry->bb->nr;
        last = first;
        FOR_EACH_PTR(ep->bbs, bb) {
                int nr = bb->nr;
                if (nr > last)
                        last = nr;
        } END_FOR_EACH_PTR(bb);

        processed = sset_init(first, last);

        // try to promote memory accesses to pseudos
        FOR_EACH_PTR(ep->accesses, pseudo) {
                ssa_convert_one_var(ep, pseudo->sym);
        } END_FOR_EACH_PTR(pseudo);

        // rename the converted accesses
        phis_all = phis_used = NULL;
        ssa_rename_insns(ep);
        ssa_rename_phis(ep);
}