/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/LoopUnrollAnalyzer.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- 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 | | #include "llvm/Analysis/LoopUnrollAnalyzer.h" |
16 | | |
17 | | using namespace llvm; |
18 | | |
19 | | /// Try to simplify instruction \param I using its SCEV expression. |
20 | | /// |
21 | | /// The idea is that some AddRec expressions become constants, which then |
22 | | /// could trigger folding of other instructions. However, that only happens |
23 | | /// for expressions whose start value is also constant, which isn't always the |
24 | | /// case. In another common and important case the start value is just some |
25 | | /// address (i.e. SCEVUnknown) - in this case we compute the offset and save |
26 | | /// it along with the base address instead. |
27 | 469k | bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) { |
28 | 469k | if (!SE.isSCEVable(I->getType())) |
29 | 163k | return false; |
30 | 306k | |
31 | 306k | const SCEV *S = SE.getSCEV(I); |
32 | 306k | if (auto *SC = dyn_cast<SCEVConstant>(S)) { |
33 | 8 | SimplifiedValues[I] = SC->getValue(); |
34 | 8 | return true; |
35 | 8 | } |
36 | 306k | |
37 | 306k | auto *AR = dyn_cast<SCEVAddRecExpr>(S); |
38 | 306k | if (!AR || AR->getLoop() != L123k ) |
39 | 183k | return false; |
40 | 122k | |
41 | 122k | const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE); |
42 | 122k | // Check if the AddRec expression becomes a constant. |
43 | 122k | if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) { |
44 | 10.7k | SimplifiedValues[I] = SC->getValue(); |
45 | 10.7k | return true; |
46 | 10.7k | } |
47 | 111k | |
48 | 111k | // Check if the offset from the base address becomes a constant. |
49 | 111k | auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S)); |
50 | 111k | if (!Base) |
51 | 2.58k | return false; |
52 | 109k | auto *Offset = |
53 | 109k | dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base)); |
54 | 109k | if (!Offset) |
55 | 57.8k | return false; |
56 | 51.2k | SimplifiedAddress Address; |
57 | 51.2k | Address.Base = Base->getValue(); |
58 | 51.2k | Address.Offset = Offset->getValue(); |
59 | 51.2k | SimplifiedAddresses[I] = Address; |
60 | 51.2k | return false; |
61 | 51.2k | } |
62 | | |
63 | | /// Try to simplify binary operator I. |
64 | | /// |
65 | | /// TODO: Probably it's worth to hoist the code for estimating the |
66 | | /// simplifications effects to a separate class, since we have a very similar |
67 | | /// code in InlineCost already. |
68 | 133k | bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) { |
69 | 133k | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
70 | 133k | if (!isa<Constant>(LHS)) |
71 | 126k | if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) |
72 | 15.7k | LHS = SimpleLHS; |
73 | 133k | if (!isa<Constant>(RHS)) |
74 | 85.3k | if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) |
75 | 1.84k | RHS = SimpleRHS; |
76 | 133k | |
77 | 133k | Value *SimpleV = nullptr; |
78 | 133k | const DataLayout &DL = I.getModule()->getDataLayout(); |
79 | 133k | if (auto FI = dyn_cast<FPMathOperator>(&I)) |
80 | 31.6k | SimpleV = |
81 | 31.6k | SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL); |
82 | 102k | else |
83 | 102k | SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL); |
84 | 133k | |
85 | 133k | if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) |
86 | 15.7k | SimplifiedValues[&I] = C; |
87 | 133k | |
88 | 133k | if (SimpleV) |
89 | 16.1k | return true; |
90 | 117k | return Base::visitBinaryOperator(I); |
91 | 117k | } |
92 | | |
93 | | /// Try to fold load I. |
94 | 78.8k | bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) { |
95 | 78.8k | Value *AddrOp = I.getPointerOperand(); |
96 | 78.8k | |
97 | 78.8k | auto AddressIt = SimplifiedAddresses.find(AddrOp); |
98 | 78.8k | if (AddressIt == SimplifiedAddresses.end()) |
99 | 48.4k | return false; |
100 | 30.3k | ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset; |
101 | 30.3k | |
102 | 30.3k | auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base); |
103 | 30.3k | // We're only interested in loads that can be completely folded to a |
104 | 30.3k | // constant. |
105 | 30.3k | if (!GV || !GV->hasDefinitiveInitializer()11.0k || !GV->isConstant()4.58k ) |
106 | 27.0k | return false; |
107 | 3.30k | |
108 | 3.30k | ConstantDataSequential *CDS = |
109 | 3.30k | dyn_cast<ConstantDataSequential>(GV->getInitializer()); |
110 | 3.30k | if (!CDS) |
111 | 981 | return false; |
112 | 2.32k | |
113 | 2.32k | // We might have a vector load from an array. FIXME: for now we just bail |
114 | 2.32k | // out in this case, but we should be able to resolve and simplify such |
115 | 2.32k | // loads. |
116 | 2.32k | if (CDS->getElementType() != I.getType()) |
117 | 2.01k | return false; |
118 | 309 | |
119 | 309 | unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U; |
120 | 309 | if (SimplifiedAddrOp->getValue().getActiveBits() > 64) |
121 | 0 | return false; |
122 | 309 | int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue(); |
123 | 309 | if (SimplifiedAddrOpV < 0) { |
124 | 2 | // FIXME: For now we conservatively ignore out of bound accesses, but |
125 | 2 | // we're allowed to perform the optimization in this case. |
126 | 2 | return false; |
127 | 2 | } |
128 | 307 | uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize; |
129 | 307 | if (Index >= CDS->getNumElements()) { |
130 | 0 | // FIXME: For now we conservatively ignore out of bound accesses, but |
131 | 0 | // we're allowed to perform the optimization in this case. |
132 | 0 | return false; |
133 | 0 | } |
134 | 307 | |
135 | 307 | Constant *CV = CDS->getElementAsConstant(Index); |
136 | 307 | assert(CV && "Constant expected."); |
137 | 307 | SimplifiedValues[&I] = CV; |
138 | 307 | |
139 | 307 | return true; |
140 | 307 | } |
141 | | |
142 | | /// Try to simplify cast instruction. |
143 | 76.8k | bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) { |
144 | 76.8k | // Propagate constants through casts. |
145 | 76.8k | Constant *COp = dyn_cast<Constant>(I.getOperand(0)); |
146 | 76.8k | if (!COp) |
147 | 74.8k | COp = SimplifiedValues.lookup(I.getOperand(0)); |
148 | 76.8k | |
149 | 76.8k | // If we know a simplified value for this operand and cast is valid, save the |
150 | 76.8k | // result to SimplifiedValues. |
151 | 76.8k | // The cast can be invalid, because SimplifiedValues contains results of SCEV |
152 | 76.8k | // analysis, which operates on integers (and, e.g., might convert i8* null to |
153 | 76.8k | // i32 0). |
154 | 76.8k | if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())3.49k ) { |
155 | 3.49k | if (Constant *C = |
156 | 3.49k | ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) { |
157 | 3.49k | SimplifiedValues[&I] = C; |
158 | 3.49k | return true; |
159 | 3.49k | } |
160 | 73.3k | } |
161 | 73.3k | |
162 | 73.3k | return Base::visitCastInst(I); |
163 | 73.3k | } |
164 | | |
165 | | /// Try to simplify cmp instruction. |
166 | 29.3k | bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) { |
167 | 29.3k | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); |
168 | 29.3k | |
169 | 29.3k | // First try to handle simplified comparisons. |
170 | 29.3k | if (!isa<Constant>(LHS)) |
171 | 29.3k | if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) |
172 | 10.7k | LHS = SimpleLHS; |
173 | 29.3k | if (!isa<Constant>(RHS)) |
174 | 7.49k | if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) |
175 | 15 | RHS = SimpleRHS; |
176 | 29.3k | |
177 | 29.3k | if (!isa<Constant>(LHS) && !isa<Constant>(RHS)18.5k ) { |
178 | 6.72k | auto SimplifiedLHS = SimplifiedAddresses.find(LHS); |
179 | 6.72k | if (SimplifiedLHS != SimplifiedAddresses.end()) { |
180 | 82 | auto SimplifiedRHS = SimplifiedAddresses.find(RHS); |
181 | 82 | if (SimplifiedRHS != SimplifiedAddresses.end()) { |
182 | 40 | SimplifiedAddress &LHSAddr = SimplifiedLHS->second; |
183 | 40 | SimplifiedAddress &RHSAddr = SimplifiedRHS->second; |
184 | 40 | if (LHSAddr.Base == RHSAddr.Base) { |
185 | 40 | LHS = LHSAddr.Offset; |
186 | 40 | RHS = RHSAddr.Offset; |
187 | 40 | } |
188 | 40 | } |
189 | 82 | } |
190 | 6.72k | } |
191 | 29.3k | |
192 | 29.3k | if (Constant *CLHS = dyn_cast<Constant>(LHS)) { |
193 | 10.8k | if (Constant *CRHS = dyn_cast<Constant>(RHS)) { |
194 | 10.0k | if (CLHS->getType() == CRHS->getType()) { |
195 | 10.0k | if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) { |
196 | 10.0k | SimplifiedValues[&I] = C; |
197 | 10.0k | return true; |
198 | 10.0k | } |
199 | 19.3k | } |
200 | 10.0k | } |
201 | 10.8k | } |
202 | 19.3k | |
203 | 19.3k | return Base::visitCmpInst(I); |
204 | 19.3k | } |
205 | | |
206 | 22.4k | bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) { |
207 | 22.4k | // Run base visitor first. This way we can gather some useful for later |
208 | 22.4k | // analysis information. |
209 | 22.4k | if (Base::visitPHINode(PN)) |
210 | 10.7k | return true; |
211 | 11.7k | |
212 | 11.7k | // The loop induction PHI nodes are definitionally free. |
213 | 11.7k | return PN.getParent() == L->getHeader(); |
214 | 11.7k | } |