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/ADT/APInt.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/Analysis/ScalarEvolution.h" |
21 | #include "llvm/IR/InstVisitor.h" |
22 | |
23 | // This class is used to get an estimate of the optimization effects that we |
24 | // could get from complete loop unrolling. It comes from the fact that some |
25 | // loads might be replaced with concrete constant values and that could trigger |
26 | // a chain of instruction simplifications. |
27 | // |
28 | // E.g. we might have: |
29 | // int a[] = {0, 1, 0}; |
30 | // v = 0; |
31 | // for (i = 0; i < 3; i ++) |
32 | // v += b[i]*a[i]; |
33 | // If we completely unroll the loop, we would get: |
34 | // v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2] |
35 | // Which then will be simplified to: |
36 | // v = b[0]* 0 + b[1]* 1 + b[2]* 0 |
37 | // And finally: |
38 | // v = b[1] |
39 | namespace llvm { |
40 | class Instruction; |
41 | |
42 | class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { |
43 | typedef InstVisitor<UnrolledInstAnalyzer, bool> Base; |
44 | friend class InstVisitor<UnrolledInstAnalyzer, bool>; |
45 | struct SimplifiedAddress { |
46 | Value *Base = nullptr; |
47 | ConstantInt *Offset = nullptr; |
48 | }; |
49 | |
50 | public: |
51 | UnrolledInstAnalyzer(unsigned Iteration, |
52 | DenseMap<Value *, Value *> &SimplifiedValues, |
53 | ScalarEvolution &SE, const Loop *L) |
54 | : SimplifiedValues(SimplifiedValues), SE(SE), L(L) { |
55 | IterationNumber = SE.getConstant(Val: APInt(64, Iteration)); |
56 | } |
57 | |
58 | // Allow access to the initial visit method. |
59 | using Base::visit; |
60 | |
61 | private: |
62 | /// A cache of pointer bases and constant-folded offsets corresponding |
63 | /// to GEP (or derived from GEP) instructions. |
64 | /// |
65 | /// In order to find the base pointer one needs to perform non-trivial |
66 | /// traversal of the corresponding SCEV expression, so it's good to have the |
67 | /// results saved. |
68 | DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; |
69 | |
70 | /// SCEV expression corresponding to number of currently simulated |
71 | /// iteration. |
72 | const SCEV *IterationNumber; |
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 *, Value *> &SimplifiedValues; |
80 | |
81 | ScalarEvolution &SE; |
82 | const Loop *L; |
83 | |
84 | bool simplifyInstWithSCEV(Instruction *I); |
85 | |
86 | bool visitInstruction(Instruction &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 |
95 | |