/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h
Line | Count | Source |
1 | | //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file implements UnrolledInstAnalyzer class. It's used for predicting |
10 | | // potential effects that loop unrolling might have, such as enabling constant |
11 | | // propagation and other optimizations. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H |
16 | | #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H |
17 | | |
18 | | #include "llvm/Analysis/InstructionSimplify.h" |
19 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
20 | | #include "llvm/IR/InstVisitor.h" |
21 | | |
22 | | // This class is used to get an estimate of the optimization effects that we |
23 | | // could get from complete loop unrolling. It comes from the fact that some |
24 | | // loads might be replaced with concrete constant values and that could trigger |
25 | | // a chain of instruction simplifications. |
26 | | // |
27 | | // E.g. we might have: |
28 | | // int a[] = {0, 1, 0}; |
29 | | // v = 0; |
30 | | // for (i = 0; i < 3; i ++) |
31 | | // v += b[i]*a[i]; |
32 | | // If we completely unroll the loop, we would get: |
33 | | // v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2] |
34 | | // Which then will be simplified to: |
35 | | // v = b[0]* 0 + b[1]* 1 + b[2]* 0 |
36 | | // And finally: |
37 | | // v = b[1] |
38 | | namespace llvm { |
39 | | class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { |
40 | | typedef InstVisitor<UnrolledInstAnalyzer, bool> Base; |
41 | | friend class InstVisitor<UnrolledInstAnalyzer, bool>; |
42 | | struct SimplifiedAddress { |
43 | | Value *Base = nullptr; |
44 | | ConstantInt *Offset = nullptr; |
45 | | }; |
46 | | |
47 | | public: |
48 | | UnrolledInstAnalyzer(unsigned Iteration, |
49 | | DenseMap<Value *, Constant *> &SimplifiedValues, |
50 | | ScalarEvolution &SE, const Loop *L) |
51 | 10.8k | : SimplifiedValues(SimplifiedValues), SE(SE), L(L) { |
52 | 10.8k | IterationNumber = SE.getConstant(APInt(64, Iteration)); |
53 | 10.8k | } |
54 | | |
55 | | // Allow access to the initial visit method. |
56 | | using Base::visit; |
57 | | |
58 | | private: |
59 | | /// A cache of pointer bases and constant-folded offsets corresponding |
60 | | /// to GEP (or derived from GEP) instructions. |
61 | | /// |
62 | | /// In order to find the base pointer one needs to perform non-trivial |
63 | | /// traversal of the corresponding SCEV expression, so it's good to have the |
64 | | /// results saved. |
65 | | DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; |
66 | | |
67 | | /// SCEV expression corresponding to number of currently simulated |
68 | | /// iteration. |
69 | | const SCEV *IterationNumber; |
70 | | |
71 | | /// A Value->Constant map for keeping values that we managed to |
72 | | /// constant-fold on the given iteration. |
73 | | /// |
74 | | /// While we walk the loop instructions, we build up and maintain a mapping |
75 | | /// of simplified values specific to this iteration. The idea is to propagate |
76 | | /// any special information we have about loads that can be replaced with |
77 | | /// constants after complete unrolling, and account for likely simplifications |
78 | | /// post-unrolling. |
79 | | DenseMap<Value *, Constant *> &SimplifiedValues; |
80 | | |
81 | | ScalarEvolution &SE; |
82 | | const Loop *L; |
83 | | |
84 | | bool simplifyInstWithSCEV(Instruction *I); |
85 | | |
86 | 469k | bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); } |
87 | | bool visitBinaryOperator(BinaryOperator &I); |
88 | | bool visitLoad(LoadInst &I); |
89 | | bool visitCastInst(CastInst &I); |
90 | | bool visitCmpInst(CmpInst &I); |
91 | | bool visitPHINode(PHINode &PN); |
92 | | }; |
93 | | } |
94 | | #endif |