/*
 * memops - try to combine memory ops.
 *
 * Copyright (C) 2004 Linus Torvalds
 */

#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>

#include "parse.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"

static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
        struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
        int local)
{
        struct basic_block *parent;

        FOR_EACH_PTR(bb->parents, parent) {
                struct instruction *one;
                struct instruction *br;
                pseudo_t phi;

                FOR_EACH_PTR_REVERSE(parent->insns, one) {
                        int dominance;
                        if (!one->bb)
                                continue;
                        if (one == insn)
                                goto no_dominance;
                        dominance = dominates(pseudo, insn, one, local);
                        if (dominance < 0) {
                                if (one->opcode == OP_LOAD)
                                        continue;
                                return 0;
                        }
                        if (!dominance)
                                continue;
                        goto found_dominator;
                } END_FOR_EACH_PTR_REVERSE(one);
no_dominance:
                if (parent->generation == generation)
                        continue;
                parent->generation = generation;

                if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
                        return 0;
                continue;

found_dominator:
                br = delete_last_instruction(&parent->insns);
                phi = alloc_phi(parent, one->target, one->type);
                phi->ident = phi->ident ? : one->target->ident;
                add_instruction(&parent->insns, br);
                use_pseudo(insn, phi, add_pseudo(dominators, phi));
        } END_FOR_EACH_PTR(parent);
        return 1;
}               

static int address_taken(pseudo_t pseudo)
{
        struct pseudo_user *pu;
        FOR_EACH_PTR(pseudo->users, pu) {
                struct instruction *insn = pu->insn;
                if (insn->bb && (insn->opcode != OP_LOAD && insn->opcode != OP_STORE))
                        return 1;
                if (pu->userp != &insn->src)
                        return 1;
        } END_FOR_EACH_PTR(pu);
        return 0;
}

static int local_pseudo(pseudo_t pseudo)
{
        return pseudo->type == PSEUDO_SYM
                && !(pseudo->sym->ctype.modifiers & (MOD_STATIC | MOD_NONLOCAL))
                && !address_taken(pseudo);
}

static void simplify_loads(struct basic_block *bb)
{
        struct instruction *insn;

        FOR_EACH_PTR_REVERSE(bb->insns, insn) {
                if (!insn->bb)
                        continue;
                if (insn->opcode == OP_LOAD) {
                        struct instruction *dom;
                        pseudo_t pseudo = insn->src;
                        int local = local_pseudo(pseudo);
                        struct pseudo_list *dominators;
                        unsigned long generation;

                        /* Check for illegal offsets.. */
                        check_access(insn);

                        if (insn->is_volatile)
                                continue;

                        RECURSE_PTR_REVERSE(insn, dom) {
                                int dominance;
                                if (!dom->bb)
                                        continue;
                                dominance = dominates(pseudo, insn, dom, local);
                                if (dominance) {
                                        /* possible partial dominance? */
                                        if (dominance < 0)  {
                                                if (dom->opcode == OP_LOAD)
                                                        continue;
                                                goto next_load;
                                        }
                                        /* Yeehaa! Found one! */
                                        convert_load_instruction(insn, dom->target);
                                        goto next_load;
                                }
                        } END_FOR_EACH_PTR_REVERSE(dom);

                        /* OK, go find the parents */
                        generation = ++bb_generation;
                        bb->generation = generation;
                        dominators = NULL;
                        if (find_dominating_parents(pseudo, insn, bb, generation, &dominators, local)) {
                                /* This happens with initial assignments to structures etc.. */
                                if (!dominators) {
                                        if (local) {
                                                assert(pseudo->type != PSEUDO_ARG);
                                                convert_load_instruction(insn, value_pseudo(0));
                                        }
                                        goto next_load;
                                }
                                rewrite_load_instruction(insn, dominators);
                        } else {        // cleanup pending phi-sources
                                pseudo_t phi;
                                FOR_EACH_PTR(dominators, phi) {
                                        kill_instruction(phi->def);
                                } END_FOR_EACH_PTR(phi);
                        }
                }
next_load:
                /* Do the next one */;
        } END_FOR_EACH_PTR_REVERSE(insn);
}

static void kill_dominated_stores(struct basic_block *bb)
{
        struct instruction *insn;

        FOR_EACH_PTR_REVERSE(bb->insns, insn) {
                if (!insn->bb)
                        continue;
                if (insn->opcode == OP_STORE) {
                        struct instruction *dom;
                        pseudo_t pseudo = insn->src;
                        int local;

                        if (!insn->type)
                                continue;
                        if (insn->is_volatile)
                                continue;

                        local = local_pseudo(pseudo);
                        RECURSE_PTR_REVERSE(insn, dom) {
                                int dominance;
                                if (!dom->bb)
                                        continue;
                                dominance = dominates(pseudo, insn, dom, local);
                                if (dominance) {
                                        /* possible partial dominance? */
                                        if (dominance < 0)
                                                goto next_store;
                                        if (dom->opcode == OP_LOAD)
                                                goto next_store;
                                        /* Yeehaa! Found one! */
                                        kill_instruction_force(dom);
                                }
                        } END_FOR_EACH_PTR_REVERSE(dom);

                        /* OK, we should check the parents now */
                }
next_store:
                /* Do the next one */;
        } END_FOR_EACH_PTR_REVERSE(insn);
}

void simplify_memops(struct entrypoint *ep)
{
        struct basic_block *bb;
        pseudo_t pseudo;

        FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
                simplify_loads(bb);
        } END_FOR_EACH_PTR_REVERSE(bb);

        FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
                kill_dominated_stores(bb);
        } END_FOR_EACH_PTR_REVERSE(bb);

        FOR_EACH_PTR(ep->accesses, pseudo) {
                struct symbol *var = pseudo->sym;
                unsigned long mod;
                if (!var)
                        continue;
                mod = var->ctype.modifiers;
                if (mod & (MOD_VOLATILE | MOD_NONLOCAL | MOD_STATIC))
                        continue;
                kill_dead_stores(ep, pseudo, local_pseudo(pseudo));
        } END_FOR_EACH_PTR(pseudo);
}