Coverage Report

Created: 2019-07-24 05:18

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