1 files changed, 179 insertions, 0 deletions
diff --git a/llvm/pass/RedundantStateElimination.cpp b/llvm/pass/RedundantStateElimination.cpp
new file mode 100644
index 0000000..2e5f715
--- /dev/null
+++ b/llvm/pass/RedundantStateElimination.cpp
@@ -0,0 +1,179 @@
+/*
+ *  (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
+ */
+