LoopUnrollAnalyzer.cpp revision de2d8694e25a814696358e95141f4b1aa4d8847e 
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
19using 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.
29bool 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.
70bool 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.
96bool 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.
139bool 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.
162bool 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
202bool 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