1 //===- LoopUnrollAnalyzer.cpp - Unrolling Effect Estimation -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/LoopUnrollAnalyzer.h"
20 /// Try to simplify instruction \param I using its SCEV expression.
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 bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
29 if (!SE.isSCEVable(I->getType()))
32 const SCEV *S = SE.getSCEV(I);
33 if (auto *SC = dyn_cast<SCEVConstant>(S)) {
34 SimplifiedValues[I] = SC->getValue();
38 auto *AR = dyn_cast<SCEVAddRecExpr>(S);
39 if (!AR || AR->getLoop() != L)
42 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 SimplifiedValues[I] = SC->getValue();
49 // Check if the offset from the base address becomes a constant.
50 auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
54 dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
57 SimplifiedAddress Address;
58 Address.Base = Base->getValue();
59 Address.Offset = Offset->getValue();
60 SimplifiedAddresses[I] = Address;
64 /// Try to simplify binary operator I.
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 bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
70 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
71 if (!isa<Constant>(LHS))
72 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
74 if (!isa<Constant>(RHS))
75 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
78 Value *SimpleV = nullptr;
79 const DataLayout &DL = I.getModule()->getDataLayout();
80 if (auto FI = dyn_cast<FPMathOperator>(&I))
82 SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
84 SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
86 if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
87 SimplifiedValues[&I] = C;
91 return Base::visitBinaryOperator(I);
94 /// Try to fold load I.
95 bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
96 Value *AddrOp = I.getPointerOperand();
98 auto AddressIt = SimplifiedAddresses.find(AddrOp);
99 if (AddressIt == SimplifiedAddresses.end())
101 ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
103 auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
104 // We're only interested in loads that can be completely folded to a
106 if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
109 ConstantDataSequential *CDS =
110 dyn_cast<ConstantDataSequential>(GV->getInitializer());
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
117 if (CDS->getElementType() != I.getType())
120 unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
121 if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
123 int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
124 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.
129 uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
130 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.
136 Constant *CV = CDS->getElementAsConstant(Index);
137 assert(CV && "Constant expected.");
138 SimplifiedValues[&I] = CV;
143 /// Try to simplify cast instruction.
144 bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
145 // Propagate constants through casts.
146 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
148 COp = SimplifiedValues.lookup(I.getOperand(0));
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
155 if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
157 ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
158 SimplifiedValues[&I] = C;
163 return Base::visitCastInst(I);
166 /// Try to simplify cmp instruction.
167 bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
168 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
170 // First try to handle simplified comparisons.
171 if (!isa<Constant>(LHS))
172 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
174 if (!isa<Constant>(RHS))
175 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
178 if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
179 auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
180 if (SimplifiedLHS != SimplifiedAddresses.end()) {
181 auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
182 if (SimplifiedRHS != SimplifiedAddresses.end()) {
183 SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
184 SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
185 if (LHSAddr.Base == RHSAddr.Base) {
186 LHS = LHSAddr.Offset;
187 RHS = RHSAddr.Offset;
193 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
194 if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
195 if (CLHS->getType() == CRHS->getType()) {
196 if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
197 SimplifiedValues[&I] = C;
204 return Base::visitCmpInst(I);
207 bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
208 // Run base visitor first. This way we can gather some useful for later
209 // analysis information.
210 if (Base::visitPHINode(PN))
213 // The loop induction PHI nodes are definitionally free.
214 return PN.getParent() == L->getHeader();