/*
 * Storage - associate pseudos with "storage" that keeps them alive
 * between basic blocks.  The aim is to be able to turn as much of
 * the global storage allocation problem as possible into a local
 * per-basic-block one.
 *
 * Copyright (C) 2004 Linus Torvalds
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "symbol.h"
#include "expression.h"
#include "linearize.h"
#include "storage.h"

ALLOCATOR(storage, "storages");
ALLOCATOR(storage_hash, "storage hash");

#define MAX_STORAGE_HASH 64
static struct storage_hash_list *storage_hash_table[MAX_STORAGE_HASH];

static inline unsigned int storage_hash(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
        unsigned hash = hashval(bb) + hashval(pseudo) + hashval(inout);
        hash += hash / MAX_STORAGE_HASH;
        return hash & (MAX_STORAGE_HASH-1);
}

static int hash_list_cmp(const void *_a, const void *_b)
{
        const struct storage_hash *a = _a;
        const struct storage_hash *b = _b;
        if (a->pseudo != b->pseudo)
                return a->pseudo < b->pseudo ? -1 : 1;
        return 0;
}

static void sort_hash_list(struct storage_hash_list **listp)
{
        sort_list((struct ptr_list **)listp, hash_list_cmp);
}

struct storage_hash_list *gather_storage(struct basic_block *bb, enum inout_enum inout)
{
        int i;
        struct storage_hash *entry, *prev;
        struct storage_hash_list *list = NULL;

        for (i = 0; i < MAX_STORAGE_HASH; i++) {
                struct storage_hash *hash;
                FOR_EACH_PTR(storage_hash_table[i], hash) {
                        if (hash->bb == bb && hash->inout == inout)
                                add_ptr_list(&list, hash);
                } END_FOR_EACH_PTR(hash);
        }
        sort_hash_list(&list);

        prev = NULL;
        FOR_EACH_PTR(list, entry) {
                if (prev && entry->pseudo == prev->pseudo) {
                        assert(entry == prev);
                        DELETE_CURRENT_PTR(entry);
                }
                prev = entry;
        } END_FOR_EACH_PTR(entry);
        PACK_PTR_LIST(&list);
        return list;
}

static void name_storage(void)
{
        int i;
        int name = 0;

        for (i = 0; i < MAX_STORAGE_HASH; i++) {
                struct storage_hash *hash;
                FOR_EACH_PTR(storage_hash_table[i], hash) {
                        struct storage *storage = hash->storage;
                        if (storage->name)
                                continue;
                        storage->name = ++name;
                } END_FOR_EACH_PTR(hash);
        }
}

struct storage *lookup_storage(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
        struct storage_hash_list *list = storage_hash_table[storage_hash(bb,pseudo,inout)];
        struct storage_hash *hash;

        FOR_EACH_PTR(list, hash) {
                if (hash->bb == bb && hash->pseudo == pseudo && hash->inout == inout)
                        return hash->storage;
        } END_FOR_EACH_PTR(hash);
        return NULL;
}

void add_storage(struct storage *storage, struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
        struct storage_hash_list **listp = storage_hash_table + storage_hash(bb,pseudo,inout);
        struct storage_hash *hash = alloc_storage_hash(storage);

        hash->bb = bb;
        hash->pseudo = pseudo;
        hash->inout = inout;

        add_ptr_list(listp, hash);
}


static int storage_hash_cmp(const void *_a, const void *_b)
{
        const struct storage_hash *a = _a;
        const struct storage_hash *b = _b;
        struct storage *aa = a->storage;
        struct storage *bb = b->storage;

        if (a->bb != b->bb)
                return a->bb < b->bb ? -1 : 1;
        if (a->inout != b->inout)
                return a->inout < b->inout ? -1 : 1;
        if (aa->type != bb->type)
                return aa->type < bb->type ? -1 : 1;
        if (aa->regno != bb->regno)
                return aa->regno < bb->regno ? -1 : 1;
        return 0;
}

static void vrfy_storage(struct storage_hash_list **listp)
{
        struct storage_hash *entry, *last;

        sort_list((struct ptr_list **)listp, storage_hash_cmp);
        last = NULL;
        FOR_EACH_PTR(*listp, entry) {
                if (last) {
                        struct storage *a = last->storage;
                        struct storage *b = entry->storage;
                        if (a == b)
                                continue;
                        if (last->bb == entry->bb
                            && last->inout == entry->inout
                            && a->type != REG_UDEF
                            && a->type == b->type
                            && a->regno == b->regno) {
                                printf("\t BAD: same storage as %s in %p: %s (%s and %s)\n",
                                        last->inout == STOR_IN ? "input" : "output",
                                        last->bb,
                                        show_storage(a),
                                        show_pseudo(last->pseudo),
                                        show_pseudo(entry->pseudo));
                        }
                }
                last = entry;
        } END_FOR_EACH_PTR(entry);
}

void free_storage(void)
{
        int i;

        for (i = 0; i < MAX_STORAGE_HASH; i++) {
                vrfy_storage(storage_hash_table + i);
                free_ptr_list(storage_hash_table + i);
        }
}

const char *show_storage(struct storage *s)
{
        static char buffer[1024];
        if (!s)
                return "none";
        switch (s->type) {
        case REG_REG:
                sprintf(buffer, "reg%d (%d)", s->regno, s->name);
                break;
        case REG_STACK:
                sprintf(buffer, "%d(SP) (%d)", s->offset, s->name);
                break;
        case REG_ARG:
                sprintf(buffer, "ARG%d (%d)", s->regno, s->name);
                break;
        default:
                sprintf(buffer, "%d:%d (%d)", s->type, s->regno, s->name);
                break;
        }
        return buffer;
}

/*
 * Combine two storage allocations into one.
 *
 * We just randomly pick one over the other, and replace
 * the other uses.
 */
