/*
 *  (C) 2017 by Computer System Laboratory, IIS, Academia Sinica, Taiwan.
 *      See COPYRIGHT in top-level directory.
 */

#include "llvm-debug.h"
#include "llvm-opc.h"
#include "llvm-target.h"
#include "llvm-pass.h"
#include "utils.h"

#define PASS_NAME "RedundantStateElimination"

/*
 * The RedundantStateElimination pass aims to remove
 * (1) redundant stores to PC, and
 * (2) redundant loads and stores enclosed by two helper function calls.
 */
class RedundantStateElimination : public FunctionPass {
    IRFactory *IF;
    MDFactory *MF;
    const DataLayout *DL;
    Value *CPU;
    IVec toErase;

public:
    static char ID;
    explicit RedundantStateElimination() : FunctionPass(ID) {}
    explicit RedundantStateElimination(IRFactory *IF)
        : FunctionPass(ID), IF(IF), MF(IF->getMDFactory()), DL(IF->getDL()) {}

    int getNumUsers(Instruction *I) {
        return distance(I->user_begin(), I->user_end());
    }

    bool isStateOfPC(Value *Ptr) {
        intptr_t Off = 0;
        Value *Base = getBaseWithConstantOffset(DL, Ptr, Off);
        if (Base == CPU && IRFactory::isStateOfPC(Off))
            return true;
        return false;
    }

    bool isDirectDominator(LoadInst *LI, StoreInst *SI) {
        Instruction *A = LI, *B = SI;
        if (A->getParent() != B->getParent())
            return false;
        for (auto II = BasicBlock::iterator(A), EE = A->getParent()->end();
             II != EE; ++II) {
            if (&*II == B)
                return true;
            /* If a non-const helper function is between the two instructions,
             * this is not a direct domination because the helper function could
             * cause side effect. */
            auto CI = dyn_cast<CallInst>(II);
            if (CI && !MDFactory::isConst(CI))
                return false;
        }
        return false;
    }

    bool removePCState(Function &F);
    bool removeHelperState(Function &F);
    bool runOnFunction(Function &F);
};

char RedundantStateElimination::ID = 0;
INITIALIZE_PASS(RedundantStateElimination, "rse",
        "Eliminate redundant CPU state loads/stores", false, false)

FunctionPass *llvm::createRedundantStateElimination(IRFactory *IF)
{
    return new RedundantStateElimination(IF);
}

/* Eliminate redundant stores to PC for each basic block. */
bool RedundantStateElimination::removePCState(Function &F)
{
    for (auto FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
        bool Found = false;

        for (auto BI = FI->rbegin(), BE = FI->rend(); BI != BE; ++BI) {
            Instruction *I = &*BI;
            if (MF->isGuestMemory(I))
                continue;

            if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
                if (isStateOfPC(getPointerOperand(SI))) {
                    if (!Found)
                        Found = true;
                    else
                        toErase.push_back(SI);
                }
            } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
                if (isStateOfPC(getPointerOperand(LI)))
                    Found = false;
            }
        }
    }

    if (toErase.empty())
        return false;

    ProcessErase(toErase);
    return true;

}

/* Eliminate redundant loads/stores enclosed by two helper function calls.
 * The redundant loads and stores are generated by StateMappingPass for
 * handling synchronization of CPU states around helper function calls.
 * A load and store can be removed if a state value is loaded and immediately
 * stored back to the same state. For example:
 *
 * Before optimization:                     After optimization:
 *   instructions to sync states              instructions to sync states
 *   call void @helper_function1()            call void @helper_function1()
 *
 *   %v0 = load i32, i32* %state0
 *   %v1 = load i32, i32* %state1
 *   store i32 %v0, i32* %state0
 *   store i32 %v1, i32* %state1
 *
 *   call void @helper_function2()            call void @helper_function2()
 *   instructions to reload states            instructions to reload states
 */
bool RedundantStateElimination::removeHelperState(Function &F)
{
    for (auto FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
        for (auto BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) {
            Instruction *I = &*BI;
            if (MF->isGuestMemory(I))
                continue;

            StoreInst *SI = dyn_cast<StoreInst>(I);
            if (!SI || SI->isVolatile())
                continue;

            LoadInst *LI = dyn_cast<LoadInst>(getValueOperand(SI));
            if (LI && isDirectDominator(LI, SI)) {
                /* We can try removing the store instruction if LI is a direct
                 * dominator of SI. */
                Value *PtrA = getPointerOperand(LI);
                Value *PtrB = getPointerOperand(SI);
                if (StripPointer(PtrA) == CPU && PtrA == PtrB)
                    toErase.push_back(SI);
            }
        }
    }

    if (toErase.empty())
        return false;

    ProcessErase(toErase);
    return true;
}

bool RedundantStateElimination::runOnFunction(Function &F)
{
    bool Changed = false;

    CPU = IF->getDefaultCPU(F);
    if (!CPU) {
        dbg() << DEBUG_PASS << "RedundantStateElimination: Cannot find CPU pointer.\n";
        return false;
    }

    Changed |= removePCState(F);
#if 0
    Changed |= removeHelperState(F);
#endif

    return Changed;
}

/*
 * vim: ts=8 sts=4 sw=4 expandtab
 */