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