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