Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CodeMetrics.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CodeMetrics.cpp - Code cost measurements ---------------------------===//
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 code cost measurement utilities.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Analysis/CodeMetrics.h"
14
#include "llvm/Analysis/AssumptionCache.h"
15
#include "llvm/Analysis/LoopInfo.h"
16
#include "llvm/Analysis/TargetTransformInfo.h"
17
#include "llvm/Analysis/ValueTracking.h"
18
#include "llvm/IR/DataLayout.h"
19
#include "llvm/IR/Function.h"
20
#include "llvm/Support/Debug.h"
21
#include "llvm/Support/raw_ostream.h"
22
23
#define DEBUG_TYPE "code-metrics"
24
25
using namespace llvm;
26
27
static void
28
appendSpeculatableOperands(const Value *V,
29
                           SmallPtrSetImpl<const Value *> &Visited,
30
206
                           SmallVectorImpl<const Value *> &Worklist) {
31
206
  const User *U = dyn_cast<User>(V);
32
206
  if (!U)
33
0
    return;
34
206
35
206
  for (const Value *Operand : U->operands())
36
410
    if (Visited.insert(Operand).second)
37
331
      if (isSafeToSpeculativelyExecute(Operand))
38
167
        Worklist.push_back(Operand);
39
206
}
40
41
static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,
42
                                    SmallVectorImpl<const Value *> &Worklist,
43
2.11M
                                    SmallPtrSetImpl<const Value *> &EphValues) {
44
2.11M
  // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
45
2.11M
  // alive only by ephemeral values.
46
2.11M
47
2.11M
  // Walk the worklist using an index but without caching the size so we can
48
2.11M
  // append more entries as we process the worklist. This forms a queue without
49
2.11M
  // quadratic behavior by just leaving processed nodes at the head of the
50
2.11M
  // worklist forever.
51
2.11M
  for (int i = 0; i < (int)Worklist.size(); 
++i167
) {
52
167
    const Value *V = Worklist[i];
53
167
54
167
    assert(Visited.count(V) &&
55
167
           "Failed to add a worklist entry to our visited set!");
56
167
57
167
    // If all uses of this value are ephemeral, then so is this value.
58
177
    if (
!all_of(V->users(), [&](const User *U) 167
{ return EphValues.count(U); }))
59
10
      continue;
60
157
61
157
    EphValues.insert(V);
62
157
    LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
63
157
64
157
    // Append any more operands to consider.
65
157
    appendSpeculatableOperands(V, Visited, Worklist);
66
157
  }
67
2.11M
}
68
69
// Find all ephemeral values.
70
void CodeMetrics::collectEphemeralValues(
71
    const Loop *L, AssumptionCache *AC,
72
1.03M
    SmallPtrSetImpl<const Value *> &EphValues) {
73
1.03M
  SmallPtrSet<const Value *, 32> Visited;
74
1.03M
  SmallVector<const Value *, 16> Worklist;
75
1.03M
76
1.03M
  for (auto &AssumeVH : AC->assumptions()) {
77
56
    if (!AssumeVH)
78
5
      continue;
79
51
    Instruction *I = cast<Instruction>(AssumeVH);
80
51
81
51
    // Filter out call sites outside of the loop so we don't do a function's
82
51
    // worth of work for each of its loops (and, in the common case, ephemeral
83
51
    // values in the loop are likely due to @llvm.assume calls in the loop).
84
51
    if (!L->contains(I->getParent()))
85
29
      continue;
86
22
87
22
    if (EphValues.insert(I).second)
88
22
      appendSpeculatableOperands(I, Visited, Worklist);
89
22
  }
90
1.03M
91
1.03M
  completeEphemeralValues(Visited, Worklist, EphValues);
92
1.03M
}
93
94
void CodeMetrics::collectEphemeralValues(
95
    const Function *F, AssumptionCache *AC,
96
1.08M
    SmallPtrSetImpl<const Value *> &EphValues) {
97
1.08M
  SmallPtrSet<const Value *, 32> Visited;
98
1.08M
  SmallVector<const Value *, 16> Worklist;
99
1.08M
100
1.08M
  for (auto &AssumeVH : AC->assumptions()) {
101
28
    if (!AssumeVH)
102
1
      continue;
103
27
    Instruction *I = cast<Instruction>(AssumeVH);
104
27
    assert(I->getParent()->getParent() == F &&
105
27
           "Found assumption for the wrong function!");
106
27
107
27
    if (EphValues.insert(I).second)
108
27
      appendSpeculatableOperands(I, Visited, Worklist);
109
27
  }
110
1.08M
111
1.08M
  completeEphemeralValues(Visited, Worklist, EphValues);
112
1.08M
}
113
114
/// Fill in the current structure with information gleaned from the specified
115
/// block.
116
void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
117
                                    const TargetTransformInfo &TTI,
