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#include "llvm/Analysis/LoopInfo.h"
17
18using 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.
28bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
29  if (!SE.isSCEVable(I->getType()))
30    return false;
31
32  const SCEV *S = SE.getSCEV(I);
33  if (auto *SC = dyn_cast<SCEVConstant>(S)) {
34    SimplifiedValues[I] = SC->getValue();
35    return true;
36  }
37
38  auto *AR = dyn_cast<SCEVAddRecExpr>(S);
39  if (!AR || AR->getLoop() != L)
40    return false;
41
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();
46    return true;
47  }
48
49  // Check if the offset from the base address becomes a constant.
50  auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
51  if (!Base)
52    return false;
53  auto *Offset =
54      dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
55  if (!Offset)
56    return false;
57  SimplifiedAddress Address;
58  Address.Base = Base->getValue();
59  Address.Offset = Offset->getValue();
60  SimplifiedAddresses[I] = Address;
61  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.
69bool 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))
73      LHS = SimpleLHS;
74  if (!isa<Constant>(RHS))
75    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
76      RHS = SimpleRHS;
77
78  Value *SimpleV = nullptr;
79  const DataLayout &DL = I.getModule()->getDataLayout();
80  if (auto FI = dyn_cast<FPMathOperator>(&I))
81    SimpleV =
82        SimplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
83  else
84    SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
85
86  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
87    SimplifiedValues[&I] = C;
88
89  if (SimpleV)
90    return true;
91  return Base::visitBinaryOperator(I);
92}
93
94/// Try to fold load I.
95bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
96  Value *AddrOp = I.getPointerOperand();
97
98  auto AddressIt = SimplifiedAddresses.find(AddrOp);
99  if (AddressIt == SimplifiedAddresses.end())
100    return false;
101  ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
102
103  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  if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
107    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  if (CDS->getElementType() != I.getType())
118    return false;
119
120  unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
121  if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
122    return false;
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.
127    return false;
128  }
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.
133    return false;
134  }
135
136  Constant *CV = CDS->getElementAsConstant(Index);
137  assert(CV && "Constant expected.");
138  SimplifiedValues[&I] = CV;
139
140  return true;
141}
142
143/// Try to simplify cast instruction.
144bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
145  // Propagate constants through casts.
146  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
147  if (!COp)
148    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  if (COp && CastInst::castIsValid(I.getOpcode(), COp, I.getType())) {
156    if (Constant *C =
157            ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
158      SimplifiedValues[&I] = C;
159      return true;
160    }
161  }
162
163  return Base::visitCastInst(I);
164}
165
166/// Try to simplify cmp instruction.
167bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
168  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
169
170  // First try to handle simplified comparisons.
171  if (!isa<Constant>(LHS))
172    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
173      LHS = SimpleLHS;
174  if (!isa<Constant>(RHS))
175    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
176      RHS = SimpleRHS;
177
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;
188        }
189      }
190    }
191  }
192
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;
198          return true;
199        }
200      }
201    }
202  }
203
204  return Base::visitCmpInst(I);
205}
206
207bool 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))
211    return true;
212
213  // The loop induction PHI nodes are definitionally free.
214  return PN.getParent() == L->getHeader();
215}
216