static struct storage * combine_storage(struct storage *src, struct storage *dst)
{
        struct storage **usep;

        /* Remove uses of "src_storage", replace with "dst" */
        FOR_EACH_PTR(src->users, usep) {
                assert(*usep == src);
                *usep = dst;
                add_ptr_list(&dst->users, usep);
        } END_FOR_EACH_PTR(usep);

        /* Mark it unused */
        src->type = REG_BAD;
        src->users = NULL;
        return dst;
}

static void set_up_bb_storage(struct basic_block *bb)
{
        struct basic_block *child;

        FOR_EACH_PTR(bb->children, child) {
                pseudo_t pseudo;
                FOR_EACH_PTR(child->needs, pseudo) {
                        struct storage *child_in, *parent_out;

                        parent_out = lookup_storage(bb, pseudo, STOR_OUT);
                        child_in = lookup_storage(child, pseudo, STOR_IN);

                        if (parent_out) {
                                if (!child_in) {
                                        add_storage(parent_out, child, pseudo, STOR_IN);
                                        continue;
                                }
                                if (parent_out == child_in)
                                        continue;
                                combine_storage(parent_out, child_in);
                                continue;
                        }
                        if (child_in) {
                                add_storage(child_in, bb, pseudo, STOR_OUT);
                                continue;
                        }
                        parent_out = alloc_storage();
                        add_storage(parent_out, bb, pseudo, STOR_OUT);
                        add_storage(parent_out, child, pseudo, STOR_IN);
                } END_FOR_EACH_PTR(pseudo);
        } END_FOR_EACH_PTR(child);
}

static void set_up_argument_storage(struct entrypoint *ep, struct basic_block *bb)
{
        pseudo_t arg;

        FOR_EACH_PTR(bb->needs, arg) {
                struct storage *storage = alloc_storage();

                /* FIXME! Totally made-up argument passing conventions */
                if (arg->type == PSEUDO_ARG) {
                        storage->type = REG_ARG;
                        storage->regno = arg->nr;
                }
                add_storage(storage, bb, arg, STOR_IN);
        } END_FOR_EACH_PTR(arg);
}

/*
 * One phi-source may feed multiple phi nodes. If so, combine
 * the storage output for this bb into one entry to reduce
 * storage pressure.
 */
static void combine_phi_storage(struct basic_block *bb)
{
        struct instruction *insn;
        FOR_EACH_PTR(bb->insns, insn) {
                struct instruction *phi;
                struct storage *last;

                if (!insn->bb || insn->opcode != OP_PHISOURCE)
                        continue;
                last = NULL;
                FOR_EACH_PTR(insn->phi_users, phi) {
                        struct storage *storage = lookup_storage(bb, phi->target, STOR_OUT);
                        if (!storage) {
                                DELETE_CURRENT_PTR(phi);
                                continue;
                        }
                        if (last && storage != last)
                                storage = combine_storage(storage, last);
                        last = storage;
                } END_FOR_EACH_PTR(phi);
                PACK_PTR_LIST(&insn->phi_users);
        } END_FOR_EACH_PTR(insn);
}

void set_up_storage(struct entrypoint *ep)
{
        struct basic_block *bb;

        /* First set up storage for the incoming arguments */
        set_up_argument_storage(ep, ep->entry->bb);

        /* Then do a list of all the inter-bb storage */
        FOR_EACH_PTR(ep->bbs, bb) {
                set_up_bb_storage(bb);
                combine_phi_storage(bb);
        } END_FOR_EACH_PTR(bb);

        name_storage();
}