diff options
Diffstat (limited to 'llvm/include/InnerLoopAnalysis.h')
-rw-r--r-- | llvm/include/InnerLoopAnalysis.h | 291 |
1 files changed, 291 insertions, 0 deletions
diff --git a/llvm/include/InnerLoopAnalysis.h b/llvm/include/InnerLoopAnalysis.h new file mode 100644 index 0000000..f11225d --- /dev/null +++ b/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 + */ |