118
3.12M
                                    const SmallPtrSetImpl<const Value*> &EphValues) {
119
3.12M
  ++NumBlocks;
120
3.12M
  unsigned NumInstsBeforeThisBB = NumInsts;
121
20.9M
  for (const Instruction &I : *BB) {
122
20.9M
    // Skip ephemeral values.
123
20.9M
    if (EphValues.count(&I))
124
32
      continue;
125
20.9M
126
20.9M
    // Special handling for calls.
127
20.9M
    if (const auto *Call = dyn_cast<CallBase>(&I)) {
128
1.48M
      if (const Function *F = Call->getCalledFunction()) {
129
1.41M
        // If a function is both internal and has a single use, then it is
130
1.41M
        // extremely likely to get inlined in the future (it was probably
131
1.41M
        // exposed by an interleaved devirtualization pass).
132
1.41M
        if (!Call->isNoInline() && 
F->hasInternalLinkage()1.41M
&&
F->hasOneUse()17.2k
)
133
96
          ++NumInlineCandidates;
134
1.41M
135
1.41M
        // If this call is to function itself, then the function is recursive.
136
1.41M
        // Inlining it into other functions is a bad idea, because this is
137
1.41M
        // basically just a form of loop peeling, and our metrics aren't useful
138
1.41M
        // for that case.
139
1.41M
        if (F == BB->getParent())
140
2.55k
          isRecursive = true;
141
1.41M
142
1.41M
        if (TTI.isLoweredToCall(F))
143
1.18M
          ++NumCalls;
144
1.41M
      } else {
145
66.5k
        // We don't want inline asm to count as a call - that would prevent loop
146
66.5k
        // unrolling. The argument setup cost is still real, though.
147
66.5k
        if (!Call->isInlineAsm())
148
53.2k
          ++NumCalls;
149
66.5k
      }
150
1.48M
    }
151
20.9M
152
20.9M
    if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
153
76
      if (!AI->isStaticAlloca())
154
76
        this->usesDynamicAlloca = true;
155
76
    }
156
20.9M
157
20.9M
    if (isa<ExtractElementInst>(I) || 
I.getType()->isVectorTy()20.9M
)
158
451k
      ++NumVectorInsts;
159
20.9M
160
20.9M
    if (I.getType()->isTokenTy() && 
I.isUsedOutsideOfBlock(BB)0
)
161
0
      notDuplicatable = true;
162
20.9M
163
20.9M
    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
164
1.45M
      if (CI->cannotDuplicate())
165
16
        notDuplicatable = true;
166
1.45M
      if (CI->isConvergent())
167
19
        convergent = true;
168
1.45M
    }
169
20.9M
170
20.9M
    if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
171
33.7k
      if (InvI->cannotDuplicate())
172
0
        notDuplicatable = true;
173
20.9M
174
20.9M
    NumInsts += TTI.getUserCost(&I);
175
20.9M
  }
176
3.12M
177
3.12M
  if (isa<ReturnInst>(BB->getTerminator()))
178
0
    ++NumRets;
179
3.12M
180
3.12M
  // We never want to inline functions that contain an indirectbr.  This is
181
3.12M
  // incorrect because all the blockaddress's (in static global initializers
182
3.12M
  // for example) would be referring to the original function, and this indirect
183
3.12M
  // jump would jump from the inlined copy of the function into the original
184
3.12M
  // function which is extremely undefined behavior.
185
3.12M
  // FIXME: This logic isn't really right; we can safely inline functions
186
3.12M
  // with indirectbr's as long as no other function or global references the
187
3.12M
  // blockaddress of a block within the current function.  And as a QOI issue,
188
3.12M
  // if someone is using a blockaddress without an indirectbr, and that
189
3.12M
  // reference somehow ends up in another function or global, we probably
190
3.12M
  // don't want to inline this function.
191
3.12M
  notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
192
3.12M
193
3.12M
  // Remember NumInsts for this BB.
194
3.12M
  NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
195
3.12M
}