1 files changed, 291 insertions, 0 deletions
diff --git a/src/llvm/include/InnerLoopAnalysis.h b/src/llvm/include/InnerLoopAnalysis.h
new file mode 100644
index 0000000..f11225d
--- /dev/null
+++ b/src/llvm/include/InnerLoopAnalysis.h
@@ -0,0 +1,291 @@
+/*
+ *  (C) 2016 by Computer System Laboratory, IIS, Academia Sinica, Taiwan.
+ *      See COPYRIGHT in top-level directory.
+ */
+
+#ifndef __INNERLOOPANALYSIS_H
+#define __INNERLOOPANALYSIS_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm-types.h"
+
+
+class InductionDesc {
+    /* Start value. */
+    Value *StartValue;
+    /* Step value. */
+    const SCEV *Step;
+
+public:
+    InductionDesc() : StartValue(nullptr), Step(nullptr) {}
+    InductionDesc(Value *Start, const SCEV *Step)
+        : StartValue(Start), Step(Step) {}
+
+    Value *getStartValue() const { return StartValue; }
+    const SCEV *getStep() const { return Step; }
+};
+
+class ReductionDesc {
+public:
+
+    enum ReductionKind {
+        NoReduction, /* Not a reduction. */
+        IntegerAdd,  /* Sum of numbers. */
+        IntegerMult, /* Product of numbers. */
+        IntegerOr,   /* Bitwise or logical OR of numbers. */
+        IntegerAnd,  /* Bitwise or logical AND of numbers. */
+        IntegerXor,  /* Bitwise or logical XOR of numbers. */
+        FloatAdd,    /* Sum of float numbers. */
+        FloatMult,   /* Product of float numbers. */
+    };
+
+    ReductionDesc()
+        : StartValue(nullptr), LoopExitInstr(nullptr),
+          Kind(ReductionKind::NoReduction), Ty(nullptr) {}
+    ReductionDesc(Value *Start, Instruction *Exit, ReductionKind K, Type *Ty)
+        : StartValue(Start), LoopExitInstr(Exit), Kind(K), Ty(Ty) {}
+
+    Value *getStartValue() const { return StartValue; }
+    Value *getNextValue() const { return LoopExitInstr; }
+    Instruction *getLoopExitInstr() { return LoopExitInstr; }
+    ReductionKind getReductionKind() { return Kind; }
+    Type *getScalarType() { return Ty; }
+
+private:
+    /* The starting value of the recurrence. */
+    Value *StartValue;
+    /* The instruction who's value is used outside the loop. */
+    Instruction *LoopExitInstr;
+    /* The kind of the recurrence.*/
+    ReductionKind Kind;
+    /* The scalar type. */
+    Type *Ty;
+};
+
+/*
+ * The InnertLoop class represents a single innertmost loop. The InnerLoop has
+ * a special shape that is specific to the DBT decoded guest loop, and its loop
+ * definition is different to a nature loop, e.g., latch and exiting block.
+ */
+class InnerLoop {
+public:
+    typedef std::map<PHINode *, InductionDesc> InductionList;
+    typedef std::map<PHINode *, ReductionDesc> ReductionList;
+
+private:
+    Loop &TheLoop;
+
+    /* The list of blocks in this loop. First entry is the header node. */
+    std::vector<BasicBlock *> Blocks;
+    SmallPtrSet<const BasicBlock *, 8> DenseBlockSet;
+
+    std::vector<BasicBlock *> Latches;
+    std::map<BasicBlock *, BasicBlock *> SplitLatches;
+
+    bool UnknownPhi;
+    InductionList Inductions;
+    ReductionList Reductions;
+
+    void addInduction(PHINode *Phi, Value *Start, const SCEV *Step) {
+        Inductions[Phi] = InductionDesc(Start, Step);
+    }
+
+    void addReduction(PHINode *Phi, Value *Start, Instruction *Exit,
+                      ReductionDesc::ReductionKind K, Type *Ty) {
+        Reductions[Phi] = ReductionDesc(Start, Exit, K, Ty);
+    }
+
+    InnerLoop(const InnerLoop &) = delete;
+    const InnerLoop& operator=(const InnerLoop &) = delete;
+
+    friend class InnerLoopAnalysis;
+
+public:
+    InnerLoop(Loop *loop);
+    ~InnerLoop() {}
+
+    Loop &getLoop() const { return TheLoop; }
+
+    BasicBlock *getHeader() const { return Blocks.front(); }
+
+    /* Return true if the specified basic block is in this loop. */
+    bool contains(const BasicBlock *BB) const {
+        return DenseBlockSet.count(BB);
+    }
+
+    /* Return true if the specified instruction is in this loop. */
+    bool contains(const Instruction *Inst) const {
+        return contains(Inst->getParent());
+    }
+
+    /* Get a list of the basic blocks which make up this loop. */
+    typedef typename std::vector<BasicBlock*>::const_iterator block_iterator;
+    const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
+    block_iterator block_begin() const { return Blocks.begin(); }
+    block_iterator block_end() const { return Blocks.end(); }
+    inline iterator_range<block_iterator> blocks() const {
+        return make_range(block_begin(), block_end());
+    }
+
+    /* Get the number of blocks in this loop in constant time. */
+    unsigned getNumBlocks() const { return Blocks.size(); }
+
+    /* True if terminator in the block can branch to another block that is 
+     * outside of the current loop. */
+    bool isLoopExiting(BasicBlock *BB) const;
+
+    /* Calculate the number of back edges to the loop header. */
+    unsigned getNumBackEdges() const;
+
+    /* Return all blocks inside the loop that have successors outside of the
+     * loop. */
+    void getExitingBlocks(SmallVectorImpl<BasicBlock *> &ExitingBlocks) const;
+
+    /* If getExitingBlocks would return exactly one block, return that block.
+     * Otherwise return null. */
+    BasicBlock *getExitingBlock() const;
+
+    /* Return all of the successor blocks of this loop. */
+    void getExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const;
+
+    /* If getExitBlocks would return exactly one block, return that block.
+     * Otherwise return null. */
+    BasicBlock *getExitBlock() const;
+
+    /* If there is a preheader for this loop, return it. A loop has a preheader
+     * if there is only one edge to the header of the loop from outside of the
+     * loop. If this is the case, the block branching to the header of the loop
+     * is the preheader node.
+     *
+     * This method returns null if there is no preheader for the loop. */
+    BasicBlock *getLoopPreheader() const;
+
+    /* If the given loop's header has exactly one unique predecessor outside the
+     * loop, return it. Otherwise return null.
+     * This is less strict that the loop "preheader" concept, which requires
+     * the predecessor to have exactly one successor. */
+    BasicBlock *getLoopPredecessor() const;
+
+    unsigned getNumLoopLatches()  const { return Latches.size(); }
+    unsigned getNumSplitLatches() const { return SplitLatches.size(); }
+
+    /* Return all loop latch blocks of this loop. A latch block is a block that
+     * contains a branch back to the header. */
+    void getLoopLatches(SmallVectorImpl<BasicBlock *> &LoopLatches) const {
+        for (auto I : Latches)
+            LoopLatches.push_back(I);
+    }
+
+    /* If there is a latch tail, return it. */
+    BasicBlock *getSingleLatchTail() const {
+        return (SplitLatches.size() == 1) ? SplitLatches.begin()->first :
+                                            nullptr;
+    }
+
+    /* If there is a latch head, return it. */
+    BasicBlock *getSingleLatchHead() const {
+        return (SplitLatches.size() == 1) ? SplitLatches.begin()->second :
+                                            nullptr;
+    }
+
+    /* Return all of the latch tails of this loop. */
+    void getLatchTails(SmallVectorImpl<BasicBlock *> &LatchTails) const {
+        for (auto &I : SplitLatches)
+            LatchTails.push_back(I.first);
+    }
+
+    /* Given a latch tail, return its latch head. */
+    BasicBlock *getLatchHead(BasicBlock *BB) {
+        if (SplitLatches.find(BB) == SplitLatches.end())
+            return nullptr;
+        return SplitLatches[BB];
+    }
+
+    /* If the given phi is an induction of the loop, return the induciton. */
+    InductionDesc *getInduction(PHINode *Phi) {
+        if (Inductions.find(Phi) == Inductions.end())
+            return nullptr;
+        return &Inductions[Phi];
+    }
+
+    /* If the given phi is a reduction of the loop, return the induciton. */
+    ReductionDesc *getReduction(PHINode *Phi) {
+        if (Reductions.find(Phi) == Reductions.end())
+            return nullptr;
+        return &Reductions[Phi];
+    }
+
+    /* Return true if the loop has unknown phi(s). A loop has unknown phi(s) if
+     * a phi node is not identified, or the loop has no preheader or latch tail.
+     * 
+     * If the loop has unknown phi(s), the data structure of Inductions and
+     * Reductions can be undefined. */
+    bool hasUnknownPhi() { return UnknownPhi; }
+
+    /* Return true if the instruction `From' can flow to instruction `To' in
+     * the loop. */
+    bool isReachable(Instruction *From, Instruction *To);
+};
+
+class InnerLoopAnalysis {
+    std::vector<InnerLoop *> InnerLoops;
+
+    void analyzePhi(InnerLoop &TheLoop, ScalarEvolution *SE);
+    bool analyzeInduction(InnerLoop &TheLoop, ScalarEvolution *SE, PHINode *Phi);
+    bool analyzeReduction(InnerLoop &TheLoop, PHINode *Phi);
+
+public:
+    InnerLoopAnalysis() {}
+    ~InnerLoopAnalysis() { releaseMemory(); }
+
+    void releaseMemory() {
+        while (!InnerLoops.empty()) {
+            InnerLoop *L = InnerLoops.back();
+            InnerLoops.pop_back();
+            delete L;
+        }
+    }
+    void print(raw_ostream &OS, const Module * = nullptr) const {}
+    void verify() const {}
+    void analyze(LoopInfo *LI, ScalarEvolution *SE);
+
+    /* iterator/begin/end - The interface to the innermost loops. */
+    typedef typename std::vector<InnerLoop *>::const_iterator iterator;
+    typedef typename std::vector<InnerLoop *>::const_reverse_iterator
+        reverse_iterator;
+    iterator begin() const { return InnerLoops.begin(); }
+    iterator end() const { return InnerLoops.end(); }
+    reverse_iterator rbegin() const { return InnerLoops.rbegin(); }
+    reverse_iterator rend() const { return InnerLoops.rend(); }
+    bool empty() const { return InnerLoops.empty(); }
+    unsigned size() { return InnerLoops.size(); }
+};
+
+/*
+ * InnerLoopAnalysisWrapperPass Pass
+ */
+class InnerLoopAnalysisWrapperPass : public FunctionPass {
+    InnerLoopAnalysis LA;
+
+public:
+    static char ID;
+    InnerLoopAnalysisWrapperPass() : FunctionPass(ID) {
+        initializeInnerLoopAnalysisWrapperPassPass(*PassRegistry::getPassRegistry());
+    }
+
+    InnerLoopAnalysis &getLoopAnalysis() { return LA; }
+    const InnerLoopAnalysis &getLoopAnalysis() const { return LA; }
+
+    void releaseMemory() override;
+    void getAnalysisUsage(AnalysisUsage &AU) const override;
+    void print(raw_ostream &OS, const Module * = nullptr) const override;
+    void verifyAnalysis() const override;
+    bool runOnFunction(Function &F) override;
+};
+
+#endif
+
+/*
+ * vim: ts=8 sts=4 sw=4 expandtab
+ */