Coverage Report

Created: 2017-10-03 07:32

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