llvm-project

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/InstructionSimplify.h"
17
#include "llvm/Analysis/LoopInfo.h"
18
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
19
#include "llvm/IR/Operator.h"
20

21
using namespace llvm;
22

23
/// Try to simplify instruction \param I using its SCEV expression.
24
///
25
/// The idea is that some AddRec expressions become constants, which then
26
/// could trigger folding of other instructions. However, that only happens
27
/// for expressions whose start value is also constant, which isn't always the
28
/// case. In another common and important case the start value is just some
29
/// address (i.e. SCEVUnknown) - in this case we compute the offset and save
30
/// it along with the base address instead.
31
bool UnrolledInstAnalyzer::simplifyInstWithSCEV(Instruction *I) {
32
  if (!SE.isSCEVable(I->getType()))
33
    return false;
34

35
  const SCEV *S = SE.getSCEV(I);
36
  if (auto *SC = dyn_cast<SCEVConstant>(S)) {
37
    SimplifiedValues[I] = SC->getValue();
38
    return true;
39
  }
40

41
  // If we have a loop invariant computation, we only need to compute it once.
42
  // Given that, all but the first occurance are free.
43
  if (!IterationNumber->isZero() && SE.isLoopInvariant(S, L))
44
    return true;
45

46
  auto *AR = dyn_cast<SCEVAddRecExpr>(S);
47
  if (!AR || AR->getLoop() != L)
48
    return false;
49

50
  const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
51
  // Check if the AddRec expression becomes a constant.
52
  if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
53
    SimplifiedValues[I] = SC->getValue();
54
    return true;
55
  }
56

57
  // Check if the offset from the base address becomes a constant.
58
  auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
59
  if (!Base)
60
    return false;
61
  auto *Offset =
62
      dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
63
  if (!Offset)
64
    return false;
65
  SimplifiedAddress Address;
66
  Address.Base = Base->getValue();
67
  Address.Offset = Offset->getValue();
68
  SimplifiedAddresses[I] = Address;
69
  return false;
70
}
71

72
/// Try to simplify binary operator I.
73
///
74
/// TODO: Probably it's worth to hoist the code for estimating the
75
/// simplifications effects to a separate class, since we have a very similar
76
/// code in InlineCost already.
77
bool UnrolledInstAnalyzer::visitBinaryOperator(BinaryOperator &I) {
78
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
79
  if (!isa<Constant>(LHS))
80
    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
81
      LHS = SimpleLHS;
82
  if (!isa<Constant>(RHS))
83
    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
84
      RHS = SimpleRHS;
85

86
  Value *SimpleV = nullptr;
87
  const DataLayout &DL = I.getDataLayout();
88
  if (auto FI = dyn_cast<FPMathOperator>(&I))
89
    SimpleV =
90
        simplifyBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
91
  else
92
    SimpleV = simplifyBinOp(I.getOpcode(), LHS, RHS, DL);
93

94
  if (SimpleV) {
95
    SimplifiedValues[&I] = SimpleV;
96
    return true;
97
  }
98
  return Base::visitBinaryOperator(I);
99
}
100

101
/// Try to fold load I.
102
bool UnrolledInstAnalyzer::visitLoad(LoadInst &I) {
103
  Value *AddrOp = I.getPointerOperand();
104

105
  auto AddressIt = SimplifiedAddresses.find(AddrOp);
106
  if (AddressIt == SimplifiedAddresses.end())
107
    return false;
108
  ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
109

110
  auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
111
  // We're only interested in loads that can be completely folded to a
112
  // constant.
113
  if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
114
    return false;
115

116
  ConstantDataSequential *CDS =
117
      dyn_cast<ConstantDataSequential>(GV->getInitializer());
118
  if (!CDS)
119
    return false;
120

121
  // We might have a vector load from an array. FIXME: for now we just bail
122
  // out in this case, but we should be able to resolve and simplify such
123
  // loads.
124
  if (CDS->getElementType() != I.getType())
125
    return false;
126

127
  unsigned ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
128
  if (SimplifiedAddrOp->getValue().getActiveBits() > 64)
129
    return false;
130
  int64_t SimplifiedAddrOpV = SimplifiedAddrOp->getSExtValue();
131
  if (SimplifiedAddrOpV < 0) {
132
    // FIXME: For now we conservatively ignore out of bound accesses, but
133
    // we're allowed to perform the optimization in this case.
134
    return false;
135
  }
136
  uint64_t Index = static_cast<uint64_t>(SimplifiedAddrOpV) / ElemSize;
137
  if (Index >= CDS->getNumElements()) {
138
    // FIXME: For now we conservatively ignore out of bound accesses, but
139
    // we're allowed to perform the optimization in this case.
140
    return false;
141
  }
142

143
  Constant *CV = CDS->getElementAsConstant(Index);
144
  assert(CV && "Constant expected.");
145
  SimplifiedValues[&I] = CV;
146

147
  return true;
148
}
149

150
/// Try to simplify cast instruction.
151
bool UnrolledInstAnalyzer::visitCastInst(CastInst &I) {
152
  Value *Op = I.getOperand(0);
153
  if (Value *Simplified = SimplifiedValues.lookup(Op))
154
    Op = Simplified;
155

156
  // The cast can be invalid, because SimplifiedValues contains results of SCEV
157
  // analysis, which operates on integers (and, e.g., might convert i8* null to
158
  // i32 0).
159
  if (CastInst::castIsValid(I.getOpcode(), Op, I.getType())) {
160
    const DataLayout &DL = I.getDataLayout();
161
    if (Value *V = simplifyCastInst(I.getOpcode(), Op, I.getType(), DL)) {
162
      SimplifiedValues[&I] = V;
163
      return true;
164
    }
165
  }
166

167
  return Base::visitCastInst(I);
168
}
169

170
/// Try to simplify cmp instruction.
171
bool UnrolledInstAnalyzer::visitCmpInst(CmpInst &I) {
172
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
173

174
  // First try to handle simplified comparisons.
175
  if (!isa<Constant>(LHS))
176
    if (Value *SimpleLHS = SimplifiedValues.lookup(LHS))
177
      LHS = SimpleLHS;
178
  if (!isa<Constant>(RHS))
179
    if (Value *SimpleRHS = SimplifiedValues.lookup(RHS))
180
      RHS = SimpleRHS;
181

182
  if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
183
    auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
184
    if (SimplifiedLHS != SimplifiedAddresses.end()) {
185
      auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
186
      if (SimplifiedRHS != SimplifiedAddresses.end()) {
187
        SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
188
        SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
189
        if (LHSAddr.Base == RHSAddr.Base) {
190
          LHS = LHSAddr.Offset;
191
          RHS = RHSAddr.Offset;
192
        }
193
      }
194
    }
195
  }
196

197
  const DataLayout &DL = I.getDataLayout();
198
  if (Value *V = simplifyCmpInst(I.getPredicate(), LHS, RHS, DL)) {
199
    SimplifiedValues[&I] = V;
200
    return true;
201
  }
202

203
  return Base::visitCmpInst(I);
204
}
205

206
bool UnrolledInstAnalyzer::visitPHINode(PHINode &PN) {
207
  // Run base visitor first. This way we can gather some useful for later
208
  // analysis information.
209
  if (Base::visitPHINode(PN))
210
    return true;
211

212
  // The loop induction PHI nodes are definitionally free.
213
  return PN.getParent() == L->getHeader();
214
}
215

216
bool UnrolledInstAnalyzer::visitInstruction(Instruction &I) {
217
  return simplifyInstWithSCEV(&I);
218
}
219