summaryrefslogtreecommitdiffstats
path: root/llvm/include/InnerLoopAnalysis.h
blob: f11225dfdaa264cac2957750468cc6bbc36e71d8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
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
 */
OpenPOWER on IntegriCloud